Clifford recompilation for faster classical simulation of quantum circuits

Hammam Qassim; Joel J. Wallman; Joseph Emerson

doi:10.22331/q-2019-08-05-170

Clifford recompilation for faster classical simulation of quantum circuits

Hammam Qassim^1,3, Joel J. Wallman^2,3, and Joseph Emerson^1,2,3

¹Department of Physics and Astronomy, University of Waterloo, Waterloo, Canada
²Department of Applied Mathematics, University of Waterloo, Waterloo, Canada
³Institute for Quantum Computing, Waterloo, Canada

Published:	2019-08-05, volume 3, page 170
Eprint:	arXiv:1902.02359v2
Doi:	https://doi.org/10.22331/q-2019-08-05-170
Citation:	Quantum 3, 170 (2019).

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

Abstract

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

@article{Qassim2019clifford,
  doi = {10.22331/q-2019-08-05-170},
  url = {https://doi.org/10.22331/q-2019-08-05-170},
  title = {Clifford recompilation for faster classical simulation of quantum circuits},
  author = {Qassim, Hammam and Wallman, Joel J. and Emerson, Joseph},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {3},
  pages = {170},
  month = aug,
  year = {2019}
}

► 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://arxiv.org/abs/1703.00111. 10.1103/PhysRevA.95.062337.
https://doi.org/10.1103/PhysRevA.95.062337
arXiv:1703.00111

[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://arxiv.org/abs/1712.05384.
arXiv: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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/1808.00128.
arXiv: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://arxiv.org/abs/1805.01450.
arXiv: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.
https://doi.org/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.
https://doi.org/10.1016/j.cpc.2018.11.005
arXiv:1805.04708

[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.
https://doi.org/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://arxiv.org/abs/1711.07848.
arXiv:1711.07848

[11] Aram W. Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203–209, sep 2017. 10.1038/nature23458.
https://doi.org/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://arxiv.org/abs/1807.10296. 10.22331/q-2019-04-08-132.
https://doi.org/10.22331/q-2019-04-08-132
arXiv:1807.10296

[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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/1808.02892. 10.22331/q-2019-03-05-128.
https://doi.org/10.22331/q-2019-03-05-128
arXiv:1808.02892

[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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/1601.07195.
arXiv: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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1137/s0097539700377025

Cited by

[1] Yun-Fei Niu, Shuo Zhang, and Wan-Su Bao, "Warm Starting Variational Quantum Algorithms with Near Clifford Circuits", Electronics 12 2, 347 (2023).

[2] Thien Nguyen, Lindsay Bassman Oftelie, Dmitry Lyakh, Phillip C. Lotshaw, Alexander McCaskey, Ryan S. Bennink, Vicente Leyton-Ortega, Raphael C. Pooser, Travis S. Humble, and Wibe A. de Jong, 2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS) 80 (2021) ISBN:978-1-7281-8674-0.

[3] Hakop Pashayan, Oliver Reardon-Smith, Kamil Korzekwa, and Stephen D. Bartlett, "Fast Estimation of Outcome Probabilities for Quantum Circuits", PRX Quantum 3 2, 020361 (2022).

[4] 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).

[5] Nikolaos Koukoulekidis, Hyukjoon Kwon, Hyejung H. Jee, David Jennings, and M. S. Kim, "Faster Born probability estimation via gate merging and frame optimisation", Quantum 6, 838 (2022).

[6] Gaurav Saxena and Gilad Gour, "Quantifying multiqubit magic channels with completely stabilizer-preserving operations", Physical Review A 106 4, 042422 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-30 15:33:07) and SAO/NASA ADS (last updated successfully 2023-09-30 15:33:08). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.