Pseudorandom unitaries are neither real nor sparse nor noise-robust
1Quantum Research Center, Technology Innovation Institute, Abu Dhabi, UAE
2Blackett Laboratory, Imperial College London SW7 2AZ, UK
3Quantum Innovation Centre (Q.InC), Agency for Science, Technology and Research (A*STAR), 2 Fusionopolis Way, Innovis #08-03, Singapore 138634, Republic of Singapore
4Institute of High Performance Computing (IHPC), Agency for Science, Technology and Research (A*STAR), 1 Fusionopolis Way, #16-16 Connexis, Singapore 138632, Republic of Singapore
5Science, Mathematics and Technology Cluster, Singapore University of Technology and Design, 8 Somapah Road, Singapore 487372, Singapore
| Published: | 2025-06-04, volume 9, page 1759 |
| Editor: | Daniel Grier |
| Eprint: | arXiv:2306.11677v4 |
| Doi: | https://doi.org/10.22331/q-2025-06-04-1759 |
| Citation: | Quantum 9, 1759 (2025). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Further, we show that PRUs need imaginarity while PRS do not have this restriction. This implies that quantum randomness requires in general a complex-valued formalism of quantum mechanics, while for random quantum states real numbers suffice. Additionally, we derive lower bounds on the coherence of PRSs and PRUs, ruling out the existence of sparse PRUs and PRSs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Further, we show an exponential advantage in imaginarity testing when having access to the complex conjugate of the state. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.
Featured image: We show that pseudorandom unitaries (PRUs), which are efficiently preparable unitaries that are indistinguishable from Haar random unitaries for efficient algorithms, cannot be real-valued, sparse, and noise-robust.
► BibTeX data
► References
[1] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. ``Pseudorandom quantum states''. In Annual International Cryptology Conference. Pages 126–152. Springer (2018).
https://doi.org/10.1007/978-3-319-96878-0_5
[2] Joseph Emerson, Yaakov S Weinstein, Marcos Saraceno, Seth Lloyd, and David G Cory. ``Pseudo-random unitary operators for quantum information processing''. Science 302, 2098–2100 (2003).
https://doi.org/10.1126/science.1090790
[3] Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. ``Efficient quantum pseudorandomness''. Phys. Rev. Lett. 116, 170502 (2016).
https://doi.org/10.1103/PhysRevLett.116.170502
[4] Fernando G S L Brandao, Aram W Harrow, and Michał Horodecki. ``Local random quantum circuits are approximate polynomial-designs''. Communications in Mathematical Physics 346, 397–434 (2016).
https://doi.org/10.1007/s00220-016-2706-8
[5] Yoshifumi Nakata, Christoph Hirche, Masato Koashi, and Andreas Winter. ``Efficient quantum pseudorandomness with nearly time-independent Hamiltonian dynamics''. Phys. Rev. X 7, 021006 (2017).
https://doi.org/10.1103/PhysRevX.7.021006
[6] Valerio Scarani. ``Guaranteed randomness''. Nature 464, 988–989 (2010).
https://doi.org/10.1038/464988a
[7] Yun Zhi Law, Jean-Daniel Bancal, Valerio Scarani, et al. ``Quantum randomness extraction for various levels of characterization of the devices''. Journal of Physics A: Mathematical and Theoretical 47, 424028 (2014).
https://doi.org/10.1088/1751-8113/47/42/424028
[8] Miguel Herrero-Collantes and Juan Carlos Garcia-Escartin. ``Quantum random number generators''. Reviews of Modern Physics 89, 015004 (2017).
https://doi.org/10.1038/npjqi.2016.21
[9] Antonio Acín and Lluis Masanes. ``Certified randomness in quantum physics''. Nature 540, 213–219 (2016).
https://doi.org/10.1038/nature20119
[10] Manabendra Nath Bera, Antonio Acín, Marek Kuś, Morgan W Mitchell, and Maciej Lewenstein. ``Randomness in quantum mechanics: philosophy, physics and technology''. Reports on Progress in Physics 80, 124001 (2017).
https://doi.org/10.1088/1361-6633/aa8731
[11] Cristian S Calude and Karl Svozil. ``Quantum randomness and value indefiniteness''. Advanced Science Letters 1, 165–168 (2008).
https://doi.org/10.1166/asl.2008.016
[12] Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. ``Random unitaries in extremely low depth''. arXiv preprint arXiv:2407.07754 (2024).
https://doi.org/10.48550/arXiv.2407.07754
[13] Fermi Ma and Hsin-Yuan Huang. ``How to construct random unitaries''. arXiv preprint arXiv:2410.10116 (2024).
https://doi.org/10.48550/arXiv.2410.10116
[14] Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. ``Quantum pseudorandom scramblers''. arXiv preprint arXiv:2309.08941 (2023).
https://doi.org/10.48550/arXiv.2309.08941
[15] Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, and Yao-Ting Lin. ``Pseudorandom isometries''. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Pages 226–254. Springer (2024).
https://doi.org/10.1007/978-3-031-58737-5_9
[16] Zvika Brakerski and Omri Shmueli. ``(Pseudo) random quantum states with binary phase''. In Theory of Cryptography Conference. Pages 229–250. Springer (2019).
https://doi.org/10.1007/978-3-030-36030-6_10
[17] Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. ``Quantum Pseudoentanglement''. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:21. Dagstuhl, Germany (2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2024.2
[18] William Kretschmer. ``Quantum Pseudorandomness and Classical Complexity''. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:20. Dagstuhl, Germany (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.TQC.2021.2
[19] Prabhanjan Ananth, Luowen Qian, and Henry Yuen. ``Cryptography from pseudorandom quantum states''. In Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part I. Pages 208–236. Springer (2022).
https://doi.org/10.1007/978-3-031-15802-5_8
[20] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. ``Pseudorandom (function-like) quantum state generators: New definitions and applications''. In Theory of Cryptography Conference. Pages 237–265. Springer (2022).
https://doi.org/10.1007/978-3-031-22318-1_9
[21] Tomoyuki Morimae and Takashi Yamakawa. ``Quantum commitments and signatures without one-way functions''. In Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part I. Pages 269–295. Springer (2022).
https://doi.org/10.1007/978-3-031-15802-5_10
[22] Prabhanjan Ananth, Yao-Ting Lin, and Henry Yuen. ``Pseudorandom Strings from Pseudorandom Quantum States''. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:22. Dagstuhl, Germany (2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2024.6
[23] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Improved stabilizer estimation via Bell difference sampling''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Page 1352–1363. STOC 2024New York, NY, USA (2024). Association for Computing Machinery.
https://doi.org/10.1145/3618260.3649738
[24] Kang-Da Wu, Tulja Varun Kondra, Swapan Rana, Carlo Maria Scandolo, Guo-Yong Xiang, Chuan-Feng Li, Guang-Can Guo, and Alexander Streltsov. ``Resource theory of imaginarity: Quantification and state conversion''. Phys. Rev. A 103, 032401 (2021).
https://doi.org/10.1103/PhysRevA.103.032401
[25] Tulja Varun Kondra, Chandan Datta, and Alexander Streltsov. ``Real quantum operations and state transformations''. New Journal of Physics 25, 093043 (2023).
https://doi.org/10.1088/1367-2630/acf9c4
[26] Ming-Cheng Chen, Can Wang, Feng-Ming Liu, Jian-Wen Wang, Chong Ying, Zhong-Xia Shang, Yulin Wu, M. Gong, H. Deng, F.-T. Liang, Qiang Zhang, Cheng-Zhi Peng, Xiaobo Zhu, Adán Cabello, Chao-Yang Lu, and Jian-Wei Pan. ``Ruling out real-valued standard formalism of quantum theory''. Phys. Rev. Lett. 128, 040403 (2022).
https://doi.org/10.1103/PhysRevLett.128.040403
[27] Marc-Olivier Renou, David Trillo, Mirjam Weilenmann, Thinh P Le, Armin Tavakoli, Nicolas Gisin, Antonio Acín, and Miguel Navascués. ``Quantum theory based on real numbers can be experimentally falsified''. Nature 600, 625–629 (2021).
https://doi.org/10.1038/s41586-021-04160-4
[28] Kang-Da Wu, Tulja Varun Kondra, Swapan Rana, Carlo Maria Scandolo, Guo-Yong Xiang, Chuan-Feng Li, Guang-Can Guo, and Alexander Streltsov. ``Operational resource theory of imaginarity''. Phys. Rev. Lett. 126, 090401 (2021).
https://doi.org/10.1103/PhysRevLett.126.090401
[29] Zheng-Da Li, Ya-Li Mao, Mirjam Weilenmann, Armin Tavakoli, Hu Chen, Lixin Feng, Sheng-Jun Yang, Marc-Olivier Renou, David Trillo, Thinh P. Le, et al. ``Testing real quantum theory in an optical quantum network''. Phys. Rev. Lett. 128, 040402 (2022).
https://doi.org/10.1103/PhysRevLett.128.040402
[30] T. Baumgratz, M. Cramer, and M. B. Plenio. ``Quantifying coherence''. Phys. Rev. Lett. 113, 140401 (2014).
https://doi.org/10.1103/PhysRevLett.113.140401
[31] Alexander Streltsov, Gerardo Adesso, and Martin B. Plenio. ``Colloquium: Quantum coherence as a resource''. Rev. Mod. Phys. 89, 041003 (2017).
https://doi.org/10.1103/RevModPhys.89.041003
[32] Kaifeng Bu, Asutosh Kumar, Lin Zhang, and Junde Wu. ``Cohering power of quantum operations''. Physics Letters A 381, 1670–1676 (2017).
https://doi.org/10.1016/j.physleta.2017.03.022
[33] Paolo Zanardi, Georgios Styliaris, and Lorenzo Campos Venuti. ``Coherence-generating power of quantum unitary maps and beyond''. Phys. Rev. A 95, 052306 (2017).
https://doi.org/10.1103/PhysRevA.95.052306
[34] Kaifeng Bu, Uttam Singh, Shao-Ming Fei, Arun Kumar Pati, and Junde Wu. ``Maximum relative entropy of coherence: An operational coherence measure''. Phys. Rev. Lett. 119, 150405 (2017).
https://doi.org/10.1103/PhysRevLett.119.150405
[35] Kaifeng Bu and Chunhe Xiong. ``A note on cohering power and de-cohering power''. Quantum Information & Computation 17, 1206–1220 (2017).
https://doi.org/10.26421/QIC17.13-14-8
[36] Alexander Streltsov, Uttam Singh, Himadri Shekhar Dhar, Manabendra Nath Bera, and Gerardo Adesso. ``Measuring quantum coherence with entanglement''. Phys. Rev. Lett. 115, 020403 (2015).
https://doi.org/10.1103/PhysRevLett.115.020403
[37] Eric Chitambar and Min-Hsiu Hsieh. ``Relating the resource theories of entanglement and quantum coherence''. Phys. Rev. Lett. 117, 020402 (2016).
https://doi.org/10.1103/PhysRevLett.117.020402
[38] Kaifeng Bu, Roy J Garcia, Arthur Jaffe, Dax Enshan Koh, and Lu Li. ``Complexity of quantum circuits via sensitivity, magic, and coherence''. Communications in Mathematical Physics 405, 161 (2024).
https://doi.org/10.1007/s00220-024-05030-6
[39] Mark Hillery. ``Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation''. Phys. Rev. A 93, 012111 (2016).
https://doi.org/10.1103/PhysRevA.93.012111
[40] J M Matera, D Egloff, N Killoran, and M B Plenio. ``Coherent control of quantum systems as a resource theory''. Quantum Science and Technology 1, 01LT01 (2016).
https://doi.org/10.1088/2058-9565/1/1/01LT01
[41] Hai-Long Shi, Si-Yuan Liu, Xiao-Hui Wang, Wen-Li Yang, Zhan-Ying Yang, and Heng Fan. ``Coherence depletion in the Grover quantum search algorithm''. Phys. Rev. A 95, 032307 (2017).
https://doi.org/10.1103/PhysRevA.95.032307
[42] Guoming Wang, Dax Enshan Koh, Peter D. Johnson, and Yudong Cao. ``Minimizing estimation runtime on noisy quantum computers''. PRX Quantum 2, 010346 (2021).
https://doi.org/10.1103/PRXQuantum.2.010346
[43] Ronitt Rubinfeld and Madhu Sudan. ``Robust characterizations of polynomials with applications to program testing''. SIAM Journal on Computing 25, 252–271 (1996).
https://doi.org/10.1137/S0097539793255151
[44] Oded Goldreich, Shari Goldwasser, and Dana Ron. ``Property testing and its connection to learning and approximation''. Journal of the ACM (JACM) 45, 653–750 (1998).
https://doi.org/10.1145/285055.285060
[45] Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig. ``Quantum property testing''. SIAM Journal on Computing 37, 1387–1400 (2008).
https://doi.org/10.1137/S009753970444241
[46] Ashley Montanaro and Ronald de Wolf. ``A survey of quantum property testing''. Pages 1–81. Number 7 in Graduate Surveys. Theory of Computing Library. (2016).
https://doi.org/10.4086/toc.gs.2016.007
[47] Aram W Harrow and Ashley Montanaro. ``Testing product states, quantum Merlin-Arthur games and tensor optimization''. Journal of the ACM (JACM) 60, 1–43 (2013).
https://doi.org/10.1145/2432622.2432625
[48] 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 (2021).
https://doi.org/10.1007/s00220-021-04118-7
[49] Thomas Chen, Shivam Nadimpalli, and Henry Yuen. ``Testing and learning quantum juntas nearly optimally''. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1163–1185. SIAM (2023).
https://doi.org/10.1137/1.9781611977554.ch43
[50] Adrian She and Henry Yuen. ``Unitary Property Testing Lower Bounds by Polynomials''. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 96:1–96:17. Dagstuhl, Germany (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2023.96
[51] Zvika Brakerski, Devika Sharma, and Guy Weissenberg. ``Unitary subgroup testing''. arXiv preprint arXiv:2104.03591 (2021).
https://doi.org/10.48550/arXiv.2104.03591
[52] Mehdi Soleimanifar and John Wright. ``Testing matrix product states''. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1679–1701. SIAM (2022).
https://doi.org/10.1137/1.9781611977073.68
[53] Nikhil Bansal, Wai-Keong Mok, Kishor Bharti, Dax Enshan Koh, and Tobias Haug. ``Pseudorandom density matrices''. PRX Quantum 6, 020322 (2025).
https://doi.org/10.1103/PRXQuantum.6.020322
[54] Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, Fernando G.S.L. Brandão, and Patrick Hayden. ``Efficient unitary designs from random sums and permutations''. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 476–484. (2024).
https://doi.org/10.1109/FOCS61266.2024.00037
[55] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. ``Pseudorandom unitaries with non-adaptive security''. arXiv preprint arXiv:2402.14803 (2024).
https://doi.org/10.48550/arXiv.2402.14803
[56] Zvika Brakerski and Nir Magrafta. ``Real-valued somewhat-pseudorandom unitaries''. arXiv preprint arXiv:2403.16704 (2024).
https://doi.org/10.48550/arXiv.2403.16704
[57] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. ``Simple constructions of linear-depth t-designs and pseudorandom unitaries''. arXiv preprint arXiv:2404.12647 (2024).
https://doi.org/10.48550/arXiv.2404.12647
[58] Eric Chitambar and Gilad Gour. ``Quantum resource theories''. Rev. Mod. Phys. 91, 025001 (2019).
https://doi.org/10.1103/RevModPhys.91.025001
[59] Victor Veitch, S A Hamed Mousavian, Daniel Gottesman, and Joseph Emerson. ``The resource theory of stabilizer quantum computation''. New Journal of Physics 16, 013009 (2014).
https://doi.org/10.1088/1367-2630/16/1/013009
[60] Adriano Barenco, Andre Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello. ``Stabilization of quantum computations by symmetrization''. SIAM Journal on Computing 26, 1541–1557 (1997).
https://doi.org/10.1137/S0097539796302452
[61] Artur K. Ekert, Carolina Moura Alves, Daniel K. L. Oi, Michał Horodecki, Paweł Horodecki, and L. C. Kwek. ``Direct estimations of linear and nonlinear functionals of a quantum state''. Phys. Rev. Lett. 88, 217901 (2002).
https://doi.org/10.1103/PhysRevLett.88.217901
[62] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al. ``Quantum advantage in learning from experiments''. Science 376, 1182–1186 (2022).
https://doi.org/10.1126/science.abn7293
[63] Michael A Nielsen and Isaac L Chuang. ``Quantum computation and quantum information''. Cambridge University Press. (2010).
https://doi.org/10.1017/CBO9780511976667
[64] Terry Rudolph and Lov Grover. ``A 2 rebit gate universal for quantum computing''. arXiv preprint quant-ph/0210187 (2002).
https://doi.org/10.48550/arXiv.quant-ph/0210187
arXiv:quant-ph/0210187
[65] Alexander Hickey and Gilad Gour. ``Quantifying the imaginarity of quantum mechanics''. Journal of Physics A: Mathematical and Theoretical 51, 414009 (2018).
https://doi.org/10.1088/1751-8121/aabe9c
[66] Tudor Giurgica-Tiron and Adam Bouland. ``Pseudorandomness from subset states''. arXiv preprint arXiv:2312.09206 (2023).
https://doi.org/10.48550/arXiv.2312.09206
[67] Fernando Granha Jeronimo, Nir Magrafta, and Pei Wu. ``Pseudorandom and pseudoentangled states from subset states''. arXiv preprint arXiv:2312.15285 (2023).
https://doi.org/10.48550/arXiv.2312.15285
[68] Daniel Gottesman. ``The Heisenberg representation of quantum computers''. Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in PhysicsPages 32–43 (1999). url: doi.org/10.48550/arXiv.quant-ph/9807006.
https://doi.org/10.48550/arXiv.quant-ph/9807006
arXiv:quant-ph/9807006
[69] Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. ``Quantum algorithmic measurement''. Nature communications 13, 887 (2022).
https://doi.org/10.1038/s41467-021-27922-0
[70] Uttam Singh, Lin Zhang, and Arun Kumar Pati. ``Average coherence and its typicality for random pure states''. Phys. Rev. A 93, 032125 (2016).
https://doi.org/10.1103/PhysRevA.93.032125
[71] Andi Gu, Lorenzo Leone, Soumik Ghosh, Jens Eisert, Susanne F. Yelin, and Yihui Quek. ``Pseudomagic quantum states''. Phys. Rev. Lett. 132, 210602 (2024).
https://doi.org/10.1103/PhysRevLett.132.210602
[72] Dax Enshan Koh, Murphy Yuezhen Niu, and Theodore J Yoder. ``Quantum simulation from the bottom up: the case of rebits''. Journal of Physics A: Mathematical and Theoretical 51, 195302 (2018).
https://doi.org/10.1088/1751-8121/aab9c4
[73] Matthew McKague. ``On the power quantum computation over real Hilbert spaces''. International Journal of Quantum Information 11, 1350001 (2013).
https://doi.org/10.1142/S0219749913500019
[74] Nicolas Delfosse, Philippe Allard Guerin, Jacob Bian, and Robert Raussendorf. ``Wigner function negativity and contextuality in quantum computation on rebits''. Phys. Rev. X 5, 021003 (2015).
https://doi.org/10.1103/PhysRevX.5.021003
[75] Yuxiang Yang, Giulio Chiribella, and Gerardo Adesso. ``Certifying quantumness: Benchmarks for the optimal processing of generalized coherent and squeezed states''. Phys. Rev. A 90, 042319 (2014).
https://doi.org/10.1103/PhysRevA.90.042319
[76] Jisho Miyazaki, Akihito Soeda, and Mio Murao. ``Complex conjugation supermap of unitary quantum maps and its universal implementation protocol''. Phys. Rev. Res. 1, 013007 (2019).
https://doi.org/10.1103/PhysRevResearch.1.013007
[77] Jonathan Katz and Yehuda Lindell. ``Introduction to modern cryptography''. CRC press. (2020).
https://doi.org/10.1201/b17668
[78] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik. ``Noisy intermediate-scale quantum algorithms''. Rev. Mod. Phys. 94, 015004 (2022).
https://doi.org/10.1103/RevModPhys.94.015004
[79] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven. ``Focus beyond quadratic speedups for error-corrected quantum advantage''. PRX Quantum 2, 010103 (2021).
https://doi.org/10.1103/PRXQuantum.2.010103
[80] Yasunari Suzuki, Suguru Endo, Keisuke Fujii, and Yuuki Tokunaga. ``Quantum error mitigation as a universal error reduction technique: applications from the NISQ to the fault-tolerant quantum computing eras''. PRX Quantum 3, 010345 (2022).
https://doi.org/10.1103/PRXQuantum.3.010345
[81] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Pseudoentanglement ain't cheap''. arXiv preprint arXiv:2404.00126 (2024).
https://doi.org/10.48550/arXiv.2404.00126
[82] Ya-Dong Wu, Yan Zhu, Giulio Chiribella, and Nana Liu. ``Efficient learning of continuous-variable quantum states''. Phys. Rev. Res. 6, 033280 (2024).
https://doi.org/10.1103/PhysRevResearch.6.033280
[83] Robbie King, Kianna Wan, and Jarrod R. McClean. ``Exponential learning advantages with conjugate states and minimal quantum memory''. PRX Quantum 5, 040301 (2024).
https://doi.org/10.1103/PRXQuantum.5.040301
[84] Ariel Bendersky, Juan Pablo Paz, and Marcelo Terra Cunha. ``General theory of measurement with two copies of a quantum state''. Physical review letters 103, 040404 (2009).
https://doi.org/10.1103/PhysRevLett.103.040404
[85] Tobias Haug and M.S. Kim. ``Scalable measures of magic resource for quantum computers''. PRX Quantum 4, 010301 (2023).
https://doi.org/10.1103/PRXQuantum.4.010301
[86] Mark Zhandry. ``How to construct quantum random functions''. Journal of the ACM (JACM) 68, 1–43 (2021).
https://doi.org/10.1109/FOCS.2012.37
[87] Sandu Popescu, Anthony J Short, and Andreas Winter. ``Entanglement and the foundations of statistical mechanics''. Nature Physics 2, 754–758 (2006).
https://doi.org/10.1038/nphys444
[88] Joonwoo Bae and Leong-Chuan Kwek. ``Quantum state discrimination and its applications''. Journal of Physics A: Mathematical and Theoretical 48, 083001 (2015).
https://doi.org/10.1088/1751-8113/48/8/083001
[89] Ashley Montanaro. ``Learning stabilizer states by Bell sampling''. arXiv preprint arXiv:1707.04012 (2017).
https://doi.org/10.48550/arXiv.1707.04012
[90] Otfried Gühne and Géza Tóth. ``Entanglement detection''. Physics Reports 474, 1–75 (2009).
https://doi.org/10.1016/j.physrep.2009.02.004
[91] Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T. Sornborger, and Patrick J. Coles. ``Quantum-assisted quantum compiling''. Quantum 3, 140 (2019).
https://doi.org/10.22331/q-2019-05-13-140
[92] Angela Sara Cacciapuoti, Marcello Caleffi, Rodney Van Meter, and Lajos Hanzo. ``When entanglement meets classical communications: Quantum teleportation for the quantum internet''. IEEE Transactions on Communications 68, 3808–3833 (2020).
https://doi.org/10.1109/TCOMM.2020.2978071
[93] Junjing Xing, Tianfeng Feng, Zhaobing Fan, Haitao Ma, Kishor Bharti, Dax Enshan Koh, and Yunlong Xiao. ``Fundamental limitations on communication over a quantum network''. arXiv preprint arXiv:2306.04983 (2023).
https://doi.org/10.48550/arXiv.2306.04983
[94] Artur K. Ekert. ``Quantum cryptography based on Bell's theorem''. Phys. Rev. Lett. 67, 661–663 (1991).
https://doi.org/10.1103/PhysRevLett.67.661
[95] Hans J Briegel, David E Browne, Wolfgang Dür, Robert Raussendorf, and Maarten Van den Nest. ``Measurement-based quantum computation''. Nature Physics 5, 19–26 (2009).
https://doi.org/10.1038/nphys1157
[96] Jacob D. Biamonte, Mauro E. S. Morales, and Dax Enshan Koh. ``Entanglement scaling in quantum advantage benchmarks''. Phys. Rev. A 101, 012349 (2020).
https://doi.org/10.1103/PhysRevA.101.012349
[97] Richard Jozsa and Maarten Van den Nest. ``Classical simulation complexity of extended Clifford circuits''. Quantum Information & Computation 14, 633–648 (2014).
https://doi.org/10.26421/QIC14.7-8
[98] Dax Enshan Koh. ``Further extensions of Clifford circuits and their classical simulation complexities''. Quantum Information & Computation 17, 0262–0282 (2017).
https://doi.org/10.26421/QIC17.3-4
[99] Adam Bouland, Joseph F. Fitzsimons, and Dax Enshan Koh. ``Complexity Classification of Conjugated Clifford Circuits''. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference (CCC 2018). Volume 102 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:25. Dagstuhl, Germany (2018). Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.CCC.2018.21
[100] 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
[101] 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
[102] Kaifeng Bu and Dax Enshan Koh. ``Efficient classical simulation of Clifford circuits with nonstabilizer input states''. Phys. Rev. Lett. 123, 170502 (2019).
https://doi.org/10.1103/PhysRevLett.123.170502
[103] 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
[104] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Stabilizer Rényi entropy''. Phys. Rev. Lett. 128, 050402 (2022).
https://doi.org/10.1103/PhysRevLett.128.050402
[105] Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang. ``Statistical complexity of quantum circuits''. Phys. Rev. A 105, 062431 (2022).
https://doi.org/10.1103/PhysRevA.105.062431
[106] Kaifeng Bu, Weichen Gu, and Arthur Jaffe. ``Stabilizer testing and magic entropy''. arXiv preprint arXiv:2306.09292 (2023).
https://doi.org/10.48550/arXiv.2306.09292
[107] Kaifeng Bu, Weichen Gu, and Arthur Jaffe. ``Discrete quantum Gaussians and central limit theorem''. arXiv preprint arXiv:2302.08423 (2023).
https://doi.org/10.48550/arXiv.2302.08423
[108] Kaifeng Bu, Weichen Gu, and Arthur Jaffe. ``Quantum entropy and central limit theorem''. Proceedings of the National Academy of Sciences 120, e2304589120 (2023).
https://doi.org/10.1073/pnas.2304589120
[109] Richard A. Low. ``Learning and testing algorithms for the Clifford group''. Phys. Rev. A 80, 052314 (2009).
https://doi.org/10.1103/PhysRevA.80.052314
[110] Guoming Wang. ``Property testing of unitary operators''. Phys. Rev. A 84, 052328 (2011).
https://doi.org/10.1103/PhysRevA.84.052328
[111] Benoı̂t Collins and Piotr Śniady. ``Integration with respect to the haar measure on unitary, orthogonal and symplectic group''. Communications in Mathematical Physics 264, 773–795 (2006).
https://doi.org/10.1007/s00220-006-1554-3
[112] Z. Puchała and J.A. Miszczak. ``Symbolic integration with respect to the Haar measure on the unitary groups''. Bulletin of the Polish Academy of Sciences: Technical Sciences 65, 21–27 (2017).
https://doi.org/10.1515/bpasts-2017-0003
Cited by
[1] Tobias Haug, Leandro Aolita, and M.S. Kim, "Probing quantum complexity via universal saturation of stabilizer entropies", Quantum 9, 1801 (2025).
[2] Linlin Ye, Zhaoqi Wu, and Nanrun Zhou, "Coherence and Imaginarity as Resources in Quantum Circuit Complexity", Advanced Quantum Technologies 9 4, e01007 (2026).
[3] Mao-Sheng Li, Rafael Wagner, and Lin Zhang, "Multistate imaginarity and coherence in qubit systems", Physical Review A 113 1, 012428 (2026).
[4] M. Hinsche, M. Ioannou, S. Jerbi, L. Leone, J. Eisert, and J. Carrasco, "Efficient Distributed Inner-Product Estimation via Pauli Sampling", PRX Quantum 6 3, 030354 (2025).
[5] Beatrice Magni, Markus Heinrich, Lorenzo Leone, and Xhek Turkeshi, "Anticoncentration and state design of doped real Clifford circuits and tensor networks", Physical Review A 113 6, 062446 (2026).
[6] Lorenzo Leone, Salvatore F.E. Oliviero, Alioscia Hamma, Jens Eisert, and Lennart Bittel, "Non-Clifford Cost of Random Unitaries", PRX Quantum 7 2, 020321 (2026).
[7] Jingyan Liu, Yue Sun, Jianwei Xu, and Ming-Jing Zhao, "Imaginarity measures induced by real part states and the complementarity relations", Journal of Physics A: Mathematical and Theoretical 59 3, 035302 (2026).
[8] Alex Grilo and Álvaro Yángüez, "Quantum pseudoresources imply cryptography", Abstract_only IACR Communications in Cryptology 2 4, cc2-4-15 (2026).
[9] Beatrice Magni, Alexios Christopoulos, Andrea De Luca, and Xhek Turkeshi, "Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudomagic States", Physical Review X 15 3, 031071 (2025).
[10] Tobias Haug and Poetri Sonya Tarabunga, "Efficient witnessing and testing of magic in mixed quantum states", npj Quantum Information 12 1, 40 (2026).
[11] Roy J. Garcia, Gaurav Bhole, Kaifeng Bu, Liyuan Chen, Haribabu Arthanari, and Arthur Jaffe, "Hardness of measuring magic resource", Physical Review Research 7 3, 033271 (2025).
[12] Yuhang Xie, Yanjun Chu, and Chenyang Cui, "Erasing imaginarity: Selective imaginarity-breaking channels and non-selective imaginarity-breaking channels", Physics Letters A 582, 131573 (2026).
[13] Lennart Bittel and Lorenzo Leone, "Adaptively Secure Unitary Designs with Constant Non-Clifford Cost", Physical Review Letters 136 21, 210802 (2026).
[14] Wonjun Lee, Minki Hhan, Gil Young Cho, and Hyukjoon Kwon, "Shallow Quantum Circuit for Generating Extremely Low-Entangled Approximate State Designs", Physical Review Letters 136 15, 150603 (2026).
[15] Tristan Nemoz, Romain Alléaume, and Peter Brown, "Exact distinguishability between real-valued and complex-valued Haar random quantum states", Quantum 10, 2120 (2026).
[16] Andrew E. Deneris, Paolo Braccia, Pablo Bermejo, N. L. Diaz, Antonio A. Mele, and M. Cerezo, "Analyzing the Free States of one Quantum Resource Theory as Resource States of Another", Advanced Quantum Technologies 9 2, e00702 (2026).
[17] Yiding Wang, Xiaofen Huang, and Tinggui Zhang, "Correlations Between Quantum Battery Capacity and Quantum Resources for Two‐qubit System", Advanced Quantum Technologies 9 4, e70289 (2026).
[18] Poetri Sonya Tarabunga and Yi-Ming Ding, "Bell Sampling in Quantum Monte Carlo Simulations", Physical Review Letters 135 20, 200403 (2025).
[19] Yinzhu Wang, Sichen Shang, Runkang Liu, Lihua Hao, Chen Cheng, and Suping Wang, "Quantifying the imaginarity of quantum channels based on the Bures angle", The European Physical Journal Plus 141 3, 216 (2026).
[20] Poetri Sonya Tarabunga, Martina Frau, Tobias Haug, Emanuele Tirrito, and Lorenzo Piroli, "A nonstabilizerness monotone from stabilizerness asymmetry", Quantum Science and Technology 10 4, 045026 (2025).
[21] Shuangshuang Fu, Tianhui Dong, and Xiaohui Li, "Quantifying the imaginarity of quantum channels", Quantum Information Processing 25 5, 140 (2026).
[22] Robbie King, Kianna Wan, and Jarrod R. McClean, "Exponential Learning Advantages with Conjugate States and Minimal Quantum Memory", PRX Quantum 5 4, 040301 (2024).
[23] Andrew E. Deneris, Paolo Braccia, Pablo Bermejo, N. L. Diaz, Antonio A. Mele, and M. Cerezo, "Analyzing the free states of one quantum resource theory as resource states of another", arXiv:2507.11793, (2025).
[24] Nikhil Bansal, Wai-Keong Mok, Kishor Bharti, Dax Enshan Koh, and Tobias Haug, "Pseudorandom Density Matrices", PRX Quantum 6 2, 020322 (2025).
[25] Fermi Ma and Hsin-Yuan Huang, "How to Construct Random Unitaries", arXiv:2410.10116, (2024).
[26] Kohdai Kuroiwa, Ryuji Takagi, Gerardo Adesso, and Hayata Yamasaki, "Robustness- and weight-based resource measures without convexity restriction: Multicopy witness and operational advantage in static and dynamical quantum resource theories", Physical Review A 109 4, 042403 (2024).
[27] Carlos Fernandes, Rafael Wagner, Leonardo Novo, and Ernesto F. Galvão, "Unitary-Invariant Witnesses of Quantum Imaginarity", Physical Review Letters 133 19, 190201 (2024).
[28] Yu-Ao Chen, Chenghong Zhu, Keming He, Yingjian Liu, and Xin Wang, "Hypothesis testing of symmetry in quantum dynamics", Physical Review A 111 5, 052406 (2025).
[29] Ewin Tang, John Wright, and Mark Zhandry, "Conjugate queries can help", arXiv:2510.07622, (2025).
[30] Wonjun Lee, Hyukjoon Kwon, and Gil Young Cho, "Pseudochaotic many-body dynamics as a pseudorandom state generator", Nature Communications 16 1, 6800 (2025).
[31] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen, "Pseudorandom unitaries with non-adaptive security", arXiv:2402.14803, (2024).
[32] Zhi-Xiang Jin, Meng-Xin Lai, Bing Yu, and Shao-Ming Fei, "Operational conversion of quantum imaginarity to quantum discord", Annals of Physics 489, 170428 (2026).
[33] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma, "Learning t-doped stabilizer states", Quantum 8, 1361 (2024).
[34] Andi Gu, Lorenzo Leone, Soumik Ghosh, Jens Eisert, Susanne F. Yelin, and Yihui Quek, "Pseudomagic Quantum States", Physical Review Letters 132 21, 210602 (2024).
[35] Xiaozhou Feng and Matteo Ippoliti, "Dynamics of pseudoentanglement", Journal of High Energy Physics 2025 2, 128 (2025).
[36] Tobias Haug, Nikhil Bansal, Wai-Keong Mok, Dax Enshan Koh, and Kishor Bharti, "Pseudorandom quantum authentication", arXiv:2501.00951, (2025).
[37] Manuel Goulão and David Elkouss, "Pseudo-Entanglement is Necessary for EFI Pairs", arXiv:2406.06881, (2024).
[38] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen, "Simple constructions of linear-depth t-designs and pseudorandom unitaries", arXiv:2404.12647, (2024).
[39] Rafael Wagner, "Coherence and contextuality as quantum resources", arXiv:2511.16785, (2025).
[40] Fernando Granha Jeronimo, Nir Magrafta, and Pei Wu, "Pseudorandom and Pseudoentangled States from Subset States", arXiv:2312.15285, (2023).
[41] Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, and Yao-Ting Lin, "Pseudorandom Isometries", arXiv:2311.02901, (2023).
[42] Tobias Haug, Soovin Lee, and M. S. Kim, "Efficient Quantum Algorithms for Stabilizer Entropies", Physical Review Letters 132 24, 240602 (2024).
[43] Zhi-Wei Wei and Shao-Ming Fei, "Nonlocal advantages of quantum imaginarity", Physical Review A 110 5, 052202 (2024).
[44] Jonathan Allcock, Joao F. Doriguello, Gábor Ivanyos, and Miklos Santha, "Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more", arXiv:2510.06848, (2025).
[45] Wonjun Lee, Hyukjoon Kwon, and Gil Young Cho, "Fast pseudothermalization", arXiv:2411.03974, (2024).
[46] Rahul Arvind, Kishor Bharti, Jun Yong Khoo, Dax Enshan Koh, and Jian Feng Kong, "Quantum tug of war between randomness and symmetries on homogeneous spaces", Physical Review Research 7 1, 013105 (2025).
[47] Shuanping Du and Zhaofang Bai, "Quantifying imaginarity in terms of pure-state imaginarity", Physical Review A 111 2, 022405 (2025).
[48] Rivu Gupta, Tanoy Kanti Konar, Ayan Patra, and Aditi Sen De, "Limits on broadcasting non-stabilizerness through unrestricted operations", arXiv:2501.15794, (2025).
[49] Julien Pinske and Klaus Mølmer, "Censorship of quantum resources in quantum networks", Physical Review A 110 6, 062404 (2024).
[50] Sagnik Chatterjee and Vyacheslav Kungurtsev, "Quantum Solutions to the Privacy vs. Utility Tradeoff", arXiv:2307.03118, (2023).
[51] Zvika Brakerski and Nir Magrafta, "Real-Valued Somewhat-Pseudorandom Unitaries", arXiv:2403.16704, (2024).
[52] Andrew Tanggara, Mile Gu, and Kishor Bharti, "Near-Term Pseudorandom and Pseudoresource Quantum States", arXiv:2504.17650, (2025).
[53] Bo Zhou, Min Chen, Hongjian Wen, and Huaixin Cao, "Geometric robustness and infidelity of imaginarity", Laser Physics Letters 22 11, 115205 (2025).
[54] Louis Schatzki, "Random Real Valued and Complex Valued States Cannot be Efficiently Distinguished", arXiv:2410.17213, (2024).
[55] Chirag Wadhwa and Mina Doosti, "Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness", arXiv:2405.12085, (2024).
[56] Linshuai Zhang and Nan Li, "Quantifying imaginarity-generating power of quantum channels via averaging", Annals of Physics 490, 170485 (2026).
[57] Álvaro Yángüez, Thomas A. Hahn, and Jan Kochanowski, "Efficient Quantum Measurements: Computational Max- and Measured Rényi Divergences and Applications", IEEE Transactions on Information Theory 72 6, 4085 (2026).
[58] Linshuai Zhang and Nan Li, "Quantifying imaginarity via the quantum optimal transport cost", European Physical Journal Plus 140 7, 669 (2025).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 23:18:32) and SAO/NASA ADS (last updated successfully 2026-08-10 23:18:33). 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.