In May 1994, Artur Ekert visited Caltech to give a seminar about quantum cryptography. Near the end of the talk, Ekert revealed an exciting new development — just weeks earlier, Peter Shor had announced the discovery of an efficient quantum algorithm for finding the prime factors of large composite integers, a problem for which no efficient classical algorithm is known.

Perhaps I’ve embellished the memory over time, but I recall being awestruck by this news. I spent the next month at the Isaac Newton Institute attending a workshop about quantum black holes, and though it was a very good workshop and I had some great discussions, I spent most of my time there secretly trying to understand Shor’s paper, which Ekert had emailed to me. This took some effort, because I knew little about algorithms or computational complexity at that time (even less than I know now), but by the end of the workshop I felt I understood the ideas behind Shor’s algorithm pretty well. I did not yet realize that I was in the midst of a career transition from particle physics to quantum information science.

I had heard before about the idea of quantum computation, but had not been very interested. After Ekert’s disclosure I grasped why the subject is really exciting — with highly controllable quantum systems we should be able to perform surprising and useful tasks that would be impossible in a world governed by classical rather than quantum physics.

Quantum technology has advanced steadily in the 18 years since I heard Ekert’s seminar, but quantum computers that can factor large numbers by running Shor’s algorithm still seem far off. I think we’ll get there eventually, but perhaps it will take a few more decades. In a future post I may say more about why it’s taking so long. Today I would rather emphasize another way to exploit controllable quantum systems.

In parallel with the progress in building hardware for quantum computing, there have been marvelous achievements in controlling systems of ultracold atoms to explore collective phenomena in quantum many-body systems. Eventually, we should be able to use these tools to simulate quantum systems that are too hard to simulate classically, and so gain valuable insights into the behavior of highly correlated quantum matter. But when?

A recent paper by Martin Zwierlein’s group at MIT (arXiv version here) suggests that this may have already happened. They measure, as a function of temperature and chemical potential, the density of a gas of spin-1/2 fermionic Lithium 6 atoms with strong short-range interactions. They compare the measured equation of state to a calculation done using a method for summing perturbation theory (which I had not heard of before) called Bold Diagrammatic Monte Carlo (BDMC), finding excellent agreement. It’s not clear how to do so accurate a calculation using any other currently known technique.

The foundations of BDMC have not been firmly established, in particular because the method rests on unproven assumptions about the convergence of perturbation theory. By validating the method in their experiment, the authors seem to have extracted some nontrivial information about a strongly-coupled quantum many-body system which goes beyond what we know from existing analytic and computational methods. As they put it: “This presents the first — although long anticipated — compelling example of how ultracold atoms can guide new microscopic theories for strongly interacting quantum matter.”

In a recent talk, I proposed using the term “quantum supremacy” to describe super-classical tasks performed using controllable quantum systems. I’m not completely happy with this term, and would be glad if readers could suggest something better.

But more importantly: Is it reasonable to say that the Zwierlein group has achieved quantum supremacy?

Steve FlammiaJuly 22, 2012 at 11:39 pmWell, I don’t think it is

unreasonable to say they have achieved “quantum supremacy” (for lack of a better term, indeed), but perhaps it is premature. Of course, I have not had a chance to carefully read the Zwierlein paper. How do these results stack up to the Penning trap results I discussed on the Pontiff? It sounds like the Zwierlein results make more of a systematic effort at classical simulation, so perhaps their claim is stronger?I guess I’m a little skeptical of making claims about quantum vs. classical until they are supported by

reallyoverwhelming evidence. Do you remember the claims by D-Wave/Google about how the D-Wave chip was outperforming Tabu search? It was all too easy to misinterpret those results, I think. And a sexy headline about quantum beating classical will travel the earth ten times before we can debunk it. It’s better to resist the temptation to claim “quantum supremacy” until the weight of the evidence is really too much to bear.rrtucciJuly 23, 2012 at 11:48 am“Is it reasonable to say that the Zwierlein group has achieved quantum supremacy?”

Quantum Supremacy (over String Theorists)

I like it!

