If Quantum Computers are not Possible Why are Classical Computers Possible?

As most of my readers know, I regard quantum computing as unrealistic. You can read more about it in my Notices AMS paper and its extended version (see also this post) and in the discussion of Puzzle 4 from my recent puzzles paper (see also this post). The amazing progress and huge investment in quantum computing (that I presented and update  routinely in this post) will put my analysis to test in the next few years.


Guy Kindler and I identified a very primitive complexity class LDP that describes noisy quantum systems in the small scales (few bosons, qubits etc.) 

Today I would like to discuss, with the help of illustrations, a central issue in the debate about quantum computing: In view of a putative impossibility (and obvious difficulty) of quantum computing, why  is classical computing possible (and so common)? This was a major challenge that Aram Harrow raised in our 2012 debate (in this post), and it goes back to Dave Bacon and others. My 2014 work with Guy Kindler on noisy BosonSampling (taking them as an analogy for noisy quantum circuits) leads to a fairly detailed answer that I will explain below, mainly with illustrations.

The picture behind the question

A common view: in principle, there is no difference between achieving quantum computing via quantum error-correcting codes and achieving classical computing via classical error-correcting codes. 


Why are classical information and computation possible?

Encoding by repetition, and decoding by “majority” are both supported by low degree polynomials

Encoding by repetition refers to a logical ‘one’ encoded by many physical ones and the same with zero.  Approximate version of majority enables decoding. Both encoding and decoding are supported by low degree polynomials. (A variant which is more realistic is that one is encoded by 70% ones (say) and zero by 30% ones.)

Why are robust quantum information and quantum computation impossible?

It is commonly expected that creating good-quality quantum error correcting codes is harder than demonstrating quantum supremacy.

Unlike the repetition/majority mechanism which is supported by very primitive computational power, creating a quantum error correcting code and the easier task of demonstrating quantum supremacy are not likely to be achieved by devices which are very low-level in terms of computational complexity.

This is the difference!

(Quantum supremacy refers to the ability of quantum computers to perform computations which are infeasible for classical computers. )

The computational complexity picture

Bounded depth computation (AC^0) is an extremely primitive computational complexity class. Sampling tasks that can be performed approximately by low degree polynomials represent an even more primitive computational task. (The proof that LPD is in AC^0 is quite clever but seems to Guy and me quite irrelevant to quantum computing 🙂 )

LDP is so low-level that it allows efficient learning!

(This leads to the following prediction: distributions coming from pure quantum states that can be approached by noisy quantum devices  allows efficient approximate learning.)

The underlying principles

Very simple, isn’t it?

The notion of “primitive computational devices” in both principles applies to the asymptotic behavior. The second principle extends to quantum devices that do not involve quantum error-correction.

Can you be a little more formal?

Let me try. (Trying to understand how insights from the theory of computation relate to real life computation is quite important.)

I don’t know how general is this insight. (I asked about it in TCSoverflow.) Note that this insight gave the rationale for the threshold theorem to start with.

My older stuff about correlated errors

My earlier work (Section 6 of the Notices paper, and earlier works cited there) proposes other goals that appear to be  easier than creating quantum error correcting codes and I expect them to be impossible.

The remarkable IBM machine applies two-qubit CNOT gates. One can expect that errors for the gated qubits have large positive correlation. This is not controversial but it would be nice to check it.

You can implement CNOT gate indirectly by a chain of other gates. I expect that it will not be possible  to reduce the positive correlation by a process that reaches the CNOT indirectly.  (You can experience the IBM quantum computer  here.)

A question by Ady Stern




It is a positive and not terribly small constant!  I am not sure what “fundamental” means.

(Sometimes, I get corrected when I pronounce my name correctly.)

The quality of my argument


But maybe the processes for quantum error-correction have more than meets the eye?

Why not just improve the physical qubits?

Q: But why can’t you simply create good enough qubits to allow universal quantum circuits with 50 qubits?

A: This will allow very primitive devices (in terms of the asymptotic behavior of computational complexity) to perform superior computation.

Q: This is an indirect explanation. Can you give an explanation on the level of a single qubit?

A: Yes, if the qubit is of too high quality, the microscopic process leading to it also demonstrates a primitive device leading to a superior computation.

Topological quantum computing?

