Handbook for Efficiently Quantifying Robustness of Magic

Hiroki Hamaguchi; Kou Hamada; Nobuyuki Yoshioka

doi:10.22331/q-2024-09-05-1461

Handbook for Efficiently Quantifying Robustness of Magic

Hiroki Hamaguchi¹, Kou Hamada¹, and Nobuyuki Yoshioka^2,3,4

¹Graduate School of Information Science and Technology, University of Tokyo, Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
²Department of Applied Physics, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
³Theoretical Quantum Physics Laboratory, RIKEN Cluster for Pioneering Research (CPR), Wako-shi, Saitama 351-0198, Japan
⁴JST, PRESTO, 4-1-8 Honcho, Kawaguchi, Saitama, 332-0012, Japan

Published:	2024-09-05, volume 8, page 1461
Eprint:	arXiv:2311.01362v4
Doi:	https://doi.org/10.22331/q-2024-09-05-1461
Citation:	Quantum 8, 1461 (2024).

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

Abstract

The nonstabilizerness, or magic, is an essential quantum resource to perform universal quantum computation. Robustness of magic (RoM) in particular characterizes the degree of usefulness of a given quantum state for non-Clifford operation. While the mathematical formalism of RoM can be given in a concise manner, it is extremely challenging to determine the RoM in practice, since it involves superexponentially many pure stabilizer states. In this work, we present efficient novel algorithms to compute the RoM. The crucial technique is a subroutine that achieves the remarkable features in calculation of overlaps between pure stabilizer states: (i) the time complexity per each stabilizer is reduced exponentially, (ii) the space complexity is reduced superexponentially. Based on this subroutine, we present algorithms to compute the RoM for arbitrary states up to $n=7$ qubits on a laptop, while brute-force methods require a memory size of 86 TiB. As a byproduct, the proposed subroutine allows us to simulate the stabilizer fidelity up to $n=8$ qubits, for which naive methods require memory size of 86 PiB so that any state-of-the-art classical computer cannot execute the computation. We further propose novel algorithms that utilize the preknowledge on the structure of target quantum state such as the permutation symmetry of disentanglement, and numerically demonstrate our state-of-the-art results for copies of magic states and partially disentangled quantum states. The series of algorithms constitute a comprehensive “handbook'' to scale up the computation of the RoM, and we envision that the proposed technique applies to the computation of other quantum resource measures as well.

Featured image: Sparsity of solution in the optimization problem that returns the value of robustness of magic.

Popular summary

The authors have proposed a numerical algorithm that significantly speed ups the evaluation of a quantity called Robustness of Magic (RoM), which characterizes the resource required for non-Clifford operation in fault-tolerant quantum computers. The key techniques rely on the structure of multiqubit stabilizer states and mathematical formulation as $L^p$-norm optimization problem. The work is expected to contribute to compress quantum circuits and realization of shorter depth quantum algorithms.

► BibTeX data

@article{Hamaguchi2024handbookefficiently,
  doi = {10.22331/q-2024-09-05-1461},
  url = {https://doi.org/10.22331/q-2024-09-05-1461},
  title = {Handbook for {E}fficiently {Q}uantifying {R}obustness of {M}agic},
  author = {Hamaguchi, Hiroki and Hamada, Kou and Yoshioka, Nobuyuki},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1461},
  month = sep,
  year = {2024}
}

► References

[1] Daniel Gottesman. ``The Heisenberg Representation of Quantum Computers'' (1998). arXiv:quant-ph/9807006.
arXiv:quant-ph/9807006

[2] Michael A. Nielsen and Isaac L. Chuang. ``Quantum Computation and Quantum Information: 10th Anniversary Edition''. Cambridge University Press. (2010).
https://doi.org/10.1017/CBO9780511976667

[3] Sergei Bravyi and Alexei Kitaev. ``Universal Quantum Computation with ideal Clifford gates and noisy ancillas''. Physical Review A 71, 022316 (2005).
https://doi.org/10.1103/PhysRevA.71.022316

[4] Daniel Litinski. ``A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery''. Quantum 3, 128 (2019).
https://doi.org/10.22331/q-2019-03-05-128

[5] Dominic Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. ``Surface code quantum computing by lattice surgery''. New Journal of Physics 14, 123011 (2012).
https://doi.org/10.1088/1367-2630/14/12/123011

[6] Austin G. Fowler and Craig Gidney. ``Low overhead quantum computation using lattice surgery'' (2019). arXiv:1808.06709.
arXiv:1808.06709

[7] Victor Veitch, Christopher Ferrie, David Gross, and Joseph Emerson. ``Negative quasi-probability as a resource for quantum computation''. New Journal of Physics 14, 113011 (2012).
https://doi.org/10.1088/1367-2630/14/11/113011

[8] Craig Gidney and Martin Ekerå. ``How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits''. Quantum 5, 433 (2021).
https://doi.org/10.22331/q-2021-04-15-433

