Last chapter, we talked about whether quantum states should be thought of as exponentially long vectors, and I brought up class BQP/qpoly and concepts like quantum advice. Actually, I’d say that the main reason why I care is something I didn't mention last time, which is that it relates to whether we should expect quantum computing to be fundamentally possible or not. There are people, like Leonid Levin and Oded Goldreich, who just take it as obvious that quantum computing must be impossible. Part of their argument is that it's extravagant to imagine a world where describing the state of 200 particles takes more bits then there are particles in the universe. To them, this is a clear indication something is going to break down. So part of the reason that I like to study the power of quantum proofs and quantum advice is that it helps us answer the question of whether we really should think of a quantum state as encoding an exponential amount of information. So, on to the Eleven Objections. Works on paper, not in practice. Violates Extended Church–Turing Thesis. Not enough “real physics.” Small amplitudes are unphysical. Exponentially large states are unphysical. Quantum computers are just souped-up analog computers. Quantum computers aren't like anything we've ever seen before. Quantum mechanics is just an approximation to some deeper theory. Decoherence will always be worse than the fault-tolerance threshold. We don't need fault-tolerance for classical computers. Errors aren't independent. What I did is to write out every skeptical argument against the possibility of quantum computing that I could think of. We'll just go through them, and make commentary along the way. Let me just start by saying that my point of view has always been rather simple: it's entirely conceivable that quantum computing is impossible for some fundamental reason. If so, then that's by far the most exciting thing that could happen for us. That would be much more interesting than if quantum computing were possible, because it changes our understanding of physics. To have a quantum computer capable of factoring 10000-digit integers is the relatively boring outcome – the outcome that we'd expect based on the theories we already have.
Last chapter, we talked about whether quantum states should be thought of as exponentially long vectors, and I brought up class BQP/qpoly and concepts like quantum advice. Actually, I’d say that the main reason why I care is something I didn't mention last time, which is that it relates to whether we should expect quantum computing to be fundamentally possible or not. There are people, like Leonid Levin and Oded Goldreich, who just take it as obvious that quantum computing must be impossible. Part of their argument is that it's extravagant to imagine a world where describing the state of 200 particles takes more bits then there are particles in the universe. To them, this is a clear indication something is going to break down. So part of the reason that I like to study the power of quantum proofs and quantum advice is that it helps us answer the question of whether we really should think of a quantum state as encoding an exponential amount of information. So, on to the Eleven Objections. Works on paper, not in practice. Violates Extended Church–Turing Thesis. Not enough “real physics.” Small amplitudes are unphysical. Exponentially large states are unphysical. Quantum computers are just souped-up analog computers. Quantum computers aren't like anything we've ever seen before. Quantum mechanics is just an approximation to some deeper theory. Decoherence will always be worse than the fault-tolerance threshold. We don't need fault-tolerance for classical computers. Errors aren't independent. What I did is to write out every skeptical argument against the possibility of quantum computing that I could think of. We'll just go through them, and make commentary along the way. Let me just start by saying that my point of view has always been rather simple: it's entirely conceivable that quantum computing is impossible for some fundamental reason. If so, then that's by far the most exciting thing that could happen for us. That would be much more interesting than if quantum computing were possible, because it changes our understanding of physics. To have a quantum computer capable of factoring 10000-digit integers is the relatively boring outcome – the outcome that we'd expect based on the theories we already have.
In the last two chapters, we talked about computational complexity up till the early 1970s. Here, we'll add a new ingredient to our already simmering stew – something that was thrown in around the mid-1970s, and that now pervades complexity to such an extent that it's hard to imagine doing anything without it. This new ingredient is randomness . Certainly, if you want to study quantum computing, then you first have to understand randomized computing. I mean, quantum amplitudes only become interesting when they exhibit some behavior that classical probabilities don't : contextuality, interference, entanglement (as opposed to correlation), etc. So we can't even begin to discuss quantum mechanics without first knowing what it is that we're comparing against. Alright, so what is randomness? Well, that’s a profound philosophical question, but I’m a simpleminded person. So, you’ve got some probability p , which is a real number in the unit interval [0, 1]. That’s randomness. But wasn’t it a big achievement when Kolmogorov put probability on an axiomatic basis in the 1930s? Yes, it was! But in this chapter, we’ll only care about probability distributions over finitely many events, so all the subtle questions of integrability, measurability, and so on won’t arise. In my view, probability theory is yet another example where mathematicians immediately go to infinite-dimensional spaces, in order to solve the problem of having a nontrivial problem to solve! And that’s fine – whatever floats your boat. I’m not criticizing that. But in theoretical computer science, we’ve already got our hands full with 2n choices. We need 2ℵ0 choices like we need a hole in the head.
Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1]. The question is, how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states, which cannot be achieved with classical bits. This statement is certainly true, but it does not tell us, specifically, what problems quantum computers can efficiently solve while classical computers fail to do so. In fact, based exactly on the technique of Feynman's path integral, the output (i.e. transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential). Therefore any quantum computation can be simulated classically; the key question is about the efficiency. Much effort has been made trying to pin down the power of quantum computers based on the machinery of the computational complexity theory. In particular, the class of computational (decision) problems that can be solved efficiently by a quantum computer is called BQP (bounded-error quantum polynomial time); the counterpart for classical computers is called P (polynomial time). Of course, BQP cannot be less than P; in principle quantum computers can simulate classical computers efficiently. The point is that the foundation of quantum computation cannot be established without a proof showing that BQP is strictly larger than P (i.e. BQP ≠ P). In this sense, this question is as interesting as the famous challenge of proving P ≠ NP (non-deterministic polynomial time). A well known instance of an NP problem is the factoring problem; Shor's quantum algorithm is capable of solving the factoring problem in polynomial time, which is not achievable with the best classical algorithm discovered so far. However, we still cannot rigorously exclude the possibility of the existence of an efficient classical algorithm for factoring. Although again without a proof, it is commonly believed that quantum computers are unable to solve some of the NP problems. In fact, the proof of this statement (if true) provides a possible path to prove P ≠ NP. A potentially less demanding question would be, when do we expect a quantum computer to be able to perform some well defined tasks (not necessarily related to any practical problem) that cannot be simulated with any currently available classical device, within a reasonable time? Once achieved, the status is called ‘quantum supremacy' [2]. One may ask, what about Grover's search algorithm, which provides a quadratic speedup over the classical search? Can we say that we can already achieve quantum supremacy with Grover's algorithm? The problem is that, instead of taking the large-N limit, quantum supremacy requires us to determine the actual number of qubits and gates that can no longer be simulated by classical computers within a reasonable time. To elaborate further, we remark that there can be two notions of classical simulation, namely ‘strong simulation' versus ‘weak simulation'. Strong simulation refers to the cases of calculating the transition probabilities, or expectation values of observables, to a high accuracy in polynomial time. Weak simulation requires the probability distributions to be accurately reproduced, which involves ‘sampling' the different outcomes of the quantum devices. Some quantum circuits that cannot be strongly simulated with an efficient classical means may have efficient classical methods for weak simulation [3]. However, we should be careful about the accuracy requirement in the simulation tasks. For example, for many decision problems, it may be sufficient to determine the transition amplitudes to within an additive error, instead of multiplicative error. In other words, the classical simulability of quantum computational problems depends on the accuracy requirement. Currently, there are three popular approaches for achieving quantum supremacy (see Fig. 1), namely (i) boson sampling [4], (ii) sampling IQP (instantaneous quantum polynomial) circuits [5], and (iii) sampling chaotic quantum circuits [6]. In all of these approaches, distributions of different bit strings or photon numbers are sampled from the quantum devices. Furthermore, they all involve the assumption that classical computers are unable to efficiently determine the transition amplitudes, and/or reproduce (or approximate) the distributions of quantum devices performing these tasks, in the sense of both strong and weak simulations. Three different approaches for achieving quantum supremacy: (a) boson sampling; (b) IQP circuits; (c) chaotic quantum circuits. In boson sampling, single photons are injected into different modes of a linear optical network. The task is to determine the photon distributions at the output ports. The key feature of boson sampling is that the transition amplitudes are related to the permanents of complex matrices, which are in general very difficult to calculate exactly, or approximate to within an multiplicative error; these problems belong to the #P-hard complexity class. Moreover, efficient weak simulation of boson sampling is believed to be impossible, unless the polynomial hierarchy collapses to its third level. However, a recent numerical study suggests that, in order to achieve quantum supremacy with boson sampling, one needs to simultaneously generate at least 50 or more single photons, which is still highly technologically challenging. An interesting question is whether linear optics, in the setting of boson sampling, can be applied to solve decision problems. In this case, the transition amplitudes may need to be determined to an additive error. However, we found that a large class of decision problems associated with boson sampling can be simulated by a classical computer [7], settling an open problem [8] by Aaronson and Hance. IQP circuits represent a simplified quantum-circuit model. The initial state starts from the all-zero state, |000…0〉, followed by applying Hadamard gates to each qubit. Then, diagonal gates are applied to the qubits, followed by applying Hadamard gates to each qubit again. The argument of showing the complexity in simulating IQP circuits is similar to that of boson sampling. In fact, the complexity of boson sampling was inspired by the complexity results of IQP circuits. However, when subject to noise, IQP circuits may become classically simulable [9]. Lastly, chaotic quantum circuits refer to the class of quantum circuits where two-qubit gates are applied regularly, while single-qubit gates are applied randomly from a gate set. The output distributions of these circuits approach the so-called Porter–Thomas distribution, which is a characteristic feature of quantum chaos. Recently, there have been several numerical investigations aiming to explore the ultimate limit of classical computing in simulating low-depth quantum circuits. For the ideal cases, one needs to consider both the qubit number and circuit depth for benchmarking quantum supremacy. However, in the presence of noise, these chaotic circuits may also become classically simulable for high-depth circuits [10]. Finally, other than these three approaches, one should expect that quantum supremacy can be achieved for many practical applications, e.g. simulation of quantum chemistry or quantum machine learning. When will it happen? Only time will tell!
As early as 1982 Richard P. Feynman suggested that it might be impossible to simulate quantum mechanical phenomena with a computer without an exponential slowdown the efficiency of computation. He also proposed that this problem may be avoided by allowing the computer to run according to the laws of quantum mechanics, thus implicitely suggesting that a computer based on the quantum mechanical systems, a quantum computer, might have exponentially more computational efficiency than any classical one. A quantum mechanical phenomenon that never occurs classical physics and which actually makes quantum computation interesting and powerful, is the superposition of states, which, loosely speaking, means that instead of being totally one single state, a particle can be in between many states. Compare this to the elements of classical computer, bits. A bit takes values zero or one, but never anything between. In a quantum computer, one is able to store it both values simultaneously one quantum bit, equally weighted or not. Moreover, the classical computer one can store a number from zero to 2n−1 a register of length n, whereas, quantum computation, all the values could be stored simultaneously. The computation, which is performed via unitary transformations the state vector space, then applies to all these values simultaneously. Thus the power of the quantum computation lies not the absolute speed of the hypothetetical quantum computer but the possibility to actually follow many computational path simultaneously, as a nondeterministic automaton does. Alas, the observation of the outcome will yield only one value destroying the rest irreversibly. However, using a procedure smart enough one could obtain some valuable information about the computation.
Turning to quantum mechanics … secret, secret, close the doors! we always have had a great deal of difficulty in understanding the world view that quantum mechanics represents. … It has not yet become obvious to me that there's no real problem. I cannot define the real problem, therefore I suspect there's no real problem, but I'm not sure there's no real problem. So that's why I like to investigate things. – Richard Feynman, 1964 The only difference between a probabilistic classical world and the equations of the quantum world is that somehow or other it appears as if the probabilities would have to go negative. – Richard Feynman, in “Simulating Physics with Computers,” 1982 Our first result is the existence of an efficient universal quantum Turning machine in Deutsch's model. … We give the first formal evidence that quantum Turning machines violate the modern complexity theoretic formulation of the Church Turning thesis. We show the existence of a problem relative to an oracle that can be solved in polynomial time on a quantum Turning machine but require super polynomial time on a bounded error probabilistic Turning machine. – E. Bernstein and U. Vazirani, “Quantum Complexity Theory,” 1997 Quantum computing is a new computational model that may be physically realizable and may provide an exponential advantage over “classical” computational models such as probabilistic and deterministic Turing machines.
Can Reality be simulated by a huge Quantum Computer? Do we believe that Reality is made of something more than interacting quantum systems? The idea that the whole Physics is ultimately a quantum computation—a strong quantum version of the Church-Turing hypothesis well synthesized by the Wheeler’s coinage It from bit—is very appealing. It is theoretically very parsimonious: an Occam razor’s quality-guaranteed description of the world. But, if this is the case, then we need to understand the entire Physics as emergent from the quantum computation. Here I will make a short exploration on how this may come about. Ask a physicist what does he thinks the world is made of. Very likely the first impetuous answer will be: it is made of particles! But, at a second thought the answer will be: it is a Quantum Field. Particles are just states or the Field: they can be created and annihilated. We have indeed a beautiful Grand Unified Field Theory, and we are looking forward to see the Higg’s boson at the LHC. But what is the Quantum Field made of? Ultimately, it is made of quantum systems that are interacting, each system located at a different position in space. Things may be indeed more complicated than that, because the field is a continuum. But is Reality actually continuous? We don ’ t know: but it looks easier to think to Reality as a continuum. Now, suppose that this is not the case, namely Reality is ultimately discrete, and the continuum is only a mathematical fiction. Then, what else is out there more than interacting quantum
Alright, so now we've got this beautiful theory of quantum mechanics, and the possibly-even-more-beautiful theory of computational complexity. Clearly, with two theories this beautiful, you can't just let them stay single – you have to set them up, see if they hit it off, etc. And that brings us to the class BQP : Bounded-Error Quantum Polynomial-Time. We talked in Chapter 7 about BPP , or Bounded-Error Probabilistic Polynomial-Time. Informally, BPP is the class of computational problems that are efficiently solvable in the physical world if classical physics is true. Now we ask, what problems are efficiently solvable in the physical world if (as seems more likely) quantum physics is true? To me it’s sort of astounding that it took until the 1990s for anyone to really seriously ask this question, given that all the tools for asking it were in place by the 1960s or even earlier. It makes you wonder, what similarly obvious questions are there today that no one’s asking?