What about topological quantum computing?

See this videotaped lecture.

Is Nature a malicious opponent of quantum computing?

My model of errors is precisely the ordinary model.


What do you mean by “primitive computational devices”?

The fate of Quantum Mechanics

What about the huge efforts and resources for building quantum computers or intermediate tasks?

Also the Commonwealth Bank

I talked about the problem with Dave Bacon in 2006

(Inspiration: math with bad drawing)

Posted in Computer Science and Optimization, Physics, Quantum | Tagged , | Leave a comment

Sergiu Hart: Two-Vote or not to Vote


Sergiu Hart raises a very interesting idea regarding elections. Consider the Brexit referendum. Sergiu  proposes to have two rounds two weeks apart.  Every voter can vote in each, and the votes of both rounds add up! The outcomes of the first round are made public well before the second round.

In the paper Repeat Voting: Two-Vote May Lead More People To Vote Segiu Hart suggests the following method:

A. Voting is carried out in two rounds.

B. Every eligible voter is entitled (and encouraged) to vote in each one of the two rounds.

C. All the votes of the two rounds are added up, and the final election result is obtained by applying the current election rules to these two-round totals.

D. The results of the first round are officially counted and published; the second round takes place, say, two weeks after the first round, but no less than one week after the official publication of the first round’s results

(The pun in the title is taken from an early version by Sergiu.)

What do you think?

Posted in Economics, Games | Tagged , | 13 Comments

A toast to Alistair: Two Minutes on Two Great Professional Surprises

Alistair and the Simons Institure friendly and helpful staff 

Luca Trevisan invited me to give a 3-minute (vidotaped or live) toast for Alistair Sinclair to celebrate that Alistair much deservedly received the SIGACT service award and to mourn that he also just retired from his role of associate director of the Simons Institute. These toasts will be part of FOCS 2017 Saturday evening reception (October 14) which will be hosted by the SI and turn into a party for Alistair. It is great that leading scientists excel also in the all so important academic administration tasks. I can think in this context about Michael Rabin who was the rector (provost) of my university and many others.

But I thought it could be a good idea to mainly mention in my toast two of Alistair’s great and mind-boggling scientific contributions. Miraculously, I had a videotaped which was lying on the editing floor for three years.  It was part of the first ever  (and maybe the only ever) Simons Institute videotaped production. (The toast video was done by me using my smartphone and it took many takes to do.) So you can hear for one minute and a half quick stories about rapid mixing and approximate permanents and inspiring persistence and volume.

From the editing floor: Two Minutes on approximating permanents, rapidly mixing random walks in algorithms, and volumes

Click here for the toast video for Alistair!

This brief video was edited out from my videotaped lecture on quantum computers (see this earlier post). When we prepared the videos, I was quite excited by the fact that we do not  need to shoot the video in the right order. (I even use this fact to outline a major difference between classical computation and quantum computation.)  We first shot the pictorial + entertaining  ending  of Video II. Then we moved to shoot Video I and the plan was to start it with Alistair Sinclair introducing me. In the beginning of the unedited video, I say to Tselil in Hebrew that we do not need to bring Alistair up to the production room  since he can record his introduction later.  (At the end we decided not to have an introduction at all.) As seen from my smile, when I thanked Alistair for his yet-to-be-given introduction I felt as sophisticated as Niccolò Machiavelli.

And here are links to the papers mentioned: Approximating the Permanent by Jerrum and Sinclair, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries by Jerrum, Sinclair and Vigoda (and here is the Journal version), and A random polynomial time algorithm for approximating the volume of convex bodies by Dyer, Frieze and Kannan.

Indeed these amazing algorithmic applications of  rapidly mixing random walks came as great surprises and are extremely important!

Lovely ending presentation, forgotten pictures of Avi and Oded, Jesus, the camel and Bob Simons, and Scott Aaronson’s 100,000$ promise.

Talking about my old Simon Institute lectures videos, let me first recommend to you the two minutes ending of the second video – lovely pictures and a wonderful song in the background. Can you identify the people there? (There are 49 altogether!)


The second video includes (toward the end, click here to jump to this part) a presentation of some pictures +funny things related (more or less) to the debate on quantum-computers. It contains (click to jump) a forgotten picture of Avi Wigderson and Oded Goldreich, Continue reading

