Nearly optimal quantum circuits for Boolean oracles

Junhong Nie; Wei Zi

REVIEW 2 major objections 6 minor 25 references

Nearly optimal quantum circuits for Boolean oracles

T0 review · 2 major / 6 minor · reviewed 2026-07-31 · grok-4.5

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

Pith's one-line read Any Boolean function has a quantum oracle whose size and depth nearly match information-theoretic limits once you dial the ancilla count.

desk verdict Solid constructive paper that actually closes the size–depth–ancilla surface for Boolean oracles; asymptotics check out and the gaps are ordinary for the genre. read the letter →

arxiv 2607.28402 v1 pith:4HBGPYBT submitted 2026-07-30 quant-ph

Junhong Nie , Wei Zi This is my paper · ORCID

classification quant-ph MSC 68Q1281P68

keywords quantumcircuitsBooleanoraclesancillatradeoffQROMpartialfunctionssparsecircuitdepthreversiblecomputing

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

Quantum algorithms often need a classical Boolean function wired into a reversible circuit, and the cost of that wiring can dominate the whole algorithm. This paper shows how to build those oracles so that size, depth, and spare qubits trade off nearly optimally for three standard families: fully general functions, functions that only matter on a small support, and functions that are 1 on only a few inputs. For a general n-bit function the size drops like 2^n over log of the ancilla budget, and the depth drops like 2^n over the total width; matching lower bounds say you cannot do much better. The same style of tradeoff is given for partial and sparse oracles down to only logarithmic ancilla. The constructions are meant to be drop-in subroutines for QROM, lookup tables, and any quantum algorithm that must embed classical data.

What carries the argument

Lupanov-style regrouping of the algebraic normal form (compute every small Boolean function once, then fan it out) combined with linear hashing that shortens or separates the effective support, plus conditionally clean ancilla so that input wires can be reused as workspace.

What would settle it

Exhibit a concrete family of n-bit Boolean functions (or a sparse/partial instance) whose minimal quantum-oracle size or depth, for some m in the claimed range and a fixed constant-width gate set, exceeds the stated upper bound by more than a polylog factor, or prove a matching lower bound that already includes those logs.

Watch

Extended reading notes

Core claim

With m ancilla qubits in the stated ranges, any total Boolean map {0,1}^n to {0,1}^b admits a quantum oracle of size O(b 2^n / log(n+m)) and depth O(b 2^n /(n+m)); partial maps of effective support d and sparse maps of true-input size d admit analogous nearly tight size-depth-ancilla tradeoffs. All upper bounds match simple counting lower bounds up to logarithmic factors inside those ancilla windows.

Load-bearing premise

The partial and sparse constructions assume linear hash matrices with the claimed collision and load bounds are already known; the circuit size does not pay for finding them.

Editorial extensions

If this is right

QROM and classical lookup tables can be compiled with asymptotically smaller Toffoli/T depth once spare qubits are available.
Reversible n-bit permutations inherit the same nearly optimal size O(n 2^n / log(n+m)) and depth O(n 2^n /(n+m)) for n < m ≤ Θ(2^n/n).
Hamiltonian-simulation and cryptanalysis routines that treat the oracle as a black box can now budget concrete size-depth-ancilla numbers instead of worst-case folklore circuits.
With only Θ(log d) ancilla a partial oracle of support d still has linear size in n log d + b d, so low-ancilla regimes remain usable.

Reading between the lines

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

If explicit constructions of the linear hashes with the same load bounds become available, the partial and sparse circuits become fully uniform without changing the asymptotics.
The same batching-plus-conditionally-clean-ancilla pattern should apply to other classical subroutines (sorting networks, arithmetic) that must run inside a quantum circuit.
When T-count is already near-optimal, the remaining Clifford volume is now the quantity these tradeoffs directly shrink.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

This is the clean resource-tradeoff paper the Boolean-oracle literature has needed. For general total functions they give, across the whole window 1 ≤ m ≤ Θ(2^n/n), size O(b 2^n / log(n+m)) and depth O(b 2^n/(n+m)), matching the Shannon-style counting lower bounds up to logs; the same style of nearly-tight surface is pushed down to logarithmic ancilla for partial and sparse oracles. Tables 1–2 make the comparison with Lupanov, Zakablukov, ZLY22/ZY24 explicit, so you can see exactly what was missing.

