Explicit Separations for One-Query Unitary Synthesis

AI summary

Overview

Research area: Quantum complexity theory and quantum cryptography — specifically the query complexity of unitary synthesis (the Aaronson–Kuperberg problem) and new cryptographic games used to prove oracle separations.

Technical level: Advanced. The paper is written for researchers in quantum complexity, quantum query algorithms, and quantum cryptography; it assumes familiarity with unitaries, oracles, diamond distance, and cryptographic game-based reductions.

Scope (1 sentence): The paper proves that several explicit, structured families of unitaries (random permutations, alternating-basis phase unitaries, and interleavings with a fixed unitary) cannot be synthesized by any efficient algorithm making a single classical oracle query, while proving a matching upper bound for complex phase unitaries.

What This Paper Is About

The unitary synthesis problem, introduced by Aaronson and Kuperberg in 2007, asks whether every n-qubit unitary U can be implemented by poly(n)-size quantum circuits given access to some classical oracle f = f_U that depends on U. Prior work (Lombardi–Ma–Wright, STOC 2024) ruled out one-query synthesis for Haar-random unitaries — that is, for unitaries with enormous randomness complexity — leaving open whether "explicit" families with efficient (even two-query) synthesis algorithms could also be separated. This paper answers that question affirmatively for permutations and for F₂ H^{⊗n} F₁ unitaries, and also shows that one natural candidate family — complex phase unitaries — is actually easy for one-query algorithms, giving a constant-factor approximation.

Key Contributions

1. One-query lower bounds for explicit unitaries. The authors prove that random n-qubit permutation unitaries P|x⟩ = |π(x)⟩ (Theorem 1.1) and unitaries of the form F₂ H F₁ for random Boolean phase functions F₁, F₂ (Theorem 1.2) admit no efficient one-query synthesis algorithm, with the latter extending to F_t H … F₂ H F₁ for more alternations (Theorem 1.3, Corollary 5.3). Both families have trivial two-query synthesis algorithms, so these are separations between one-query and two-query unitary synthesis.

2. A new hardness framework: the oracle state search game and oracle Choi state game. Rather than deriving lower bounds from state pseudorandomness as in prior work, the authors introduce (Definition 4.1) a challenger–adversary search game — the challenger sends |ψ_k⟩ for k ← [K] and the adversary must return k — and a harder "oracle Choi state game" (Definition 4.7) based on the Choi state of U†. Hardness of these games suffices to rule out unitary synthesis, and the search game variant they use is a single-copy variant of a one-way state generator (citing [MY22]) strong enough to imply quantum bit commitment ([BCQ23]).

3. An upper bound contradicting the lower-bound technique's reach. For complex phase unitaries |x⟩ ↦ α_x|x⟩ with α: {0,1}ⁿ → S¹, the authors give a Ω(1)-approximate (in diamond distance, Definition 3.4) one-query synthesis algorithm (Theorem 1.5), plus a composition theorem (Corollary 1.6) showing that a (3/4 + ε)-correct one-query algorithm relative to complex phase unitaries implies an Ω(ε²)-correct one-query algorithm relative to binary phase unitaries or Boolean functions.

4. A simplified proof of the prior state-of-the-art bound and a new quantum-advice separation. The search-game analysis yields a simpler proof of the [LMW24] general-purpose one-query lower bound (Theorem 1.12, extended to Haar-random U in Theorem A.4), and a new hardness-of-approximation result for "quantum programs": a zero-query algorithm using S qubits of advice succeeds with probability ε ≤ O(S/K) (Theorem 1.13).

Main Findings

• Permutations are hard in one query: For a uniformly random permutation π on {0,1}ⁿ and the state family {PH|k⟩} indexed by k ∈ [K] \ {0}, every one-query adversary with workspace dimension M satisfies 𝔼_π[Win(𝒜|π)] = O(log²M · log²K / K) (Theorem 1.9, Theorem 5.1).
• F₂HF₁ is hard in one query: For uniformly random Boolean f₁, f₂ and F_j = Σ_x (−1)^{f_j(x)}|x⟩⟨x|, the search game on {F₂HF₁H|k⟩} gives 𝔼_{f₁,f₂}[Win(𝒜|f₁,f₂)] = O(log M · log(MN) / K) (Theorem 1.10, Theorem 5.2). The result extends to F_t H … F₂ H F₁ (Theorem 1.3) and to F₂ U₀ F₁ for a fixed unitary U₀ whose entries are all small — for example a tensor power of a one-qubit unitary with all four entries bounded away from 0 (Theorem C.2).
• Pseudorandomness provably fails where the search game succeeds: For permutations, there exists a one-query adversary that, for every permutation unitary P, has some classical oracle f_π relative to which it distinguishes {PH|k⟩}_{k∈[2^{n/2}]} from Haar-random input with constant advantage (Theorem 1.11). This demonstrates why the [LMW24] decision-to-search route cannot prove these results and why the search game is the right tool.
• Complex phase unitaries are easy in one query: Despite having a clean two-query "compute-then-uncompute" algorithm with no obvious one-query shortcut, arbitrary diagonal phase unitaries admit an Ω(1)-approximate one-query synthesis algorithm (Theorem 1.5, Theorem 5.5). This explains why existing lower-bound techniques — which rule out approximation algorithms too — cannot apply to complex phase unitaries.
• Simplified proof for i.i.d. binary phase states: Any one-query adversary with workspace dimension M wins the search game for |ψ_{R,k}⟩ = (1/√N) Σ_x R(k,x)|x⟩ with probability at most (2 log M + O(1))/K (Theorem 1.12, Theorem A.1); the analysis extends to states U|k⟩ for Haar-random U (Theorem A.4).
• Separation from quantum programs: For a uniformly random f: {0,1}ⁿ → {0,1}, a zero-query non-uniform algorithm using S qubits of advice that must output k from one copy of FH|k⟩ succeeds with probability ε ≤ O(S/K) (Theorem 1.13, Theorem 5.7). This is tight up to constants when K = Ω(N), and Section 10.5 shows tightness over the entire range of S. The paper notes this search game is asymptotically harder than the "classical" game on states |x⟩|y ⊕ f(x)⟩, whose trivial algorithm wins with probability 2^{−ℓ} for output length ℓ.
• A general open frontier: Proving one-query lower bounds against algorithms that receive quantum advice before querying remains open for every family considered — permutations, F₂H^{⊗n}F₁, and Haar-random U; the present proofs handle only classical advice.

