Debate round 3: Computation cannot hide the physics

Mark Kac was a great mathematician, and worked mainly in probability theory. Kac is famous for the Erdős-Kac theorem, which is often called “the fundamental theorem of probabilistic number theory.” It asserts that the distribution of the number of distinct prime factors of an integer behaves like a standard normal distribution with mean and variance . He is also famous for the Feynman-Kac formula from stochastic partial differential equations.

Today we present the third round of our debate between Gil Kalai and Aram Harrow on the feasibility of building scalable universal quantum computers. We intend one further post with final summations by both.

Kac is recalled most of all for the following famous question he posed:

Can one hear the shape of a drum?

This sounds evocative but is actually technical. Hearing depends mostly on the spectrum of the drum vibrations. How much does that tell us about the structure of what is being vibrated?

Technically speaking the question is about our ability to “read” the geometry of a domain from the eigenvalues of its Laplacian. Years of study showed that while we can hear a great deal of the shape of the drum, the answer to Kac’s question is no, as there are iso-spectral drums with substantially different geometry. But the basic question still reverberates, and Gil Kalai here asks about its extent in quantum computation.

Our debate began in late January with a post in which Gil explained his conjectures of impediments to quantum computation, and Aram described the roadmap for his reply. Aram responded in three posts (I, II, III), to which Gil attached short rejoinders. A second round of the debate emerged after Aram co-wrote a draft paper with Steve Flammia that proposed compelling counterexamples to Gil’s original Conjecture C, in which Gil replied with revisions to his conjecture. As we go to “press,” we note another recent paper by John Preskill on related matters.

Gil Again: Taking Stock

We have had a very interesting and wide-ranging discussion on various issues surrounding quantum computers and quantum fault-tolerance. This has been joined by over a dozen researchers besides ourselves in hundreds of comments to the posts, which have continued right up through this month, and which both I and Aram have learned from. I will first summarize by taking a wider look at the subject at hand, and my later summation will reply to the two most important issues that Aram has raised.

Recent posts by Dick and Ken have compared the world with to the world with , also considering various forms of each alternative. Russell Impagliazzo famously compared “five possible worlds” in complexity and cryptography. Here, moving to the quantum domain, I consider two other worlds, two that are likewise mutually incompatible and one of which we belong to. FTQC stands for the world with universal fault-tolerant quantum computers. NFT, for “non-FT evolutions,” refers to the situation that we actually have without quantum fault tolerance which enable universal quantum computers.

Telling Between Two Worlds

Below are six fundamental differences between the world before (or without) universal quantum computers and the world after. Here “noiseless” means for all practical purposes, i.e., that the probability of error is negligible.

1. Can an (essentially) noiseless encoded qubit be constructed? For non-FT evolutions the answer is no. With FTQC: yes.
2. For mixed-state approximations of pure states, is there a systematic relation between the state and the noise? For non-FT evolutions: yes. With FTQC: essentially no.

   This distinction means that the same pure states (e.g., Bose-Einstein states) will have different mixed-state approximations in nature compared to their mixed-state approximations in fault-tolerant quantum computers.

3. Are there general-purpose quantum emulators? Alternatively, perhaps every type of quantum state/evolution that can be emulated requires a special machine? For non-FT evolutions: the latter. With FTQC: the former. We discuss this issue in the last part of my post.

   Now we come to the opening thematic question speaking a fourth fundamental difference, which we discuss further below:

4. Can you hear the shape of a quantum computer? If universal quantum computers can be built the answer is no. I conjecture that the answer is yes.
5. Are complicated quantum states based on complicated multi-qubit interaction “physical”?

   Universal quantum computers (must) allow complicated quantum states that involve multi-qubit interaction. Non-FT quantum evolutions imply severe restrictions on pure states that can be approximated. This is what Conjecture C is trying to express.

   And finally,

6. Can devices based on quantum mechanics lead to superior computational power?

   Universal quantum computers allow superior computational power (including an efficient method for factoring). Non-FT quantum evolutions are likely to leave us with as the maximum generally feasible class.

In the original post, Conjectures 1 and 2 address item 1 here, Conjectures 3 and 4 address item 2, and Conjecture C addresses item 5. Now we discuss items 3 and 4. The prospect of ‘yes’ on item 6 is behind both the expectations and hopes of those building quantum computers and the concerns of those who are skeptical.

Can You Hear the Shape of a Quantum Computer?

Let me first talk a little about geometry and discuss point number 4. The basic model for quantum computers is combinatorial, and geometry plays no role. Also in my conjectures that propose why (universal) quantum computers fail, geometry plays no role. In fact this was one of my principles in this pursuit. A basic question is:

Can you learn about the geometry/physics from the states/evolutions of your quantum computer?

For classical computers the answer is no. If universal quantum computers can be constructed, the answer for quantum computers must be no as well.

Namely, the quantum evolution run by our universal quantum computer would not give us any hint about its geometry. A universal quantum computer would allow us to simulate a high-dimensional quantum process on an array of qubits with a geometry of our choice. Consider, for example, Alexei Kitaev’s four-dimensional self-correcting memory. This is a remarkable quantum analog of the 2D Ising model, and it is an outstanding open question whether 3D objects with similar properties can be constructed. Once we have a universal quantum computer we will even be able to realize Kitaev’s 4D model on an array of qubits that looks like this (src):

If my conjectures are correct then there are plenty of quantum evolutions and quantum states that cannot be achieved at all. In addition, I expect that the evolutions and states that can be reached will depend on the geometry of your quantum device and the geometry and physics of your world.

One philosophical reason for why I would tend to think that the geometry can be “read” from the states and evolutions of a quantum device is the following. I see quantum mechanics as the theory where the buck stops. If the universe is a large quantum computer of some sort, and if we cannot hear the shape of a quantum computer, then where does geometry come from?

