Magic of quantum hypergraph states

Junjie Chen1, Yuxuan Yan1, and You Zhou2,3

1Center for Quantum Information, Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, China
2Key Laboratory for Information Science of Electromagnetic Waves (Ministry of Education), Fudan University, Shanghai 200433, China
3Hefei National Laboratory, Hefei 230088, China

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


Magic, or nonstabilizerness, characterizes the deviation of a quantum state from the set of stabilizer states, playing a fundamental role in quantum state complexity and universal fault-tolerant quantum computing. However, analytical and numerical characterizations of magic are very challenging, especially for multi-qubit systems, even with a moderate qubit number. Here, we systemically and analytically investigate the magic resource of archetypal multipartite quantum states—quantum hypergraph states, which can be generated by multi-qubit controlled-phase gates encoded by hypergraphs. We first derive the magic formula in terms of the stabilizer Rényi-$\alpha$ entropies for general quantum hypergraph states. If the average degree of the corresponding hypergraph is constant, we show that magic cannot reach the maximal value, i.e., the number of qubits $n$. Then, we investigate the statistical behaviors of random hypergraph states' magic and prove a concentration result, indicating that random hypergraph states typically reach the maximum magic. This also suggests an efficient way to generate maximal magic states with random diagonal circuits. Finally, we study hypergraph states with permutation symmetry, such as $3$-complete hypergraph states, where any three vertices are connected by a hyperedge. Counterintuitively, such states can only possess constant or even exponentially small magic for $\alpha\geq 2$. Our study advances the understanding of multipartite quantum magic and could lead to applications in quantum computing and quantum many-body physics.

Talk on Quantum Resources 2023:

In quantum information processing, a kind of quantum state known as hypergraph state holds promise for new quantum technologies. Quantum hypergraph states have intricate structures formed by linking multiple qubits in a way that goes beyond traditional pair-wise connections. This complex connectivity allows these states to possess 'magic', a unique property that makes them invaluable for quantum computing. Magic, in quantum terms, refers to a state's ability to perform computations that are otherwise impossible with classical systems, pushing the boundaries of quantum computing.

In this work, we have developed new methods to analyze the magic in these states, shedding light on their potential applications. A noteworthy contribution of our study is the magic formula for stabilizer Renyi entropies for general quantum hypergraph states. According to it, we prove that the magic cannot reach the maximal value if the average degree of the corresponding hypergraph is constant. We also discovered that when these hypergraph states are randomly generated, they typically exhibit maximum magic, making them potential candidates for quantum computational tasks. Additionally, we explored states with specific symmetries and found intriguing patterns in their magical properties.

As outlined in our conclusion and outlook, our research results not only advance the understanding of multipartite quantum magic but also hint at potential applications in quantum computing and quantum many-body physics.

► BibTeX data

► References

[1] Barbara M. Terhal. Quantum error correction for quantum memories. Rev. Mod. Phys., 87: 307–346, Apr 2015. 10.1103/​RevModPhys.87.307.

[2] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Phys. Rev. A, 71: 022316, Feb 2005. 10.1103/​PhysRevA.71.022316.

[3] Victor Veitch, SA Hamed Mousavian, Daniel Gottesman, and Joseph Emerson. The resource theory of stabilizer quantum computation. New Journal of Physics, 16 (1): 013009, 2014. 10.1088/​1367-2630/​16/​1/​013009.

[4] Earl T Campbell, Barbara M Terhal, and Christophe Vuillot. Roads towards fault-tolerant universal quantum computation. Nature, 549 (7671): 172–179, 2017. 10.1038/​nature23460.

[5] Daniel Gottesman and Isaac L Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402 (6760): 390–393, 1999. 10.1038/​46503.

[6] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum entanglement. Rev. Mod. Phys., 81: 865–942, Jun 2009. 10.1103/​RevModPhys.81.865.

[7] Emanuel Knill. Quantum computing with realistically noisy devices. Nature, 434 (7029): 39–44, 2005. 10.1038/​nature03350.

[8] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A, 70: 052328, Nov 2004. 10.1103/​PhysRevA.70.052328.

[9] Sergey Bravyi, Graeme Smith, and John A. Smolin. Trading classical and quantum computational resources. Phys. Rev. X, 6: 021043, Jun 2016. 10.1103/​PhysRevX.6.021043.

[10] 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.

[11] 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, September 2019. ISSN 2521-327X. 10.22331/​q-2019-09-02-181.

