{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T20:15:24Z","timestamp":1775852124027,"version":"3.50.1"},"reference-count":48,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:00:00Z","timestamp":1725494400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"JST PRESTO","award":["JPMJPR2119"],"award-info":[{"award-number":["JPMJPR2119"]}]},{"name":"JST COI-NEXT","award":["JPMJPF2221"],"award-info":[{"award-number":["JPMJPF2221"]}]},{"name":"JST ERATO","award":["JPMJER2302"],"award-info":[{"award-number":["JPMJER2302"]}]},{"name":"JST CREST","award":["JPMJCR23I4"],"award-info":[{"award-number":["JPMJCR23I4"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Nonstabilizerness, or magic, is an essential quantum resource for performing universal quantum computation. Specifically, Robustness of Magic (RoM) characterizes the usefulness of a given quantum state for non-Clifford operations. While the mathematical formalism of RoM is concise, determining RoM in practice is highly challenging due to the necessity of dealing with a super-exponential number of stabilizer states. In this work, we present novel algorithms to compute RoM. The key technique is a subroutine for calculating overlaps between all stabilizer states and a target state, with the following remarkable features: (i) the time complexity per state is reduced {exponentially}, and (ii) the total space complexity is reduced {super-exponentially}. Based on this subroutine, we present algorithms to compute RoM for arbitrary states up to n<\/mml:mi>=<\/mml:mo>8<\/mml:mn><\/mml:math> qubits, whereas the naive method requires a memory size of at least 86 PiB<\/mml:mtext><\/mml:mrow><\/mml:math>, which is infeasible for any current classical computer. Additionally, the proposed subroutine enables the computation of stabilizer fidelity for a mixed state up to n<\/mml:mi>=<\/mml:mo>8<\/mml:mn><\/mml:math> qubits. We further propose novel algorithms that exploit prior knowledge of the structure of the target quantum state, such as permutation symmetry or disentanglement, and numerically demonstrate our results for copies of magic states and partially disentangled quantum states. This series of algorithms constitutes a comprehensive ``handbook'' for scaling up the computation of RoM. We envision that the proposed technique will also apply to the computation of other quantum resource measures.<\/jats:p>","DOI":"10.22331\/q-2024-09-05-1461","type":"journal-article","created":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T08:01:28Z","timestamp":1725523288000},"page":"1461","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":11,"title":["Handbook for Quantifying Robustness of Magic"],"prefix":"10.22331","volume":"8","author":[{"given":"Hiroki","family":"Hamaguchi","sequence":"first","affiliation":[{"name":"Graduate School of Information Science and Technology, University of Tokyo, Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan"}]},{"given":"Kou","family":"Hamada","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technology, University of Tokyo, Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan"}]},{"given":"Nobuyuki","family":"Yoshioka","sequence":"additional","affiliation":[{"name":"Department of Applied Physics, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan"},{"name":"Theoretical Quantum Physics Laboratory, RIKEN Cluster for Pioneering Research (CPR), Wako-shi, Saitama 351-0198, Japan"},{"name":"JST, PRESTO, 4-1-8 Honcho, Kawaguchi, Saitama, 332-0012, Japan"}]}],"member":"9598","published-online":{"date-parts":[[2024,9,5]]},"reference":[{"key":"0","unstructured":"Daniel Gottesman. ``The Heisenberg Representation of Quantum Computers'' (1998). arXiv:quant-ph\/9807006."},{"key":"1","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsen and Isaac L. Chuang. ``Quantum Computation and Quantum Information: 10th Anniversary Edition''. Cambridge University Press. (2010).","DOI":"10.1017\/CBO9780511976667"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Sergei Bravyi and Alexei Kitaev. ``Universal Quantum Computation with ideal Clifford gates and noisy ancillas''. Physical Review A 71, 022316 (2005).","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Daniel Litinski. ``A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery''. Quantum 3, 128 (2019).","DOI":"10.22331\/q-2019-03-05-128"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"5","unstructured":"Austin G. Fowler and Craig Gidney. ``Low overhead quantum computation using lattice surgery'' (2019). arXiv:1808.06709."},{"key":"6","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088\/1367-2630\/14\/11\/113011"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Craig Gidney and Martin Eker\u00e5. ``How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits''. Quantum 5, 433 (2021).","DOI":"10.22331\/q-2021-04-15-433"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.2.030305"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Vera von Burg, Guang Hao Low, Thomas H\u00e4ner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer. ``Quantum computing enhanced computational catalysis''. Physical Review Research 3, 033055 (2021).","DOI":"10.1103\/PhysRevResearch.3.033055"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/s41534-024-00839-4"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Graeme Smith, and John Smolin. ``Trading classical and quantum computational resources''. Physical Review X 6, 021043 (2016).","DOI":"10.1103\/PhysRevX.6.021043"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.109.L040401"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Oliver Hahn, Alessandro Ferraro, Lina Hultquist, Giulia Ferrini, and Laura Garc\u00eda-\u00c1lvarez. ``Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding''. Physical Review Letters 128, 210502 (2022).","DOI":"10.1103\/PhysRevLett.128.210502"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Tobias Haug, Soovin Lee, and M. S. Kim. ``Efficient quantum algorithms for stabilizer entropies''. Phys. Rev. Lett. 132, 240602 (2024).","DOI":"10.1103\/PhysRevLett.132.240602"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.2.010345"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Zi-Wen Liu and Andreas Winter. ``Many-body quantum magic''. PRX Quantum 3, 020333 (2022).","DOI":"10.1103\/PRXQuantum.3.020333"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Stabilizer R\u00e9nyi Entropy''. Physical Review Letters 128, 050402 (2022).","DOI":"10.1103\/PhysRevLett.128.050402"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.118.090501"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. ``Estimating outcome probabilities of quantum circuits using quasiprobabilities''. Physical Review Letters 115, 070501 (2015).","DOI":"10.1103\/PhysRevLett.115.070501"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Markus Heinrich and David Gross. ``Robustness of Magic and Symmetries of the Stabiliser Polytope''. Quantum 3, 132 (2019).","DOI":"10.22331\/q-2019-04-08-132"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.22331\/q-2019-09-02-181"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Daniel Gottesman. ``Improved Simulation of Stabilizer Circuits''. Physical Review A 70, 052328 (2004).","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"23","doi-asserted-by":"publisher","unstructured":"H\u00e9ctor J. Garc\u00eda, Igor L. Markov, and Andrew W. Cross. ``On the geometry of stabilizer states''. Quantum Info. Comput. 14, 683\u2013720 (2014).","DOI":"10.48550\/arXiv.1711.07848"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1098\/rspa.2019.0251"},{"key":"25","unstructured":"Gurobi Optimization, LLC. ``Gurobi Optimizer Reference Manual'' (2023)."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Steven Diamond and Stephen Boyd. ``CVXPY: A python-embedded modeling language for convex optimization''. Journal of Machine Learning Research 17, 2909\u20132913 (2016).","DOI":"10.5555\/2946645.3007036"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. ``A rewriting system for convex optimization problems''. Journal of Control and Decision 5, 42\u201360 (2018).","DOI":"10.1080\/23307706.2017.1397554"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Fino and Algazi. ``Unified Matrix Treatment of the Fast Walsh-Hadamard Transform''. IEEE Transactions on Computers C-25, 1142\u20131146 (1976).","DOI":"10.1109\/TC.1976.1674569"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Victor Kac and Pokman Cheung. ``Quantum Calculus''. Universitext. Springer. (2002).","DOI":"10.1007\/978-1-4613-0071-7"},{"key":"30","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.2.010307"},{"key":"31","unstructured":"Hiroki Hamaguchi, Kou Hamada, and Nobuyuki Yoshioka. ``RoM-handbook''. GitHub Repository (2024)."},{"key":"32","doi-asserted-by":"publisher","unstructured":"Gilbert Strang. ``Linear algebra and learning from data''. Wellesley-Cambridge Press. (2019).","DOI":"10.1137\/1.9780692196380"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon Solomon, editors. ``Column Generation''. Springer US. (2005).","DOI":"10.1007\/b135457"},{"key":"34","unstructured":"SciPy. ``scipy.sparse.csc_matrix''. SciPy."},{"key":"35","doi-asserted-by":"publisher","unstructured":"William K Wootters and Brian D Fields. ``Optimal state-determination by mutually unbiased measurements''. Annals of Physics 191, 363\u2013381 (1989).","DOI":"10.1016\/0003-4916(89)90322-9"},{"key":"36","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.70.062101"},{"key":"37","unstructured":"Danielsen Lars Eirik. ``Database of self-dual quantum codes''. larsed\/vncorbits\/link."},{"key":"38","unstructured":"Hiroki Hamaguchi, Kou Hamada, Naoki Marumo, and Nobuyuki Yoshioka. ``Faster computation of stabilizer extent'' (2024). arXiv:2406.16673."},{"key":"39","doi-asserted-by":"publisher","unstructured":"Beatriz Dias and Robert Koenig. ``Classical simulation of non-Gaussian fermionic circuits''. Quantum 8, 1350 (2024).","DOI":"10.22331\/q-2024-05-21-1350"},{"key":"40","unstructured":"Oliver Reardon-Smith, Micha\u0142 Oszmaniec, and Kamil Korzekwa. ``Improved simulation of quantum circuits dominated by free fermionic operations'' (2024). arXiv:2307.12702."},{"key":"41","unstructured":"Joshua Cudby and Sergii Strelchuk. ``Gaussian decomposition of magic states for matchgate computations'' (2023). arXiv:2307.12654."},{"key":"42","doi-asserted-by":"publisher","unstructured":"Lukas Hantzko, Lennart Binkowski, and Sabhyata Gupta. ``Tensorized pauli decomposition algorithm''. Physica Scripta 99, 085128 (2024).","DOI":"10.1088\/1402-4896\/ad6499"},{"key":"43","unstructured":"Tyson Jones. ``Densepaulidecomposer''. GitHub Repository (2024)."},{"key":"44","unstructured":"Tyson Jones. ``Decomposing dense matrices into dense Pauli tensors'' (2024). arXiv:2401.16378."},{"key":"45","doi-asserted-by":"publisher","unstructured":"Sebasti\u00e1n Vidal Romero and Juan Santos-Su\u00e1rez. ``PauliComposer: Compute tensor products of Pauli matrices efficiently''. Quantum Information Processing 22, 449 (2023).","DOI":"10.1007\/s11128-023-04204-w"},{"key":"46","unstructured":"Hiroki Hamaguchi, Kou Hamada, and Nobuyuki Yoshioka. ``paulidecomp''. GitHub Repository (2024)."},{"key":"47","doi-asserted-by":"publisher","unstructured":"Arno Jaeger and Bertram Mond. ``On direct sums and tensor products of linear programs''. Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und Verwandte Gebiete 3, 19\u201331 (1964).","DOI":"10.1007\/BF00531681"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-09-05-1461\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T10:50:45Z","timestamp":1726483845000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-09-05-1461\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,5]]},"references-count":48,"URL":"https:\/\/doi.org\/10.22331\/q-2024-09-05-1461","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,5]]},"article-number":"1461"}}