This archive contains the preprint The Clean Two-Query Threshold for Unitary Synthesis, its self-contained sources, companion notes, verification code, and scoped Lean checks. For fixed two-query architectures with arbitrary contractions and independent unimodular selectors, the Gaussian mean width is at most 2 min(N,Q) sqrt(log(2Q)). Universal clean synthesis consequently requires Omega(2^n) oracle input bits independently of workspace. A two-query permutation-transport construction matches the fixed-error exponential resource threshold. This does not resolve unrestricted two-query synthesis with garbage or the full Aaronson-Kuperberg problem. The complete analytic proof is not formalized. The recorded AI audits are not external peer review. Licensing is file-specific: the manuscript and prose are CC BY 4.0 (LICENSE); verification and other software are MIT (LICENSE-CODE). The record-level CC BY 4.0 label describes the preprint, not a relicensing of the accompanying software.
This archive contains the preprint The Clean Two-Query Threshold for Unitary Synthesis, its self-contained sources, companion notes, verification code, and scoped Lean checks. For fixed two-query architectures with arbitrary contractions and independent unimodular selectors, the Gaussian mean width is at most 2 min(N,Q) sqrt(log(2Q)). Universal clean synthesis consequently requires Omega(2^n) oracle input bits independently of workspace. A two-query permutation-transport construction matches the fixed-error exponential resource threshold. This does not resolve unrestricted two-query synthesis with garbage or the full Aaronson-Kuperberg problem. The complete analytic proof is not formalized. The recorded AI audits are not external peer review. Licensing is file-specific: the manuscript and prose are CC BY 4.0 (LICENSE); verification and other software are MIT (LICENSE-CODE). The record-level CC BY 4.0 label describes the preprint, not a relicensing of the accompanying software.
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=fU 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∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅H⊗n⋅F1. 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 ∣x⟩↦αx∣x⟩, 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.
We give exponential quantum query separations between the standard XOR interface and two forward-only interfaces that supply neither an adjoint nor an inverse oracle. Let $X=\F_2^n$, N=∣X∣, and fh,r(x)=(h(x),x,rx), where h:X→X is promised to be either a permutation or a Simon two-to-one function, and r is a fixed table of n-bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most n+2 standard XOR queries, but has forward-erasing query complexity Θ(N). This answers affirmatively open question 11 in [Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1-14:9, 2021] . We also embed these instances into permutations. The detailed construction retains the copy of x in each prescribed output, but for these promises that copy can be replaced by one bit that distinguishes the two inputs in every Simon pair. This gives a permutation domain of size L=4N2 and a permutation problem with the same standard-query upper bound and forward-only in-place query complexity Θ(N)=Θ(L1/4). Both lower bounds remain valid with a clean coherent bypass. The common lower bound uses an analysis-only recording replacement. In the replacement computation, tracing out the fixed random tag table after T calls gives a sum of positive-semidefinite operator contributions, each depending on h at no more than T addresses. On such a set, the restrictions induced by random permutations and random Simon functions differ only if the set contains a hidden Simon pair, an event of probability O(T2/N).
We give a positive answer to the constant-error formulation of the Aaronson–Kuperberg unitary synthesis problem. For every n, a quantum oracle circuit generated in polynomial time from n alone can approximate the channel of every n-qubit unitary to full diamond-norm error at most 1/2, after a suitable Boolean oracle is chosen. Using the fixed gates H,T,T^\dagger,\mathrm{CNOT}, the circuit has polynomially many qubits, elementary gates, and oracle calls, and its oracle queries have polynomial length. The oracle may depend on the target unitary; the theorem does not give an efficient classical procedure for constructing it.
Preprint by Seth Douglas (seth.douglas@gmail.com). A finite closed mixed-apparatus construction approximates any Schur channel of Gram rank k in half-diamond distance using a physical apparatus of dimension of order epsilon^-2 (sqrt(k) + ln d), with a maximally mixed initializer of rank of order sqrt(k). A universal entropy converse 2Q - P >= S(J) and an exact extreme-channel cost P, Q >= log2 k give, for a known extreme rank-two ququart Schur channel, a matched leading-order exact-versus-vanishing-error separation: exact service needs P = Q = T, while error T^-4 admits Q = T/2 + O(log T) and P = O(log T). A separately scoped scheduled-delivery theorem compares sublogarithmic and superlogarithmic delay under mandatory arrivals, a common release schedule and observation-only stopping. Includes the complete manuscript, TeX source, reproducibility scripts and partial Lean coverage. Scoped licenses: the manuscript, PDF and TeX are licensed under Creative Commons Attribution 4.0 International (CC-BY-4.0). Original code and accompanying software documentation are MIT-licensed. These are separate file-specific licenses, not a choice of license for every file. See LICENSE.md and LICENSES/ in the archive. The aggregate Other (Open) category represents this mixed-license package. Lean coverage is partial: fourteen scoped dependency closures, not the headline analytic theorems. The construction is a probabilistic existence proof; no efficient compiler, arbitrary-channel upper bound, caller-paced delivery guarantee or sharp logarithmic-delay frontier is claimed. AI assistance is disclosed in the manuscript. This is a separate sequel to the closed repeated-use memory paper, DOI 10.5281/zenodo.22779673.
We prove a new lower bound for the unitary synthesis problem in the so-called 1.5-query setting. Our analysis establishes that any attempt to implement arbitrary n-qubit unitaries via limited oracle access requires resources that exceed the fractional query threshold. This result extends the one-query lower bound of Lombardi, Ma, and Wright (2023) to the fractional query regime, and introduces a conservative and chaining-based approach to handle intermediate query complexities. As a consequence, we derive cryptographic implications, showing that pseudorandom quantum states remain secure against adversaries restricted to 1.5 queries. Our work provides both conceptual clarification of fractional-query complexity and practical insights into the design of quantum cryptographic protocols.
This note records a self-contained exact reduction from every even-order symmetric matrix with binary nonnegative rational off-diagonal entries to a simple unweighted perfect-matching count, with polynomial encoding length, an explicit logarithmic integer-weight gadget, exact rational scaling, and weighted matching fibers. Citing the general-graph FPRAS of OpenAI, it derives a uniform rational hafnian FPRAS with exact zero detection and a rigorously specified bounded-bit total-variation approximate sampler. Logarithmic integer weight removal, binary rational weighted-to-unweighted equivalence, and counting self-reduction are established machinery and credited to earlier work, including Dell and collaborators, McQuillan, and Jerrum, Valiant, and Vazirani. The approximation breakthrough belongs to OpenAI. This is an attributed consequence and implementation note; no first-publication, new reduction, or independent solution of the base approximation problem is claimed. The supplement contains proofs, transparent code, exact finite enumeration and output-law checks, dependency and priority audits, and clean reproduction instructions. Finite checks do not certify the upstream FPRAS. The real upstream Lean statement was inspected, but no independent kernel rebuild was reproduced. Nonnegative rational inputs only; no signed or complex hafnian or unrestricted Gaussian-boson-sampling consequence. AI tools were used extensively in research, drafting and automated adversarial verification. The preprint has not undergone conventional human peer review or refereeing at publication. Automated reviews are not human peer review. Newly authored prose and data are CC BY 4.0; code is MIT as specified in the archive.