Posted in Computer Science and Optimization, Updates | Tagged | Leave a comment

TYI 31 – Rados Radoicic’s Rope Problem


Ropemaker (source)

Rados Radoicic wrote me:

“Several years back, I heard the following puzzle that turns out to be rather ‘classical’:

“There are N ropes in a bag. In each step, two rope ends are picked uniformly at random, tied together and put back into a bag. The process is repeated until there are no free ends. What is the expected number of loops at the end of the process?”

Before moving on, please try to answer this question.

Let me go on with Rados’ email:

“Upon hearing this puzzle, I came up with and have been wondering (for years now) about the following “natural” variation:

“What if at each step, each end is picked with the probability proportional to the length of its rope?”

I made no epsilon-worthy progress on this problem since then. A properly-trained probabilist (unlike me) might find it easy, but somehow my gut feeling tells me it may be very interesting and not simple at all.”

The challenges are to test yourself on the first question and try to answer the second. No polls this time; comments and thoughts on both versions are welcome.

Posted in Combinatorics, Probability, Test your intuition | Tagged , | 7 Comments

Eran Nevo: g-conjecture part 4, Generalizations and Special Cases

This is the fourth in a series of posts by Eran Nevo on the g-conjecture. Eran’s first post was devoted to the combinatorics of the g-conjecture and was followed by a further post by me on the origin of the g-conjecture. Eran’s second post was about the commutative-algebra content of the conjecture. It described the Cohen-Macaulay property known to hold for simplicial spheres and the Lefshetz property which is known for simplicial polytopes and is wide open for simplicial spheres. Eran’s third post was about the connection to algebraic shifting. The fifth and last post is planned to deal with connections to rigidity, a fascinating topic on its own which is related also like yesterday’s post  to architecture and art.

(From right): Udo Pachner, Peter Kleinschmidt, and Günter Ewald. (Oberwolfach photo collection)

All kinds of spheres

It is possible that the link of a vertex in a simplicial sphere is no longer a sphere. This is not good if we look for a proof by induction. A subfamily which is closed under links is the piecewise linear spheres. Another advantage of this family for inductive proof is given by Pachner: any PL-(d-1)-sphere can be obtained from the boundary of the d-simplex by a finite sequence of bistellar moves aka Pachner moves.  This is a family of d+1 possible local moves, defined combinatorially.

However, so far no proof of the g-conjecture for PL-spheres is known. Continue reading

Posted in Combinatorics, Convex polytopes, Guest post, Open problems | Tagged , | 2 Comments

The World of Michael Burt: When Architecture, Mathematics, and Art meet.


This remarkable 3D geometric object tiles space! It is related to a theory of “spacial networks” extensively studied by Michael Burt and a few of his students. The network associated to this object is described in the picture below.

And below you can see the first step in tiling the whole space: How two tiles fit together.

Michael Burt started finding and classifying related objects in his 1967 Master thesis. My academic grandfather Branko Grunbaum (below left) helped him in his early works. The thesis was so impressive that Michael (below, right) was awarded a doctorate for it.


You can find more about it in Michael’s site. The site includes slides for various lectures like the one on UNIFORM NETWORKS, SPONGE SURFACES AND UNIFORM SPONGE POLYHEDRA IN 3-D SPACE.

Below are some more pictures from Michel Burt’s home. In one of them you can see Michael, his wife Tamara, and my friend since university days Yoav Moriah who initiated the visit.


Posted in Art, Combinatorics, Geometry | Tagged , , | 4 Comments


This story is implicitly referred to in the 2008 opening post of this blog.


It was high time to raise the level of the discussion, I thought. Princeton, Fall 1995. We were a group of mathematicians at the IAS lunch table, and discussing a really profound idea was called for. But I was missing a word and I asked Avi Wigderson what is the English word for a lion’s hair. Avi replied “layish”.

This was precisely what I was missing. It was time to voice my new thought:

” Isn’t it the case and isn’t it amazing that Avi’s hair looks just like a layish?”, I asked



Pierre Deligne looked busy thinking about his own business, but Enrico Bombieri looked interested and he was trying to understand what I was saying. Robert Langlands seemed to have got it –  he was nodding his head in agreement – or so I thought. I also sensed a positive reaction from Bob MacPherson.  Well, it takes time for great ideas, however simple, to get through.

