The clean two-query threshold for unitary synthesis

As the paper states it, in briefClean two-query synthesis of every $n$-qubit unitary needs, and can be done with, $\mathrm{\Theta }(2^n)$ qubits and oracle input bits, up to a factor $\log (1/\epsilon )$; the garbage-model problem reduces to a clean four-insertion width bound, which remains open.

• Partly answered Can every $n$-qubit unitary be implemented by a polynomial-size circuit making few queries to a classical oracle? posed by others
• Answered How many qubits does clean two-query synthesis of every $n$-qubit unitary need?
• Open Does the clean four-insertion width bound hold? left open

Audits

An independent audit and a final adversarial audit, which found no remaining blocker within its scope.

Machine checks

Nine finite-check scripts

Lean

Seven scoped declarations; the analytic proof is not formalized.

Peer review

Not yet.

Every check here is internal. How we check results.

Novelty

Extends named prior work: Lombardi, Ma and Wright named the quantity bounded here and proved that small capacity implies a lower bound; this paper supplies the missing premise for two-query architectures.

PDF

papers/two-query-v1.0.4.pdf, version 1.0.4, 510,967 bytes.

SHA-256 1529c00e91c5153b8f03fbaef6283f2c149ce9294574170faa5f45bed79e508d

DOI

10.5281/zenodo.22740995

Code

github.com/Apsiape/two-query-unitary-synthesis

None so far.

All corrections, and what counts as one.

@misc{douglas2026twoquery,
  author  = {Douglas, Seth},
  title   = {The clean two-query threshold for unitary synthesis},
  year    = {2026},
  version = {1.0.4},
  doi     = {10.5281/zenodo.22740995},
  url     = {https://doi.org/10.5281/zenodo.22740995}
}

two-query.bibAll papers as BibTeX