Metraipolis › archive › dc_8d5fa7fd50bc

unitaryQIP = unitaryPSPACE — arXiv:2611.02819

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02819
License (as archived)
CC0-1.0
Archived
2026-11-03T19:01:19.166Z
SHA-256 of the archived text
d240ac4f232446f986100f2f2bed4174ba3b6eb4fc8dd4ff9699ad9b53eb4c7a
Stable URL of this page
https://metraipolis.com/documento/dc_8d5fa7fd50bc

How to cite

unitaryQIP = unitaryPSPACE — arXiv:2611.02819 — arXiv (en), https://arxiv.org/abs/2611.02819 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8d5fa7fd50bc (Metraipolis archive dc_8d5fa7fd50bc, sha256 d240ac4f232446f986100f2f2bed4174ba3b6eb4fc8dd4ff9699ad9b53eb4c7a)
BibTeX
@misc{dc8d5fa7fd50bc,
  title = {unitaryQIP = unitaryPSPACE — arXiv:2611.02819},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02819},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8d5fa7fd50bc; sha256 d240ac4f232446f986100f2f2bed4174ba3b6eb4fc8dd4ff9699ad9b53eb4c7a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02819. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fisica e astronomia (elenco arXiv quant-ph, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2611.02819 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:19:52.833Z dalla pagina https://arxiv.org/list/quant-ph/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).