{"id":"arxiv/2610.03705","url":"https://arxiv.org/abs/2610.03705","tags":["quant-ph","cs.CC","cs.CR"],"score":0,"title":"Unitary complexity in polynomial space","domain":"quant-ph","source":"arxiv","authors":["William Kretschmer","Ewin Tang"],"reviews":0,"subject":"quant-ph","summary":"We 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. We prove our main result as a consequence of a more general lemma, which shows that every unitary in $\\mathsf{unitaryPSPACE}$ either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for $\\mathsf{NEXP}$ search…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-02","reactions":{}}