[12] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. Estimating outcome probabilities of quantum circuits using quasiprobabilities. Phys. Rev. Lett., 115: 070501, Aug 2015. 10.1103/​PhysRevLett.115.070501.

[13] Mark Howard and Earl Campbell. Application of a resource theory for magic states to fault-tolerant quantum computing. Phys. Rev. Lett., 118: 090501, Mar 2017. 10.1103/​PhysRevLett.118.090501.

[14] 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, Mar 2021. 10.1103/​PRXQuantum.2.010345.

[15] Luigi Amico, Rosario Fazio, Andreas Osterloh, and Vlatko Vedral. Entanglement in many-body systems. Rev. Mod. Phys., 80: 517–576, May 2008. 10.1103/​RevModPhys.80.517.

[16] S Sarkar, C Mukhopadhyay, and A Bayat. Characterization of an operational quantum resource in a critical many-body system. New Journal of Physics, 22 (8): 083077, aug 2020. 10.1088/​1367-2630/​aba919.

[17] Tyler D Ellison, Kohtaro Kato, Zi-Wen Liu, and Timothy H Hsieh. Symmetry-protected sign problem and magic in quantum phases of matter. Quantum, 5: 612, 2021. 10.22331/​q-2021-12-28-612.

[18] Zi-Wen Liu and Andreas Winter. Many-body quantum magic. PRX Quantum, 3: 020333, May 2022. 10.1103/​PRXQuantum.3.020333.

[19] Shiyu Zhou, Zhi-Cheng Yang, Alioscia Hamma, and Claudio Chamon. Single t gate in a clifford circuit drives transition to universal entanglement spectrum statistics. SciPost Phys., 9: 087, 2020. 10.21468/​SciPostPhys.9.6.087.

[20] Jonas Haferkamp, Felipe Montealegre-Mora, Markus Heinrich, Jens Eisert, David Gross, and Ingo Roth. Efficient unitary designs with a system-size independent number of non-clifford gates. Communications in Mathematical Physics, 397: 994, Feb 2023. 10.1007/​s00220-022-04507-6.

[21] Sarah True and Alioscia Hamma. Transitions in Entanglement Complexity in Random Circuits. Quantum, 6: 818, September 2022. ISSN 2521-327X. 10.22331/​q-2022-09-22-818.

[22] Troy J. Sewell and Christopher David White. Mana and thermalization: Probing the feasibility of near-clifford hamiltonian simulation. Phys. Rev. B, 106: 125130, Sep 2022. 10.1103/​PhysRevB.106.125130.

[23] Lorenzo Leone, Salvatore F. E. Oliviero, You Zhou, and Alioscia Hamma. Quantum chaos is quantum. Quantum, 5: 453, may 2021. 10.22331/​q-2021-05-04-453.

[24] Kanato Goto, Tomoki Nosaka, and Masahiro Nozaki. Probing chaos by magic monotones. Phys. Rev. D, 106: 126009, Dec 2022. 10.1103/​PhysRevD.106.126009.

[25] Roy J. Garcia, Kaifeng Bu, and Arthur Jaffe. Resource theory of quantum scrambling. Proceedings of the National Academy of Sciences, 120 (17): e2217031120, 2023. 10.1073/​pnas.2217031120.

[26] Christopher David White, ChunJun Cao, and Brian Swingle. Conformal field theories are magical. Phys. Rev. B, 103: 075145, Feb 2021. 10.1103/​PhysRevB.103.075145.

[27] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma. Learning efficient decoders for quasichaotic quantum scramblers. Phys. Rev. A, 109: 022429, Feb 2024. 10.1103/​PhysRevA.109.022429.

[28] Lorenzo Leone, Salvatore F. E. Oliviero, Stefano Piemontese, Sarah True, and Alioscia Hamma. Retrieving information from a black hole using quantum machine learning. Phys. Rev. A, 106: 062434, Dec 2022a. 10.1103/​PhysRevA.106.062434.

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

[30] James R. Seddon and Earl T. Campbell. Quantifying magic for multi-qubit operations. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 475 (2227): 20190251, jul 2019. 10.1098/​rspa.2019.0251.

[31] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov. Lower bounds on the non-clifford resources for quantum computations. Quantum Science and Technology, 5 (3): 035009, may 2020. 10.1088/​2058-9565/​ab8963.