But as is often the case, one great idea led to another.

Isn’t it amazing that the word “layish” means in Hebrew “a lion,” a meaning so close to the English meaning? I asked

While trying to further repeat, promote and discuss these two ideas a conflicting piece of information came to my mind. Another word for a lion’s hair in English was something like “main” or “mane”, I started to vaguely remember. When I asked Avi about it, he could not hold his laughter any longer, and the sad reality had emerged.

The second great idea was just an artifact of Avi’s juvenile behavior, a behavior that  also had a devastating effect on the presentation of the first idea. The first idea, as great as it might be,  failed to come through due to problematic notation. It should have waited for another opportunity. And now, 22 years later this opportunity has come!

The observation regarding Avi’s hair is not isolated. Continue reading

Posted in Combinatorics, Computer Science and Optimization, Games, Mathematics to the rescue, Philosophy, Rationality, Sport, Taxi-and-other-stories | Tagged , , | 4 Comments

Some Mathematical Puzzles that I encountered during my career

Recently, I gave some lectures based on a general-audience personal tour across four (plus one) mathematical puzzles that I encountered during my career. Here is a paper based on these lectures which is meant for a very wide audience (in English)

Puzzles on trees, high dimensions, elections, computation and noise.

A  videotaped lecture is here. An earlier Hebrew version is

חידות על עצים , ממדים גבוהים, בחירות, חישוב ורעש

(It deals only with the first four puzzles.) A short videotaped Hebrew lecture (where I only discuss the first two puzzles and touch on the third) is here.

A drawing by my daughter Neta for puzzle number 3. (Based on a famous Florida recount picture.)

Summary: I will talk about some mathematical puzzles that have preoccupied me over the years, and I will also reveal to you some of the secrets of our trade. Continue reading

Posted in Combinatorics, Computer Science and Optimization, Quantum | Tagged | 1 Comment

Friendship and Sesame, Maryam and Marina, Israel and Iran

Happy new (Jewish) year everybody.

Amazing scientific partnership  between Jordan, Cyprus, Egypt, Iran, Israel, Pakistan, the Palestinian Authority, and Turkey

SESAME (Synchrotron-light for Experimental Science and Applications in the Middle East) is a “third-generation” synchrotron light source that was officially opened in Allan (Jordan) on 16 May 2017. It is the Middle East’s first major international research center. It is very nice to see scientific cooperation between countries which otherwise do have some difficulties in their relationships.

Narrowing on Israel and Iran, there are many personal scientific friendships and collaborations between Israeli and Iranian scientists and it will certainly be nice to see in the future visits of Israeli scientists to Iran and of  Iranian scientists to Israel.

Marina, Maryam and Maths Friendships

Last July, Marina Ratner and Maryam Mirzakhani, two eminent mathematicians working in the area of dynamics passed away. Maryam was the first woman to win the Fields Medal, and Marina was, for a short time, a faculty member at my department and a close friend of the Hebrew University ever since.   Many of my colleagues knew both Marina and Maryam very well, and were great admirers of their personalities as much as their mathematics. Amie Wilkinson wrote a beautiful NYT article about Marina and Maryam’s mathematics: With Snowflakes and Unicorns, Marina Ratner and Maryam Mirzakhani Explored a Universe in Motion. (See also this HUJI memorial page, this post on Terry Tao’s blog, and this post on GLL.)

Amir Asghari had a nice idea to open a site dedicated to maths friendships in memory of Maryam Mirzakhani.  Let me also mention that there is a well known Israeli Facebook group for “digging into mathematics” that dedicated its profile picture to Maryam.



Posted in Obituary, Updates, Women in science | Tagged , , , , | 1 Comment

Elchanan Mossel’s Amazing Dice Paradox (your answers to TYI 30)

TYI 30 asked Elchanan Mossel’s Amazing Dice Paradox (that I heard from Yuval Peres yesterday)

You throw a die until you get 6. What is the expected number of throws (including the throw giving 6) conditioned on the event that all throws gave even numbers?

Most people answered 3.

Is it the right answer?


Continue reading

Posted in Combinatorics, Probability, Test your intuition | Tagged , | 62 Comments