What is new is the complete surface, not any single trick. They glue Lupanov regrouping to the conditionally-clean-ancilla idea from their own NZS24 Toffoli work for the m < n regime, linear hashing plus parallel decision-tree bins for partial functions, and X-separating hashes plus batched membership plus a low-width sequential AND for sparse functions. The lower-bound lemmas are standard counting plus light-cone and are specialized correctly. I walked the recurrences at the asymptotic level; they close.

Soft spots are real but proportionate. The hash matrices (Lemmas 24–25, 28–29) are non-uniform existence statements via the probabilistic method; the circuits do not construct them. That is normal non-uniform circuit complexity and does not break the claims, but anyone who needs explicit hashes will pay a load penalty. Theorem 34 is only a sketch, constant-factor cleanup is omitted, and the “nearly optimal” slogan for sparse oracles is fully tight only when d = Ω(n)—which the paper already notes. Fact 9’s 0-ancilla fan-out is slightly loose for dirty targets, but m ≥ 1 is always present in the main theorems so the log-depth bound is restored. None of these overturn the central asymptotics.

This is for people who actually budget Toffoli/T depth and ancilla inside QROM, SELECT, or Hamiltonian simulation. Citation pattern is honest; self-cites supply primitives, not the target tradeoff. I would send it to referees without hesitation and would cite the general and sparse statements myself.

Referee Report

2 major / 6 minor

Summary. The paper gives nearly optimal size–depth–ancilla tradeoffs for quantum oracles of three Boolean-function families under a constant-size, constant-width gate set (e.g. Clifford+T). For total functions f:{0,1}^n→{0,1}^b and 1≤m≤Θ(2^n/n) ancilla it achieves size O(b 2^n/log(n+m)) and depth O(b 2^n/(n+m)) (Theorem 1), with a corollary for reversible maps. For partial oracles of effective support d it gives size O(n log d+bd) and a matching depth–ancilla tradeoff for Θ(log d)≤m≤Θ(d) (Theorem 3). For sparse oracles with |f^{-1}(1)|=d it gives size O(n² log d + nd/log(log d+m/n)) and depth O(n² log n log d/(n+m)+log n+nd/m) for Θ(log n+log d)≤m≤Θ(nd/log d), with a further logarithmic improvement when Θ(n) extra ancilla are available (Theorems 4 and 34). Matching Shannon-style counting and light-cone lower bounds (Theorems 15–17) show the bounds are asymptotically tight up to logarithmic factors in the stated ancilla regimes. Constructions combine Lupanov regrouping, conditionally clean ancilla, linear hashing (including JKZ25 max-load), decision-tree parallelization, and X-separating hash families with batched membership checks.

Significance. Boolean oracles and QROM are recurring bottlenecks in Hamiltonian simulation, cryptanalysis, and data-intensive quantum algorithms; worst-case size/depth/ancilla tradeoffs with matching lower bounds have been incomplete. The work essentially closes the general-total and reversible cases over a broad ancilla range (improving on folklore, Lupanov translations, and Zakablukov’s reversible bounds), and substantially extends the sparse/partial regimes of ZLY22/ZY24 down to near-logarithmic ancilla. Strengths include independent counting lower bounds, fully constructive upper bounds built from standard primitives (fan-out/fan-in, log-depth n-Toffoli), and explicit comparison tables. Results are non-uniform (hash matrices exist by the probabilistic method and are hardwired), which is standard for this complexity model and does not undercut the asymptotic claims. If the stated tradeoffs hold, they are directly usable as black-box resource estimates in algorithm design.

major comments (2)

