Towards quantum supremacy

 Quantum phenomena do not occur in a Hilbert space. They occur in a laboratory.

Asher Peres

Being a theorist, it is easy to forget that physics is an empirical science.  This is especially true for those of us working on quantum information. Quantum theory has been so thoroughly tested, that we have gotten into the habit of assuming our theoretical predictions must correspond to physical reality. If an experiment deviates from the theory, we look for technical flaws (and usually find them) before seeking an explanation outside the standard theory. Luckily, we have experimentalists who insist on testing our prediction.

Quantum computers are an extreme prediction of quantum theory. Those of us who expect to see working quantum computers at some point in the future, expect the theory to hold for fairly large systems undergoing complex dynamics.  This is a reasonable expectation but it is not trivial.  Our only way to convince ourselves that quantum theory holds at fairly large scales, is through experiment. Conversely, the most reasonable way to convince ourselves that the theory breaks down at some scale, is through experiment. Either way, the consequences are immense,  either we build quantum computers or we make the most significant scientific discovery in decades.

Unfortunately, building quantum computers is very difficult.

There are many different routes towards  quantum computers.  The long and difficult roads, are those gearing towards universal quantum computers, i.e those that are at least as powerful as any other quantum  computer. The (hopefully) shorter and less difficult roads are those aimed at specialized (or semi or sub-universal) quantum computers. These should outperform classical computers for some specialized tasks and allow a demonstration of quantum supremacy; empirical evidence that quantum mechanics does not break down at a fairly high level of complexity.

One of the difficulties in building quantum computers is optimizing the control sequences. In many cases we end up dealing with catch-22. In order to optimize the sequence we need to simulate the system; in order to simulate the system we need a quantum computer; in order to build a quantum computer we need to optimize the control sequence…..

