Clifford recompilation for faster classical simulation of quantum circuits

Hammam Qassim1,3, Joel J. Wallman2,3, and Joseph Emerson1,2,3

1Department of Physics and Astronomy, University of Waterloo, Waterloo, Canada
2Department of Applied Mathematics, University of Waterloo, Waterloo, Canada
3Institute for Quantum Computing, Waterloo, Canada

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Simulating quantum circuits classically is an important area of research in quantum information, with applications in computational complexity and validation of quantum devices. One of the state-of-the-art simulators, that of Bravyi et al, utilizes a randomized sparsification technique to approximate the output state of a quantum circuit by a stabilizer sum with a reduced number of terms. In this paper, we describe an improved Monte Carlo algorithm for performing randomized sparsification. This algorithm reduces the runtime of computing the approximate state by the factor $\ell/m$, where $\ell$ and $m$ are respectively the total and non-Clifford gate counts. The main technique is a circuit recompilation routine based on manipulating exponentiated Pauli operators. The recompilation routine also facilitates numerical search for Clifford decompositions of products of non-Clifford gates, which can further reduce the runtime in certain cases by reducing the 1-norm of the vector of expansion, ${\lVert a \rVert}_1$. It may additionally lead to a framework for optimizing circuit implementations over a gate-set, reducing the overhead for state-injection in fault-tolerant implementations. We provide a concise exposition of randomized sparsification, and describe how to use it to estimate circuit amplitudes in a way which can be generalized to a broader class of gates and states. This latter method can be used to obtain additive error estimates of circuit probabilities with a faster runtime than the full techniques of Bravyi et al. Such estimates are useful for validating near-term quantum devices provided that the target probability is not exponentially small.

► BibTeX data

► References

[1] Ryan S Bennink, Erik M Ferragut, Travis S Humble, Jason A Laska, James J Nutaro, Mark G Pleszkoch, and Raphael C Pooser. Monte carlo simulation of near-clifford quantum circuits. arXiv preprint, 2017. URL https:/​/​​abs/​1703.00111. 10.1103/​PhysRevA.95.062337.

[2] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, and Hartmut Neven. Simulation of low-depth quantum circuits as complex undirected graphical models. arXiv preprint arXiv:1712.05384, 2017. URL https:/​/​​abs/​1712.05384.

[3] Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by clifford gates. Phys. Rev. Lett., 116: 250501, Jun 2016. 10.1103/​PhysRevLett.116.250501.

[4] Sergey Bravyi, Graeme Smith, and John A Smolin. Trading classical and quantum computational resources. Physical Review X, 6 (2): 021043, 2016. 10.1103/​physrevx.6.021043.

[5] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. Simulation of quantum circuits by low-rank stabilizer decompositions. arXiv preprint, 2018. URL https:/​/​​abs/​1808.00128.

[6] Jianxin Chen, Fang Zhang, Mingcheng Chen, Cupjin Huang, Michael Newman, and Yaoyun Shi. Classical simulation of intermediate-size quantum circuits. arXiv preprint, 2018a. URL https:/​/​​abs/​1805.01450.

[7] Zhaoyun Chen, Qi Zhou, Cheng Xue, Xia Yang, Guangcan Guo, and Guoping Guo. 64-qubit quantum circuit simulation. Science Bulletin, 63 (15): 964–971, aug 2018b. 10.1016/​j.scib.2018.06.007.

[8] Hans De Raedt, Fengping Jin, Dennis Willsch, Madita Nocon, Naoki Yoshioka, Nobuyasu Ito, Shengjun Yuan, and Kristel Michielsen. Massively parallel quantum computer simulator, eleven years later. arXiv preprint arXiv:1805.04708, 2018. 10.1016/​j.cpc.2018.11.005.

[9] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86 (3), sep 2012. 10.1103/​physreva.86.032324.

[10] Héctor J García, Igor L Markov, and Andrew W Cross. On the geometry of stabilizer states. Quantum Information & Computation, 14 (7&8): 683–720, 2014. URL https:/​/​​abs/​1711.07848.

[11] Aram W. Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203–209, sep 2017. 10.1038/​nature23458.

[12] Markus Heinrich and David Gross. Robustness of magic and symmetries of the stabiliser polytope. arXiv preprint arXiv:1807.10296, 2018. URL https:/​/​​abs/​1807.10296. 10.22331/​q-2019-04-08-132.

[13] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58 (301): 13–30, 1963. 10.1007/​978-1-4612-0865-5_26.

[14] Mark Howard and Earl Campbell. Application of a resource theory for magic states to fault-tolerant quantum computing. Physical Review Letters, 118 (9): 090501, 2017. 10.1103/​physrevlett.118.090501.

[15] Daniel Litinski. A game of surface codes: Large-scale quantum computing with lattice surgery. arXiv preprint arXiv:1808.02892, 2018. URL https:/​/​​abs/​1808.02892. 10.22331/​q-2019-03-05-128.

[16] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, R. Barends, B. Burkett, Y. Chen, Z. Chen, A. Fowler, B. Foxen, M. Giustina, R. Graff, E. Jeffrey, T. Huang, J. Kelly, P. Klimov, E. Lucero, J. Mutus, M. Neeley, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, H. Neven, and J. M. Martinis. A blueprint for demonstrating quantum supremacy with superconducting qubits. Science, 360 (6385): 195–199, apr 2018. 10.1126/​science.aao4309.

[17] John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2: 79, aug 2018. 10.22331/​q-2018-08-06-79.

[18] Mikhail Smelyanskiy, Nicolas PD Sawaya, and Alán Aspuru-Guzik. qhipster: the quantum high performance software testing environment. arXiv preprint arXiv:1601.07195, 2016. URL https:/​/​​abs/​1601.07195.

[19] Dan Stahlke. Quantum interference as a resource for quantum speedup. Phys. Rev. A, 90: 022302, Aug 2014. 10.1103/​PhysRevA.90.022302.

[20] Barbara M. Terhal and David P. DiVincenzo. Classical simulation of noninteracting-fermion quantum circuits. Physical Review A, 65 (3), mar 2002. 10.1103/​physreva.65.032325.

[21] Leslie G Valiant. Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 31 (4): 1229–1254, 2002. 10.1137/​s0097539700377025.

Cited by

[1] James R. Seddon, Bartosz Regula, Hakop Pashayan, Yingkai Ouyang, and Earl T. Campbell, "Quantifying Quantum Speedups: Improved Classical Simulation From Tighter Magic Monotones", PRX Quantum 2 1, 010345 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2021-04-23 07:58:13). The list may be incomplete as not all publishers provide suitable and complete citation data.

On SAO/NASA ADS no data on citing works was found (last attempt 2021-04-23 07:58:13).