A somewhat similar story can be told about time. Let’s leave it for another time.

Special-Purpose Quantum Emulators

Scott Aaronson gave a nice description of the central problem for realizing universal quantum computing, in his IEEE Tech Talk article on February 7th, explaining his backing his words with a $100,000 open wager:

The central problem is decoherence, meaning unwanted interactions between the computer and its external environment, which prematurely “measure” the computer and destroy its fragile quantum state. The more complicated the quantum computation, the worse a problem decoherence can become. So for the past fifteen years, the hope for building scalable quantum computers has rested with a mathematically-elegant theory called “quantum fault-tolerance,” which shows how, if decoherence can be kept below a certain critical level, clever error-correction techniques can be used to render its remaining effects insignificant. (Emphasis added)

I outlined the word “if.” When it comes to general-purpose quantum computers the skeptical explanation is that, very simply, decoherence cannot be kept low; in fact it scales up. Therefore, universal quantum computers cannot be built. My approach is that this should be demonstrated by studying the behavior of special-purpose machines for emulating quantum evolutions. My conjectures apply to special-purpose machines and to natural mechanisms to create quantum evolutions.

The crux of the matter is understanding the behavior of special-purpose devices for creating quantum evolutions. Realizing this nullifies the sentiment (or argument) that damaging noise models manifest some conspiracy or malice by nature. A bicycle ride around the block requires a different device and hence carries different risks from a manned mission to Mars.

Aram’s Third-Round Response

Quantum mechanics has long benefited from critics and skeptics. Erwin Schrödinger himself came up with his famous cat to highlight the seemingly absurd consequences of the new theory of quantum mechanics; now experimentalists boast of creating “cat states” in trapped ions and other implementations. Entanglement, arguably the most radical feature of quantum mechanics, was first described in its modern form by Albert Einstein, Boris Podolsky, and Nathan Rosen in a paper in 1935 that sought to highlight the problems with this new theory. Now EPR pairs play the same role in quantum information that NAND gates do in circuits.

More recently, quantum computing (and specifically Peter Shor’s factoring algorithm) met with criticism in the mid 1990’s on the grounds that decoherence would prevent quantum computers from getting off the ground. For example, Bill Unruh argued in 1994 that the maximum number of steps taken by a quantum computer should be , where is the temperature, which corresponds to a natural noise rate. Shor’s paper introducing fault-tolerant quantum computation (FTQC) credits the role of critics:

I would like to thank Rolf Landauer and Bill Unruh for their skepticism, which in part motivated this work.

Unruh was convinced by this paper, and has dropped his objections. Landauer unfortunately is no longer alive, but his protégé Charlie Bennett has gone on to become a leader in the field of quantum information, as well as an independent discoverer of quantum error-correcting codes.

But not all skeptics are convinced. Despite the provable extension of the FT threshold theorem to ever more general scenarios, and the lack of any theory of noise that is both consistent with observation and inconsistent with FTQC, the idea of quantum computing remains controversial. However, the task of the skeptics is now a difficult one. Attempting to give a theory that would exclude quantum computers while keeping quantum mechanics reminds me of the famous saying of Jesus:

It is easier for a camel to pass through the eye of a needle than for a rich man to enter heaven.

What I like about this quote is that it expresses the idea that something may be in principle possible (a rich man going to heaven), but there are so many difficulties along the way (how one acquired one’s wealth, the fact that it hasn’t been given to those in need, etc.) that we are left with either the vivid impossibility of the camel, or the painful alternate reading of trying to thread rope made of hemp or camel hair.

Similarly, Gil and other modern skeptics need a theory of physics which is compatible with existing quantum mechanics, existing observations of noise processes, existing classical computers, and potential future reductions of noise to sub-threshold (but still constant) rates, all while ruling out large-scale quantum computers. Such a ropy camel-shaped theory would have difficulty in passing through the needle of mathematical consistency.

Some Specifics

Let me get down to specifics. Gil suggests that even if FTQC is possible in general, one might be able to define a “sixth world” of NFT, in which quantum computing is implemented without using fault-tolerant methods. But fault-tolerance is not a special switch that can be turned on like the noise-canceling feature of headphones. It is simply a recipe for putting together a series of quantum gates (or in more complicated versions, also measurements, classical side computation, and adaptive modification of the quantum gates being applied). Allowing QC but not fault tolerance is a little like allowing general-purpose classical computing, but forbidding the Fast Fourier Transform (FFT).

Could one define the sixth world of “NFFT” (for “No FFT”)? Clearly not. It is impossible to say whether, lurking somewhere in a complicated computation, the ideas of the FFT have been encoded. Similarly, NFT cannot hope to be meaningfully defined. Finally, what about hearing the shape of things? I don’t see how the analogy quite fits, but in any case, it seems not to go in the way of the skeptics. Even for systems that “compute” only a simple linear response, one cannot always hear the shape. Here is a picture of two iso-spectral drum surfaces with different shapes (src):

It is not clear to me what the right analogue of this question is for computation. Does the spectrum of the drum become replaced by the function computed by a circuit? If so, certainly we have different classical circuits computing the same function, and as a corollary, we have different quantum circuits computing the same function. After all, classical computing is a special case of quantum computing.

Open Problems

How does the analogy with Mark Kac’s problem play out? Note that the spectrum of an ordinary undirected graph is even further from characterizing its structure than Kac thought might be the case for surfaces. Nevertheless spectra of graphs have been fundamental to understanding expanders, which in turn have driven many important recent results.

For a particular issue, does quantum teleportation already nullify the possibility of a systematic dependence between the quantum evolution and the geometry of the quantum computer?

[fixed link to Unruh paper]