Pith. sign in

REVIEW 3 major objections 5 minor 22 references

Explicit Separations for One-Query Unitary Synthesis

T0 review · 3 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random permutation unitaries and alternating-basis phase unitaries cannot be synthesized with a single classical query, even though two queries suffice.

desk verdict Solid and important: new lower bounds for one-query unitary synthesis via a flexible search-game framework, with a clean external dependency on LMW's normal form. read the letter →

arxiv 2607.26478 v1 pith:6KMUYN3I submitted 2026-07-29 quant-ph cs.CCcs.CR

Fangqi Dong , Alex Lombardi , Fermi Ma This is my paper · ORCID
classification quant-phcs.CCcs.CR MSC 81P6868Q17 PACS 03.67.Lx03.67.Dd
keywords unitarysynthesisone-queryalgorithmsquantumquerycomplexitypermutationunitariesphaseoraclesearchgameadvicematrixconcentration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that some quantum unitaries with simple two-query algorithms cannot be implemented with just one query to a classical oracle. Specifically, random permutation unitaries and unitaries built from two random phase layers separated by a Hadamard transform are shown to resist every efficient one-query algorithm. To establish this, the authors introduce an oracle state search game, where an adversary must identify a hidden index from a single quantum state after one query; hardness of this game is shown to imply synthesis hardness. The same game yields a simpler proof of an existing one-query lower bound for Haar-random unitaries, a constant-correctness one-query algorithm for complex phase unitaries, and a quantitative separation between one-query synthesis and quantum-advice programs.

What carries the argument

The central object is the oracle state search game, in which a challenger samples a random key k, sends the state |ψ_{R,k}⟩ to the adversary, and the adversary must output k after one query to an oracle that may depend on R but not on k. Hardness of this game implies hardness of unitary synthesis via a fixed normal form for one-query algorithms: an isometry V, a single phase-oracle query, and a projective measurement. The analysis uses a weight-vector decomposition that writes V|ψ_{R,k}⟩ as a rescaling of a fixed unit vector, reducing the search winning probability to the squared spectral norm of a random matrix M_R = (1/√K) Σ Π_k D_{R,k}. Concentration of this matrix is then controlled by t

What would settle it

A concrete one-query algorithm that synthesizes random permutation unitaries (or F₂ H F₁ unitaries) with success probability 1/poly(n) for every permutation would directly contradict the main theorems. Conversely, an explicit adversary that wins the oracle state search game for the permutation state family with probability significantly larger than O(log²M logK / K) would falsify the key spectral bound underlying the proof.

Watch

Extended reading notes

Core claim

The paper's central claim is a separation between one-query and two-query unitary synthesis for explicit, structured families. It proves that for a uniformly random permutation π, no one-query algorithm with workspace dimension M can synthesize the permutation unitary P|x⟩ = |π(x)⟩ with more than O(log²M logK / K) success on the associated search game, and similarly for unitaries F₂ H F₁ with random Boolean phases F₁, F₂, the success is at most O(log M · log(MN) / K). Because both families have clean two-query synthesis algorithms, these bounds establish that the extra query is strictly necessary. The proofs proceed by reducing synthesis hardness to the oracle state search game, then applyin

Load-bearing premise

The lower bounds assume that every one-query algorithm can be represented as a fixed isometry, a single phase-oracle query, and a projective measurement; if some one-query algorithm escapes this normal form, the spectral relaxation and all derived bounds would not apply to it.

Editorial extensions

