arXiv preprint ·
unitaryQIP = unitaryPSPACE
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Unitary synthesis complexity studies the computational cost of applying a target unitary to an unknown quantum state, extending complexity theory beyond its traditional focus on problems with classical inputs and outputs. Rosenthal and Yuen (ITCS 2022) introduced two complexity classes for unitary synthesis: $\mathsf{unitaryQIP}$ and $\mathsf{unitaryPSPACE}$ for the unitary families implementable via interactive proofs and in polynomial space, respectively. In this work, we prove the equality $\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}$ and thereby establish a unitary-complexity analogue of $\mathsf{QIP} = \mathsf{PSPACE}$ (Jain, Ji, Upadhyay, and Watrous, J. ACM 2011) and $\mathsf{stateQIP}=\mathsf{statePSPACE}$ (Rosenthal and Yuen, ITCS 2022; Metger and Yuen, FOCS 2023). To prove $\mathsf{unitaryQIP} \subseteq \mathsf{unitaryPSPACE}$, we use an acceptance rigidity lemma derived from the soundness condition to show that the polynomial-space prover constructed for a fixed input in state synthesis (Metger and Yuen, FOCS 2023) implements the target unitary on every input, leading to a polynomial-space simulation of the protocol. For the reverse inclusion, we build on OpenAI's recently announced solution to the unitary synthesis problem (Aaronson and Kuperberg, Theory Comput. 2007), and show that $\mathsf{unitaryPSPACE}$ families can be synthesized in polynomial time with a $\mathsf{PSPACE}$ oracle. We then implement the oracle queries using auxiliary states prepared via the $\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}$ protocol (Rosenthal and Yuen, ITCS 2022). Beyond the equality, we show that our protocol for $\mathsf{unitaryPSPACE}$ can be parallelized to constant rounds when the verifier receives polynomially many copies of the input, and we also obtain a complexity-theoretic barrier to proving the existence of $\mathsf{EFI}$ pairs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Achievability of CSS codes performance limits over Pauli channels under separate ML decoding with bounded graphical complexity
Anti-distinguishability of quantum channels
MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits
Entanglement Allocation for Quantum Integrated Sensing and Communication
Quantum simulation of dissipative acoustic and elastic waves by Schrödingerisation: absorbing boundaries and explicit polynomial-size circuits
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.