[Abstract; Theorem 4; §1.2; §6.1] Abstract and Theorem 4 claim size/depth are “asymptotically optimal up to logarithmic factors” over the full stated ancilla range. The matching lower bound (Theorem 17) is Ω(d(n−log d)/log min{W,d(n−log d)}). When d=o(n) the leading upper-bound term O(n² log d) from computing κ=n+1 hash maps (proof of Theorem 4, §6.1) does not match this lower bound; the paper itself notes near-optimality “when d=Ω(n)” only in related work (§1.2). The abstract, Theorem 4 statement, and the optimality sentence after Theorem 34 should restrict the “nearly optimal” claim to d=Ω(n), or quantify the gap for smaller d.
[§4.3, proof of Theorem 1] In the m<n case of Theorem 1 (§4.3), the construction computes σ_S, conditionally zeros the first p inputs via fan-out, runs f_S treating those wires as ancilla, then writes A∧B into the target. The write-up does not spell out uncomputation of f_S and restoration of the p input wires on the A=0 path. A standard compute–U–write–U† sandwich works (U† restores dirty ancilla when A=0), but this should be written explicitly so that clean-ancilla semantics (Definition 8) and the claimed size/depth are verified rather than left implicit.

minor comments (6)

[Abstract; §1] Abstract opening: “the study focusing at quantum circuit optimization of such oracle is yet closed” is ungrammatical; intended meaning is that the question remains open. Same sentence appears in the introduction.
[§2.2, Fact 9] Fact 9 claims 0-ancilla O(log n)-depth fan-out. Standard dirty-target constructions need a clean workspace or recursive doubling with temporary space; since all main theorems have m≥1 this is harmless, but the fact should state the precise ancilla model or cite the 1-ancilla log-depth version.
[Table 1] Table 1 header “Fourier expansion∗ / Not full reversible logic” is easy to miss; a short footnote clarifying that the O(2^n) Fourier circuit is not a standard clean oracle would help.
[§6.1, Lemma 31] Lemma 31 (sequential AND of oracles) is a useful primitive; a one-line remark that it is essentially a low-width “OR of zeros” counter would aid readers implementing it.
[§4.3; §5.2] Several “we omit here” constant-factor and log b depth improvements (§4.3 end, §5.2 end) are fine for asymptotics but could be collected in a short appendix remark for implementers.
[Throughout; Corollary 2; Table 2] Typos/notation: “tradeoﬀs” consistently vs “tradeoffs”; “eﬀective” hyphenation; Corollary 2 ancilla “n+1≤m” vs table “n<m”; arXiv ID line “30 Jul 2026” looks like a placeholder year.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: constructive upper bounds and independent counting lower bounds

full rationale

The paper’s central claims are explicit circuit constructions (Lupanov regrouping plus conditionally clean ancilla for total oracles; linear hashing plus decision-tree bins for partial oracles; X-separating hashes plus batched membership and sequential AND for sparse oracles) matched against Shannon-style counting lower bounds over a fixed finite gate set (Lemmas 12–14 → Theorems 15–17). Those lower bounds do not depend on the constructions, and the constructions do not fit parameters to data or redefine the target quantities. Self-citations (chiefly NZS24 for log-depth multi-controlled Toffoli / conditionally clean ancilla) supply standard circuit primitives whose statements do not encode the claimed size–depth–ancilla tradeoffs; external citations (Lup58, JKZ25) likewise supply classical synthesis and hashing facts used as black-box ingredients. Hash matrices are non-uniform existence objects via the probabilistic method, which is ordinary non-uniform circuit complexity rather than circular prediction. No step reduces a claimed asymptotic by construction to its own fitted input or to an unverified self-citation uniqueness theorem.

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

The paper is constructive circuit complexity over a fixed finite gate set. It inherits classical Lupanov synthesis, standard quantum fan-out/Toffoli depth facts, and recent linear-hashing load bounds. No numerical fitting. The only non-constructive ingredients are probabilistic-method hash families treated as non-uniform advice.

assumptions (5)

domain assumption Finite constant-width gate set (e.g. Clifford+T); size/depth counted in that basis with no approximation error.
Stated in §1 and §3; all lower and upper bounds are relative to this model.
standard math Lupanov's classical Boolean synthesis: any n-bit Boolean function has circuit size (1+o(1))2^n/n.
Invoked as Theorem 22 / [Lup58] and used as a black-box subroutine in Lemma 23 and Theorem 1.
domain assumption n-controlled Toffoli in O(n) size, O(log n) depth, 1 ancilla (Theorem 11 / NZS24); fan-out and fan-in in O(n) size O(log n) depth, 0 ancilla (Facts 9–10).
Used throughout every construction; NZS24 has author overlap but is an independent primitive claim.
standard math Linear hashing achieves near-optimal max load in expectation (JKZ25) and random linear maps separate a fixed set X from its complement with O(n) maps into F_{log d}^{2} (Lemmas 24, 28, 29).
Existence via probabilistic method; circuits treat the matrices as given non-uniform advice.
domain assumption Clean ancilla model: ancilla start and end in |0⟩, implementing the exact oracle unitary on the data register (Definition 8).
All resource claims are for clean ancilla; dirty-ancilla variants are not analyzed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nearly optimal quantum circuits for Boolean oracles." pith.science (2026). https://pith.science/paper/4HBGPYBT

