Limits and Solvability of Quantum Computing

Scott Aaronson

Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae +3 more

This paper investigates the power of polynomial-time quantum computation in which only a very limited number of qubits are initially clean in the |0> state, and all the remaining qubits are initially in the totally mixed state. No initializations of qubits are allowed during the computation, nor intermediate measurements. The main results of this paper are unexpectedly strong error-reducible properties of such quantum computations. It is proved that any problem solvable by a polynomial-time quantum computation with one-sided bounded error that uses logarithmically many clean qubits can also be solvable with exponentially small one-sided error using just two clean qubits, and with polynomially small one-sided error using just one clean qubit. It is further proved in the case of two-sided bounded error that any problem solvable by such a computation with a constant gap between completeness and soundness using logarithmically many clean qubits can also be solvable with exponentially small two-sided error using just two clean qubits. If only one clean qubit is available, the problem is again still solvable with exponentially small error in one of the completeness and soundness and polynomially small error in the other. As an immediate consequence of the above result for the two-sided-error case, it follows that the TRACE ESTIMATION problem defined with fixed constant threshold parameters is complete for the classes of problems solvable by polynomial-time quantum computations with completeness 2/3 and soundness 1/3 using logarithmically many clean qubits and just one clean qubit. The techniques used for proving the error-reduction results may be of independent interest in themselves, and one of the technical tools can also be used to show the hardness of weak classical simulations of one-clean-qubit computations (i.e., DQC1 computations).

Rolando D. Somma, Howard Barnum, Gerardo Ortíz +1 more

One way to specify a model of quantum computing is to give a set of control Hamiltonians acting on a quantum state space whose initial state and final measurement are specified in terms of the Hamiltonians. We formalize such models and show that they can be simulated classically in a time polynomial in the dimension of the Lie algebra generated by the Hamiltonians and logarithmic in the dimension of the state space. This leads to a definition of Lie-algebraic "generalized mean-field Hamiltonians." We show that they are efficiently (exactly) solvable. Our results generalize the known weakness of fermionic linear optics computation and give conditions on control needed to exploit the full power of quantum computing.

Scott Aaronson

Brennan Michael King

Materov

Since Turing, it's been generally accepted that computing systems have two types of limitations: algorithmic (some problems are fundamentally unsolvable) and engineering (the hardware is imperfect, noisy, and breaks). Quantum computing has added a third type— complexity : some problems are solvable, but require resources that grow faster than any polynomial. This supplement introduces a fourth type of restriction, previously not described in the literature: The fundamental limit of quantum computing (FQC) is a limit on the precision of any quantum computing device, which arises not from imperfections in the implementation, but from the discrete structure of spacetime at the Planck scale. This limit cannot be overcome by any technological advancement. It is not a consequence of decoherence , thermal noise, or imperfect gates. It is built into the geometry of reality—just as the speed of light is built into the structure of spacetime and cannot be overcome by any acceleration.Unlike collapse-model-based limits on quantum hardware, the Fundamental Limit of Quantum Computation is proposed as an ontological bound arising from the discrete structure of spacetime itself.