stateQIP = statePSPACE

Understand

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 polynomial-time 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.