@misc{pith2026260728402,
  author       = {Pith},
  title        = {Pith review of: Nearly optimal quantum circuits for Boolean oracles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4HBGPYBT}},
  note         = {Machine review of arXiv:2607.28402}
}

abstract

Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size $b$: with $1\le m\le\Theta\left(\frac{2^n}{n}\right)$ ancilla, size $\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)$, depth $\mathcal{O}\left(\frac{b2^n}{n+m}\right)$; partial Boolean functions of effective support size $d$ and output size $b$: with $\Theta\left(\log d\right)\le m\le \Theta\left(d\right)$ ancilla, size $\mathcal{O}\left(n\log d+bd\right)$, depth $\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)$; sparse Boolean functions of true input size $d$: with $\Theta\left(\log n+\log d\right)\le m\le\Theta\left(\frac{nd}{\log d}\right)$ ancilla, size $\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)$, depth $\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)$. All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references

[1]

Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm

Dong An and Lin Lin. Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm . ACM Transactions on Quantum Computing , 3(2):5:1--5:28, March 2022

2022
[2]

Multiplicative complexity of vector valued Boolean functions

Joan Boyar and Magnus Gausdal Find. Multiplicative complexity of vector valued Boolean functions. Theoretical Computer Science , 720:36--46, April 2018

2018
[3]

Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven

Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity . Physical Review X , 8(4):041015, October 2018

2018
[4]

Optimal T depth quantum circuits for implementing arbitrary Boolean functions, June 2025

Suman Dutta, Anik Basu Bhaumik, Anupam Chattopadhyay, and Subhamoy Maitra. Optimal T depth quantum circuits for implementing arbitrary Boolean functions, June 2025

2025
[5]

Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing , pages 212--219. ACM, 1996

1996
[6]

Kumar, and David Zuckerman

Michael Jaber, Vinayak M. Kumar, and David Zuckerman. Linear Hashing Is Optimal . In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 245--255, Prague Czechia, June 2025. ACM

2025
[7]

Implementing grover oracles for quantum key search on AES and LowMC

Samuel Jaques, Michael Naehrig, Martin Roetteler, and Fernando Virdia. Implementing grover oracles for quantum key search on AES and LowMC . In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology-- EUROCRYPT 2020 , volume 12106 of Lecture Notes in Computer Science , pages 280--310, Cham, May 2020. Springer

2020
[8]

Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian Simulation by Quantum Signal Processing . Physical Review Letters , 118(1):010501, January 2017

2017

Show all 25 references

[9]

Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization . Quantum , 3:163, July 2019

2019
[10]

Trading T gates for dirty qubits in state preparation and unitary synthesis

Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. Trading T gates for dirty qubits in state preparation and unitary synthesis. Quantum , 8:1375, June 2024

2024
[11]

O. B. Lupanov. Ob odnom metode sinteza skhem [on a method of circuit synthesis]. Izvestiya Vysshikh Uchebnykh Zavedenii. Radiofizika , 1(1):120--140, 1958. In Russian

1958
[12]

Halving the cost of QROM , May 2026

Danial Motlagh and Matthew Pocrnic. Halving the cost of QROM , May 2026

2026
[13]

The Role of Multiplicative Complexity in Compiling Low T-count Oracle Circuits

Giulia Meuli, Mathias Soeken, Earl Campbell, Martin Roetteler, and Giovanni de Micheli . The Role of Multiplicative Complexity in Compiling Low T-count Oracle Circuits . In 2019 IEEE / ACM International Conference on Computer-Aided Design ( ICCAD ) , pages 1--8, November 2019

2019
[14]

Quantum circuit for multi-qubit Toffoli gate with optimal resource, February 2024