Methodology in Plain English

The starting point is a "game" reformulation of hardness. Instead of asking directly whether an algorithm can implement a unitary U, the authors ask whether it can win a guessing game: a challenger picks a random index k, hands over a quantum state |ψ_k⟩ that depends on the hidden U (and on a classical oracle), and the algorithm must return k. If implementing U† were easy, winning this game would be easy — so an upper bound on the win probability is a lower bound on synthesis.

The authors then model any one-query algorithm in a standard normal form: a fixed isometry V, followed by a phase oracle that may depend on the hidden randomness, followed by a measurement. Because the measurement outcomes must be orthogonal, the win probability reduces to the squared norm of a certain random matrix sum, which is then controlled by computing its matrix variance (which comes out to roughly 1/K under mild conditions: each state is maximally mixed in expectation, and coefficients for different k are uncorrelated) and invoking matrix concentration for Rademacher-type series.

The interesting structural work is showing this variance calculation survives for structured randomness. For permutations, the relevant states P H^{⊗n}|k⟩ have amplitudes determined by π⁻¹, so the matrices for different k are highly dependent; the authors instead exploit the fact that the entropy is in the second half of π⁻¹(x), and handle the dependence directly. The same framework, applied to i.i.d. binary phase states, gives a short alternative proof of the earlier [LMW24] lower bound. Finally, an explicit attack (using Rosenthal's one-query state synthesis algorithm plus a SWAP test) shows that the pseudorandomness-based distinguishing route genuinely fails for permutations, justifying the switch from decision games to search games.

Why This Matters

• Impact on research: The results establish that adaptivity is genuinely powerful in unitary synthesis — one query is strictly weaker than two for explicit, efficiently synthesizable families — and provide a new, mathematically simpler and more flexible source of hardness than state pseudorandomness. They bear on unitary complexity theory (which the paper says would need complexity classes with no classical correspondence if the Aaronson–Kuperberg conjecture is false) and on quantum cryptography, where the search game suffices to build quantum bit commitments and raises the possibility of computational quantum cryptography not based on separating traditional complexity classes. The paper also frames Question 1.4 — whether F_t H … F₁ requires t sequential queries, proved here only for t = 2 — as a route to the full unitary synthesis conjecture.
• Potential real-world applications (long-term, speculative; the paper itself is foundational and does not claim deployed applications):
  • Quantum circuit compilation and transpilation: understanding when a desired transformation can be "compiled" from a small number of oracle calls versus needing sequential composition informs compiler design and resource estimates.
  • Quantum-secure primitives: the oracle state search game and oracle Choi state game provide new building blocks for quantum bit commitment and single-copy one-way state generators.
  • Verification and benchmarking of quantum devices: separating what one-query versus two-query algorithms can achieve gives sharper benchmarks for how much power adaptivity actually buys.
  • Foundations for "quantum programs" and advice-based models, relevant to how much classical versus quantum side information a device or algorithm needs.
• Industry relevance: Relevant to quantum software and compiler teams reasoning about query/adaptivity costs, and to post-quantum and quantum cryptography groups interested in assumptions weaker than standard complexity separations. It is foundational rather than immediately deployable.

Future Directions

1. Prove one-query lower bounds against quantum advice. The current Theorem 1.13 handles only classical advice; the paper explicitly states this is open for any family of unitaries, including permutations, F₂H^{⊗n}F₁, and Haar-random U.
2. Resolve the t-query question. Prove Question 1.4 — that synthesizing F_t H … F₂ H F₁ requires t sequential queries — for all t = poly(n), which the authors note would prove the unitary synthesis conjecture.
3. Characterize when the search game is the right hardness notion. Theorem 1.11 shows pseudorandomness fails for permutations; a broader understanding of which structured state families are hard for search but easy for distinguishing would clarify the boundary.
4. Develop the oracle Choi state game. The authors describe it as the weakest natural formulation of average-case unitary synthesis hardness, use it for Theorem C.2 and alternative proofs in Appendix C, and explicitly call it worthy of future study.

Target Audience

Quantum complexity theorists and quantum cryptographers, particularly researchers working on unitary synthesis, quantum query complexity, oracle separations, pseudorandom states, one-way state generators, and quantum bit commitment. Graduate students with a background in quantum computing and theoretical cryptography will find the technical overview (Section 2) the most accessible entry point, though the full results require comfort with matrix concentration and diamond-distance approximation.

Authors’ abstract

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.