unitaryQIP = unitaryPSPACE

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 paper asks whether interactive proofs characterize polynomial-space computation for worst-case unitary synthesis: applying a target unitary to an arbitrary unknown quantum input, rather than preparing a fixed state. It proves $\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}$, with both classes defined using arbitrarily inverse-polynomial synthesis error. The interactive characterization has perfect completeness and soundness threshold $1/2$; soundness bounds the conditional output error whenever a prover is accepted above that threshold. For $\mathsf{unitaryQIP}\subseteq\mathsf{unitaryPSPACE}$, an acceptance-rigidity lemma shows that soundness constrains a fixed prover’s acceptance probability across inputs. This allows a polynomial-space prover optimized for the all-zero input to work on every input. The simulation incurs error at most $c+\varepsilon+7\delta$, under stated completeness–soundness gap conditions. For the reverse inclusion, the construction builds on a recently announced positive solution to the unitary synthesis problem, establishing that polynomial-space unitaries admit polynomial-size synthesis circuits querying a fixed $\mathsf{PSPACE}$ language. Oracle queries are replaced by adaptive phase-state injection, with resource states verified through existing state-synthesis protocols. Quantitatively, $\mathsf{unitaryPSPACE}_{\delta^2/2^{14}}\subseteq\mathsf{unitaryQIP}_{0,s,\delta}$ for inverse-polynomially bounded parameters. Further results give three-round synthesis with polynomially many input copies and show that EFI pairs imply $\mathsf{BQP}\ne\mathsf{PSPACE}$, using polynomial-space Helstrom measurements and oracle synthesis. The three-round result does not establish constant-round synthesis with one input copy. Single-copy gap amplification, constant-round parallelization, and complete problems for the worst-case synthesis classes remain open.