Faster Born probability estimation via gate merging and frame optimisation

Nikolaos Koukoulekidis; Hyukjoon Kwon; Hyejung H. Jee; David Jennings; M. S. Kim

doi:10.22331/q-2022-10-13-838

Faster Born probability estimation via gate merging and frame optimisation

Nikolaos Koukoulekidis¹, Hyukjoon Kwon^1,2, Hyejung H. Jee³, David Jennings^1,4, and M. S. Kim¹

¹Department of Physics, Imperial College London, London SW7 2AZ, UK
²Korea Institute for Advanced Study, Seoul, 02455, Korea
³Department of Computing, Imperial College London, London SW7 2AZ, UK
⁴School of Physics and Astronomy, University of Leeds, Leeds, LS2 9JT, UK

Published:	2022-10-13, volume 6, page 838
Eprint:	arXiv:2202.12114v2
Doi:	https://doi.org/10.22331/q-2022-10-13-838
Citation:	Quantum 6, 838 (2022).

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

Abstract

Outcome probability estimation via classical methods is an important task for validating quantum computing devices. Outcome probabilities of any quantum circuit can be estimated using Monte Carlo sampling, where the amount of negativity present in the circuit frame representation quantifies the overhead on the number of samples required to achieve a certain precision. In this paper, we propose two classical sub-routines: circuit gate merging and frame optimisation, which optimise the circuit representation to reduce the sampling overhead. We show that the runtimes of both sub-routines scale polynomially in circuit size and gate depth. Our methods are applicable to general circuits, regardless of generating gate sets, qudit dimensions and the chosen frame representations for the circuit components. We numerically demonstrate that our methods provide improved scaling in the negativity overhead for all tested cases of random circuits with Clifford+$T$ and Haar-random gates, and that the performance of our methods compares favourably with prior quasi-probability simulators as the number of non-Clifford gates increases.

Featured image: Sketch of our routine on a toy circuit. The first step (a) $\rightarrow$ (b) is gate merging, here implemented with $n = 2$. Gates that share input and output wires merge in the schematic way depicted in the figure. The second step (b) $\rightarrow$ (c) is frame optimisation, here implemented with $\ell= 2$ in a block $B$ comprising the three merged gates. The optimisation results into updated frames $G_4, G_7$, while the remaining frames that connect the block $B$ to the rest of the circuit components are left unchanged at this optimisation cycle.

Popular summary

Quantum computers are expected to provide significant speed-ups compared to classical computing for certain tasks. Determining the set of computational tasks that can be accelerated by the use of quantum computers is a notoriously hard question. A natural approach towards carving out this set consists of studying how well classical computers can simulate these tasks. A large family of such classical simulators relies on representing the tasks as stochastic processes that propagate an input state probabilistically. Quantum tasks contain negative probabilities that in principle require exponential runtimes to simulate classically. In this work, we introduce an efficient optimisation to the classical simulation strategy which works by minimising the negative probabilities that arise during the process. Our results are of practical significance as they provide a faster way to simulate quantum computers, while on a fundamental level, they probe the extent to which negative probabilities are an indicator of non-classical physics.

► BibTeX data

