Strengths and Weaknesses of Quantum Computing

TLDR

Quantum computation has attracted attention after results such as Shor’s algorithm showed it can solve factoring and discrete logarithms in polynomial time, prompting questions about its power over classical probabilistic computers. The authors aim to determine whether all problems in NP can be solved efficiently on a quantum Turing machine. They prove that, with probability one over a uniformly random oracle, NP cannot be solved by a quantum Turing machine in time o(2ⁿ⁄²). They further show that, with probability one over a random permutation oracle, NP∩coNP cannot be solved in time o(2ⁿ⁄³), and that this bound is tight because Grover’s algorithm achieves O(2ⁿ⁄²) for NP.

Abstract

Recently a great deal of attention has focused on quantum computation following a sequence of results suggesting that quantum computers are more powerful than classical probabilistic computers. Following Shor's result that factoring and the extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of NP can be efficiently solved in quantum polynomial time. In this paper, we address this question by proving that relative to an oracle chosen uniformly at random, with probability 1, the class NP cannot be solved on a quantum Turing machine in time $o(2^{n/2})$. We also show that relative to a permutation oracle chosen uniformly at random, with probability 1, the class $NP \cap coNP$ cannot be solved on a quantum Turing machine in time $o(2^{n/3})$. The former bound is tight since recent work of Grover shows how to accept the class NP relative to any oracle on a quantum computer in time $O(2^{n/2})$.