Quantum advantage with shallow circuits

By Sergey Bravyi, David Gosset, Robert T. König. Science, 2017

487 citations recorded by the source corpus.

Quantum outperforms classical Quantum computers are expected to be better at solving certain computational problems than classical computers. This expectation is based on (well-founded) conjectures in computational complexity theory, but rigorous comparisons between the capabilities of quantum and classical algorithms are difficult to perform. Bravyi et al. proved theoretically that whereas the number of “steps” needed by parallel quantum circuits to solve certain linear algebra problems was independent of the problem size, this number grew logarithmically with size for analogous classical circuits (see the Perspective by Montanaro). This so-called quantum advantage stems from the quantum correlations present in quantum circuits that cannot be reproduced in analogous classical circuits. Science, this issue p. 308; see also p. 289 Parallel quantum circuits outperform classical counterparts at solving certain linear algebra problems. Quantum effects can enhance information-processing capabilities and speed up the solution of certain computational problems. Whether a quantum advantage can be rigorously proven in some setting or demonstrated experimentally using near-term devices is the subject of active debate. We show that parallel quantum algorithms running in a constant time period are strictly more powerful than their classical counterparts; they are provably better at solving certain linear algebra problems associated with binary quadratic forms. Our work gives an unconditional proof of a computational quantum advantage and simultaneously pinpoints its origin: It is a consequence of quantum nonlocality. The proposed quantum algorithm is a suitable candidate for near-future experimental realizations, as it requires only constant-depth quantum circuits with nearest-neighbor gates on a two-dimensional grid of qubits (quantum bits).

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/62be3f565b34fc33f586983d9066763d6f4e3f5a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Quantum simulation and computing with Rydberg-interacting qubits (2020, background): “It has been proposed as a possible approach to achieving a quantum advantage with low-depth circuits 262,286 .”
Quantum Computing for Finance: State-of-the-Art and Future Prospects (2020, methodology): “An example of a task for which Quantum Advantage has been proven was introduced in [4] This is also a step on the way to the development of fault-tolerant universal quantum computers (FTQCs), which require error correction [17]–[19] and which will allow for arbitrary quantum algorithms backed by the”
Materials challenges and opportunities for quantum computing hardware (2021, background): “The next frontier in QIP is to achieve quantum advantage (19, 20) for useful problems, which will require reducing system errors and advancing physical platforms to larger scale.”