If this is right

  • One-query and two-query unitary synthesis are separated for explicit, structured families, showing that adaptivity in the number of oracle queries is a real resource in quantum unitary synthesis.
  • The oracle state search and Choi state games provide a flexible framework that re-derives the known one-query hardness for Haar-random unitaries with simpler proofs, and extends to families that are not fully random.
  • Complex phase unitaries admit a one-query algorithm with constant correctness, so binary and complex phase oracles are equivalent up to a constant approximation factor; this explains why approximation-rule-out lower bounds cannot apply to complex phases.
  • The quantum-advice lower bound (success ≤ O(S/K) with S advice qubits) sharply separates one-query synthesis from quantum programs for phase states, with a matching algorithm up to logarithmic factors.
  • The one-query hardness extends to any number of alternating layers F_t H ... F₂ H F₁, with a reduction to the t=2 case; the paper proposes that proving t-query hardness for larger t would resolve the full unitary synthesis conjecture.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The search-game formulation suggests that one-query synthesis hardness of a unitary family is governed by a single-copy state-identification problem, which may be easier to analyze than pseudorandomness for structured families; this heuristic could be applied to other families, such as unitaries with small circuit depth or low entanglement.
  • The constant-correctness algorithm for complex phases indicates a sharp boundary: the hardness is specific to binary-phase oracles, so any separation for complex phases must rely on a mechanism beyond the standard approximation-rule-out arguments.
  • The quantum-advice lower bound and the matching algorithm imply that the advantage of a one-query oracle over an S-qubit quantum program is essentially a factor of S in the success probability for this task; testing whether the same tightness holds for permutation unitaries or F₂ H F₁ would further clarify the role of quantum advice in synthesis.
  • The Choi state game's connection to quantum bit commitment suggests that these lower bounds double as security proofs for quantum cryptographic primitives; future work might extract explicit commitment schemes from the hardness of the search game for other unitary families.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies one-query unitary synthesis lower bounds. It introduces the oracle state search game and the oracle Choi state game, and proves that one-query adversaries fail to win these games for two natural low-randomness families: states built from random permutation unitaries P (via P H|k>) and states built from random alternating phase unitaries F_2 H F_1 (via F_2 H F_1 H|k>). These search bounds are used to infer one-query synthesis lower bounds for related unitary families, giving separations between one-query and two-query synthesis. The paper also gives a one-query constant-correctness algorithm for arbitrary complex phase unitaries, and a quantum-advice lower bound for the phase-state search game, plus a simplified proof of the LMW24 one-query lower bound for Haar-random unitaries.

Significance. If the results hold as stated, the paper makes a substantial contribution: it extends one-query unitary synthesis lower bounds from Haar-random unitaries to explicit, low-randomness families that admit two-query algorithms, thereby demonstrating the power of adaptivity. The new search/Choi game framework is flexible and likely to be reused, and the paper ships fully explicit proofs with concrete matrix-concentration estimates. The matching upper bound for phase unitaries and the quantum-advice lower bound add further value. The main caveat is that the reduction from search hardness to synthesis hardness contains a quantitative error (fidelity vs. overlap) and the connection to the headline 'permutation' and 'F_2 H F_1' synthesis statements is not explicitly justified; both are fixable.

major comments (3)
  1. [§4.1, Lemma 4.6; §4.2, Lemma 4.10] The proof claims that if the output state has fidelity at least η with |k> (or |Ψ_EPR>), then the measurement outcome k (or EPR acceptance) occurs with probability at least η. With the standard fidelity used in Definition 3.6 and Proposition 3.8, fidelity equals the square root of the overlap, so the success probability is at least η², not η. Consequently, a search bound of δ only rules out synthesis correctness greater than √δ, and the same factor applies to the Choi-game reduction. The lemmas and the derived quantitative synthesis statements (e.g., the informal Theorems 1.1/1.2 and the last sentence of Lemma 4.6) need to be corrected. The qualitative separation survives, but the stated bounds change.
  2. [§1.2, §5, and §4.1] The formal theorems (Theorems 5.1 and 5.2) are search-game bounds for the state families P H|k> and F_2 H F_1 H|k>. The informal synthesis theorems claim lower bounds for synthezing random permutation unitaries P and alternating unitaries F_2 H F_1. The unitary that maps P H|k> to |k> is H P^{-1}, not P; the unitary that maps F_2 H F_1 H|k> to |k> is H F_1 H F_2, not F_2 H F_1. The paper does not state or prove that one-query synthesis for permutations (resp. F_2 H F_1) implies one-query synthesis for these relative families. This closure is true (post-compose with H and use the inverse/renaming), but it is load-bearing and should be made explicit.
  3. [§10.3, Lemma 10.5] In bounding ||Π_Win |Φ_1>||², the text obtains (t−2)/N, but a direct norm calculation gives (t−2)/K: the sum over k ∈ {0,1}^n contributes a factor N that cancels the 1/N in the normalization. Since K ≤ N, the displayed bound is too strong. The subsequent 4t/K conclusion still holds if the term is (t−2)/K, so this appears to be a typo rather than a fatal flaw, but it should be corrected.