[9] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush. ``Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction''. PRX Quantum 2, 030305 (2021).
https://doi.org/10.1103/PRXQuantum.2.030305

[10] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer. ``Quantum computing enhanced computational catalysis''. Physical Review Research 3, 033055 (2021).
https://doi.org/10.1103/PhysRevResearch.3.033055

[11] Nobuyuki Yoshioka, Tsuyoshi Okubo, Yasunari Suzuki, Yuki Koizumi, and Wataru Mizukami. ``Hunting for quantum-classical crossover in condensed matter problems''. npj Quantum Information 10, 45 (2024).
https://doi.org/10.1038/s41534-024-00839-4

[12] Sergey Bravyi, Graeme Smith, and John Smolin. ``Trading classical and quantum computational resources''. Physical Review X 6, 021043 (2016).
https://doi.org/10.1103/PhysRevX.6.021043

[13] Emanuele Tirrito, Poetri Sonya Tarabunga, Gugliemo Lami, Titas Chanda, Lorenzo Leone, Salvatore F. E. Oliviero, Marcello Dalmonte, Mario Collura, and Alioscia Hamma. ``Quantifying nonstabilizerness through entanglement spectrum flatness''. Physical Review A: Atomic, Molecular, and Optical Physics 109, L040401 (2024).
https://doi.org/10.1103/PhysRevA.109.L040401

[14] Oliver Hahn, Alessandro Ferraro, Lina Hultquist, Giulia Ferrini, and Laura García-Álvarez. ``Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding''. Physical Review Letters 128, 210502 (2022).
https://doi.org/10.1103/PhysRevLett.128.210502

[15] Tobias Haug, Soovin Lee, and M. S. Kim. ``Efficient quantum algorithms for stabilizer entropies''. Phys. Rev. Lett. 132, 240602 (2024).
https://doi.org/10.1103/PhysRevLett.132.240602

[16] 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, 010345 (2021).
https://doi.org/10.1103/PRXQuantum.2.010345

[17] Zi-Wen Liu and Andreas Winter. ``Many-body quantum magic''. PRX Quantum 3, 020333 (2022).
https://doi.org/10.1103/PRXQuantum.3.020333

[18] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Stabilizer Rényi Entropy''. Physical Review Letters 128, 050402 (2022).
https://doi.org/10.1103/PhysRevLett.128.050402

[19] Mark Howard and Earl T. Campbell. ``Application of a resource theory for magic states to fault-tolerant quantum computing''. Physical Review Letters 118, 090501 (2017).
https://doi.org/10.1103/PhysRevLett.118.090501

[20] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. ``Estimating outcome probabilities of quantum circuits using quasiprobabilities''. Physical Review Letters 115, 070501 (2015).
https://doi.org/10.1103/PhysRevLett.115.070501

[21] Markus Heinrich and David Gross. ``Robustness of Magic and Symmetries of the Stabiliser Polytope''. Quantum 3, 132 (2019).
https://doi.org/10.22331/q-2019-04-08-132

[22] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. ``Simulation of quantum circuits by low-rank stabilizer decompositions''. Quantum 3, 181 (2019).
https://doi.org/10.22331/q-2019-09-02-181

[23] Scott Aaronson and Daniel Gottesman. ``Improved Simulation of Stabilizer Circuits''. Physical Review A 70, 052328 (2004).
https://doi.org/10.1103/PhysRevA.70.052328

[24] Héctor J. García, Igor L. Markov, and Andrew W. Cross. ``On the geometry of stabilizer states''. Quantum Info. Comput. 14, 683–720 (2014).
https://doi.org/10.48550/arXiv.1711.07848

[25] James Seddon and Earl Campbell. ``Quantifying magic for multi-qubit operations''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475, 20190251 (2019).
https://doi.org/10.1098/rspa.2019.0251

[26] Gurobi Optimization, LLC. ``Gurobi Optimizer Reference Manual'' (2023).

[27] Steven Diamond and Stephen Boyd. ``CVXPY: A python-embedded modeling language for convex optimization''. Journal of Machine Learning Research 17, 2909–2913 (2016).
https://doi.org/10.5555/2946645.3007036

[28] Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. ``A rewriting system for convex optimization problems''. Journal of Control and Decision 5, 42–60 (2018).
https://doi.org/10.1080/23307706.2017.1397554

[29] Fino and Algazi. ``Unified Matrix Treatment of the Fast Walsh-Hadamard Transform''. IEEE Transactions on Computers C-25, 1142–1146 (1976).
https://doi.org/10.1109/TC.1976.1674569

[30] Victor Kac and Pokman Cheung. ``Quantum Calculus''. Universitext. Springer. (2002).
https://doi.org/10.1007/978-1-4613-0071-7

