Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2301.07730 · Annual Symposium on Foundations of Computer Science

stateQIP = statePSPACE

Tony Metger, Henry Yuen

Published Nov 6, 2023• 11 citations
arXivHTMLPDF

Abstract

Complexity theory traditionally studies the hardness of solving classical computational problems. In the quantum setting, it is also natural to consider a different notion of complexity, namely the complexity of physically preparing a certain quantum state. We study the relation between two such state complexity classes: statePSPACE, which contains states that can be generated by space-uniform polynomial-space quantum circuits, and stateQIP, which contains states that a polynomialtime quantum verifier can generate by interacting with an all-powerful untrusted quantum prover. The latter class was recently introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE $\subseteq$ stateQIP.Our main result is the reverse inclusion, stateQIP $\subseteq$ statePSPACE, thereby establishing equality of the two classes and providing a natural state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum algorithm for solving a large class of exponentially large “PSPACE-computable” semidefinite programs (SDPs), which also prepares an optimiser encoded in a quantum state. Our SDP solver relies on recent blockencoding techniques from quantum algorithms, demonstrating that these techniques are also useful for complexity theory.Using similar techniques, we also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum polynomial space. We prove this by studying an algorithmic version of Uhlmann’s theorem and establishing an upper bound on the complexity of implementing Uhlmann transformations.

DOI
10.1109/focs57990.2023.00082

Related papers

Quantum Merlin-Arthur proof systems for synthesizing quantum states

Hugo Delavenne, François Le Gall, Yupan Liu +1 more

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 NP , referred to as 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 stateQIP recently introduced by Rosenthal and Yuen (ITCS 2022) \cite{RY22}, 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 ( stateBQP ) and space-uniform polynomial-space quantum circuits ( statePSPACE ). Furthermore, we establish that the family of UQMA witnesses, considered as one of the most natural candidates for stateQMA containments, is in stateQMA . Additionally, we demonstrate that stateQCMA achieves perfect completeness.

arXiv:2303.01877•Quantum•Apr 3, 2025•1 citation

Unitary Complexity and the Uhlmann Transformation Problem

John Bostanci, Yuval Efron, Tony Metger +3 more

State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann's theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.

arXiv:2306.13073•Leibniz international proceedings in informatics•Jun 22, 2023•2 citations

A slightly improved upper bound for quantum statistical zero-knowledge

François Le Gall, Yupan Liu, Qisheng Wang

The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$, which was simplified following the inclusion $\mathsf{QIP(2)} \subseteq \mathsf{PSPACE}$ established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, $\mathsf{QIP(2)}$ denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and $\text{co-}\mathsf{QIP(2)}$ denotes the complement of $\mathsf{QIP(2)}$. We slightly improve this upper bound to $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$ with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original $\mathsf{QSZK}$ proof system. A similar improvement also applies to the upper bound for the non-interactive variant $\mathsf{NIQSZK}$. Our main techniques are algorithmic versions of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).

quant-pharXiv:2512.11597•Leibniz international proceedings in informatics•Dec 15, 2025•0 citations

Quantum State and Unitary Complexity

Gregory Rosenthal

Many natural problems in quantum computing involve constructing a quantum state or implementing a unitary transformation. However, relatively little is known about the computational complexity of these problems compared to that of computing boolean functions. In this thesis we do the following:• We prove upper bounds on the complexity of constructing arbitrary states and implementing arbitrary unitaries with the help of a classical oracle. • We prove bounds on the complexity of computing parity in QAC0, a quantum analogue of AC0, by way of a reduction to the task of constructing a certain type of state. • We prove upper bounds on the circuit size and depth required to construct arbitrary states and implement arbitrary unitaries, in various quantum circuit models. Many of these bounds are tight. • We define models of interactive proofs for constructing states and implementing unitaries with the help of an untrusted prover. We prove a quantum state analogue of the inclusion PSPACE ⊆ QIP, and obtain somewhat analogous results for unitaries and with multiple entangled provers. • We present barriers to improving several of the above results.

•Nov 1, 2023•0 citations

A Relativizing MIP for BQP

Scott Aaronson, Anand Natarajan, Avishay Tal +1 more

Complexity class containments involving interactive proof classes are famously nonrelativizing: although $\mathsf{IP} = \mathsf{PSPACE}$, Fortnow and Sipser showed that that there exists an oracle relative to which $\mathsf{coNP} \not\subseteq \mathsf{IP}$. In contrast, the question of whether the containment $\mathsf{BQP} \subseteq \mathsf{IP}$ is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment $\mathsf{BQP} \subseteq \mathsf{MIP}$ holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle $O$, a $\mathsf{PCP}$ proof system for $\mathsf{BQP}^{O}$ where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle $O$. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an $\mathsf{IP}$ for $\mathsf{BQP}$ in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.

quant-pharXiv:2604.11952•Apr 15, 2026•0 citations

Interactive Proofs for Synthesizing Quantum States and Unitaries

Gregory Rosenthal, Henry Yuen

Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomial-time quantum verifier interacts with an untrusted quantum prover, and a verifier who accepts also outputs an approximation of the target state (for the state synthesis problem) or the result of the target unitary applied to the input state (for the unitary synthesis problem); furthermore there should exist an "honest" prover which the verifier accepts with probability 1. Our main result is a "state synthesis" analogue of the inclusion $\mathsf{PSPACE} \subseteq \mathsf{IP}$: any sequence of states computable by a polynomial-space quantum algorithm (which may run for exponential time) admits an interactive protocol of the form described above. Leveraging this state synthesis protocol, we also give a unitary synthesis protocol for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.

