Unitary synthesis asks how a quantum circuit can implement a prescribed transformation when it may consult a classical function in quantum superposition. The choice of function can carry substantial information about the requested transformation. The question changes when that function must be sampled uniformly: how many queries are needed before the resulting circuit can approximate a uniformly random unitary? Huang, Ramkumar and Wright prove a lower bound for this random-oracle model, even when the circuit has arbitrarily many ancillary qubits. The result concerns query complexity, rather than the time needed to execute the intervening gates. Source, §§1 and 4.
The distinction matters for understanding what information a synthesis procedure obtains from its oracle. A truth table may be extremely large, while a circuit consults it only a few times. This mission formalizes the paper's random-oracle synthesis lower bound, its pseudorandom-unitary query bound and constructions, and selected supporting results. It does not ask for a new conjectural lower bound.
An n-qubit register has computational basis indexed by words of length n over {0,1}, and complex Hilbert-space dimension N=2ⁿ. A circuit uses m total qubits, with n≤m, and queries a Boolean function f on m₀ input bits, where m₀≤m. There is no requirement m₀≤n. The oracle input register can therefore overlap the ancillary register. Write M₀=2ᵐ⁰ for the number of truth-table bits, rather than the number of input wires.
The phase oracle multiplies each computational basis vector by (−1) raised to the value of f on its first m₀ bits. Its action is fixed on the entire register. A sequence of fixed unitaries V₀,…,Vₖ defines
The gates are chosen before f is drawn. They may vary with the query position and incur no gate-complexity restriction. The isometry J appends m−n zero qubits. The implemented quantum channel E_f appends those qubits, applies W_f, and traces out the ancillary register. The compressed matrix A_f=J†W_fJ is also used in supporting results, but E_f includes every ancillary output, including garbage. Source, §2.1 and §3.
The diamond distance D⋄ is half the trace norm of the channel difference, optimized over every finite reference system and every joint density operator. A synthesis coupling is a joint distribution on two channels whose first marginal is the law of E_f for a uniform truth table and whose second marginal is the law of conjugation by a Haar-random U∈U(N). The approximation promise is an expected distance at most ε. Dependence between the two channels is unrestricted. In particular, no deterministic assignment from f to a target unitary is required. Source, Definition 3.6.
For pseudorandom unitaries in the random oracle model (ROM-PRUs), bounds implementation error almost surely and is standard non-adaptive design error. Strong adaptive designs allow classically adaptive calls to the unitary, inverse, conjugate, transpose, and controlled versions. The constructions interleave random th-root phase layers with Haar-random unitaries or Hadamards.
The paper's main results are the synthesis lower bound (refTheorem 4.1), the ROM-PRU query bound (refTheorem 4.2), the Haar-interleaved construction (refTheorem 5.1), and the Hadamard construction (refTheorem 6.1), whose computational consequence appears as Theorem 1.4. The platform allows one goal, so Theorem 4.1 remains the goal and the other three are milestones of equal standing.
For a family indexed by n, set a(n)=1−ε(n). The goal is the complete statement of Theorem 4.1:
The Ω constant is absolute; the eventual threshold may depend on the family. Both the number of ancillary qubits and the oracle length may grow without restriction. The same goal includes the polynomial consequence
for positive B,B′ and nonnegative d,d′. Source, Theorem 4.1.
The eight supporting targets retain their printed constants and complete conclusions:
These targets are the paper's source-numbered dependency chain. Source, §§4.1–4.3.
Section 4: ROM-PRU query bound.
Section 5: Haar-interleaved random phases.
Section 6: Hadamard random phases.
For an inverse-polynomial accuracy gap, the query requirement is exponential in the number of system qubits, up to polynomial factors. Adding ancillary qubits cannot restore a polynomial-query implementation in this model. The dependence on a preserves a regime substantially broader than fixed error: the theorem allows error approaching one subject to the stated asymptotic condition. Source, Theorem 4.1 and its following discussion.
Formalization would provide reusable interfaces for finite oracle circuits, channel-valued couplings, matrix-valued resampling, and Haar correlation estimates. Existing published definitions supply basic norms, density operators, partial trace, Pauli matrices, and finite Shannon entropy. The local theorem files are statement drafts with proof placeholders; this mission does not claim that the source's proof has already been machine checked.
A circuit's accessible information cannot be read off from the length of its oracle truth table. Entropy bounds must remain meaningful under matrix approximation. Ancillary output can also change with the input, so a compressed matrix need not describe the implemented channel. Finally, a promise about expected approximation allows highly nonuniform errors across targets; replacing it by a uniform error guarantee would change the problem. The targets explicitly retain each of these features. Source, discussions following Theorem 4.5 and in §4.2.
Registers use finite binary words and full complex matrices. Spectral and Frobenius norms are explicitly selected. Channels use matrix-unit coordinates, with the usual Borel structure, so equality of channel laws does not depend on a choice of Kraus representation. Haar measure is normalized on the complete compact unitary group. Expectations of nonnegative channel distances use the nonnegative Lebesgue integral; resampling expectations are finite sums. Entropy is in bits with zero-mass terms contributing zero.
The resampling procedure visits each input once, tests both forced bit values, and uses independent fair replacement bits. It records selected positions even when replacement leaves a bit unchanged. Zero queries have a defined independent-resampling case. Finite nets are nonempty, and their members have spectral norm at most one. Real parts of traces express quantities already real for Hermitian products. The approximation promise contains no lower-bound or covering conclusion. Contributions proving the thirteen targets, establishing their analytic infrastructure, or developing reusable structural APIs are welcome.
Theorem 1.4's computational-security consequence is excluded because its security assumptions are not defined in the paper; Theorem 6.1 supplies its unconditional mathematical content.
2f2d7fa67fe2665257ec12cb0d11d7e2a80752cdecc0484b26a311d1223c5d11. The title page displays November 3, 2026; citation follows the pinned submission metadata.namespace RandomOracleUnitarySynthesis
theorem synthesis_query_bound :
∃ c : ℝ, 0 < c ∧ ∀ (m m₀ k : ℕ → ℕ)
(C : (n : ℕ) → synthesis_Circuit n (m n) (m₀ n) (k n)) (ε : ℕ → ℝ),
synthesis_Admissible m m₀ k C ε → synthesis_GapRegime ε →
(∀ᶠ n : ℕ in atTop, c * (2 : ℝ)^n ≤ (k n : ℝ)^2 * ((1-ε n)⁻¹)^6) ∧
(∀ B d : ℝ, 0 < B → 0 ≤ d → synthesis_PolynomialGap ε B d →
∃ B' d' : ℝ, 0 < B' ∧ 0 ≤ d' ∧
∀ᶠ n : ℕ in atTop, Real.sqrt ((2 : ℝ)^n) /
(B' * Real.rpow ((n : ℝ)+1) d') ≤ (k n : ℝ)) := by sorry
end RandomOracleUnitarySynthesis
There is an absolute constant such that the following holds for every synthesis family. At system size , the circuit has arbitrary , , fixed gates, and eventually at least one query. Its random-oracle channel admits the channel-valued Haar coupling of Definition 3.6 with expected diamond error at most . Put and . If , then eventually
In particular, for every and with eventually, there are and such that eventually
The first constant is independent of the family, circuit, and ancilla count. The eventual thresholds and polynomial constants may depend on the family and the polynomial accuracy bound. Both conclusions belong to this single goal.
Differences from the source:
No open leaves. Every sub-goal is proved or awaiting decomposition.