An AMS article by Gil Kalai updates his skeptical position on quantum computers

Gil Kalai is a popularizer of mathematics as well as a great researcher. His blog has some entries on Polymath projects going back to the start of this year. He has just contributed an article to the May AMS Notices titled, “The Quantum Computer Puzzle.”

Today we are happy to call attention to it and give some extra remarks.

The article includes a photograph of Gil with Aram Harrow, who was his partner in a yearlong debate we hosted in 2012. We say partner because this was certainly more constructive than the political debates we have been seeing this year.

We’ve missed chances to review some newer work by both of them. In 2014, Gil wrote a paper with Greg Kuperberg on quantum noise models and a paper with Guy Kindler relating to the sub-universal BosonSampling approach. Among much work these past two years, Aram wrote a position paper on the quantum computing worldview and this year a paper with Edward Farhi. The latter reviews possible ways to realize experiments that leverage complexity-based approaches to demonstrating quantum supremacy, a term they credit to a 2011-12 paper by John Preskill.

Supremacy

Quantum supremacy has a stronger meaning than saying that nature is fundamentally quantum: it means that nature operates in concrete ways that cannot be emulated by non-quantum models. If factoring is not in —let alone randomized classical quadratic time—then nature can do something that our classical complexity models need incomparably longer computations to achieve. We like to say further that it means nature has a “notation” that escapes our current mathematical notation—insofar as we use objects like vectors and matrices that have roughly the same size as classical computations they describe, but swell to exponential size when we try to use them to describe quantum computations.

Aram’s paper with Fahri leverages complexity-class collapse connections shown by Michael Bremner, Richard Jozsa, and Daniel Shepherd and an earlier paper by Sergey Bravyi, David DiVincenzo, Reberto Oliveira, and Barbara Terhal. For instance, via the former they observe that if the outputs of certain low-depth quantum circuits can be sampled classically with high approximation then the polynomial hierarchy collapses to level 3. This remains true even under an oracle that permits efficient sampling of a kind of quantum annealing process. This is arguably more of a hard-and-fast structural complexity collapse than factoring being in would be.

Quantum supremacy also entails that the quantum systems be controllable. Preskill’s paper raises concrete avenues besides ones involving asymptotic complexity classes. Gil’s article picks up on some of them:

1. Attempts to create small universal quantum circuits with up to “a few tens of qubits.”
2. Attempts to create stable logical qubits based on surface codes.
3. Attempts to have Boson Sampling for 10–50 bosons.
4. Attempts to create stable qubits based on anyonic states.
5. Attempts to demonstrate quantum speedup based on quantum annealing.

As Gil notes, the last has been undertaken by the company D-Wave Systems. This has come amid much controversy but also admirable work and give-and-take by numerous academic and corporate groups.

Some Remarks

Our first remark is that Gil’s paper highlights a nice example of how computational complexity theory informs and gives structure to a natural-science debate. Aram and others have done so as well. We especially like the connection between prevalent noise and bounded-depth circuits vis-à-vis low-degree polynomials. We believe the AMS Notices audience will especially appreciate that. We’ve wanted to go even further and highlight how Patrick Hayden and Daniel Harlow have proposed that complexity resolves the recent black hole firewall paradox.

Our second remark is that this is still largely a position paper—the arguments need to be followed into the references. For example, the fourth of Gil’s five predictions reads:

No logical qubits. Logical qubits cannot be substantially more stable than the raw qubits used to construct them.

On the face of it, this is just the negation of what the quantum error-correcting codes in the fault-tolerance theorem purport to do. Gil follows with a more technical section countering quantum fault-tolerance in a stronger fashion with some technical detail but still asserting positions.

Our third remark is that the nub—that “when we double the number of qubits in [a quantum] circuit, the probability for a single qubit to be corrupted in a small time interval doubles”—is presented not as new modeling but “just based on a different assumption about the rate of noise.” We think there needs to be given a fundamental provenance for the increased noise rate.

For instance, a silly way to “double” a circuit is to consider two completely separate systems and to be one “circuit.” That alone cannot jump up the rate, so what Gil must mean is that this refers to doubling up when and already have much entanglement. But then the increased rate must be an artifact of entangling them, which to our mind entails a cause that proceeds from the entanglement. Preskill on page 2 of his paper tabs the possible cause of supremacy failing as “physical laws yet to be discovered.” We’ll come back to this at the end.