[32] Xin Wang, Mark M Wilde, and Yuan Su. Quantifying the magic of quantum channels. New Journal of Physics, 21 (10): 103002, 2019. 10.1088/​1367-2630/​ab451d.

[33] Xin Wang, Mark M Wilde, and Yuan Su. Efficiently computable bounds for magic state distillation. Physical review letters, 124 (9): 090505, 2020. 10.1103/​PhysRevLett.124.090505.

[34] Tobias Haug and M.S. Kim. Scalable measures of magic resource for quantum computers. PRX Quantum, 4 (1), jan 2023. 10.1103/​prxquantum.4.010301.

[35] Gaurav Saxena and Gilad Gour. Quantifying multiqubit magic channels with completely stabilizer-preserving operations. Phys. Rev. A, 106: 042422, Oct 2022. 10.1103/​PhysRevA.106.042422.

[36] Kaifeng Bu, Weichen Gu, and Arthur Jaffe. Quantum entropy and central limit theorem. Proceedings of the National Academy of Sciences, 120 (25): e2304589120, 2023. 10.1073/​pnas.2304589120.

[37] Markus Heinrich and David Gross. Robustness of Magic and Symmetries of the Stabiliser Polytope. Quantum, 3: 132, April 2019. ISSN 2521-327X. 10.22331/​q-2019-04-08-132.

[38] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. Stabilizer rényi entropy. Phys. Rev. Lett., 128: 050402, Feb 2022b. 10.1103/​PhysRevLett.128.050402.

[39] Lorenzo Leone and Lennart Bittel. Stabilizer entropies are monotones for magic-state resource theory. arXiv:2404.11652, 2024. 10.48550/​arXiv.2404.11652.

[40] Salvatore F. E. Oliviero, Lorenzo Leone, Alioscia Hamma, and Seth Lloyd. Measuring magic on a quantum processor. npj Quantum Information, 8 (1): 148, Dec 2022a. ISSN 2056-6387. 10.1038/​s41534-022-00666-5.

[41] Tobias Haug, Soovin Lee, and MS Kim. Efficient stabilizer entropies for quantum computers. arXiv preprint arXiv:2305.19152, 2023. 10.48550/​arXiv.2305.19152.

[42] Salvatore F. E. Oliviero, Lorenzo Leone, and Alioscia Hamma. Magic-state resource theory for the ground state of the transverse-field ising model. Phys. Rev. A, 106: 042426, Oct 2022b. 10.1103/​PhysRevA.106.042426.

[43] Jovan Odavić, Tobias Haug, Gianpaolo Torre, Alioscia Hamma, Fabio Franchini, and Salvatore Marco Giampaolo. Complexity of frustration: A new source of non-local non-stabilizerness. SciPost Phys., 15: 131, 2023. 10.21468/​SciPostPhys.15.4.131.

[44] Davide Rattacaso, Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. Stabilizer entropy dynamics after a quantum quench. Phys. Rev. A, 108: 042407, Oct 2023. 10.1103/​PhysRevA.108.042407.

[45] Stefano Piemontese, Tommaso Roscilde, and Alioscia Hamma. Entanglement complexity of the rokhsar-kivelson-sign wavefunctions. Phys. Rev. B, 107: 134202, Apr 2023. 10.1103/​PhysRevB.107.134202.

[46] Lorenzo Leone, Salvatore FE Oliviero, and Alioscia Hamma. Learning t-doped stabilizer states. arXiv preprint arXiv:2305.15398, 2023a. 10.48550/​arXiv.2305.15398.

[47] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. Nonstabilizerness determining the hardness of direct fidelity estimation. Phys. Rev. A, 107: 022429, Feb 2023b. 10.1103/​PhysRevA.107.022429.

[48] Tobias Haug and Lorenzo Piroli. Quantifying nonstabilizerness of matrix product states. Phys. Rev. B, 107: 035148, Jan 2023a. 10.1103/​PhysRevB.107.035148.

[49] Guglielmo Lami and Mario Collura. Quantum magic via perfect pauli sampling of matrix product states. arXiv:2303.05536, 2023. 10.48550/​arXiv.2303.05536.

[50] Tobias Haug and Lorenzo Piroli. Stabilizer entropies and nonstabilizerness monotones. Quantum, 7: 1092, August 2023b. ISSN 2521-327X. 10.22331/​q-2023-08-28-1092.

