Faster Born probability estimation via gate merging and frame optimisation
1Department of Physics, Imperial College London, London SW7 2AZ, UK
2Korea Institute for Advanced Study, Seoul, 02455, Korea
3Department of Computing, Imperial College London, London SW7 2AZ, UK
4School 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.
![](https://quantum-journal.org/wp-content/uploads/2022/10/sketch_of_routine-1.png)
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
► BibTeX data
► 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] Xhek Turkeshi, Marco Schirò, and Piotr Sierant, "Measuring nonstabilizerness via multifractal flatness", Physical Review A 108 4, 042408 (2023).
[3] Denis A. Kulikov, Vsevolod I. Yashin, Aleksey K. Fedorov, and Evgeniy O. Kiktenko, "Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations", Physical Review A 109 1, 012219 (2024).
[4] 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 2024-09-01 06:13:31) and SAO/NASA ADS (last updated successfully 2024-09-01 06:13:32). 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.