The Puzzle

Gil puts the overall issue as being between two hypotheses which he states as follows:

• Optimistic Hypothesis: It is possible to realize universal quantum circuits with a small bounded error level regardless of the number of qubits. The effort required to obtain a bounded error level for universal quantum circuits increases moderately with the number of qubits. Therefore, large-scale fault-tolerant quantum computers are possible.
• Pessimistic Hypothesis: The error rate in every realization of a universal quantum circuit scales up (at least) linearly with the number of qubits. The effort required to obtain a bounded error level for any implementation of universal quantum circuits increases (at least) exponentially with the number of qubits. Thus, quantum computers are not possible.

I have a position that Dick and I have discussed that sounds midway but is really a kind of pessimism because it might make nobody happy:

• “Medimistic” Hypothesis: A full binary tree of Controlled-NOT gates on qubits, possibly with 1-qubit Hadamard and -gates in-between, takes not effort in our world. So the effort required to obtain a bounded error level for any implementation of universal quantum circuits increases quadratically with the number of qubits. Thus, quantum computers are possible but the most general ones are sandbagged.

This would put factoring in quantum time. That would still leave public-key cryptography as we know it under a cloud, though it might retain better security than Ralph Merkle’s “Puzzles” scheme. But the quadratic scale would be felt in all general quantum applications. It would leave everyone—“makers” and “breakers” alike—operating under the time and hardware and energy constraints of Merkle’s Puzzles, which we recently discussed.

Thus we have a “pun-intended” opinion on how the “Puzzle” in Gil’s title might resolve. However, I have not yet solved some puzzles of my own for marshaling the algebraic-geometric ideas outlined here to answer “why quadratic?” They entail having a mathematical law that burns-in the kind of lower-bound modeling in this 2010 paper by Byung-Soo Choi and Rodney van Meter, under which they prove an depth lower bound for emulating such CNOT trees with limited interaction distance where is a dimensionality parameter. This brings us to our last note.

The Onus of Novelty

The main issue—which was prominent in Gil and Aram’s 2012 debate—is that everything we know allows the quantum fault-tolerance process to work. Nothing so far has directly contradicted the optimistic view of how the local error rate behaves as circuits scale up. If engineering can keep below a fixed constant rate then the coding constructions kick in to create stable logical qubits. If some is a barrier in our world, what might the reason be?

It could be that this is a condition of our world, perhaps having to do with the structure of space and entanglement that emerged from the Big Bang. Gil ends by arguing that quantum supremacy would create more large-scale time-reversibility than we observe in nature. It would also yield emulations of high-dimensional quantum systems on low-dimensional hardware of kinds not achieved in quantum experiments to date—on top of our long-term difficulties of maintaining more than a handful of qubits.

This hints that an explanation could be as hard as explaining the arrow of time, or that could be a fundamental constant like others in nature for which string theory has trended against unique causes. Still, these other quantities have large supporting casts of proposed theory. If the explanation has to do with the state of the world as we find it then how do initial conditions connect to the error rate? More theory might indicate a mechanism by which initial should at least help indicate why isn’t simply an engineering issue.

Thus there is still an onus of novelty for justifying the pessimistic position. It may need to propose a new physical law, or a deepened algebraic theory of the impact of spatial geometry that retains current models as a limit, or at least a more direct replacement for what Gil’s article tabs as “the incorrect modeling of locality.”

Open Problems

How effective is the “Puzzle” for guiding scientific theory?

We note that the much–acclaimed and soberly–evaluated answer on quantum computing by Canada’s Prime Minister, Justin Trudeau, had this context: A reporter said, “I was going to ask you to explain quantum computing, but… [haha]…when do you expect Canada’s ISIL mission to begin again…?” Trudeau ended his spiel by saying, “Don’t get me going on this or we’ll be here all day. Trust me.” Would he have been able to detail the challenges?

Update: Gil released an expanded version to the ArXiv.

[added qualifier on Choi-van Meter result, added main sources for Farhi-Harrow]