Unitary complexity in polynomial space
Abstract
We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or BPP ≠ NEXP. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in unitaryPSPACE either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for NEXP search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving unitaryPSPACE would imply breakthrough classical lower bounds such as NC ≠ NP. Along the way, we propose new definitions for the unitary complexity classes unitaryP and unitaryPSPACE. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that unitaryPSPACE has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that unitaryPSPACE can generically erase garbage, a result that provably fails relative to unitary oracles.
Related
- Polynomial-time local-unitary equivalence of graph states
- Quantum Complexity of Ancilla-Free Unitary Embeddings for Nonlinear Dynamics via Generalized State-Dependent Double-Bracket Flows
- Optimal linear-optical interferometers for unitary t-designs in a multi-photon Fock space
- Emergent de Sitter Space and Non-Unitary Tensor Networks from Non-Hermitian Quantum Criticality
- Polynomial Initial-State Jumps and Christoffel Transforms in Krylov Complexity
BibTeX
@misc{kretschmer2026unitary,
title = {{Unitary complexity in polynomial space}},
author = {William Kretschmer and Ewin Tang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03705},
eprint = {2610.03705},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03705},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Unitary complexity in polynomial space
AU - William Kretschmer
AU - Ewin Tang
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.03705
UR - https://arxiv.org/abs/2610.03705
AB - We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or BPP ≠ NEXP. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in unitaryPSPACE either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for NEXP search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving unitaryPSPACE would imply breakthrough classical lower bounds such as NC ≠ NP. Along the way, we propose new definitions for the unitary complexity classes unitaryP and unitaryPSPACE. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that unitaryPSPACE has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that unitaryPSPACE can generically erase garbage, a result that provably fails relative to unitary oracles.
ER -