Recently Jun Li and collaborators found a loophole. The optimization algorithm requires a simulation of the quantum system under the imperfect pulses. This type of simulation can be done efficiently on the same quantum processor. We can generate the imperfect pulse `perfectly’, on our processor and it can obviously simulate itself.   In-fact, the task of optimizing pulses seems like a perfect candidate for demonstrating quantum supremacy.

I was lucky to be in the right place at the right time and be part of the group that implemented this idea on a 12-qubit processor. We showed that at the 12-qubit level, this method can outperform a fairly standard computer. It is not a demonstration of quantum supremacy yet, but it seems like a promising road towards this task. It is also a promising way to optimize control pulses.

As a theorist, I cannot see a good reason why quantum computers will not be a reality, but it is always nice to know that physical reality matches my expectations at least at the 12-qubit level.

P.S – A similar paper appeared on arXiv a few days after ours.

  1. Towards quantum supremacy: enhancing quantum control by bootstrapping a quantum processor – arXiv:1701.01198
  2. In situ upgrade of quantum simulators to universal computers – arXiv:1701.01723
  3. Realization of a Quantum Simulator Based Oracle Machine for Solving Quantum Optimal Control Problem – arXiv:1608.00677

Some updates

These last four and a half months have been exciting in may ways. Three papers submitted to arXiv: The first on Entanglement in DQC1, the second, a Leggett Garg experiment in liquid state NMR; and the third, a book chapter titled Why should we care about quantum discord? I also had two papers published one on quantum money and the second on  sequential measurements.

In August I organized a workshop on Semi-quantum computing and recently wrote about it on the IQC blog.  I also attended a workshop on Entanglement and quantumnes  in Montréal.

Earlier this month I got sucked into a discussion about publishing.


Nonlocal Measurements

My paper Nonlocal Measurements Via Quantum Erasure has  finally been published in PRL.  There is a short news story on the work on the IQC website. I also recently wrote a related blog post on nonlocal measurements for the IQC blog.

IQC blog post: Tomaytos, Tomahtos and Non-local Measurements



Nonlocal measurements via quantum erasure, A. Brodutch and E. Cohen  Phys. Rev. Lett 116 (2016)



Misconceptions about weak measurements: 2. Weak, not noisy

It’s about time that I continue writing about misunderstandings surrounding weak measurements and weak values. This time I will try to explain the difference between weak measurements and noisy measurements.

Why weak? 

One of the first things we learn about quantum mechanics is that  the measurement process causes an unavoidable back-action on the measured system. As a consequence, some measurements are incompatible, i.e. the result of a measurement on observable  A  can change significantly if a different observable,  B, is measured before A.  A well known example is the measurements of position and momentum where the back-action leads to the Heisenberg uncertainty relation.

The measurement back-action can create  some seemingly paradoxical situations when we make counterfactual arguments such as

We measured A and got the result a, but had we measured B we would have go the result b which is incompatible with a.

These situations appear very often  when we consider  systems both past and future boundary conditions. In these cases they are known as pre and post selection (PPS) paradoxes. In PPS paradoxex the measurement back-action is important even when A and B commute.  An example is the three box paradox that I explain without mathematical detail:

A single particle is placed in one of three boxes A,B,C (actually in a superposition) at time t0 and is later found to be in some other superposition state at t1.  At time t0< t m < t1 one box is opened. The initial t0 and final t1 states of the particle are chosen in such a way that the following happens:

If box A is opened, the particle will be discovered with certainty. If box B is opened, the particle will also be found with certainty. If box C is opened the particle will be found with some probability. The situation seems paradoxical:

If the ball is found with certainty in box A, then it must have been in box A to begin with. But if it is also found with certainty in box B, so it must have been there …

One way to solve this apparent paradox is to note that the measurements are incompatible. i.e opening box A and not B,C is incompatible with opening box B and not A,C etc.

These are the types of questions that Aharonov Albert and Vaidman were investigating  1980s1 . Weak measurements were studied as a way to minimize the measurement back-action. These measurements then  provided a picture that arguably gives a solid (if somewhat strange) foundation to statements like the one above.

The motivation of weak measurements is therefore an attempt to derive a consistent picture where all observables are mutually compatible in a way which is similar to classical physics. In quantum mechanics this comes at a cost. The classical information gained by reading out the result of a single weak measurement is usually indistinguishable from noise. In other words  weak measurements are noisy measurements.


Weak, not noisy

Part of the confusion around weak measurements lies in the fact that the statement above is not a sufficient condition for a weak measurement. One may argue noise is not even a necessary requirement, it is rather, a consequence of quantum mechanics. Weak measurements may be noisy, but noisy measurements are, in most cases, not weak. To understand this fact it is good to examine  both a classical and quantum scenario.

The classical scenario

Walking on the beach you see a person drowning. Being  a good swimmer you go in and try to save this person. As you get back to the beach you see that he is not responsive and decide to to find if he is alive. You are now faced with the choice of how to perform the measurement.

A weak measurement – You try to get a pulse – The measurement is somewhat noisy since the pulse may be too weak to notice. It is also a weak measurement since it is unlikely to change this person’s state.

A noisy measurement – You start screaming for help. There is some small chance that the guy will wake up and tell you to shut up.

A noisy, strong measurement – You start kicking the guy in the head, hoping that he regains conciseness. This is a strong measurement, but it is also noisy. The person might be alive and you still won’t notice after kicking his head, moreover the kick in the head might kill him.

The quantum scenario

You want to find the \sigma_z component of a spin 1/2 particle.

A weak measurement – Perform the usual von Neumann measurement with weak coupling. There is still some back-action but if the coupling is sufficiently weak you can ignore it. The down side is that you will get very little information.

A noisy measurement – Perform the weak measurement as above, but follow it with a unitary rotation and some dephasing.

A noisy, strong measurement – Perform a standard projective measurement, but then add extra noise at the readout stage. This could, for example,  be the result of a defective amplifier.

While all of the measurements above are noisy, only the weak measurements follow the original motivation of making a measurement with a weak back-action.

An extreme example

One neat example of a measurement which is noisy but not weak involves a wave function with a probability distribution that has no tails.

Take the measurement of a Pauli observable that has results \pm1 and imagine that after the readout we get the following probability distributions: If the system was initially in the state corresponding to +1 we get a flat distribution between -9 and 11, if the result is -1 we get a flat distribution between -11 and 9. The measurement is noisy, in fact any result between -9 and +9 will give us no information about the system. However it is not weak since any result outside this range will cause the state of the system to collapse into an eigenstate.

A pointer with no tails: The probability density function for the result of a  dichotomic measurement. A +1 state will produce the blue distribution while a   -1 state will produce the orange one. Although a result between -9 and +9 will provide no information, the measurement is still not weak.

It is not surprising that this type of measurement will not produce a weak value as the expectation value of a given set of measurements on a pre and post selected system.  While this is is obviously an extreme case,  any situation where the probability density function for the readout probabilities has no tails will not be weak for the same reason. The same is usually true in cases where the derivatives of the probability density function are very large. In less technical terms – noise is not a sufficient condition for a weak measurement.

1. To get a partial historic account of what AAV were thinking see David Albert’s remarks in Howard Wiseman’s QTWOIII talk on weak measurements (around minute 25-29) 



Misconceptions about weak measurements: 1. Weak ‘measurements’.

It seems that I am somehow drawn to controversial subjects. Maybe it’s my nature as an Israeli. Much of my Phd research has been around the controversial topic of ‘quantum discord‘.  Now I find myself working hard on the subject of my Master’s thesis, ‘weak measurements’, yet another topic which is both controversial and misunderstood.  Unlike quantum discord which became controversial mainly due to it’s popularity (aka the discord bubble),  weak measurements were controversial from day one.   This controversy  is, at leas in part, due to both misunderstandings, different interpretations, and choice of words; in particular the word `measurement’.