Junhong Nie, Wei Zi, and Xiaoming Sun. Quantum circuit for multi-qubit Toffoli gate with optimal resource, February 2024

2024
[15]

Optimization of Quantum Read-Only Memory Circuits , April 2022

Koustubh Phalak, Mahabubul Alam, Abdullah Ash-Saki , Rasit Onur Topaloglu, and Swaroop Ghosh. Optimization of Quantum Read-Only Memory Circuits , April 2022

2022
[16]

Claude . E. Shannon. The synthesis of two-terminal switching circuits. The Bell System Technical Journal , 28(1):59--98, January 1949

1949
[17]

LUT-Based Hierarchical Reversible Logic Synthesis

Mathias Soeken, Martin Roetteler, Nathan Wiebe, and Giovanni De Micheli. LUT-Based Hierarchical Reversible Logic Synthesis . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 38(9):1675--1688, September 2019

2019
[18]

BDD-based synthesis of reversible logic for large functions

Robert Wille and Rolf Drechsler. BDD-based synthesis of reversible logic for large functions. In Proceedings of the 46th Annual Design Automation Conference , pages 270--275, San Francisco California, July 2009. ACM

2009
[19]

Asymptotically optimal synthesis of reversible circuits

Xian Wu and Lvzhou Li. Asymptotically optimal synthesis of reversible circuits. Information and Computation , 301:105235, December 2024

2024
[20]

Zakablukov

Dmitry V. Zakablukov. On Asymptotic Gate Complexity and Depth of Reversible Circuits With Additional Memory , March 2016

2016
[21]

Zakablukov

Dmitry V. Zakablukov. General Upper Bounds for Gate Complexity and Depth of Reversible Circuits Consisting of NOT , CNOT and 2- CNOT Gates , March 2017

2017
[22]

Zakablukov

Dmitry V. Zakablukov. On asymptotic gate complexity and depth of reversible circuits without additional memory. Journal of Computer and System Sciences , 84:132--143, March 2017

2017
[23]

Quantum State Preparation with Optimal Circuit Depth : Implementations and Applications

Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. Quantum State Preparation with Optimal Circuit Depth : Implementations and Applications . Physical Review Letters , 129(23):230504, November 2022

2022
[24]

Unified architecture for quantum lookup tables

Shuchen Zhu, Aarthi Sundaram, and Guang Hao Low. Unified architecture for quantum lookup tables. Physical Review Research , 7(4):043230, December 2025

2025
[25]

Circuit complexity of quantum access models for encoding classical data

Xiao-Ming Zhang and Xiao Yuan. Circuit complexity of quantum access models for encoding classical data. npj Quantum Information , 10(1):42, April 2024

2024

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.

[1] [1]

Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm

Dong An and Lin Lin. Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm . ACM Transactions on Quantum Computing , 3(2):5:1--5:28, March 2022

2022

[2] [2]

Multiplicative complexity of vector valued Boolean functions

Joan Boyar and Magnus Gausdal Find. Multiplicative complexity of vector valued Boolean functions. Theoretical Computer Science , 720:36--46, April 2018

2018

[3] [3]

Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven

Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity . Physical Review X , 8(4):041015, October 2018

2018

[4] [4]

Optimal T depth quantum circuits for implementing arbitrary Boolean functions, June 2025

Suman Dutta, Anik Basu Bhaumik, Anupam Chattopadhyay, and Subhamoy Maitra. Optimal T depth quantum circuits for implementing arbitrary Boolean functions, June 2025

2025

[5] [5]

Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing , pages 212--219. ACM, 1996

1996

[6] [6]

Kumar, and David Zuckerman

Michael Jaber, Vinayak M. Kumar, and David Zuckerman. Linear Hashing Is Optimal . In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 245--255, Prague Czechia, June 2025. ACM

2025

[7] [7]

Implementing grover oracles for quantum key search on AES and LowMC

Samuel Jaques, Michael Naehrig, Martin Roetteler, and Fernando Virdia. Implementing grover oracles for quantum key search on AES and LowMC . In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology-- EUROCRYPT 2020 , volume 12106 of Lecture Notes in Computer Science , pages 280--310, Cham, May 2020. Springer

2020

[8] [8]

Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian Simulation by Quantum Signal Processing . Physical Review Letters , 118(1):010501, January 2017

2017