Trading Classical and Quantum Computational Resources

By Sergey Bravyi, Graeme Smith, John A. Smolin. 2015

415 citations recorded by the source corpus.

We propose examples of a hybrid quantum-classical simulation where a classical computer assisted by a small quantum processor can efficiently simulate a larger quantum system. First we consider sparse quantum circuits such that each qubit participates in O(1) two-qubit gates. It is shown that any sparse circuit on n+k qubits can be simulated by sparse circuits on n qubits and a classical processing that takes time $2^{O(k)} poly(n)$. Secondly, we study Pauli-based computation (PBC) where allowed operations are non-destructive eigenvalue measurements of n-qubit Pauli operators. The computation begins by initializing each qubit in the so-called magic state. This model is known to be equivalent to the universal quantum computer. We show that any PBC on n+k qubits can be simulated by PBCs on n qubits and a classical processing that takes time $2^{O(k)} poly(n)$. Finally, we propose a purely classical algorithm that can simulate a PBC on n qubits in a time $2^{c n} poly(n)$ where $c\approx 0.94$. This improves upon the brute-force simulation method which takes time $2^n poly(n)$. Our algorithm exploits the fact that n-fold tensor products of magic states admit a low-rank decomposition into n-qubit stabilizer states.

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

View Paper: https://www.semanticscholar.org/paper/07d34a3ea40b2322a05cebb085f3de4009b5daae

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

The future of quantum computing with superconducting qubits (2022, background): “The most well-known example is circuit cutting 12–15 .”
Simulation of quantum circuits by low-rank stabilizer decompositions (2018, methodology): “ into a superposition of stabilizer states. A reader interested only in the application for simulation of quantum circuits may wish to proceed to Sections2.2,2.3. Deﬁnition 1 (Exact stabilizer rank, χ[14]). Suppose ψis a pure n-qubit state. The exact stabilizer rank χ(ψ) is the smallest integer ksuc”
Quantum circuits and low-degree polynomials over F2 (2016, background): “It is known that the inner product between two arbitrary stabilizer states can be computed in time O ( n 3 ) [2, 20, 9], implying an O ( n 3 ) algorithm for computing gap( f ) for degree-2 polynomials f : { 0 , 1 } n → { 0 , 1 } .”