I first realized that the use of the word measurement may  cause of confusion after watching a recorded lecture by Anthony Leggett.  But the problem really sank in after many discussion with Marco Piani who helped me clarify my thoughts about the subject.  At one point Marco’s reaction reminded me of the phrase “You keep using that word. I do not think it means what you think it means.“.

Let me explain.

In a discussion of measurements, Asher Peres, one of the main critics of weak measurements (and my academic `grandfather’) wrote `The “detector clicks” are the only real thing we have to consider. Their observed relative frequencies are objective data.’ This is the usual sense we think of measurements in quantum information, a measurement  is a channel that takes a quantum state as input and gives probabilities (the relative frequencies) as an output.  Let us call this the quantum information approach. In more technical language a measurement is completely specified by the POVM elements. Roughly speaking any set of POVM elements that sum up to the identity can describe a measurement i.e probabilities for the various detectors clicking. However, a weak measurement cannot be described in this way, the POVM elements are at best, only part of the picture.



The quantum information approach. Quantum in – classical out


The first time I encountered the term POVM was during the time between my B.Sc and M.Sc when I started learning the basics of quantum information. As  an undergad, I was taught about a different type of quantum measurement. The quantum world, I was told, is made up of quantities that are observable; these correspond to Hermitian operators. The results of the measurements are eigenvalues and after the measurement the measured system will change its state to the relevant eigenvector, the so-called collapse of the wave function. I will call this the textbook approach. The big difference between this and the `quantum information approach’ (above) is that the channel has a classical input and a classical (eigenvalue) and quantum (eigenvector) output. This is closer in spirit to the `measurement’ in a weak measurement. However this framework does not have any variable strength.


The textbook approach. Quantum in- classical [eigenvalue] and quantum [eigenvector] out.

The `textbook approach’ is unsatisfactory in two ways. First it allows a limited class of measurements that do not necessarily correspond to realistic situations. Second it does not include a dynamical picture: measurements simply happen. Although a full dynamical picture is still an (if not the) open problem, von Neumann gave the a reasonable dynamical picture for the measurement which is know as the von Neumann scheme. The measurement is described as a coherent interaction between the measured system and a (quantum) meter initially in a state |0>.  The interaction Hamiltonian is set up so that: if the system is in an eigenstate a of the desired observable, the meter will shift accordingly i.e it will end up in the state |a>.  Generally the system-meter state will be entangled after the measurement. With the right choice of interaction Hamiltonian the local picture will be  a mixed state that gives the right statistics for the textbook measurement. A slightly more elaborate picture can be used to describe more general measurements.


The von Neumann scheme. Quantum [product system-meter] in- quantum [entangled system-meter] out.

A weak measurement is a measurement in this sense, i.e it is a channel that has a system-meter (quantum) input and a system-meter (quantum) output. The measurement can be followed by a readout stage where a single detector `clicks’, but this part simply tells us something about the meter and only indirectly about the system whose state has changed.To complete the transition from the von Neumann scheme to a weak measurement we simply need to make the interaction Hamiltonian weak. It should be so weak that, after the measurement, the shifts corresponding to different eigenvalues will strongly overlap. The first  advantage of this  method is that the system state is virtually unchanged by the measurement process. Other, surprising  advantages follow, especially when one considers the fact that this measurement process is symmetric with respect to time.

I hope I convinced you that the term `measurement’ means different things to different people; While quantum information theorists say measurement and mean `a quantum to classical channel’ the weak measurement community think of a `quantum to quantum channel’. I believe this is major source of confusion that leads to controversy around weak measurements. My advice to people in the quantum information community is: either stop thinking about weak measurements as measurements, or read the literature and try to convince yourself that this channel represents the closest thing we have to a measurement in quantum theory.  Either way stop trying to understand weak measurements simply in terms of POVM elements.


In upcoming posts I will try to clarify some other misconceptions including the difference between `noisy measurements’ and `weak measurements’, and an explanation of what is anomalous about ‘anomalous weak values’.

Weak measurements and post selection in NMR.

Last summer  I started thinking about my master’s thesis on weak measurements. I’ve been keeping an eye out  for interesting weak measurement papers for a while and have had the opportunity to referee a few  papers on the subject that forced me to keep up to date.     I started playing around with some weak measurement ideas  when Raymond Laflamme (one of my current supervisors)  suggested I  give a short introduction at the next group meeting. The biggest question at the end of this short introduction was “can we do this in (liquid state)  NMR?”. My first response was an outright `NO’, because any interesting weak measurement experiment would require post-selection (see below), a very difficult task in an ensemble system like NMR.  After some serious thought I realized that the solution was actually very simple.  What I found amazing was that the experimentalists  were able to perform the experiment immediately, in-fact these guys can perform any small quantum circuit without too much trouble. The result was the first weak measurement experiment that did not involve any optics. The paper was published in NJP (open access) and a video-abstract is available on the NJP website and youtube.

This month I also taught a short four lecture module on weak measurements and the two state vector formalism as part of QIC 890. But I will keep the discussion of weak measurements to another post. For now I will explain the trick used in the NMR experiment. That will require me to first explain some issues regarding ensemble quantum computers.

 Ensemble quantum computing

Today we don’t know what a quantum computer will look like. We don’t know what it will be made of and we don’t know how it will work. While from a computer science perspective all architectures are the same, that is they can solve the same problems, from a practical perspective they are quite different.  Nevertheless in most cases we like to think of an abstract quantum processor in a similar way to a standard processor, in terms of circuits.

The circuit accepts a classical input, a series of zeros and ones, encoded in quantum bits. The circuit itself is a sequence of operations on those quantum bits. These operations are reversible (unitary) but otherwise they can be quite general. At the end, some of the quantum bits are measured in a specific way and a classical output (a series of zeros and ones) is produced. This output is usually not deterministic so the program can produce different outputs for the same input. Although this seems like a flaw it is not, as long as the probability for an unwanted result is low.

In liquid state NMR the quantum bits are the nuclear spin degree of freedom of single atoms on a molecule. The molecule is the processor and the natural electromagnetic interactions inside the molecules are supplemented with controlled external fields to produce the dynamics (i.e the gates).   Control in this system is very good but there are a number of downsides. The main downside is that the signal is very noisy. To overcome the issue of noise a large number of molecules are used. This means that a large number of identical processors are running in parallel.

One of the drawbacks of running the computation on an ensemble of identical processors is in the readout stage.  The final measurement is an ensemble measurement and the result is a statistical average.  Why is this bad? Let us say for example that we are running a classical computation on two bits with two possible results. Half the time the result is 0,0 and half the time it is 1,1. Now if we read the average on each bit we get that each bit is 1 half the time and 0 half the time so on average it is 1/2. But this average result 1/2,1/2 is also consistent with an output which is 0,1 half the time and 1,0 half the time.  So we can’t distinguish between these results.

Liquid state NMR is not the only system where this kind of ensemble paradigm applies and it is quite possible that ensemble quantum processors will be the way to go for quantum computing, at least in the short term. Liquid state NMR is also the current record system, with good control of 12 qubits.  It is therefore not a surprise that people have come up with methods for circumventing the shortcomings of ensemble readouts.  Going back to the example above it is possible to have a third bit register set to   1 if the first two are equal and 0 if they are not. This will distinguish between the first and second scenario above. In the first case we will have 0,0,1 half the time and 1,1,1 the other half while in the second case we will have 1,0,0 half the time and 0,1,0 the other half.

Post selection and weak measurements.

In the case of post selection we want to read the average result of the first (quantum) bit but only in the case where the second one is in a specific state (say 0).  So if we have 0,1 one third of the time 0,0 one third and 1,0 one third we should to read out 1/2, the average of the first bit only in the two cases where the second was 0.  A similar situation exists when we want to get an interesting result for a weak measurement. The reading on the measuring device  must be post-selected according to the  state of the measured system.

To perform the post-selection we used a (seemingly) non reversible operation. Sticking to the example of classical bits above our algorithm worked in the following way.  We want to post select on the cases where the second bit is 0. To achieve this we perform an operation that randomizes the first bit if the second bit is 1. When we get the averages at the end we know how many times we got a random result (by measuring the second bit) and how many times we got a `real` result.  Using this information we can get the statistical average of the post-selected states.

The quantum case is a little  more involved but the basic idea is the same.  This trick allowed us to perform the weak measurement experiment with post selection and get strange results such as complex values and values in outside the normal range. The method we used for post-selection goes beyond weak measurements. We are currently thinking about other weak measurement experiments as well as other experiments that involve post-selection. The advantage is that we can control bigger systems than anyone else (by we I mean the experimentalists, I can’t control anything).

This was also my first collaboration with experimentalists. I’m looking forward to more.

Experimental realization of post-selected weak measurements on an NMR quantum processor,

Dawei Lu, Aharon Brodutch, Jun Li, Hang Li, Raymond Laflamme,  NJP 2014.



Discord and completely positive maps

After over two years of work  we finally published our results showing that the connection between discord and complete positivity is quite weak, and probably has no operational significance. But let me start at the beginning:

In the beginning… and then there was a big discussion/argument about possible maps describing the evolution of a quantum system interacting with the environment. In the case where they are initially correlated this discussion is still not settled. In 2007 came a paper by Cesar Rodriguez-Rosario Kavan Modi, Aik-meng Kuah, Anil Shaji and ECG Sudarshan titled “Completely positive maps and classical correlations“, I call it Cesar and Kavan’s paper. They examined a situation where some initial family of system-environement, $$mathcal{SE}$$ states is classically correlated (has zero discord). It turns out that such a family of states is in the consistency domain of  a completely positive assignment map. In slightly less technical language: given a family of classically correlated $$mathcal{SE}$$ states it is possible to describe the evolution of the system using a completely positive map. Without going into details this comes with some caveats. Cesar, Kavan and Alán Aspuru-Guzik explained these caveats in another paper.

About a year after Cesar and Kavan’s paper Alireza Shabani and Daniel Lidar published a paper titled “Vanishing Quantum Discord is Necessary and Sufficient for Completely Positive Maps” This result was published in PRL, I will call it the SL paper. It made a lot of waves and has since been cited around 150 times. Unfortunately no one really understands it. I don’t know who should be blamed here, the authors for writing an unreadable paper (I assume they can read it), the editor for accepting an unreadable paper, or the referees who thought the paper was readable. But as it stands this paper was accepted, and since it was published in a prestigious journal and has such a bombastic title, people love to cite it. Especially to justify their research on discord. I guess I could start a rant but it’s nothing new so let us return to the story.

In September 2010 I had the extreme pleasure of attending the “Quantum Coherenece and Decoherence” workshop in Benasque where I met Cesar and Animesh Datta. After a short conversation about discord and interesting results in the field we discovered that although we have all cited SL we don’t know what they actually claim. We all assumed it was the “necessary” part of Cesar and Kavan’s “sufficient” result for completely positive maps but none of us could really explain the bottom line. After spending a few days in trying to understand the paper together we finally gave up, and instead came up with a counterexample. That is, we found a family of discordant states which is consistent with a completely positive assignment map.

A few weeks later I met Kavan in Singapore and we discussed this result further…

[missing reel]

.. and finally  Ángel Rivas joined our jolly group. The work was very slow, mostly due to us being on 4 different continents. By the time time I was at IQC we had a draft. When Kavan came to visit we finalized the paper.

The final version is much more then a comment on SL’s result. We showed that the problem of finding the map that correctly describes the evolution is a matter of how the problem is stated. More to the point, we showed that in at least thee sensible frameworks for approaching this problem there is at best a one way connection between positivity of the map and discord. Presumably there might be a framework where zero discord is both necressary and sufficient for completely positive maps. Unfortunately we were unable to identify this framework.


Vanishing quantum discord is not necessary for completely-positive maps
Aharon Brodutch, Animesh Datta, Kavan Modi, Ángel Rivas, César A. Rodríguez-Rosario arXiv:1212.4387Phys. Rev. A 87, 042301