Unitary complexity in polynomial space
Proving quantum commitments exist unconditionally requires solving either the unitary synthesis problem or the BPP vs NEXP question, linking cryptographic assumptions to classical complexity open problems.
The paper shows that if quantum commitments exist, then either the unitary synthesis problem has no polynomial-time solution or BPP differs from NEXP, making unconditional proofs of quantum commitments at least as hard as longstanding open questions. A general lemma proves every unitary in unitaryPSPACE either resists efficient synthesis relative to any classical oracle or is efficiently synthesizable with an NEXP search oracle; certain oracle separations would imply breakthrough classical lower bounds like NC vs NP. The authors also refine the definitions of unitaryP and unitaryPSPACE, show both garbage-erasing and garbage-allowing implementations coincide, and characterize unitaryPSPACE as transformations whose entries are computable in polynomial space.
- Quantum commitments imply either no fast unitary synthesis or BPP != NEXP
- unitaryPSPACE characterized by polynomial-space computable matrix entries
- unitaryPSPACE can generically erase garbage, a fact that fails relative to unitary oracles
- New robust definitions for unitaryP and unitaryPSPACE proposed
From the original article
1 min read at arxiv.orgWe show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{NEXP}$. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory.
By William Kretschmer · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.