PaperlayerView exact revision on arXiv

Source-linked AI summary

Unitary complexity in polynomial space

William Kretschmer, Ewin Tang

arXiv:2610.03705v2quant-phcs.CCcs.CR

TL;DR

The paper addresses the unclear relationship between quantum cryptographic hardness and classical complexity, alongside the conceptual definitions of unitary complexity classes. It develops and compares unitary-class definitions, characterizes unitaryPSPACE by entrywise computation, and reports that its results connect secure quantum cryptography to longstanding complexity questions.

  • Problem

    Quantum commitments are not known to imply standard complexity-theoretic hardness, and unitary synthesis does not specify how the oracle's complexity relates to the unitary.

    Source: §1 · p. 3

  • Method

    The authors define unitary classes using implementations with and without garbage erasure, compare the resulting classes, and characterize unitaryPSPACE through entrywise computation.

    Source: §2.2 · pp. 7, 9, §3.1 · p. 10, §3.2 · p. 11

  • Results

    The paper concludes that proving computationally secure quantum cryptography is as hard as longstanding complexity problems, and gives unitaryPSPACE an entrywise characterization and generic garbage erasure.

    Source: §3.2 · p. 11, §3.4 · p. 13

  • Takeaways & Limitations

    The authors conclude that unitaryPSPACE is robust, with an entrywise characterization and generic garbage erasure.

    Source: §3.4 · p. 13

    A projective unitary in unitaryPSPACE may encode uncomputable information in its phases, so it need not itself belong to unitaryPSPACE.

    Source: §3.2 · p. 11

Abstract