@article{Koukoulekidis2022fasterborn,
  doi = {10.22331/q-2022-10-13-838},
  url = {https://doi.org/10.22331/q-2022-10-13-838},
  title = {Faster {B}orn probability estimation via gate merging and frame optimisation},
  author = {Koukoulekidis, Nikolaos and Kwon, Hyukjoon and Jee, Hyejung H. and Jennings, David and Kim, M. S.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {838},
  month = oct,
  year = {2022}
}

► References

[1] R. P. Feynman, International Journal of Theoretical Physics 21, 467 (1982).
https://doi.org/10.1007/BF02650179

[2] J. Preskill, ``Quantum computing 40 years later,'' (2021), arXiv:2106.10522.
arXiv:2106.10522

[3] R. Jozsa and M. V. den Nest, Quantum Inf. Comput. 14, 633 (2014).

[4] D. E. Koh, Quantum Info. Comput. 17, 262–282 (2017).

[5] S. Aaronson, A. Bouland, G. Kuperberg, and S. Mehraban (Association for Computing Machinery, New York, NY, USA, 2017) p. 317–327.

[6] M. Hebenstreit, R. Jozsa, B. Kraus, and S. Strelchuk, Phys. Rev. A 102, 052604 (2020).
https://doi.org/10.1103/PhysRevA.102.052604

[7] M. Yoganathan, R. Jozsa, and S. Strelchuk, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475, 20180427 (2019).
https://doi.org/10.1098/rspa.2018.0427

[8] S. Aaronson and A. Arkhipov, ``The computational complexity of linear optics,'' (2010), arXiv:1011.3245.
arXiv:1011.3245

[9] M. J. Bremner, R. Jozsa, and D. J. Shepherd, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 459 (2011).
https://doi.org/10.1098/rspa.2010.0301

[10] T. Morimae, K. Fujii, and J. F. Fitzsimons, Phys. Rev. Lett. 112, 130502 (2014).
https://doi.org/10.1103/PhysRevLett.112.130502

[11] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Phys. Rev. Lett. 117, 080501 (2016).
https://doi.org/10.1103/PhysRevLett.117.080501

[12] X. Gao, S.-T. Wang, and L.-M. Duan, Phys. Rev. Lett. 118, 040502 (2017).
https://doi.org/10.1103/PhysRevLett.118.040502

[13] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, Phys. Rev. X 8, 021010 (2018).
https://doi.org/10.1103/PhysRevX.8.021010

[14] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Phys. Rev. Lett. 120, 200502 (2018).
https://doi.org/10.1103/PhysRevLett.120.200502

[15] A. Bouland, J. F. Fitzsimons, and D. E. Koh (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU, 2018).

[16] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nature Physics 14, 595 (2018).
https://doi.org/10.1038/s41567-018-0124-x

[17] H. Pashayan, S. D. Bartlett, and D. Gross, Quantum 4, 223 (2020).
https://doi.org/10.22331/q-2020-01-13-223

[18] L. G. Valiant, SIAM Journal on Computing 31, 1229 (2002).
https://doi.org/10.1137/S0097539700377025

[19] B. M. Terhal and D. P. DiVincenzo, Phys. Rev. A 65, 032325 (2002).
https://doi.org/10.1103/PhysRevA.65.032325

[20] S. D. Bartlett, B. C. Sanders, S. L. Braunstein, and K. Nemoto, Phys. Rev. Lett. 88, 097904 (2002).
https://doi.org/10.1103/PhysRevLett.88.097904

[21] S. Aaronson and D. Gottesman, Phys. Rev. A 70, 052328 (2004).
https://doi.org/10.1103/PhysRevA.70.052328

[22] D. Gross, S. T. Flammia, and J. Eisert, Phys. Rev. Lett. 102, 190501 (2009).
https://doi.org/10.1103/PhysRevLett.102.190501

[23] D. J. Brod, Phys. Rev. A 93, 062332 (2016).
https://doi.org/10.1103/PhysRevA.93.062332

[24] T. Haug and M. S. Kim, ``Scalable measures of magic for quantum computers,'' (2022).
https://doi.org/10.48550/ARXIV.2204.10061

[25] H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, and et al., Science 370, 1460–1463 (2020).
https://doi.org/10.1126/science.abe8770

[26] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, Nature 574, 505 (2019).
https://doi.org/10.1038/s41586-019-1666-5

[27] H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, and et al., Nature 551, 579–584 (2017).
https://doi.org/10.1038/nature24622

[28] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, and et al., Science 360, 195–199 (2018).
https://doi.org/10.1126/science.aao4309

[29] J. P. Bonilla Ataides, D. K. Tuckett, S. D. Bartlett, S. T. Flammia, and B. J. Brown, Nature Communications 12, 2172 (2021).
https://doi.org/10.1038/s41467-021-22274-1

[30] S. Bravyi, S. Sheldon, A. Kandala, D. C. Mckay, and J. M. Gambetta, Phys. Rev. A 103, 042605 (2021).
https://doi.org/10.1103/PhysRevA.103.042605

[31] A. Kandala, K. Temme, A. D. Córcoles, A. Mezzacapo, J. M. Chow, and J. M. Gambetta, Nature 567, 491 (2019).
https://doi.org/10.1038/s41586-019-1040-7

[32] S. Endo, S. C. Benjamin, and Y. Li, Phys. Rev. X 8, 031027 (2018).
https://doi.org/10.1103/PhysRevX.8.031027

[33] K. Temme, S. Bravyi, and J. M. Gambetta, Phys. Rev. Lett. 119, 180509 (2017).
https://doi.org/10.1103/PhysRevLett.119.180509

[34] J. Preskill, Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[35] A. W. Harrow and A. Montanaro, Nature 549, 203 (2017).
https://doi.org/10.1038/nature23458

[36] R. S. Bennink, E. M. Ferragut, T. S. Humble, J. A. Laska, J. J. Nutaro, M. G. Pleszkoch, and R. C. Pooser, Phys. Rev. A 95, 062337 (2017).
https://doi.org/10.1103/PhysRevA.95.062337

[37] V. Veitch, C. Ferrie, D. Gross, and J. Emerson, New Journal of Physics 14, 113011 (2012).
https://doi.org/10.1088/1367-2630/14/11/113011

[38] D. Gottesman, in Encyclopedia of Mathematical Physics, edited by J.-P. Françoise, G. L. Naber, and T. S. Tsun (Academic Press, Oxford, 2006) pp. 196 – 201.
https://doi.org/10.1016/B0-12-512666-2/00273-X

[39] H. Pashayan, O. Reardon-Smith, K. Korzekwa, and S. D. Bartlett, ``Fast estimation of outcome probabilities for quantum circuits,'' (2021), arXiv:2101.12223.
https://doi.org/10.1103/PRXQuantum.3.020361
arXiv:2101.12223

[40] J. R. Seddon, B. Regula, H. Pashayan, Y. Ouyang, and E. T. Campbell, PRX Quantum 2, 010345 (2021).
https://doi.org/10.1103/PRXQuantum.2.010345

[41] S. Bravyi and D. Gosset, Phys. Rev. Lett. 116, 250501 (2016).
https://doi.org/10.1103/PhysRevLett.116.250501

[42] S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, Quantum 3, 181 (2019).
https://doi.org/10.22331/q-2019-09-02-181

[43] S. Bravyi, G. Smith, and J. A. Smolin, Phys. Rev. X 6, 021043 (2016).
https://doi.org/10.1103/PhysRevX.6.021043

[44] H. Qassim, J. J. Wallman, and J. Emerson, Quantum 3, 170 (2019).
https://doi.org/10.22331/q-2019-08-05-170

[45] Y. Huang and P. Love, Phys. Rev. A 99, 052307 (2019).
https://doi.org/10.1103/PhysRevA.99.052307

[46] L. Kocia and M. Sarovar, Phys. Rev. A 103, 022603 (2021).
https://doi.org/10.1103/PhysRevA.103.022603

[47] A. Kissinger, J. van de Wetering, and R. Vilmart, ``Classical simulation of quantum circuits with partial and graphical stabiliser decompositions,'' (2022), arXiv:2202.09202.
https://doi.org/10.4230/LIPIcs.TQC.2022.5
arXiv:2202.09202

[48] H. Qassim, H. Pashayan, and D. Gosset, Quantum 5, 606 (2021).
https://doi.org/10.22331/q-2021-12-20-606

[49] H. Pashayan, J. J. Wallman, and S. D. Bartlett, Phys. Rev. Lett. 115, 070501 (2015).
https://doi.org/10.1103/PhysRevLett.115.070501

[50] D. Stahlke, Phys. Rev. A 90, 022302 (2014).
https://doi.org/10.1103/PhysRevA.90.022302

[51] P. Rall, D. Liang, J. Cook, and W. Kretschmer, Phys. Rev. A 99, 062337 (2019).
https://doi.org/10.1103/PhysRevA.99.062337

[52] J. R. Seddon and E. T. Campbell, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475, 20190251 (2019).
https://doi.org/10.1098/rspa.2019.0251

[53] C. Ferrie and J. Emerson, Journal of Physics A: Mathematical and Theoretical 41, 352001 (2008).
https://doi.org/10.1088/1751-8113/41/35/352001

[54] C. Ferrie and J. Emerson, New Journal of Physics 11, 063040 (2009).
https://doi.org/10.1088/1367-2630/11/6/063040

[55] D. Gross, Journal of Mathematical Physics 47, 122107 (2006).
https://doi.org/10.1063/1.2393152

[56] M. Ruzzi, M. A. Marchiolli, and D. Galetti, Journal of Physics A: Mathematical and General 38, 6239 (2005).
https://doi.org/10.1088/0305-4470/38/27/010

[57] M. A. Marchiolli, M. Ruzzi, and D. Galetti, Phys. Rev. A 72, 042308 (2005).
https://doi.org/10.1103/PhysRevA.72.042308

[58] D. S. França, S. Strelchuk, and M. Studziński, Phys. Rev. Lett. 126, 210502 (2021).
https://doi.org/10.1103/PhysRevLett.126.210502

[59] M. Howard and E. Campbell, Phys. Rev. Lett. 118, 090501 (2017).
https://doi.org/10.1103/PhysRevLett.118.090501

[60] M. Heinrich and D. Gross, Quantum 3, 132 (2019).
https://doi.org/10.22331/q-2019-04-08-132

[61] S. Rahimi-Keshari, T. C. Ralph, and C. M. Caves, Phys. Rev. X 6, 021039 (2016).
https://doi.org/10.1103/PhysRevX.6.021039

[62] A. Mari and J. Eisert, Phys. Rev. Lett. 109, 230503 (2012).
https://doi.org/10.1103/PhysRevLett.109.230503

[63] R. Raussendorf, D. E. Browne, N. Delfosse, C. Okay, and J. Bermejo-Vega, Physical Review A 95, 052334 (2017).
https://doi.org/10.1103/PhysRevA.95.052334

[64] C. Jones, Phys. Rev. A 87, 022328 (2013).
https://doi.org/10.1103/PhysRevA.87.022328

[65] D. J. Wales and J. P. K. Doye, The Journal of Physical Chemistry A 101, 5111–5116 (1997).
https://doi.org/10.1021/jp970984n

[66] M. S. A. et al., ``Qiskit: An open-source framework for quantum computing,'' (2021).
https://doi.org/10.5281/zenodo.2573505

[67] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Nature Reviews Physics 3, 625 (2021).
https://doi.org/10.1038/s42254-021-00348-9

Cited by

[1] Tobias Haug and Lorenzo Piroli, "Quantifying nonstabilizerness of matrix product states", Physical Review B 107 3, 035148 (2023).

[2] Tobias Haug and M. S. Kim, "Scalable Measures of Magic Resource for Quantum Computers", PRX Quantum 4 1, 010301 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-09 10:42:12) and SAO/NASA ADS (last updated successfully 2023-06-09 10:42:13). 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.