[51] Poetri Sonya Tarabunga, Emanuele Tirrito, Titas Chanda, and Marcello Dalmonte. Many-body magic via pauli-markov chains—from criticality to gauge theories. PRX Quantum, 4: 040317, Oct 2023. 10.1103/​PRXQuantum.4.040317.

[52] M Rossi, M Huber, D Bruß, and C Macchiavello. Quantum hypergraph states. New Journal of Physics, 15 (11): 113022, nov 2013. 10.1088/​1367-2630/​15/​11/​113022.

[53] Ri Qu, Juan Wang, Zong-shang Li, and Yan-ru Bao. Encoding hypergraphs into quantum states. Phys. Rev. A, 87: 022311, Feb 2013. 10.1103/​PhysRevA.87.022311.

[54] Robert Raussendorf and Hans J. Briegel. A one-way quantum computer. Phys. Rev. Lett., 86: 5188–5191, May 2001. 10.1103/​PhysRevLett.86.5188.

[55] Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel. Measurement-based quantum computation on cluster states. Phys. Rev. A, 68: 022312, Aug 2003. 10.1103/​PhysRevA.68.022312.

[56] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117: 080501, Aug 2016. 10.1103/​PhysRevLett.117.080501.

[57] Jacob Miller and Akimasa Miyake. Hierarchy of universal entanglement in 2d measurement-based quantum computation. npj Quantum Information, 2 (1): 1–6, 2016. 10.1038/​npjqi.2016.36.

[58] Yuki Takeuchi, Tomoyuki Morimae, and Masahito Hayashi. Quantum computational universality of hypergraph states with pauli-x and z basis measurements. Scientific Reports, 9 (1): 13585, Sep 2019. ISSN 2045-2322. 10.1038/​s41598-019-49968-3.

[59] Michael Levin and Zheng-Cheng Gu. Braiding statistics approach to symmetry-protected topological phases. Phys. Rev. B, 86: 115109, Sep 2012. 10.1103/​PhysRevB.86.115109.

[60] Beni Yoshida. Topological phases with generalized global symmetries. Phys. Rev. B, 93: 155131, Apr 2016. 10.1103/​PhysRevB.93.155131.

[61] Jacob Miller and Akimasa Miyake. Latent computational complexity of symmetry-protected topological order with fractional symmetry. Phys. Rev. Lett., 120: 170503, Apr 2018. 10.1103/​PhysRevLett.120.170503.

[62] Christopher David White and Justin H Wilson. Mana in haar-random states. arXiv preprint arXiv:2011.13937, 2020. 10.48550/​arXiv.2011.13937.

[63] M. Hein, J. Eisert, and H. J. Briegel. Multiparty entanglement in graph states. Phys. Rev. A, 69: 062311, Jun 2004. 10.1103/​PhysRevA.69.062311.

[64] Bryn A Bell, DA Herrera-Martí, MS Tame, Damian Markham, WJ Wadsworth, and JG Rarity. Experimental demonstration of a graph state quantum error-correction code. Nature communications, 5 (1): 3658, 2014. 10.1038/​ncomms4658.

[65] C. Kruszynska and B. Kraus. Local entanglability and multipartite entanglement. Phys. Rev. A, 79: 052304, May 2009a. 10.1103/​PhysRevA.79.052304.

[66] Géza Tóth and Otfried Gühne. Detecting genuine multipartite entanglement with two local measurements. Phys. Rev. Lett., 94: 060501, Feb 2005. 10.1103/​PhysRevLett.94.060501.

[67] Otfried Gühne, Marti Cuquet, Frank ES Steinhoff, Tobias Moroder, Matteo Rossi, Dagmar Bruß, Barbara Kraus, and Chiara Macchiavello. Entanglement and nonclassical properties of hypergraph states. Journal of Physics A: Mathematical and Theoretical, 47 (33): 335303, 2014. 10.1088/​1751-8113/​47/​33/​335303.

[68] You Zhou and Alioscia Hamma. Entanglement of random hypergraph states. Phys. Rev. A, 106: 012410, Jul 2022. 10.1103/​PhysRevA.106.012410.

[69] Marco Tomamichel. A framework for non-asymptotic quantum information theory. arXiv preprint arXiv:1203.2142, 2012. 10.48550/​arXiv.1203.2142.

[70] Zi-Wen Liu, Kaifeng Bu, and Ryuji Takagi. One-shot operational quantum resource theory. Phys. Rev. Lett., 123: 020401, Jul 2019. 10.1103/​PhysRevLett.123.020401.

