What Should We Do With A Small Quantum Computer?
Aram W. Harrow, Massachusetts Institute of Technology
A large-scale quantum computer would be able to solve problems that existing classical computers would take much longer than the age of the universe to solve. This would have dramatic implications for cryptography, chemistry, material science, nuclear physics and probably other areas that are still un- known. But what about quantum computers that will be available in the next few years? Experimentalists working with ion traps and superconducting qubits have plans to build quantum computers with 50-100 qubits capable of performing some thousands of quantum gates. The company D-Wave is already selling devices with over 1000 qubits, although they can only run a single algorithm (the adiabatic algorithm) and they suffer high rates of noise. An important milestone for these early quantum computers would be to demonstrate “quantum supremacy”; that is, solving a computational problem that could not be solved using classical computers without an astronomical amount of time.
In this talk, I will discuss the prospects for quantum supremacy with current and near-term quantum computers. First I will look at the adiabatic algorithm, which has shown promise in its ability to use quantum tunneling to solve opti- mization problems more efficiently than classical local search. Here I will show that a different classical algorithm (using ideas from condensed-matter theory) can simulate the adiabatic algorithm in these cases. This fast simulation sug- gests that adiabatic tunneling does not outperform classical computing and thus is not a promising approach to quantum supremacy. Second, I will discuss sim- ple variational quantum algorithms that try to approximately minimize some objective function. I will describe methods of running these algorithms efficiently and will show that conjectures from complexity theory imply that these algorithms cannot in general be simulated by classical computers.