Michel Dyakonov’s View on QC My view (based on Michel’s drawing*)
Alexander Vlasov’s view (based on Michel and Mikhail’s drawing)
It has been a while since I devoted a post to quantum computation. Meanwhile, we had a cozy, almost private, easy-going, and very interesting discussion thread on my previous, March 2014 post (that featured my Simons Institute videotaped lectures (I,II).)
What can we learn from a failure of quantum computers?
Last week we had a workshop on “Quantum computing: achievable reality or unrealistic dream.” This was a joint venture of the American Physics Society and the Racah Institute of Physics here at HUJI, organized by Professor Miron Ya. Amusia, and it featured me and Nadav Katz as the main speakers. Here are the slides of my lecture: What can we learn from a failure of quantum computers.
Noise Sensitivity and BosonSampling
Earlier, I gave a lecture in our CS colloquium about a recent work with Guy Kindler on noise sensitivity of BosonSampling. We show that for a constant level of noise, noisy BosonSampling can be approximated by bounded-depth computation, and that the correlation between the noisy outcome and the noiseless outcome tends to zero if the noise level is ω(1/n) where n is the number of bosons. Here is the paper Gaussian noise sensitivity and BosonSampling, the videotaped lecture Complexity and sensitivity of noisy BosonSampling, and the slides of the lecture.
Contagious error sources would need time travel to prevent quantum computation
On the positive side, Greg Kuperberg and I wrote a paper Contagious error sources would need time travel to prevent quantum computation showing that for a large class of correlated noise, (teleportation-based) quantum fault-tolerance works! Greg and I have had a decade-long email discussion (over 2000 emails) regarding quantum computers, and this work grew from our 2009 discussion (about my “smoothed Lindblad evolution” model), and heavily relies on ideas of Manny Knill.
Nadav Katz: Quantum information science – the state of the art
Some years ago, two brilliant experimentalists, Hagai Eisenberg and Nadav Katz, joined the already strong, mainly theoretical, quantum information group here at HUJI. Nadav Katz gave the second lecture in the workshop, and here are the slides of Nadav’s lecture: Quantum information science – the state of the art.
Experimental progress toward stable encoded qubits
Also very much on the positive side, Nadav mentioned a remarkable recent progress by the Martini’s group showing certain encoded states based on 9 physical qubits which are order-of-magnitude (factor 8.4, to be precise,) more stable than the “raw” qubits used for creating them !!
Here is a link to the paper: State preservation by repetitive error detection in a superconducting quantum circuit, by J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Yu Chen, Z. Chen, B. Chiaro, A. Dunsworth, I.-C. Hoi, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, A. N. Cleland, and John M. Martinis.
Update: Further comments on a Shtetl-optimized post (especially a comment by Graeme Smith,) help to place the new achievement of the Martinis group within the seven smilestones toward quantum computers from a 2012 Science paper by Schoelkopf and Devoret, originated by David DiVincenzo’s 2000 paper “The physical implementation of quantum computation“. (You can watch these milestone here also .)
The new achievement of having a very robust realization of certain encoded states can be seen as achieving the 3.5 milestone. The difference between the 3.5th milestone and the 4th milestone plays a central role in the seventh post of my 2012-debate with Aram Harrow in connection with a conjecture I made in the first post (“Conjecture 1″). Aram made the point that classical error-correction can lead to very stable encoded qubits in certain states (which is essentially the 3.5 milestone). I gave a formal description of the conjecture, which essentially asserts that the 4th milestone, namely insisting that encoded qubits allows arbitrary superpositions, cannot be reached. As I said many times (see, for example, the discussion in my 2012 Simons Institute videotaped lecture 2), a convincing demonstration of the 4th milestone, namely implementation of quantum error-correction with encoded qubits which are substantially more stable than the raw qubits (and allow arbitrary superposition for the encoded qubit) will disprove my conjectures. Such stable encoded qubits are expected from implementations of distance-5 surface code. So we are 0.5 milestones away 🙂
I will be impressed to see even a realization of distance-3 (or distance-5) surface code that will give good quality encoded qubits, even if the encoded qubits will have a quality which is somewhat worse than that of the raw qubits used for the encoding. These experiments, including those that were already carried out, also give various other opportunities to test my conjectures.
Peter Shor’s challenge #1 and my predictions from the failure of quantum computation
My lecture on predictions from the failure of QC is based on two lengthy recent comments (first, second) regarding predictions from the failure of quantum computers. On April 2014, Peter Shor challenged me with the following:
So if “quantum computers cannot work” is the premise of your theory, does your theory lead to any concrete predictions besides “quantum computers cannot work”? If it doesn’t, then I can’t help thinking that there really isn’t much substance to it.
While the discussion continued, it was not until November that I gave a detailed reply – a list of around 18 concrete predictions, along with other connections, possible applications, further vaguer predictions and speculations. (The comments have a much wider scope than the lecture.)
Peter Shor’s challenge #2: Is particle physics immune to my hypothesis?
Following my longish prediction comments, Peter challenged me with yet another great question.
We already know that the standard formulation of quantum physics appears to be computationally difficult (I am talking about the formulation without smoothed Lindblad evolution).
What you are saying is that introduced noise will make the system behave differently from its current predictions and make it easier to simulate.
Right now, particle physics experiments are simulated using lattice QFT, this simulation is computationally very intensive, and simulating particle physics is believed to high computational complexity. If we extrapolate your prediction, you predict that particle physics experiments will actually behave differently from the standard predictions, and in a way that is easier to simulate.
Is this correct, or is particle physics for some reason immune to your hypothesis?
The very short answer is that particle physics is not immune to my hypothesis!
This is an extremely interesting topic that a few of us here at HUJI have been thinking about together in the last year or so. What are the best examples for “quantum supremacy” in the context of many-body quantum systems (be it from condensed matter physics, chemistry, nuclear or atomic physics, or high energy physics), and how can we test and challenge (even on a heuristic level) the quantum-supremacy claim. (This is a difficult conceptual issue and we also looked briefly on connections with chaotic behavior in classical systems.) We discussed quite a few potential candidates like energy levels and other features of heavy atoms, highly accurate atomic clocks, and more, and right now, the best candidate we have is QED computations for energy levels of the Hydrogen atom.
My renewed conversation with Peter (and also with Aram, Alexander Vlasov, and Klas) has led also to this TCS stackexchange question: Quantum algorithms for QED computations related to the fine structure constants, and to two questions: QCD and QED with unlimited computational power – how precise are they going to be? and The fine structure constant – can it genuinely be a random variable? ,on the sister physics site.
I am not sure what is stronger: the fact that, in quantum physics, computations are lagging behind experiments, sometimes by several order of magnitudes — as an argument in favour of QC as a realistic possibility, or the (likely) fact that QC will enable to perform quantum physics computations, hundreds of orders of magnitude more accurately than experiments –as an argument against QC as a realistic possibility.
Michel and I, and Scott
Miron’s initial plan was to invite Michel Dyakonov, a prominent theoretical physicist with strong skeptical views regarding QC. While we are both skeptics regarding QC, Michel’s views are different from mine, see the pictures at the top. (Here is a link to a presentation of Michel from 2009 explaining his thoughts on the matter.) Michel who visited HUJI last winter does not expect failure of QC to lead to important physics predictions, but he prefers to draw some strong sociological insights. This winter, Scott Aaronson, who also has strong views on the matter of QC, was in town and it was fun to spend some time with him and chat face-to-face.
I remember a lengthy discussion on “polymath4” with many contributions from both Noam Nisan and me, and then how much better it was to actually meet Noam, in person, in the cafeteria one day. (This gap is even larger when it comes to debates and disagreements.) When I mentioned this to Terry Tao he told me that in Internet discussions he can actually “visualize” the other participants so it is almost like talking with them in person.
Updates: 1) a related Shtetl-optimized post describes the Martini’s group experimental breakthrough as well as a theoretical one by Ed Farhi, Jeffrey Goldstone, and Sam Gutmann about a quantum algorithm for approximation of an NP-hard optimization problem.
2) Michel’s picture at the top of this post was designed as an illustration to Michel’s 2001 presentation “Quantum computing: a view from the enemy camp” . The “enemy camp” is presented on the right side of the picture. The actual drawing was done by Michel’s son, 16 years old at that time. ( I remember that I when I read the paper I felt, or imagined, some “anti-mathematics” sentiment. When I asked Michel about it last year, he told me that his son is actually a mathematician! )
In the pictures you can see also Miron, Nadav, Guy and Scott, and the stormy sea at the Tel-Aviv old harbor as taken by Guy.
A videotaped lecture on BosonSampling
Update: A video of the debate