Learning t-doped stabilizer states

Lorenzo Leone1,2, Salvatore F. E. Oliviero1,3, and Alioscia Hamma4,5

1Physics Department, University of Massachusetts Boston, 02125, USA
2Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
3NEST, Scuola Normale Superiore and Istituto Nanoscienze, Consiglio Nazionale delle Ricerche, Piazza dei Cavalieri 7, IT-56126 Pisa, Italy
4Dipartimento di Fisica `Ettore Pancini', Università degli Studi di Napoli Federico II, Via Cintia 80126, Napoli, Italy
5INFN, Sezione di Napoli, Italy

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

Abstract

In this paper, we present a learning algorithm aimed at learning states obtained from computational basis states by Clifford circuits doped with a finite number $t$ of $T$-gates. The algorithm learns an exact tomographic description of $t$-doped stabilizer states in terms of Pauli observables. This is possible because such states are countable and form a discrete set. To tackle the problem, we introduce a novel algebraic framework for $t$-doped stabilizer states, which extends beyond $T$-gates and includes doping with any kind of local non-Clifford gate. The algorithm requires resources of complexity $\operatorname{poly}(n,2^t)$ and exhibits an exponentially small probability of failure.

► BibTeX data

► References

[1] Matteo Paris and Jaroslav Řeháček, editors. ``Quantum State Estimation''. Volume 649 of Lecture Notes in Physics. Springer. Berlin, Heidelberg (2004).
https:/​/​doi.org/​10.1007/​b98673

[2] Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. ``Efficient quantum state tomography''. Nat. Commun. 1, 149–149 (2010).
https:/​/​doi.org/​10.1038/​ncomms1147

[3] David Gross, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, and Jens Eisert. ``Quantum State Tomography via Compressed Sensing''. Phys. Rev. Lett. 105, 150401–150401 (2010).
https:/​/​doi.org/​10.1103/​PhysRevLett.105.150401

[4] Scott Aaronson. ``Shadow Tomography of Quantum States''. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Pages 325–338–325–338. Association for Computing Machinery (2018).
https:/​/​doi.org/​10.1145/​3188745.3188802

[5] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, et al. ``Classical simulation of quantum supremacy circuits'' (2020). arxiv:2005.06787.
arXiv:2005.06787

[6] Hsin-Yuan Huang, Richard Kueng, and John Preskill. ``Predicting many properties of a quantum system from very few measurements''. Nat. Phys. 16, 1050–1057 (2020).
https:/​/​doi.org/​10.1038/​s41567-020-0932-7

[7] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. ``Optimal algorithms for learning quantum phase states'' (2023). arxiv:2208.07851.
arXiv:2208.07851

[8] Scott Aaronson and Sabee Grewal. ``Efficient Tomography of Non-Interacting-Fermion States''. In Omar Fawzi and Michael Walter, editors, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Volume 266 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:18. Dagstuhl, Germany (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2023.12

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

[10] Ashley Montanaro. ``Learning stabilizer states by Bell sampling'' (2017). arxiv:1707.04012.
arXiv:1707.04012

[11] Dagmar Bruß and Chiara Macchiavello. ``Optimal state estimation for d-dimensional quantum systems''. Phys. Lett. A 253, 249–251 (1999).
https:/​/​doi.org/​10.1016/​S0375-9601(99)00099-7

[12] Daniel Gottesman. ``Theory of fault-tolerant quantum computation''. Phys. Rev. A 57, 127–137–127–137 (1998).
https:/​/​doi.org/​10.1103/​PhysRevA.57.127

[13] Lorenzo Leone, Salvatore F. E. Oliviero, You Zhou, and Alioscia Hamma. ``Quantum Chaos is Quantum''. Quantum 5, 453–453 (2021).
https:/​/​doi.org/​10.22331/​q-2021-05-04-453

[14] Salvatore F. E. Oliviero, Lorenzo Leone, and Alioscia Hamma. ``Transitions in entanglement complexity in random quantum circuits by measurements''. Phys. Lett. A 418, 127721–127721 (2021).
https:/​/​doi.org/​10.1016/​j.physleta.2021.127721

[15] Ching-Yi Lai and Hao-Chung Cheng. ``Learning Quantum Circuits of Some T Gates''. IEEE Transactions on Information Theory 68, 3951–3964–3951–3964 (2022).
https:/​/​doi.org/​10.1109/​tit.2022.3151760

[16] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Stabilizer Rényi Entropy''. Phys. Rev. Lett. 128, 050402–050402 (2022).
https:/​/​doi.org/​10.1103/​PhysRevLett.128.050402

[17] Jiaqing Jiang and Xin Wang. ``Lower bound for the $t$ count via unitary stabilizer nullity''. Phys. Rev. Appl. 19, 034052 (2023).
https:/​/​doi.org/​10.1103/​PhysRevApplied.19.034052

[18] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma. ``Learning efficient decoders for quasichaotic quantum scramblers''. Phys. Rev. A 109, 022429 (2024).
https:/​/​doi.org/​10.1103/​PhysRevA.109.022429

[19] Salvatore F. E. Oliviero, Lorenzo Leone, Seth Lloyd, and Alioscia Hamma. ``Unscrambling quantum information with clifford decoders''. Phys. Rev. Lett. 132, 080402 (2024).
https:/​/​doi.org/​10.1103/​PhysRevLett.132.080402

[20] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov. ``Lower bounds on the non-Clifford resources for quantum computations''. Quantum Sci. and Technol. 5, 035009–035009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​ab8963

[21] Nolan J. Coble, Matthew Coudron, Jon Nelson, and Seyed Sajjad Nezhadi. ``Hamiltonians whose low-energy states require $\Omega(n)$ T gates'' (2023). arxiv:2310.01347.
arXiv:2310.01347

[22] Andi Gu, Salvatore F. E. Oliviero, and Lorenzo Leone. ``Doped stabilizer states in many-body physics and where to find them'' (2024). arXiv:2403.14912.
arXiv:2403.14912

[23] Tobias Haug, Kishor Bharti, and Dax Enshan Koh. ``Pseudorandom unitaries are neither real nor sparse nor noise-robust'' (2023). arxiv:2306.11677.
arXiv:2306.11677

[24] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Improved stabilizer estimation via bell difference sampling'' (2024). arXiv:2304.13915.
arXiv:2304.13915

[25] Marcel Hinsche, Marios Ioannou, Sofiene Jerbi, Lorenzo Leone, Jens Eisert, and Jose Carrasco. ``Efficient distributed inner product estimation via Pauli sampling'' (2024) arXiv:2405.06544.
arXiv:2405.06544

[26] Sergey Bravyi and Dmitri Maslov. ``Hadamard-Free Circuits Expose the Structure of the Clifford Group''. IEEE Transactions on Information Theory 67, 4546–4563 (2021).
https:/​/​doi.org/​10.1109/​TIT.2021.3081415

[27] David Gross, Sepehr Nezami, and Michael Walter. ``Schur–Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations''. Communications in Mathematical Physics 385, 1325–1393–1325–1393 (2021).
https:/​/​doi.org/​10.1007/​s00220-021-04118-7

[28] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates'' (2023). arxiv:2305.13409.
arXiv:2305.13409

[29] Dominik Hangleiter and Michael J. Gullans. ``Bell sampling from quantum circuits'' (2023). arxiv:2306.00083.
arXiv:2306.00083

[30] M. Ram Murty and Purusottam Rath. ``Liouville's Theorem''. In M. Ram Murty and Purusottam Rath, editors, Transcendental Numbers. Pages 1–6. Springer, New York, NY (2014).
https:/​/​doi.org/​10.1007/​978-1-4939-0832-5_1

Cited by

[1] Poetri Sonya Tarabunga, Emanuele Tirrito, Mari Carmen Bañuls, and Marcello Dalmonte, "Nonstabilizerness via matrix product states in the Pauli basis", arXiv:2401.16498, (2024).

[2] Nai-Hui Chia, Daniel Liang, and Fang Song, "Quantum State Learning Implies Circuit Lower Bounds", arXiv:2405.10242, (2024).

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

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

[5] Anurag Anshu and Srinivasan Arunachalam, "A survey on the complexity of learning quantum states", Nature Reviews Physics 6 1, 59 (2024).

[6] Guglielmo Lami and Mario Collura, "Learning the stabilizer group of a Matrix Product State", arXiv:2401.16481, (2024).

[7] Lorenzo Leone and Lennart Bittel, "Stabilizer entropies are monotones for magic-state resource theory", arXiv:2404.11652, (2024).

[8] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang, "Improved Stabilizer Estimation via Bell Difference Sampling", arXiv:2304.13915, (2023).

[9] Dominik Hangleiter and Michael J. Gullans, "Bell sampling from quantum circuits", arXiv:2306.00083, (2023).

[10] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang, "Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates", arXiv:2305.13409, (2023).

[11] Junjie Chen, Yuxuan Yan, and You Zhou, "Magic of quantum hypergraph states", Quantum 8, 1351 (2024).

[12] Chen Qian, Wei-Feng Zhuang, Rui-Cheng Guo, Meng-Jun Hu, and Dong E. Liu, "Information scrambling and entanglement in quantum approximate optimization algorithm circuits", European Physical Journal Plus 139 1, 14 (2024).

[13] Lennart Bittel, Antonio A. Mele, Jens Eisert, and Lorenzo Leone, "PAC-learning of free-fermionic states is NP-hard", arXiv:2404.03585, (2024).

[14] Nai-Hui Chia, Ching-Yi Lai, and Han-Hsuan Lin, "Efficient learning of t-doped stabilizer states with single-copy measurements", Quantum 8, 1250 (2024).

[15] Nolan J. Coble, Matthew Coudron, Jon Nelson, and Seyed Sajjad Nezhadi, "Hamiltonians whose low-energy states require $\Omega(n)$ T gates", arXiv:2310.01347, (2023).

[16] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang, "Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements", arXiv:2308.07175, (2023).

[17] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang, "Pseudoentanglement Ain't Cheap", arXiv:2404.00126, (2024).

[18] Marcel Hinsche, Marios Ioannou, Sofiene Jerbi, Lorenzo Leone, Jens Eisert, and Jose Carrasco, "Efficient distributed inner product estimation via Pauli sampling", arXiv:2405.06544, (2024).

[19] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang, "Agnostic Tomography of Stabilizer Product States", arXiv:2404.03813, (2024).

[20] Chris D. White and Martin J. White, "The magic of entangled top quarks", arXiv:2406.07321, (2024).

[21] Jonathan Allcock, Joao F. Doriguello, Gábor Ivanyos, and Miklos Santha, "Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits", arXiv:2405.06357, (2024).

[22] Tobias Haug, Leandro Aolita, and M. S. Kim, "Probing quantum complexity via universal saturation of stabilizer entropies", arXiv:2406.04190, (2024).

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