minor comments (5)
  1. [Abstract and §1.2, Theorem 1.5] The phrase 'Ω(1)-approximate in diamond distance' is misleading: the formal guarantee is constant correctness (fidelity) of 1/4 or 1/2, which only implies diamond distance ≤ √(1−η) ≈ 0.87 or 0.71. The formal Theorem 5.5 statement is clearer; the abstract should align with it.
  2. [§7.2] The notation [K] is used both as {0,1,...,K−1} and as a key set that excludes 0. This is a source of small off-by-one ambiguities; a cleaner notation such as K∗ for the nonzero key space would help.
  3. [§8.7] The statement of Corollary 8.1 uses 'F1,...,f_t' in the proof while the theorem states f_1,...,f_t; the typesetting of subscripts should be made uniform.
  4. [§3.1, Definition 3.6] The relationship between 'correctness' η and standard fidelity should be stated explicitly, especially given the Lemma 4.6 issue. A one-line clarification that F is the standard fidelity would prevent ambiguity.
  5. [§C.3, parameter estimates] The Choi-state permutation proof in Appendix C is dense; several norm bounds are asserted with 'basic properties' and would benefit from a few more intermediate steps. This does not affect the main text.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the new lower bounds are derived from the oracle state search/Choi game reductions and matrix concentration inequalities, not from the statements being proved.

full rationale

The paper's central claims—one-query lower bounds for permutation unitaries and for F2 H F1 unitaries—are obtained by (1) defining new search games, (2) proving a reduction from search-game hardness to synthesis hardness (Lemma 4.6), (3) relaxing the search game to a spectral norm of a random matrix (Lemma 6.1), and (4) bounding that norm with external matrix concentration inequalities (Tropp, Mackey–Jordan–Chen–Farrell–Tropp). No parameter is fitted to the target result, and no quantity is defined in terms of the very bound it is supposed to predict. The only load-bearing external dependency is the one-query normal form of [LMW24, Corollary 3.34], which is cited rather than re-proved. Although [LMW24] shares authors with this paper, the normal form is a structural theorem about one-query algorithms, not a statement equivalent to the permutation or F2 H F1 lower bounds; the paper's new content—the search/Choi game framework and the concrete matrix analyses—does not reduce to that citation. The paper is also self-contained against the external benchmarks it addresses, and it even supplies an alternative proof of the prior LMW24 lower bound (Appendix A). No step exhibits the required reduction of a prediction to its input by construction, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard matrix concentration theorems and on the one-query normal form from LMW24. No free parameters are fitted; the games are internal computational definitions rather than empirical entities.

assumptions (5)
  • domain assumption One-query normal form for unitary synthesis algorithms (isometry V, phase oracle, measurement)
    Assumed WLOG citing [LMW24, Cor 3.34]; used to model all one-query adversaries in the lower bounds.
  • standard math Matrix Rademacher series concentration bound (Theorem 3.11 from [Tro15])
    Used to bound ||M_R||^2 in Theorems 5.2 and A.1.
  • standard math Bernstein inequality for combinatorial matrix sums (Theorem 3.12 from [MJC+14])
    Used to bound permutation search game win probability.
  • standard math Jordan's lemma for two projectors
    Used in the alternating measurement game reduction (Lemma 10.2).
  • standard math Zhandry's compressed oracle technique
    Used to bound conditional winning probabilities in Section 10.3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Explicit Separations for One-Query Unitary Synthesis." pith.science (2026). https://pith.science/paper/6KMUYN3I