Surjeet RajendranJuly 26, 2012 at 11:16 pmThis is perhaps a bit off topic – what do you make of the recent Almheiri, Marolf, Polchinski and Sully (arxiv:1207.3123) argument about black hole firewalls?

preskillJuly 27, 2012 at 5:22 pmYes, pretty far off topic …

The paper by Almeiri et al. notes something puzzling about black hole evaporation. The standard view of quantum black holes is that the radiation emitted by an old black hole is nearly maximally entangled with the radiation emitted earlier. On the other hand, according to semiclassical theory, even for an old black hole the radiation emitted is nearly maximally entanged with field modes behind the horizon. If A, B, C are three quantum systems, it is not possible for B to be maximally entangled with both A and C. So something seems to be wrong.

This is a useful point, because it sharpens our understanding of what kinds of violations of semiclassical physics should be expected in black hole evaporation. By feeling is that when thinking about such situations we should be careful to speak about entanglement in operational terms. The puzzle becomes less troubling if we have no way to verify both the AB entanglement and the BC entanglement. I haven’t thought it through in detail, but my guess is that is the right way to resolve the puzzle. There is a recent paper by Harlow which seems to have a similar viewpoint (arXiv:1207.6243).

ThomasJuly 27, 2012 at 3:32 pmI think they have achieved “supremacy” in the sense that for a designer Hamiltonian they have determined physical quantities (the ground state energy and the equation of state) with an accuracy that is superior to existing numerical calculations. I would note that both experiment and computational methods have improved rapidly in recent years (that means experimental results from few years ago, obtained by groups at Duke, ENS, .. were also superior to numerical results obtained at the time). What is really new is that the MIT group has quantified remaining uncertainties much more fully than before.

I would also like to note that this particular problem is numerically hard, but not numerically intractable. This problem can be viewed as an attractive Hubbard model in the limit of zero filling. There is no sign problem, and the computational effort presumably scales as N (the number of particles) to a fixed power. (The UMass group uses a method that actually has a sign problem, but this simply means that for a finite system it may be more efficient to use an algorithm that has a mild sign problem).

Finally I would like to mention that computing real time properties (for example transport coefficients, like the shear viscosity or the spin diffusion constant) is (presumably) intractable using known algorithms (the real time path integral clearly has a severe sign problem). These quantities have been measured by the Duke/NC State group and by Martin’s group at MIT. While the results are not as accurate as the equation of state, they are clearly superior to existing numerical results (which are almost completely non-existent).

preskillJuly 27, 2012 at 3:49 pmThanks, Thomas! It would be great if you could provide references on the transport measurements.

ThomasJuly 29, 2012 at 7:36 pmUniversal Spin Transport in a Strongly Interacting Fermi Gas

Ariel Sommer, Mark Ku, Giacomo Roati, Martin W. Zwierlein

Nature 472, 201-204 (2011)

http://arxiv.org/abs/1103.2337

Universal Quantum Viscosity in a Unitary Fermi Gas

C. Cao, E. Elliott, J. Joseph, H. Wu, J. Petricka, T. Schaefer, J. E.Thomas

Science 331:58,2011

http://arxiv.org/abs/1007.2625

Charlie TAugust 21, 2012 at 9:38 amJohn, _obviously_, “spookytechnology” is the appropriate term (http://arxiv.org/abs/0710.2537). Since its introduction this term has taken the world by storm .

Charlie TAugust 21, 2012 at 9:39 amdoh – was supposed to end with: (sounds of crickets chirping).

Quantum Supremacy or Classical Control? « Gödel’s Lost Letter and P=NPOctober 3, 2012 at 9:14 pm[…] quantum computers. What is our computational world—our mundus computationalis?—one with quantum supremacy or classical […]

Is Alice burning? The black hole firewall controversy | Quantum FrontiersDecember 3, 2012 at 4:00 pm[…] — the discovery of a quantum algorithm for factoring intergers efficiently. I told the story here of how I secretly struggled to understand Shor’s algorithm while attending a workshop on black […]

My 10 biggest thrills | Quantum FrontiersMarch 21, 2014 at 11:40 am[…] written before about how Peter Shor’s discovery of an efficient quantum algorithm for factoring numbers […]