Quantum Merlin-Arthur proof systems for synthesizing quantum states

Hugo Delavenne; François Le Gall; Yupan Liu; Masayuki Miyamoto

doi:10.22331/q-2025-04-03-1688

Quantum Merlin-Arthur proof systems for synthesizing quantum states

Hugo Delavenne^1,2, François Le Gall¹, Yupan Liu¹, and Masayuki Miyamoto¹

¹Graduate School of Mathematics, Nagoya University
²ENS Paris-Saclay, Université Paris-Saclay

Published:	2025-04-03, volume 9, page 1688
Editor:	Tom Gur
Eprint:	arXiv:2303.01877v4
Doi:	https://doi.org/10.22331/q-2025-04-03-1688
Citation:	Quantum 9, 1688 (2025).

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

Abstract

Complexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it is natural to apply a different notion of complexity, namely the complexity of synthesizing quantum states. We investigate a state-synthesizing counterpart of the class $\sf{NP}$, referred to as $\sf{stateQMA}$, which is concerned with preparing certain quantum states through a polynomial-time quantum verifier with the aid of a single quantum message from an all-powerful but untrusted prover. This is a subclass of the class $\sf{stateQIP}$ recently introduced by Rosenthal and Yuen (ITCS 2022) [57], which permits polynomially many interactions between the prover and the verifier. Our main result consists of error reduction of this class and its variants with an exponentially small gap or bounded space, as well as how this class relates to other fundamental state synthesizing classes, i.e., states generated by uniform polynomial-time quantum circuits ($\sf{stateBQP}$) and space-uniform polynomial-space quantum circuits ($\sf{statePSPACE}$). Furthermore, we establish that the family of $\sf{UQMA}$ witnesses, considered as one of the most natural candidates for $\sf{stateQMA}$ containments, is in $\sf{stateQMA}$. Additionally, we demonstrate that $\sf{stateQCMA}$ achieves perfect completeness.

Featured image: stateQMA verification circuit

► BibTeX data

@article{Delavenne2025quantummerlinarthur,
  doi = {10.22331/q-2025-04-03-1688},
  url = {https://doi.org/10.22331/q-2025-04-03-1688},
  title = {Quantum {M}erlin-{A}rthur proof systems for synthesizing quantum states},
  author = {Delavenne, Hugo and Le Gall, Fran{\c{c}}ois and Liu, Yupan and Miyamoto, Masayuki},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1688},
  month = apr,
  year = {2025}
}

► References

[1] Scott Aaronson. Quantum copy-protection and quantum money. In Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity. pages 229–242. IEEE. 2009.
https://doi.org/10.1109/CCC.2009.42

[2] Scott Aaronson. The complexity of quantum states and transformations: from quantum money to black holes. arXiv preprint. 2016.
arXiv:1607.05256

[3] Dorit Aharonov, Michael Ben-Or, Fernando GSL Brandao, and Or Sattath. The pursuit of uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings. Quantum. 6:668. 2022.
https://doi.org/10.22331/q-2022-03-17-668

[4] Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica. 55(3):395–421. 2009.
https://doi.org/10.1007/s00453-008-9168-0

[5] Johannes Bausch and Elizabeth Crosson. Analysis and limitations of modified circuit-to-Hamiltonian constructions. Quantum. 2:94. 2018.
https://doi.org/10.22331/q-2018-09-19-94

[6] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proceedings of the forty-sixth annual ACM Symposium on Theory of Computing. pages 283–292. 2014.
https://doi.org/10.1145/2591796.2591854

[7] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters. 114(9):090502. 2015.
https://doi.org/10.1103/PhysRevLett.114.090502

[8] Dominic W Berry, Andrew M Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. pages 792–809. IEEE. 2015.
https://doi.org/10.1109/FOCS.2015.54

[9] Thomas C Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, and Henry Yuen. Good approximate quantum LDPC codes from spacetime circuit Hamiltonians. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. pages 481–490. 2019.
https://doi.org/10.1145/3313276.3316384

[10] John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen. Unitary complexity and the Uhlmann transformation problem. arXiv preprint. 2023.
arXiv:2306.13073

[11] Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear T complexity. Physical Review X. 8(4):041015. 2018.
https://doi.org/10.1103/PhysRevX.8.041015

[12] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy. Finding angles for quantum signal processing with machine precision. arXiv preprint. 2020.
arXiv:2003.02831

[13] Léo Colisson, Frédéric Grosshans, and Elham Kashefi. Non-destructive zero-knowledge proofs on quantum states, and multi-party generation of authorized hidden GHZ states. arXiv preprint. 2021.
arXiv:2104.04742

[14] Marcos Crichigno and Tamara Kohler. Clique Homology is $\mathsf{QMA}_1$-hard. Nature Communications. 15(1):9846. 2024.
https://doi.org/10.1038/s41467-024-54118-z

[15] Léo Colisson, Garazi Muguruza, and Florian Speelman. Oblivious transfer from zero-knowledge proofs - or how to achieve round-optimal quantum oblivious transfer and zero-knowledge proofs on quantum states. In Advances in Cryptology – ASIACRYPT 2023 : 29th International Conference on the Theory and Application of Cryptology and Information Security. volume 14445. pages 3–38. Springer. 2023.
https://doi.org/10.1007/978-981-99-8742-9_1

