Quantum computing: achievable reality or unrealistic dream

QC-michel-view QC-gilview

Michel Dyakonov’s View on QC                                     My view (based on Michel’s drawing*)



Alexander Vlasov’s view (based on Michel and Konstantin’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: Continue reading

Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes

Special Quantum PCP and/or Quantum Codes: Simplicial Complexes and Locally Testable CodesDay

24 Jul 2014 – 09:30 to 17:00

room B-220, 2nd floor, Rothberg B Building

On Thursday, the 24th of July we will host a SC-LTC (simplicial complexes and classical and quantum locally testable codes) at the Hebrew university, Rothberg building B room 202 (second floor) in the Givat Ram campus. Please join us, we are hoping for a fruitful and enjoyable day, with lots of interactions. Coffee and refreshments will be provided throughout the day, as well as free “tickets” for lunch on campus
There is no registration fee, but please email dorit.aharonov@gmail.com preferably by next Tuesday if there is a reasonable probability that you attend –  so that we have some estimation regarding the number of people, for food planning

Program:SC-LTC day – simplicial complexes and locally testable classical and quantum codes -Rothberg building B202
9:00 gathering: coffee and refreshments

9:30 Irit Dinur: Locally testable codes, a bird’s eye view

10:15: coffee break

10:45 Tali Kaufman, High dimensional expanders and property testing

11:30 15 minutes break

11:45 Dorit Aharonov, quantum codes and local testability

12:30 lunch break

2:00 Alex Lubotzky: Ramanujan complexes

2:50 coffee break

3:15 Lior Eldar: Open questions about quantum locally testable codes and quantum entanglement

3:45 Guy Kindler: direct sum testing and relations to simplicial complexes ( Based on David, Dinur, Goldenberg, Kindler, and Shinkar, 2014)

4:15-5 free discussion, fruit and coffee


Influence, Threshold, and Noise



My dear friend Itai Benjamini told me that he won’t be able to make it to my Tuesday talk on influence, threshold, and noise, and asked if I already have  the slides. So it occurred to me that perhaps I can practice the lecture on you, my readers, not just with the slides (here they are) but also roughly what I plan to say, some additional info, and some pedagogical hesitations. Of course, remarks can be very helpful.

I can also briefly report that there are plenty of exciting things happening around that I would love to report about – hopefully later in my travel-free summer. One more thing: while chatting with Yuval Rabani and Daniel Spielman I realized that there are various exciting things happening in algorithms (and not reported so much in blogs). Much progress has been made on basic questions: TSP, Bin Packing, flows & bipartite matching, market equilibria, and k-servers, to mention a few, and also new directions and methods. I am happy to announce that Yuval kindly agreed to write here an algorithmic column from time to time, and Daniel is considering contributing a guest post as well.

The second AMS-IMU meeting

Since the early 70s, I have been a devoted participants in our annual meetings of the Israeli Mathematical Union (IMU), and this year we will have the second joint meeting with the American Mathematical Society (AMS). Here is the program. There are many exciting lectures. Let me mention that Eran Nevo, this year Erdős’ prize winner, will give a lecture about the g-conjecture. Congratulations, Eran! Among the 22 exciting special sessions there are a few related to combinatorics, and even one organized by me on Wednsday and Thursday.

Contact person: Gil Kalai, gil.kalai@gmail.com
TAU, Dan David building, Room 103
 Wed, 10:50-11:30 Van H. Vu (Yale University) Real roots of random polynomials (abstract)
Wed, 11:40-12:20 Oriol Serra (Universitat Politecnica de Catalunya, Barcelona)  Arithmetic Removal Lemmas (abstract)
 Wed, 12:30-13:10 Tali Kaufman (Bar-Ilan University)  Bounded degree high dimensional expanders (abstract)
 Wed, 16:00-16:40 Rom Pinchasi (Technion)  On the union of arithmetic progressions (abstract)
Wed, 16:50-17:30  Isabella Novik (University of Washington, Seattle) Face numbers of balanced spheres, manifolds, and pseudomanifolds (abstract)
 Wed, 17:40-18:20 Edward Scheinerman (Johns Hopkins University, Baltimore) On Vertex, Edge, and Vertex-Edge Random Graphs (abstract)
 Thu, 9:20-10:00 Yael Tauman Kalai (MSR, New England) The Evolution of Proofs in Computer Science (abstract)
 Thu, 10:10-10:50  Irit Dinur (Weitzman Institute)  Lifting locally consistent solutions to global solutions (abstract)
 Thu, 11:00-11:40 Benny Sudakov (ETH, Zurich) The minimum number of nonnegative edges in hypergraphs (abstract)


And now for my own lecture.

Influence, Threshold, and Noise:

Continue reading

Why Quantum Computers Cannot Work: The Movie!

Here are links to a videotaped lecture in two parts entitled “why quantum computers cannot work” recorded at the Simons Institute for the Theory of Computing on December 2013 and two additional videos: a short talk on topological quantum computers and a twelve minute overview.  Here are the links: OverviewPart IPart IITopological QC.  (Update, Nov 14: BosonSampling.)

Why Quantum Computers Cannot Work:

Overview and Vision.

Why Quantum Computers Cannot Work I:

From the “Trivial Flow” to Smoothed Lindblad Evolutions

Why Quantum Computers Cannot Work II:

Debate, Reasons to Disbelieve, and Experimentation

Why Topological Quantum Computers Cannot Work

The Geometry of Spacetime is Enabled by the Failure of Quantum Fault-Tolerance


Left: Nick Read; Right The front page of Nick’s 1990 famous paper with Greg Moore on nonabelions, and below his email to me from March 2005 on topological quantum computation. (click for full view.)


Left: the argument regarding topological QC demonstrated via Harris’ famous cartoon. While not strictly needed I expect the argument to extend from qubits to gates as well. Right: a recent discussion with Nick over Shtetl Optimized (click for full view). Update: We are actually not in an agreement as it seems from the above discussion (see the discussion below). 

Update (Nov’ 2014): A fifth video, this time in front of a live audience

Complexity and Sensitivity of Noisy BosonSampling

Update: A subsequent post by Steve Flammia, Quantum computers can work in principle over The Quantum Pontiff. (July:) See also this post: Quantum future” just beyond our grasp.

Added later (April 18): Let me quote from what Steve wrote about the videos: The surprising part is the superior production value relative to your typical videotaped lecture (at least for the first overview video). Producing the videos was an interesting and demanding experience and I was certainly happy to read Steve’s description of the production value.  (Of course, the main purpose of Steve’s post was to express his disagreement with the content of the videos. See either the post or Co-‘s comment below.) 

Also there are two earlier versions of my lecture (in 1-hour format) that were videotaped. The first was taken by Jesus De Loera in Davis. Very interesting shooting-angle and interesting comments by Greg Kuperberg, Bruno Nachtergaele and other participants.  The second was taken in Seattle in a UW-PIMS colloquium lecture. Again interesting questions by several participants including James Lee and John Sidles.

(July:) The Simons Institite (almost identical) versions of the movies are now linked from the web-page of my November 15 lecture at SI.

(Added nov 2014): The only difference from the HUJI version is that there are no opening slides and that for the closing slides I used two pictures of my department’s administrative staff.

es1  es2

The administrative crew of the Einstein Institite of Mathematics (click to enlarge)

I thought of it as a nice opportunity to thank our great administrative staff whose part is crucial  in the academic endeavor, and this is a good opportunity to thank the staff in my second academic home – Yale University, in the Simons Institute, in many other places.


Alistair Sinclair and the Simons Institure friendly and helpful staff (click for full size) 

Following Saharon Shelah: How to watch these videos

(Added Nov 2014)

Saharon Shelah explained in an introduction to one of his books, that instructions on “how to read this book” are actually instruction on “how to not read this book”. If you want to read the book you start on page 1 and read through to the last page.  Instructions for “how to read  this book” rather tell you how to jump to a place that interests you.

So, in a similar spirit, here are direct links to the different parts of the videos.

Continue reading

Pictures from Recent Quantum Months


A special slide I prepared for my lecture at Gdansk featuring Robert Alicki and I as climber on the mountain of quantum computers “because it is not there.”

It has been quite a while since I posted here about quantum computers. Quite a lot happened in the last months regarding this side of my work, and let me devote this post mainly to pictures. So here is a short summary going chronologically backward in time. Last week – Michel Dyakonov visited Jerusalem, and gave here the condensed matter physics seminar on the spin Hall effect. A couple of weeks before in early January we had the very successful Jerusalem physics winter school on Frontier in quantum information. (Here are the recorded lectures.) Last year I gave my evolving-over-time lecture on why quantum computers cannot work in various place and different formats in Beer-Sheva, Seattle, Berkeley, Davis (CA), Gdansk, Paris, Cambridge (US), New-York, and Jerusalem. (The post about the lecture at MIT have led to a long and very interesting discussion mainly with Peter Shor and Aram Harrow.) In August I visited Robert Alicki, the other active QC-skeptic, in Gdansk and last June I took part in organizing a (successful) quantum information conference Qstart in Jerusalem (Here are the recorded lectures.).

And now some pictures in random ordering

2013-08-01 10.09.28

With Robert Alicki in Gdynia near Gdansk


With (from left) Connie Sidles, Yuri Gurevich, John Sidles and Rico Picone in Seattle  (Victor Klee used to take me to the very same restaurant when I visited Seattle in the 90s and 00s.) Update: Here is a very interesting post on GLL entitled “seeing atoms” on John Sidles work.


With Michel Dyakonov (Jerusalem, a few days ago)


With Michal Horodecki in Sopot  near Gdansk (Michal was a main lecturer in our physics school a few weeks ago.)


Aram Harrow and me meeting a year ago at MIT.

2013-08-01 10.12.45

2013-08-01 10.12.52

Sometimes Robert and I look skeptically in the same direction and other times we look skeptically in opposite directions. These pictures are genuine! Our skeptical face impressions are not staged. The pictures were taken by Maria, Robert’s wife. Robert and I are working for many years (Robert since 2000 and I since 2005) in trying to examine skeptically the feasibility of quantum fault-tolerance. Various progress in experimental quantum error-correction and other experimental works give good reasons to believe that our views could be examined in the rather near future.


A slide I prepared for a 5-minute talk at the QSTART rump session referring to the impossibility of quantum fault-tolerance as a mild earthquake with wide impact.

GTprod2This is a frame from the end-of-shooting of a videotaped lecture on “Why quantum computers cannot work” at the Simons Institute for the Theory of Computing at Berkeley. Producing a videotaped lecture is a very interesting experience! Tselil Schramm (in the picture holding spacial sets of constant width) helped me with this production.