[71] C. Kruszynska and B. Kraus. Local entanglability and multipartite entanglement. Phys. Rev. A, 79: 052304, May 2009b. 10.1103/​PhysRevA.79.052304.

[72] Yoshifumi Nakata and Mio Murao. Diagonal quantum circuits: Their computational power and applications. The European Physical Journal Plus, 129 (7): 152, Jul 2014. ISSN 2190-5444. 10.1140/​epjp/​i2014-14152-9.

[73] Jason Iaconis. Quantum state complexity in computationally tractable quantum circuits. PRX Quantum, 2: 010329, Feb 2021. 10.1103/​PRXQuantum.2.010329.

[74] Yoshifumi Nakata and Mio Murao. Generic entanglement entropy for quantum states with symmetry. Entropy, 22 (6): 684, 2020. 10.3390/​e22060684.

[75] Hui Li and F. D. M. Haldane. Entanglement spectrum as a generalization of entanglement entropy: Identification of topological order in non-abelian fractional quantum hall effect states. Phys. Rev. Lett., 101: 010504, Jul 2008. 10.1103/​PhysRevLett.101.010504.

[76] Claudio Chamon, Alioscia Hamma, and Eduardo R. Mucciolo. Emergent irreversibility and entanglement spectrum statistics. Phys. Rev. Lett., 112: 240501, Jun 2014. 10.1103/​PhysRevLett.112.240501.

[77] Daniel Shaffer, Claudio Chamon, Alioscia Hamma, and Eduardo R Mucciolo. Irreversibility and entanglement spectrum statistics in quantum circuits. Journal of Statistical Mechanics: Theory and Experiment, 2014 (12): P12007, 2014. 10.1088/​1742-5468/​2014/​12/​P12007.

[78] Ning Bao, ChunJun Cao, and Vincent Paul Su. Magic state distillation from entangled states. Physical Review A, 105 (2): 022602, 2022. 10.1103/​PhysRevA.105.022602.

[79] Emanuele Tirrito, Poetri Sonya Tarabunga, Gugliemo Lami, Titas Chanda, Lorenzo Leone, Salvatore FE Oliviero, Marcello Dalmonte, Mario Collura, and Alioscia Hamma. Quantifying non-stabilizerness through entanglement spectrum flatness. arXiv preprint arXiv:2304.01175, 2023. 10.48550/​arXiv.2304.01175.

Cited by

[1] M. Frau, P. S. Tarabunga, M. Collura, M. Dalmonte, and E. Tirrito, "Non-stabilizerness versus entanglement in matrix product states", arXiv:2404.18768, (2024).

[2] Andi Gu, Lorenzo Leone, Soumik Ghosh, Jens Eisert, Susanne F. Yelin, and Yihui Quek, "Pseudomagic Quantum States", Physical Review Letters 132 21, 210602 (2024).

[3] Xhek Turkeshi, Anatoly Dymarsky, and Piotr Sierant, "Pauli Spectrum and Magic of Typical Quantum Many-Body States", arXiv:2312.11631, (2023).

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

[5] Tobias Haug, Soovin Lee, and M. S. Kim, "Efficient quantum algorithms for stabilizer entropies", arXiv:2305.19152, (2023).

[6] Guanyu Zhu, Shehryar Sikander, Elia Portnoy, Andrew W. Cross, and Benjamin J. Brown, "Non-Clifford and parallelizable fault-tolerant logical gates on constant and almost-constant rate homological quantum LDPC codes via higher symmetries", arXiv:2310.16982, (2023).

[7] Poetri Sonya Tarabunga, "Critical behaviours of non-stabilizerness in quantum spin chains", arXiv:2309.00676, (2023).

[8] Xu-Jie Peng, Qing Liu, Lu Liu, Ting Zhang, You Zhou, and He Lu, "Experimental Hybrid Shadow Tomography and Distillation", arXiv:2404.11850, (2024).

[9] Qingyue Zhang, Qing Liu, and You Zhou, "Minimal-Clifford shadow estimation by mutually unbiased bases", Physical Review Applied 21 6, 064001 (2024).

[10] Xingjian Zhang, Zhaokai Pan, and Guoding Liu, "Unconditional quantum MAGIC advantage in shallow circuit computation", arXiv:2402.12246, (2024).

[11] Zijian Song and Guanyu Zhu, "Magic Boundaries of 3D Color Codes", arXiv:2404.05033, (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2024-06-18 05:26:25). 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-06-18 05:26:23).