Share this post:

The IBM Quantum team envisions a future where quantum computers interact frictionlessly with high performance computing resources, taking over for the specific problems where quantum can offer a computational advantage. Pushing the envelope of classical computing is crucial to this goal, especially as we develop new quantum algorithms and try to understand which problems are worth tackling with a quantum computer.

Quantum algorithms are usually described by quantum circuits, a series of operations acting on qubits. Although any quantum circuit can be simulated on a conventional classical computer, such simulation is believed to require an exponentially long time. Loosely speaking, adding a single extra qubit to a quantum circuit increases its classical simulation cost by a factor of two. However, efficient (polynomial time) classical simulation is possible for certain restricted classes of quantum circuits with a special algebraic or geometric structure. Understanding which quantum circuits can be simulated efficiently is very important as it helps researchers to benchmark small-scale quantum devices and validate quantum algorithms executed by such devices. This explains why classical simulation of quantum circuits has become an active research area. Like a worthy athletic rival, we must continue to set the bar with classical computing so that quantum engineers and developers can try to leap higher.

In the recently published Nature Physics paper “Classical algorithms for quantum mean values,” we, along with our colleague Dr. David Gosset, associate professor at the University of Waterloo’s Institute for Quantum Computing, show that certain properties of constant-depth quantum circuits on a two-dimensional grid of qubits can be simulated classically in time that grows only linearly with the number of qubits. This stands in sharp contrast with the simulation of deep quantum circuits, those without a limitation to their number of operations, which is believed to require an exponentially long classical computation, becoming impractical beyond more than 40 or 50 qubits.

Two-dimensional quantum circuits model an architecture in which qubits are arranged in a 2D grid and entangling gates can be applied only to nearest-neighbor qubits. This architecture is adopted by almost all quantum computing platforms based on superconducting qubits. From an experimental perspective, the 2D geometry is preferred to minimize crosstalk between qubits and perform high-fidelity quantum gates. We study constant-depth 2D circuits composed of a constant number of gate layers such that entangling gates within each layer are disjoint. Such circuits can propagate information only within a lightcone of constant radius – a crucial property used in our simulation algorithm.

Our paper isolates the core computational subroutine of many noisy-era quantum algorithms: computing the expected value of a multi-qubit observable on the output state of a constant-depth quantum circuit. Let’s unpack this definition. Recall that the output of a quantum circuit is a classical bit string obtained by measuring each qubit. Repeating the circuit several times may generally produce different bit strings after each run. Quantum mechanics gives us a set of rules to compute the probability of observing each bit string. However, predicting which bit strings are likely to appear and reproducing their statistics is a notoriously hard problem for classical computers, even in the special case of constant-depth quantum circuits. Suppose, instead, that we ask questions about average quantities. For example, suppose we run a quantum circuit 100 times and record the output bit string after each run. What fraction of the output strings have an odd number of ‘1’? This is an example of a “quantum mean value problem” which we consider in the paper. A suitably formalized version of this problem is a common step of so-called variational quantum algorithms. In fact, this is the only step that requires a quantum hardware. All other steps of variational quantum algorithms can be efficiently performed on a classical computer.

Variational Quantum Algorithm (VQA): An algorithm that employs a classical optimizer to train a parametrized quantum circuit, with the purpose of approximating answers to a given problem.

For example, variational algorithms for quantum chemistry applications aim to minimize the expected energy of a Hamiltonian describing a system of interacting electrons over a suitable class of variational states. Such states are usually prepared by constant-depth quantum circuits to suppress the accumulation of errors. Electronic Hamiltonians expressed in terms of qubits can be written as a weighted sum of simple multi-qubit observables called Pauli operators. The expected energy of such a Hamiltonian becomes a weighted sum of quantum mean values of the type that we consider in the paper. Thus a classical algorithm that can efficiently solve the quantum mean value problem can also efficiently simulate variational quantum algorithms (at least those based on constant-depth circuits).

The runtime of our classical simulation algorithm has a favorable, linear scaling with the number of qubits, meaning that the time it takes to solve the problem is equal to the number of qubits times a constant. However, adding more gates greatly increases the simulation’s runtime, which may prevent us from classically simulating circuits with a super-constant depth that grows even mildly with the number of qubits. Likewise, quantum circuits violating the 2D qubit connectivity condition are out of reach for our simulator.

Essentially, our results show that classical computers can efficiently simulate variational quantum algorithms employing constant-depth quantum circuits. However, variational quantum algorithms employing deep quantum circuits, or running on hardware whose qubit connectivity cannot be represented using a 2D grid, are beyond the reach of classical simulators (though a recent paper by Nolan Coble and Matthew Coudron, “Quasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits,” extended our algorithm, with certain technical caveats, to the simulation of 3D constant-depth quantum circuits.)

Exploring the frontier of quantum computation is a constant interplay between quantum hardware and high-performance classical simulation, and these classical simulations are especially important today as we check the work of noisy, intermediate-scale quantum devices and try to establish quantum advantages. After all, pushing the limits of computation means advancing our computational abilities on all fronts, quantum and classical.

Bravyi, S., Gosset, D. & Movassagh, R. Classical algorithms for quantum mean values. Nat. Phys. (2021). https://doi.org/10.1038/s41567-020-01109-8