[31] G.I. Struchalin, Ya. A. Zagorovskii, E.V. Kovlakov, S.S. Straupe, and S.P. Kulik. ``Experimental Estimation of Quantum State Properties from Classical Shadows''. PRX Quantum 2, 010307 (2021).
https://doi.org/10.1103/PRXQuantum.2.010307

[32] Hiroki Hamaguchi, Kou Hamada, and Nobuyuki Yoshioka. ``RoM-handbook''. GitHub Repository (2024).
https://github.com/quantum-programming/RoM-handbook

[33] Gilbert Strang. ``Linear algebra and learning from data''. Wellesley-Cambridge Press. (2019).
https://doi.org/10.1137/1.9780692196380

[34] Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon Solomon, editors. ``Column Generation''. Springer US. (2005).
https://doi.org/10.1007/b135457

[35] SciPy. ``scipy.sparse.csc_matrix''. SciPy.
https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csc_matrix.html

[36] William K Wootters and Brian D Fields. ``Optimal state-determination by mutually unbiased measurements''. Annals of Physics 191, 363–381 (1989).
https://doi.org/10.1016/0003-4916(89)90322-9

[37] Kathleen S. Gibbons, Matthew J. Hoffman, and William K. Wootters. ``Discrete phase space based on finite fields''. Physical Review A: Atomic, Molecular, and Optical Physics 70, 062101 (2004).
https://doi.org/10.1103/PhysRevA.70.062101

[38] Danielsen Lars Eirik. ``Database of self-dual quantum codes''. larsed/vncorbits/link.
http://www.ii.uib.no/textasciitilde

[39] Hiroki Hamaguchi, Kou Hamada, Naoki Marumo, and Nobuyuki Yoshioka. ``Faster computation of stabilizer extent'' (2024). arXiv:2406.16673.
arXiv:2406.16673

[40] Beatriz Dias and Robert Koenig. ``Classical simulation of non-Gaussian fermionic circuits''. Quantum 8, 1350 (2024).
https://doi.org/10.22331/q-2024-05-21-1350

[41] Oliver Reardon-Smith, Michał Oszmaniec, and Kamil Korzekwa. ``Improved simulation of quantum circuits dominated by free fermionic operations'' (2024). arXiv:2307.12702.
arXiv:2307.12702

[42] Joshua Cudby and Sergii Strelchuk. ``Gaussian decomposition of magic states for matchgate computations'' (2023). arXiv:2307.12654.
arXiv:2307.12654

[43] Lukas Hantzko, Lennart Binkowski, and Sabhyata Gupta. ``Tensorized pauli decomposition algorithm''. Physica Scripta 99, 085128 (2024).
https://doi.org/10.1088/1402-4896/ad6499

[44] Tyson Jones. ``Densepaulidecomposer''. GitHub Repository (2024).
https://github.com/TysonRayJones/DensePauliDecomposer

[45] Tyson Jones. ``Decomposing dense matrices into dense Pauli tensors'' (2024). arXiv:2401.16378.
arXiv:2401.16378

[46] Sebastián Vidal Romero and Juan Santos-Suárez. ``PauliComposer: Compute tensor products of Pauli matrices efficiently''. Quantum Information Processing 22, 449 (2023).
https://doi.org/10.1007/s11128-023-04204-w

[47] Hiroki Hamaguchi, Kou Hamada, and Nobuyuki Yoshioka. ``paulidecomp''. GitHub Repository (2024).
https://github.com/quantum-programming/paulidecomp

[48] Arno Jaeger and Bertram Mond. ``On direct sums and tensor products of linear programs''. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 3, 19–31 (1964).
https://doi.org/10.1007/BF00531681

Cited by

[1] Poetri Sonya Tarabunga, Emanuele Tirrito, Mari Carmen Bañuls, and Marcello Dalmonte, "Nonstabilizerness via Matrix Product States in the Pauli Basis", Physical Review Letters 133 1, 010601 (2024).

[2] Poetri Sonya Tarabunga and Claudio Castelnovo, "Magic in generalized Rokhsar-Kivelson wavefunctions", Quantum 8, 1347 (2024).

[3] Roy J. Garcia, Gaurav Bhole, Kaifeng Bu, Liyuan Chen, Haribabu Arthanari, and Arthur Jaffe, "On the Hardness of Measuring Magic", arXiv:2408.01663, (2024).

[4] Lukas Hantzko, Lennart Binkowski, and Sabhyata Gupta, "Tensorized Pauli decomposition algorithm", Physica Scripta 99 8, 085128 (2024).

[5] Arash Ahmadi, Jonas Helsen, Cagan Karaca, and Eliska Greplova, "Mutual information fluctuations and non-stabilizerness in random circuits", arXiv:2408.03831, (2024).

[6] Hiroki Hamaguchi, Kou Hamada, Naoki Marumo, and Nobuyuki Yoshioka, "Faster Computation of Stabilizer Extent", arXiv:2406.16673, (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2024-09-09 08:09:32). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2024-09-09 08:05:27).

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.