[16] Richard P Feynman. Simulating physics with computers. International Journal of Theoretical Physics. 21(6-7):467–488. 1982.
https://doi.org/10.1201/9780429500459-11

[17] Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura. Space-efficient error reduction for unitary quantum computations. In 43rd International Colloquium on Automata, Languages, and Programming. volume 55. page 14. 2016.
https://doi.org/10.4230/LIPIcs.ICALP.2016.14

[18] Bill Fefferman and Cedric Lin. Quantum Merlin Arthur with exponentially small gap. arXiv preprint. 2016.
arXiv:1601.01975

[19] Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quantum space. In 9th Innovations in Theoretical Computer Science Conference. volume 94. page 4. 2018.
https://doi.org/10.4230/LIPIcs.ITCS.2018.4

[20] Christopher A Fuchs and Jeroen van de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Transactions on Information Theory. 45(4):1216–1227. 1999.
https://doi.org/10.1109/18.761271

[21] Bill Fefferman and Zachary Remscrim. Eliminating intermediate measurements in space-bounded quantum computation. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. pages 1343–1356. 2021.
https://doi.org/10.1145/3406325.3451051

[22] András Gilyén. Quantum singular value transformation & its algorithmic applications. PhD thesis. University of Amsterdam. 2019. URL: https://hdl.handle.net/11245.1/20e9733e-6014-402d-afa9-20f3cc4a0568. Appearances:.
https://hdl.handle.net/11245.1/20e9733e-6014-402d-afa9-20f3cc4a0568

[23] Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008.
https://doi.org/10.1017/CBO9780511804106

[24] Uma Girish and Ran Raz. Eliminating intermediate measurements using pseudorandom generators. In 13th Innovations in Theoretical Computer Science Conference. volume 215. pages 76:1–76:18. 2022.
https://doi.org/10.4230/LIPIcs.ITCS.2022.76

[25] Sevag Gharibian and Dorian Rudolph. Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement. In 14th Innovations in Theoretical Computer Science Conference. volume 251. pages 53:1–53:23. 2023.
https://doi.org/10.4230/LIPIcs.ITCS.2023.53

[26] Uma Girish, Ran Raz, and Wei Zhan. Quantum logspace algorithm for powering matrices with bounded norm. In 48th International Colloquium on Automata, Languages, and Programming. volume 198. pages 73:1–73:20. 2021.
https://doi.org/10.4230/LIPIcs.ICALP.2021.73

[27] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. pages 193–204. 2019.
https://doi.org/10.1145/3313276.3316366

[28] Jeongwan Haah. Product decomposition of periodic functions in quantum signal processing. Quantum. 3:190. 2019.
https://doi.org/10.22331/q-2019-10-07-190

[29] Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum search-to-decision reductions and the state synthesis problem. In Proceedings of the 37th Computational Complexity Conference. pages 1–19. 2022.
https://doi.org/10.4230/LIPIcs.CCC.2022.5

[30] Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. $\mathsf{QIP}=\mathsf{PSPACE}$. Journal of the ACM. 58(6):1–27. 2011.
https://doi.org/10.1145/2049697.2049704

[31] Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang. On the power of a unique quantum witness. Theory of Computing. 8(1):375–400. 2012.
https://doi.org/10.4086/toc.2012.v008a017

[32] Stephen P Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura. Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information & Computation. 12(5-6):461–471. 2012.
https://doi.org/10.26421/QIC12.5-6-7

[33] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Advances in Cryptology–CRYPTO 2018: 38th Annual International Cryptology Conference. pages 126–152. Springer. 2018.
https://doi.org/10.1007/978-3-319-96878-0_5

[34] Stephen P Jordan and Daniel Nagaj. $\mathsf{QCMA}$ with one-sided error equals $\mathsf{QCMA}$ with two-sided error. arXiv preprint. 2011.
arXiv:1111.5306v1

[35] Camille Jordan. Essai sur la géométrie á $n$ dimensions. Bulletin de la Société mathématique de France. 3:103–174. 1875.
https://doi.org/10.24033/bsmf.90

[36] Alastair Kay. Tutorial on the quantikz package. arXiv preprint. 2018.
arXiv:1809.03842

[37] Alexei Yu Kitaev. Quantum measurements and the Abelian stabilizer problem. arXiv preprint. 1995.
arXiv:quant-ph/9511026

[38] Alexei Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys. 52(6):1191. 1997.
https://doi.org/10.1070/rm1997v052n06abeh002155

[39] Alexei Y. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. Classical and quantum computation. volume 47 of Graduate Studies in Mathematics. American Mathematical Society. 2002.
https://doi.org/10.1090/gsm/047

[40] Greg Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing. 11(1):183–219. 2015.
https://doi.org/10.4086/toc.2015.v011a006

[41] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by uniform spectral amplification. arXiv preprint. 2017.
arXiv:1707.05391

[42] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum. 3:163. 2019.
https://doi.org/10.22331/q-2019-07-12-163

