We know that Shor’s algorithm can factor integers on a quantum computer exponentially faster than any known classical algorithm, and that there are problems, such as the simulation of physical systems as posed by Richard Feynman in the 1980s, that quantum computers can solve that would take classical computers more than the lifetime of the universe to calculate.
But can we prove that a quantum computer can solve a problem exponentially faster than a classical computer?
In 2018, work by Sergey Bravyi (IBM Research), David Gosset (University of Waterloo), and Robert Koenig (Technische Universität München) described a problem that could be solved by a shallow quantum circuit but provably could not be solved by a shallow classical bounded circuit. (More on shallow bounded and unbounded circuits below.)
The primary question left open in their work was: Can shallow quantum circuits solve a problem that even a shallow classical unbounded circuit could not?
The answer is yes.
Robin Kothari, a Senior Researcher at Microsoft Quantum, Luke Schaeffer (University of Waterloo and former intern at Microsoft Quantum), and collaborators Adam Bene Watts (MIT) and Avishay Tal (UC Berkeley) recently showed that: shallow quantum circuits can solve problems that cannot be solved by shallow classical unbounded circuits, unless they use exponentially many gates.
These breakthrough results were presented by Luke Schaeffer at the Annual Conference on Quantum Information Processing (QIP), the largest quantum computing conference in the world, and at the Annual ACM SIGACT Symposium on Theory of Computing (STOC). Their findings are outlined here.
Motivated by the constraints of near-term quantum computing hardware, we compared the power of today’s depth-restricted quantum computers with depth-restricted classical computers.
Using today’s quantum computing hardware, we can study the power of quantum computers that run “shallow” quantum algorithms, whose run time is very small compared to the size of the problem being solved.
But first, some quantum basics.
An idealized quantum computer consists of some number of quantum bits, or “qubits.” There is a small set of quantum operations called quantum gates that act on two qubits at a time and can be applied to any pair of qubits. In a single time step, we allow these gates to be applied to pairs of qubits that do not overlap. For example, in one time step we can apply a quantum gate to qubits 1 and 2, and apply a potentially different quantum gate to qubits 3 and 4, and yet another quantum gate to qubits 5 and 6.
- A quantum circuit is a sequence of quantum gates.
- The depth of a quantum circuit is the number of time steps required to implement a quantum circuit.
Shallow quantum circuits are quantum circuits whose depth is fixed and does not increase with the size of the problem being solved.
The reality of near-term quantum computers is that they have a high error rate and can only tolerate a few time steps of quantum operations before noise overwhelms the signal in the circuit, so on the quantum hardware we currently run, we are motivated to run problems that use shallow quantum circuits.
We use a problem inspired by the work of David Mermin in 1990 on quantum pseudo-telepathy.*
Computer scientists have studied several classes of shallow classical circuits, the most well-known of which are called NC0 and AC0. We will call these circuits “shallow bounded circuits” and “shallow unbounded circuits,” respectively.
NC0 – shallow bounded circuits – are shallow classical circuits where:
- The allowed gates are the logical AND and OR gates on 2 bits, and the NOT gate.
- The AND gate takes in two input bits and outputs 1, if and only if both inputs are 1.
- The OR gate takes in two input bits outputs 1, if and only if at least one input bit is 1.
- The NOT gate negates the input bit.
Note that these shallow bounded circuits are known to be quite weak and their limitations are well understood. For example, these circuits cannot solve the simple problem of deciding if all input bits are equal to 0.
AC0 – shallow unbounded circuits – are similar, except that:
- The AND and OR gates can accept an unbounded or unlimited number of inputs.
- An AND gate with many inputs outputs 1, if and only if all inputs equal 1.
- An OR gate with many inputs outputs 1, if and only if at least one of the inputs is 1.
Shallow unbounded circuits are much more powerful than shallow bounded circuits and as a standard and well-studied model, remain an active area of research.
With this discovery, we hope that new doors open, inspiring others to find solutions to real-world problems with quantum computing.
Watch Luke present these findings at QIP
Learn more about quantum computing
Start solving quantum problems; download the Microsoft Quantum Development Kit
* In 1990, David Mermin described a problem that could be solved by a group of quantum computers located far from each other that could not be explained by classical physics. It was as if the quantum computers used telepathy, which gave rise to the term “quantum pseudo-telepathy.” However, shallow quantum circuits cannot solve Mermin’s problem because the solution requires a quantum state known as the cat state (named after Schrödinger’s cat), which shallow quantum circuits cannot create. Instead, the problem used in this result swaps out the cat state and replaces it with a “poor man’s cat state” which can be created by shallow quantum circuits. The resulting problem can be solved by shallow quantum circuits but cannot even be solved by shallow classical unbounded circuits, as the authors show.