stateQIP = statePSPACE

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.

Authors

• Tony Metger
• Henry Yuen

Keywords

• Computer science
• Quantum algorithm
• Upper bound
• Protocols
• Quantum state
• Encoding
• Complexity theory
• Interactive
• Complex Class
• Semidefinite Programming
• Classical Computer
• Notion Of Complexity
• Quantum Circuit
• Space Of Polynomials
• Quantum Algorithms
• General Quantum
• Operational Units
• Feasible Solution
• Function Approximation
• Mixed State
• Quantum Computing
• Decision Problem
• Density Matrix
• Sequence Of States
• Sign Function
• Hermitian Matrix
• Pure State
• Classical Circuit
• Intermediate Measures
• Polynomial Approximation
• Turing Machine
• Nuclear Norm
• Inverse Error
• Algorithmic Techniques
• quantum complexity
• interactive protocols
• quantum state complexity
• state synthesis
• semi-definite programming
• block encoding