from arXiv · show

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 problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving $\mathsf{unitaryPSPACE}$ would imply breakthrough classical lower bounds such as $\mathsf{NC} \neq \mathsf{NP}$. Along the way, we propose new definitions for the unitary complexity classes $\mathsf{unitaryP}$ and $\mathsf{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 $\mathsf{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 $\mathsf{unitaryPSPACE}$ can generically erase garbage, a result that provably fails relative to unitary oracles.

1 Introduction

The introduction asks whether quantum cryptographic hardness can connect to classical complexity despite the lack of a known connection for quantum commitments. It presents unitary synthesis as a central open problem and derives conditional consequences for commitments and classical lower bounds.

1 Introduction

  • Quantum commitments are a promising candidate for a minimal primitive underlying quantum cryptography, but they are not known to imply standard complexity-theoretic hardness.The broader motivation is that prior oracle results show substantial quantum cryptography can coexist with easy NP-complete problems [Kre21] [KQST23] [KQT25].Source: §1 · p. 3
  • Unitary synthesis asks whether every unitary can be approximately implemented by a polynomial-time quantum oracle algorithm using some classical oracle.A positive answer would imply that superpolynomial lower bounds for unitary implementation yield superpolynomial hardness for some classical function.Source: §1 · p. 3
  • Falsifiable computationally secure quantum cryptography implies unitaryP ≠ unitaryPSPACE, though it is not known to imply a separation of P and PSPACE.The paper also highlights that synthesis is existential and that lower bounds for Haar-random unitaries may not apply to a particular commitment scheme.Source: §1 · p. 3

1.1 This work

  • If quantum commitments exist, then either unitary synthesis has no polynomial-time solution or BPP ≠ NEXP.An unconditional proof of commitments would therefore resolve at least one of two longstanding open complexity questions.Source: §1.1 · p. 4
  • For every unitary in unitaryPSPACE, either no classical oracle enables efficient synthesis, or an NEXP search oracle does.The lemma is presented as the key step toward the commitments result.Source: §1.1 · p. 4
  • If unitary synthesis holds, then unitaryPSPACE is contained in unitaryP with an FNEXP oracle.FNEXP denotes NEXP search problems; the paper notes it is not known to be separated from PSPACE.Source: §1.1 · p. 4
  • A certain oracle separation involving unitaryPSPACE would imply either a solution to unitary synthesis or a classical lower bound such as NC ≠ NP.The paper notes that the lower-bound implication does not involve relativization.Source: §1.1 · p. 5

2 Detour: (re)defining unitary complexity classes

The paper revisits unitary complexity definitions because prior choices can behave poorly under error reduction and oracle composition. It proposes definitions guided by robustness, consistency, intuition, and composability, while treating clean and garbage-allowing implementations as distinct possibilities.

2.1 Why do we need new definitions?

  • Prior definitions lack generic error reduction, and inverse-error scaling can let an apparently simple unitary reveal a hard computation under repeated oracle use.The paper illustrates this with a phase encoding a hard function that becomes accessible after repeated applications.Source: §2 · p. 5, §2.1 · pp. 5–6
  • Zhandry’s error choices can fail under composition or padding, while non-uniform dependence permits circuit descriptions to vary arbitrarily with the error parameter.The paper argues that scaling complexity with log(1/ε) avoids these issues while preserving gate-set robustness.Source: §2.1 · p. 6, §2.2 · p. 8

2.2 Motivating our definitions

  • The definitions are developed around robustness, consistency, intuitive scope, and composability rather than being chosen backward from desired results.The authors use these criteria to distinguish cosmetic choices from consequential or essential ones.Source: §2.2 · pp. 6–7
  • A unitary problem is a size-indexed sequence of unitaries, and the paper defines both clean implementations and projective implementations that may leave garbage.The clean version returns ancillas to their initial state; the projective version requires the target unitary only on the first register and disregards global phase.Source: §2.2 · p. 7
  • The authors retain both clean and garbage-allowing classes because neither is known to subsume the other, and garbage can yield strictly more power relative to unitary oracles.The paper also notes that the two notions have different treatment of global phase.Source: §2.2 · pp. 7–8
  • The chosen error metrics are equivalent up to polynomial overhead: clean implementations use extensions, while garbage-allowing implementations use dilations or traced-out ancillas.These are worst-case error notions over all inputs.Source: §2.2 · p. 8
  • The definitions require complexity polynomial in n and log(1/ε), with a uniform machine generating the circuit description from n and ε.The paper says larger error scaling can harm composition, while smaller scaling can undermine robustness to gate-set changes.Source: §2.2 · p. 8
  • The framework models algorithms with unitary gates and grants broad oracle access, while a simulation result bounds accumulated garbage to at most n qubits.For projective classes, controlled unitaries are excluded because they would make global phase distinguishable.Source: §2.2 · pp. 9–10

3 Technical overview and further results

The overview relates clean and garbage-allowing unitary implementations, characterizes space-bounded unitary computation through its entries, and connects unitary synthesis to classical complexity and quantum cryptography.

3.1 Comparing unitary and projective unitary classes

  • U is in projUnitaryP exactly when U ⊗ U† or U ⊗ U* is in unitaryP, and U is in unitaryP exactly when cU is in projUnitaryP.These equivalences let proofs use whichever definition is more convenient; the authors note that clean implementations avoid juggling garbage states.Source: §3.1 · pp. 10–11

3.2 Characterizing space-bounded unitary computation

  • unitaryPSPACE membership is equivalent to polynomial-space approximation of every unitary entry, and projUnitaryPSPACE membership guarantees a clean representative up to global phase.The original phase information may encode uncomputable information, so this does not imply that the original U belongs to unitaryPSPACE.Source: §3.2 · p. 11
  • Relative to unitary oracles, garbage erasure can fail: some U in projUnitaryP has no phase-equivalent implementation in unitaryPSPACE relative to U ⊗ U†.The paper relates this failure to the absence of a continuous way to assign a global phase to every projective unitary.Source: §3.2 · p. 12

3.3 Relation to unitary synthesis

  • For every U in unitaryPSPACE, either no classical oracle enables efficient synthesis, or NEXP witness search does.The proof uses an NEXP witness encoding a classical oracle's answers and verifies the resulting implementation against U's entries.Source: §3.3 · p. 12
  • Combining the synthesis lemma with classical complexity results yields further consequences, including different relativization behavior for the AM = NEXP and NC = NP corollaries.For the NC = NP consequence, the discussion notes a collapse of NEXP to PSPACE relative to oracles when queries are only polynomial length.Source: §3.3 · p. 12
  • If unitaryP equals unitaryPSPACE, the statistically optimal measurement for distinguishing an EFI pair becomes efficiently implementable, violating its security against polynomial-time adversaries.The argument uses that an EFI pair consists of efficiently generated, far-apart states that are computationally indistinguishable to polynomial-time quantum adversaries.Source: §3.3 · pp. 12–13

3.4 Discussion

  • The authors present both garbage-free and garbage-allowing definitions as meaningful, require polylogarithmic error dependence, and emphasize the definitions' robust, elegant proofs.They also describe unitaryPSPACE as having an entrywise characterization and generically allowing garbage erasure.Source: §3.4 · p. 13
  • Whether every polynomial-time unitary implementation can erase garbage remains open; the authors report a negative answer relative to a unitary oracle but no unrelativized candidate separation.They also ask whether an explicit hard EFI pair could yield classical circuit lower bounds.Source: §3.4 · p. 13

4 Preliminaries

The preliminaries specify how approximate gate descriptions define quantum circuits, then establish the space-bounded circuit model and its relation to classical PSPACE.

4.1 Quantum circuits

  • FPTEAS gate encodings permit approximation in time polynomial in input length and log 1/ε, while FPSEAS encodings use polynomial space and polynomial-length output.The gate entries are treated as exact channels even though they are accessed computationally through approximations.Source: §4.1 · p. 14
  • A quantum circuit lists the qubits each gate acts on and an FPTEAS encoding of its channel; a unitary circuit restricts gates to unitary superoperators.The circuit description length includes the gate descriptions and acted-on qubit labels.Source: §4.1 · p. 14

4.2 Quantum complexity theory

  • BQPSPACE and BQUPSPACE use length-indexed, space-uniform circuit families on polynomially many qubits, with a designated output qubit measured for acceptance.The length-uniform formulation supports applying algorithms coherently to superpositions of inputs.Source: §4.2 · pp. 14–15
  • BQPSPACE and BQUPSPACE both equal PSPACE, and this equivalence holds relative to classical oracles.The oracle-relative statement is noted as a consequence of the proof's relativization.Source: §4.2 · p. 15
  • The PSPACE simulation approximates entries of the circuit's channel matrix by recursively composing gate matrices and summing products using polynomial space.Choosing sufficiently small entrywise error keeps the total acceptance-probability error low enough to distinguish the promised cases.Source: §4.2 · pp. 15–16
  • A unitary language is a sequence of n-qubit unitaries, and ordinary languages embed into this framework through XOR oracle unitaries.The embedding acts on each input x and answer bit b by XORing the language value into b.Source: §4.2 · p. 16

5 Unitary complexity definitions

This section develops two formulations of unitary complexity—garbage-free classes defined via extensions and projective classes defined via dilations that may leave garbage—and studies their approximation and closure properties. It also relates the formulations by showing how each can be reformulated using the other, including in oracle settings.

5.1 Garbage-free unitary complexity

  • unitaryP and unitaryPSPACE use time- and space-uniform circuit families, respectively, that approximate an extension of the target unitary in operator norm; approximate action on the zero-ancilla subspace suffices for a close extension.The circuit families use at most poly(n, log 1/ε) qubits, and the extension is within ε of the circuit when its action on that subspace is within ε/2.Source: §5.1 · p. 16
  • For K in {P, PSPACE}, unitaryK is closed under conjugation, inverse, transpose, and controlled versions of these transformations.The transformations are implemented gate by gate, using conjugated, inverted, transposed, or controlled gates.Source: §5.1 · p. 17
  • Unitary classes subsume ordinary language classes and are self-low: unitaryK^unitaryK^O = unitaryK^O for K in {P, PSPACE}.The language-subsumption result uses the unitary embedding of a language and the same gates as the unitary-oracle model.Source: §5.1 · pp. 18–19

5.2 Unitary complexity allowing garbage

  • projUnitaryP and projUnitaryPSPACE replace extensions with dilations, allowing a fixed garbage state; approximate implementations and diamond-norm approximations yield close dilations.The respective operator-norm bounds are ε from an ε/2 implementation and 4√ε from an ε-close channel in diamond distance.Source: §5.2 · p. 20
  • For K in {P, PSPACE}, projUnitaryK is closed under conjugation, inverse, and transpose, but not controlled implementation because a dilation can absorb global phase into its garbage state.The controlled-unitary obstruction is inherent: an identity circuit with a halting-dependent garbage phase would make an efficient controlled implementation decide the halting problem.Source: §5.2 · p. 21
  • Projective unitary classes subsume language classes and are self-low for K ∈ {P, PSPACE}.The garbage-allowing definition is also said to satisfy the same desiderata as the preceding definition.Source: §5.2 · pp. 21–22

5.3 Relations between definitions with and without garbage

  • For K ∈ {P, PSPACE}, U is in projUnitaryK exactly when U ⊗ U† or U ⊗ U* is in unitaryK.These characterizations connect garbage-allowing implementations to garbage-erasing ones.Source: §5.3 · p. 22
  • For K ∈ {P, PSPACE}, U is in unitaryK exactly when its controlled embedding cU is in projUnitaryK.This gives a reverse containment characterization of unitaryK using the projective class.Source: §5.3 · p. 23
  • The two definitions are not necessarily equivalent, but statements about either class have equivalent reformulations in terms of the other.The paper describes the classes as isomorphic to subclasses of each other.Source: §5.3 · p. 23
  • The characterizations extend to oracle settings, including the U ⊗ U†, U ⊗ U*, and cU formulations.The corresponding results use paired oracles O ⊗ O† and O ⊗ O*, or the controlled oracle cO.Source: §5.3 · pp. 23–24

6 Characterization of unitaryPSPACE

This section characterizes unitaryPSPACE through polynomial-space approximation of real-valued functions and computation of unitary entries, connecting these characterizations to phase encodings, column preparation, and unitary simulation. It also compares projective and garbage-free implementations, showing their equivalence up to global phase for classical language oracles but not for unitary oracles.

6.1 Approximation in polynomial space

  • A function has an FPUSEAS relative to a unitary language O exactly when it is exponentially bounded and its approximation promise problem lies in BQUPSPACE^O; relative to any language, FPUSEAS and FPSEAS coincide.An FPUSEAS uses space-uniform unitary circuits with polynomially many qubits in the input length and log(1/ε).Source: §6.1 · pp. 24–25
  • A phase encoding fPhase belongs to unitaryPSPACE^O exactly when f has an FPUSEAS relative to O.The phase encoding takes f values in [−π/2, π/2].Source: §6.1 · p. 25
  • If fPhase is in unitaryPSPACE^O, then (g ◦ f)Phase is too when g maps [−π/2, π/2] into itself, has a polylogarithmic modulus of continuity, and has an FPTEAS.Source: §6.1 · p. 27

6.2 Entrywise characterization

  • UEntryPhase belongs to unitaryPSPACE^U, and UColumn belongs to unitaryPSPACE^UEntryPhase.The entry encoding is approximated using a Hadamard test and amplitude estimation; column preparation uses exact amplitude amplification, avoiding direct error accounting. UColumn leaves the input |x⟩ as garbage, so it does not by itself implement U.Source: §6.2 · pp. 27–28
  • U belongs to unitaryPSPACE^UColumn: column access can be used to erase the input register through reflection and exact amplitude amplification.This is the cited result of Rosenthal [Ros26, Theorem 2.2].Source: §6.2 · p. 30
  • Theorem 6.17 gives equivalent entrywise characterizations of unitaryPSPACE.The section also shows that allowing general nonunitary circuits to implement the associated channel does not change projUnitaryPSPACE, since its matrix entries can be approximated with polynomial-space overhead.Source: §6.2 · p. 30

6.3 Erasing garbage

  • For classical language oracles, a unitary is in projUnitaryPSPACE exactly when it equals a unitaryPSPACE transformation up to a sequence of global phases, enabling generic garbage erasure.The proof selects a canonical phase using an entry found by lexicographic search, then uses the entrywise characterization to show the resulting transformation is in unitaryPSPACE.Source: §6.3 · p. 31
  • The phase-based equivalence fails for unitary oracles: a diagonalized unitary has no phase-equivalent representative in unitaryPSPACE relative to U⊗U†, although it is in projUnitaryPSPACE.The proof uses that oracle-circuit behavior is continuous in U⊗U† and that the circuit evaluates its target to nontrivial precision.Source: §6.3 · pp. 33–34

7 Unitary complexity and the unitary synthesis problem

The section studies the unitary synthesis problem and its connections to NEXP witness oracles and cryptographic separations. It relates these topics to separations between unitary complexity classes, including a consequence for BPP and NEXP under the stated assumption.

7 Unitary complexity and the unitary synthesis problem

  • The unitary synthesis problem asks whether unitaryALL = unitaryPALL, or equivalently whether every unitary language can be implemented efficiently relative to some classical oracle.The section’s NEXP relation framework defines witness oracles that return a valid witness whenever one exists.Source: §7 · p. 34, §7.1 · p. 34

7.2 Bounds on unitary synthesis oracles

  • Every U in unitaryPSPACE^L either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized using an FNEXP^L[poly] witness oracle.The witness relation is verified in exponential time, with witnesses of exponential length and L-queries restricted to polynomial length.Source: §7.2 · pp. 34, 36, §7.1 · p. 34
  • If NC = NP, every FNEXP^L[poly] relation has a PSPACE^L witness oracle; if A^L = NEXP^L, every FNEXP^L relation has an EXPTIME^L witness oracle.The combined corollary states that either condition yields PSPACE^L witness oracles for every FNEXP^L[poly] relation.Source: §7.2 · pp. 36–37
  • For a separation between unitaryP^PSPACE^L and unitaryPSPACE^L, the weaker-separation corollary lists BPPL != NEXPL as one possible consequence.The passage identifies this as its second alternative; its first alternative is not included in the supplied text.Source: §7.2 · p. 37

7.3 Implications for cryptography

  • If EFI pairs exist relative to a language L, then unitaryP^L ≠ unitaryPSPACE^L; assuming equality would yield a distinguisher with advantage at least δ/4, contradicting EFI indistinguishability.Source: §7.3 · pp. 38–39
  • The cryptographic implication is BPPL̸ = NEXPL.The proof uses Theorem 7.14 to infer unitaryPL̸ = unitaryPSPACEL under the corollary’s assumption, then applies Corollary 7.11.Source: §7.3 · p. 39

8 AI Disclosure

The authors disclose using ChatGPT in manuscript preparation and in developing proofs for several results. They verified all AI-generated proofs and revised them for clarity.

8 AI Disclosure

  • ChatGPT suggested notation, including for uniform circuit families and the name projUnitaryP, and provided the proof of Lemma 6.22 with minimal author input.For Lemmas 6.11 and 6.15 and Theorem 7.14, it suggested substantially different proofs, which the authors included because they were simpler.Source: §8 · p. 40
  • The authors used ChatGPT interactively on proofs for Lemmas 6.7, 6.11, 6.15, 7.4, and 7.6, and Theorems 6.19, 6.23, and 7.14.They supplied author-conceived proof sketches; for Theorem 6.19, ChatGPT considerably simplified their strategy.Source: §8 · p. 40
  • The authors verified all AI-generated proofs and reworked them for clarity; they used ChatGPT-5.5 except for Theorem 7.14, which used ChatGPT-6.Source: §8 · p. 40

Related papers

Loading 2610.03705v2…