[43] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM. 39(4):859–868. 1992.
https://doi.org/10.1145/146585.146605

[44] Yulong Li. A simple proof of $\mathsf{PreciseQMA}=\mathsf{PSPACE}$. arXiv preprint. 2022.
arXiv:2206.09230

[45] Seth Lloyd. Universal quantum simulators. Science. 273(5278):1073–1078. 1996.
https://doi.org/10.1126/science.273.5278.1073

[46] François Le Gall, Yupan Liu, and Qisheng Wang. Space-bounded quantum state testing via space-efficient quantum singular value transformation. arxiv preprint. 2023.
arXiv:2308.05079

[47] François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed Merlin-Arthur synthesis of quantum states and its applications. In 48th International Symposium on Mathematical Foundations of Computer Science. volume 272. pages 63:1–63:15. 2023.
https://doi.org/10.4230/LIPIcs.MFCS.2023.63

[48] David A Levin and Yuval Peres. Markov chains and mixing times. volume 107. American Mathematical Society. 2017.
https://doi.org/10.1090/mbk/107

[49] Dieter van Melkebeek and Thomas Watson. Time-space efficient simulations of quantum computations. Theory of Computing. 8(1):1–51. 2012.
https://doi.org/10.4086/toc.2012.v008a001

[50] Chris Marriott and John Watrous. Quantum Arthur–Merlin games. computational complexity. 14(2):122–152. 2005.
https://doi.org/10.1007/s00037-005-0194-x

[51] Tony Metger and Henry Yuen. $\mathsf{stateQIP}=\mathsf{statePSPACE}$. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science. pages 1349–1356. IEEE. 2023.
https://doi.org/10.1109/FOCS57990.2023.00082

[52] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge University Press. 2010.
https://doi.org/10.1017/CBO9780511976667

[53] Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of $\mathsf{QMA}$. Quantum Information & Computation. 9(11):1053–1068. 2009.
https://doi.org/10.26421/QIC9.11-12-8

[54] David Poulin and Pawel Wocjan. Preparing ground states of quantum many-body systems on a quantum computer. Physical Review Letters. 102(13):130503. 2009.
https://doi.org/10.1103/PhysRevLett.102.130503

[55] Oded Regev. Witness-preserving amplification of $\mathsf{QMA}$. https://cims.nyu.edu/ regev/teaching/quantum_fall_2005/ln/qma.pdf. 2006.
https://cims.nyu.edu/~regev/teaching/quantum_fall_2005/ln/qma.pdf

[56] Gregory Rosenthal. Efficient quantum state synthesis with one query. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. pages 2508–2534. SIAM. 2024.
https://doi.org/10.1137/1.9781611977912.89

[57] Gregory Rosenthal and Henry Yuen. Interactive proofs for synthesizing quantum states and unitaries. In 13th Innovations in Theoretical Computer Science Conference. volume 215. pages 112:1–112:4. 2022.
https://doi.org/10.4230/LIPIcs.ITCS.2022.112

[58] Adi Shamir. $\mathsf{IP}=\mathsf{PSPACE}$. Journal of the ACM. 39(4):869–877. 1992.
https://doi.org/10.1145/146585.146609

[59] Yaoyun Shi. Both toffoli and controlled-not need little help to do universal quantum computing. Quantum Information & Computation. 3(1):84–92. 2003.
https://doi.org/10.26421/QIC3.1-7

[60] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Information and Computation. 82(1):93–133. 1989.
https://doi.org/10.1016/0890-5401(89)90067-9

[61] Mikhail Vyalyi. $\mathsf{QMA}=\mathsf{PP}$ implies that $\mathsf{PP}$ contains $\mathsf{PH}$. In Electronic Colloquium on Computational Complexity. Citeseer. 2003.
https://eccc.weizmann.ac.il/report/2003/021

[62] John Watrous. Limits on the power of quantum statistical zero-knowledge. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. pages 459–468. IEEE. 2002.
https://doi.org/10.1109/SFCS.2002.1181970

[63] John Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing. 39(1):25–58. 2009.
https://doi.org/10.1137/060670997

[64] Huangjun Zhu and Masahito Hayashi. Efficient verification of pure quantum states in the adversarial scenario. Physical Review Letters. 123(26):260504. 2019.
https://doi.org/10.1103/PhysRevLett.123.260504

Cited by

[1] Yuki Takeuchi, "Catalytic Transformation from Computationally Universal to Strictly Universal Measurement-Based Quantum Computation", Physical Review Letters 133 5, 050601 (2024).

[2] Alex Lombardi, Fermi Ma, and John Wright, "A one-query lower bound for unitary synthesis and breaking quantum cryptography", arXiv:2310.08870, (2023).

[3] Tony Metger and Henry Yuen, "stateQIP = statePSPACE", arXiv:2301.07730, (2023).

[4] François Le Gall, Yupan Liu, Harumichi Nishimura, and Qisheng Wang, "Space-bounded quantum interactive proof systems", arXiv:2410.23958, (2024).

[5] Hugo Delavenne and François Le Gall, "Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction", arXiv:2407.02907, (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-19 14:18:38). 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 2026-08-19 14:18:36).

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.