arXiv:2108.07192•Leibniz international proceedings in informatics•Aug 16, 2021•6 citations
Complexity theory traditionally studies the hardness of solving classical computational problems. In the quantum setting, it is also natural to consider a different notion of complexity, namely the complexity of physically preparing a certain quantum state. We study the relation between two such state complexity classes: statePSPACE, which contains states that can be generated by space-uniform polynomial-space quantum circuits, and stateQIP, which contains states that a polynomialtime quantum verifier can generate by interacting with an all-powerful untrusted quantum prover. The latter class was recently introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE ⊆\subseteq⊆ stateQIP.Our main result is the reverse inclusion, stateQIP ⊆\subseteq⊆ statePSPACE, thereby establishing equality of the two classes and providing a natural state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum algorithm for solving a large class of exponentially large “PSPACE-computable” semidefinite programs (SDPs), which also prepares an optimiser encoded in a quantum state. Our SDP solver relies on recent blockencoding techniques from quantum algorithms, demonstrating that these techniques are also useful for complexity theory.Using similar techniques, we also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum polynomial space. We prove this by studying an algorithmic version of Uhlmann’s theorem and establishing an upper bound on the complexity of implementing Uhlmann transformations.
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 NP , referred to as 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 stateQIP recently introduced by Rosenthal and Yuen (ITCS 2022) \cite{RY22}, 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 ( stateBQP ) and space-uniform polynomial-space quantum circuits ( statePSPACE ). Furthermore, we establish that the family of UQMA witnesses, considered as one of the most natural candidates for stateQMA containments, is in stateQMA . Additionally, we demonstrate that stateQCMA achieves perfect completeness.
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann's theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
The complexity class Quantum Statistical Zero-Knowledge (QSZK\mathsf{QSZK}QSZK), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound QIP(2)∩co-QIP(2)\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}QIP(2)∩co-QIP(2), which was simplified following the inclusion QIP(2)⊆PSPACE\mathsf{QIP(2)} \subseteq \mathsf{PSPACE}QIP(2)⊆PSPACE established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, QIP(2)\mathsf{QIP(2)}QIP(2) denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and co-QIP(2)\text{co-}\mathsf{QIP(2)}co-QIP(2) denotes the complement of QIP(2)\mathsf{QIP(2)}QIP(2). We slightly improve this upper bound to QIP(2)∩co-QIP(2)\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}QIP(2)∩co-QIP(2) with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original QSZK\mathsf{QSZK}QSZK proof system. A similar improvement also applies to the upper bound for the non-interactive variant NIQSZK\mathsf{NIQSZK}NIQSZK. Our main techniques are algorithmic versions of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).
Many natural problems in quantum computing involve constructing a quantum state or implementing a unitary transformation. However, relatively little is known about the computational complexity of these problems compared to that of computing boolean functions. In this thesis we do the following:• We prove upper bounds on the complexity of constructing arbitrary states and implementing arbitrary unitaries with the help of a classical oracle. • We prove bounds on the complexity of computing parity in QAC0, a quantum analogue of AC0, by way of a reduction to the task of constructing a certain type of state. • We prove upper bounds on the circuit size and depth required to construct arbitrary states and implement arbitrary unitaries, in various quantum circuit models. Many of these bounds are tight. • We define models of interactive proofs for constructing states and implementing unitaries with the help of an untrusted prover. We prove a quantum state analogue of the inclusion PSPACE ⊆ QIP, and obtain somewhat analogous results for unitaries and with multiple entangled provers. • We present barriers to improving several of the above results.
Complexity class containments involving interactive proof classes are famously nonrelativizing: although IP=PSPACE\mathsf{IP} = \mathsf{PSPACE}IP=PSPACE, Fortnow and Sipser showed that that there exists an oracle relative to which coNP⊈IP\mathsf{coNP} \not\subseteq \mathsf{IP}coNP⊆IP. In contrast, the question of whether the containment BQP⊆IP\mathsf{BQP} \subseteq \mathsf{IP}BQP⊆IP is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment BQP⊆MIP\mathsf{BQP} \subseteq \mathsf{MIP}BQP⊆MIP holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle OOO, a PCP\mathsf{PCP}PCP proof system for BQPO\mathsf{BQP}^{O}BQPO where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle OOO. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an IP\mathsf{IP}IP for BQP\mathsf{BQP}BQP in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.
Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomial-time quantum verifier interacts with an untrusted quantum prover, and a verifier who accepts also outputs an approximation of the target state (for the state synthesis problem) or the result of the target unitary applied to the input state (for the unitary synthesis problem); furthermore there should exist an "honest" prover which the verifier accepts with probability 1. Our main result is a "state synthesis" analogue of the inclusion PSPACE⊆IP\mathsf{PSPACE} \subseteq \mathsf{IP}PSPACE⊆IP: any sequence of states computable by a polynomial-space quantum algorithm (which may run for exponential time) admits an interactive protocol of the form described above. Leveraging this state synthesis protocol, we also give a unitary synthesis protocol for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.