@misc{pith2026260726478,
  author       = {Pith},
  title        = {Pith review of: Explicit Separations for One-Query Unitary Synthesis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6KMUYN3I}},
  note         = {Machine review of arXiv:2607.26478}
}
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 \pi(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 \alpha_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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 2 linked inside Pith

  1. [1]

    The complexity of quantum states and transformations: from quantum money to black holes

    Scott Aaronson. The complexity of quantum states and transformations: from quantum money to black holes. arXiv preprint arXiv:1607.05256 , 2016

    arXiv 2016

  2. [2]

    Quantum versus classical proofs and advice

    Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07) , pages 115--128. IEEE, 2007

    2007

  3. [3]

    On the computational hardness needed for quantum cryptography

    Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. In Yael Tauman Kalai, editor, ITCS 2023 , volume 251, pages 24:1--24:21. LIPIcs , January 2023

    2023

  4. [4]

    Unitary Complexity and the Uhlmann Transformation Problem

    John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen. Unitary Complexity and the Uhlmann Transformation Problem . In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , volume 362 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 24:1--24:17, Dagstuhl, Ger...

    2026

  5. [5]

    Approximating the little grothendieck problem over the orthogonal and unitary groups

    Afonso S Bandeira, Christopher Kennedy, and Amit Singer. Approximating the little grothendieck problem over the orthogonal and unitary groups. Mathematical programming , 160(1):433--475, 2016

    2016

  6. [6]

    Post-quantum succinct arguments: Breaking the quantum rewinding barrier

    Alessandro Chiesa, Fermi Ma, Nicholas Spooner, and Mark Zhandry. Post-quantum succinct arguments: Breaking the quantum rewinding barrier. In 62nd FOCS , pages 49--58. IEEE Computer Society Press, February 2022

    2022

  7. [7]

    Commitments to quantum states

    Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry. Commitments to quantum states. In Barna Saha and Rocco A. Servedio, editors, 55th ACM STOC , pages 1579--1588. ACM Press, June 2023

    2023

  8. [8]

    Quantum search-to-decision reductions and the state synthesis problem

    Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum search-to-decision reductions and the state synthesis problem. In Proceedings of the 37th Computational Complexity Conference , pages 1--19, 2022

    2022

Show all 22 references
  1. [9]

    Pseudorandom quantum states

    Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III , volume 10993 of LNCS , pages 126--152. Springer, Cham, August 2018

    2018

  2. [10]

    Quantum pseudorandomness and classical complexity

    William Kretschmer. Quantum pseudorandomness and classical complexity. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021) , pages 2--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2021

    2021

  3. [11]

    Non-uniformity and quantum advice in the quantum random oracle model

    Qipeng Liu. Non-uniformity and quantum advice in the quantum random oracle model. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I , volume 14004 of LNCS , pages 117--143. Springer, Cham, April 2023

    2023

  4. [12]

    A one-query lower bound for unitary synthesis and breaking quantum cryptography

    Alex Lombardi, Fermi Ma, and John Wright. A one-query lower bound for unitary synthesis and breaking quantum cryptography. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell , editors, 56th ACM STOC , pages 979--990. ACM Press, June 2024

    2024

  5. [13]

    Matrix concentration inequalities via the method of exchangeable pairs

    Lester Mackey, Michael I Jordan, Richard Y Chen, Brendan Farrell, and Joel A Tropp. Matrix concentration inequalities via the method of exchangeable pairs. The Annals of Probability , 42(3):906--945, 2014

    2014

  6. [14]

    Quantum commitments and signatures without one-way functions

    Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I , volume 13507 of LNCS , pages 269--295. Springer, Cham, August 2022

    2022

  7. [15]

    Query and depth upper bounds for quantum unitaries via grover search

    Gregory Rosenthal. Query and depth upper bounds for quantum unitaries via grover search. arXiv preprint arXiv:2111.07992 , 2021

    2021 arXiv

  8. [16]

    Efficient quantum state synthesis with one query

    Gregory Rosenthal. Efficient quantum state synthesis with one query. In David P. Woodruff, editor, 35th SODA , pages 2508--2534. ACM-SIAM , January 2024

    2024

  9. [17]

    A comparison principle for functions of a uniformly random subspace

    Joel A Tropp. A comparison principle for functions of a uniformly random subspace. Probability Theory and Related Fields , 153(3):759--769, 2012

    2012

  10. [18]

    An introduction to matrix concentration inequalities

    Joel Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning , 8(1-2):1--230, 2015

    2015

  11. [19]

    The Theory of Quantum Information

    John Watrous. The Theory of Quantum Information . Cambridge University Press, USA, 1st edition, 2018

    2018

  12. [20]

    General properties of quantum bit commitments (extended abstract)

    Jun Yan. General properties of quantum bit commitments (extended abstract). In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part IV , volume 13794 of LNCS , pages 628--657. Springer, Cham, December 2022

    2022

  13. [21]

    Lecture 6 from COMS E6998 :\ F rontiers of quantum complexity and cryptography

    Henry Yuen. Lecture 6 from COMS E6998 :\ F rontiers of quantum complexity and cryptography. Found at https://www.henryyuen.net/spring2022/lec6-statesynthesis.pdf and https://www.henryyuen.net/spring2022/lec6-unitarysynthesis.pdf, 2022

    2022

  14. [22]

    How to record quantum queries, and applications to quantum indifferentiability

    Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part II , page 239–268, Berlin, Heid...

    2019

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.