2015/06/03 by Sergey Bravyi, Graeme Smith, John A. Smolin +1 · 8 citations
Computer Science · Physics and Astronomy · #Computation #Electronic circuit #MAGIC (telescope) #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum circuit #Quantum computer #Quantum many-body systems #Qubit #quant-ph
paper · pdf · doi:10.1103/physrevx.6.021043
published as Phys. Rev. X 6, 021043 (2016) · 14 pages, 4 figures
arxiv created 2015/06/03 · openalex created_date 2016/06/24 · openalex publication_date 2016/06/29 · arxiv updated 2016/07/06 · openalex updated_date 2026/08/06
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 O1 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 Ok polyn. Second, we study Pauli-based computation (PBC), where allowed operations are nondestructive 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 Ok polyn. Finally, we propose a purely classical algorithm that can simulate a PBC on n qubits in a time 2 n polyn, where 0.94. This improves upon the brute-force simulation method, which takes time 2 n polyn. Our algorithm exploits the fact that n-fold tensor products of magic states admit a low-rank decomposition into n-qubit stabilizer states.