REVIEW 3 major objections 5 minor 31 references
The Role of Multiplicative Complexity in Compiling Low T-count Oracle Circuits
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper proves that a Boolean function's multiplicative complexity $c_\land(f)$ gives a quantum oracle with at most $4c_\land(f)$ T gates and $c_\land(f)$ ancillae.
desk verdict The multiplicative-complexity connection is genuinely useful, but the printed Algorithm 1 has polarity and output-copy bugs, so the 4c∧(f) bound is not proven as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the xor-and inverter graph (XAG), a Boolean network over $\{\land,\oplus,1\}$ with inverters pushed to the inputs, whose AND-node count $c$ is the parameter that drives the cost. The mechanism is the compute/uncompute asymmetry of the Toffoli gate: a logical-AND Toffoli costs 4 T gates to compute, but it can be uncomputed with a measurement followed by a Clifford-controlled-$Z$ correction, using zero T gates. The paper exploits this by computing each AND node once, copying the final result onto the output line, and uncomputing all AND nodes in reverse order; XOR blocks are realized in-place on the ancilla lines via CNOTs, so only AND nodes contribute to the T-count. A second mechanism is a reversible pebble game with XOR-in-place semantics, encoded as a SAT formula, which finds legal schedules that use fewer pebbles (qubits) at the cost of recomputing AND gates.
What would settle it
Simulate the compiled oracle for a small function whose XAG has at least two sequential AND gates (for instance a 2-bit multiplier) on all $2^n$ input values, and check that the ancilla qubits return to $|0\rangle$ and that the output qubits carry $y\oplus f(x)$ with no residual phase. A direct test of the gadget is to use the output of one measurement-based uncompute as the control of a later Toffoli before its own uncompute, and verify that the Clifford correction still returns the full system to the intended state; any deviation would refute the claimed $4c_\land(f)$ bound for general circuits.
Extended reading notes
Core claim
The central discovery is that the multiplicative complexity of a Boolean function is, up to a constant factor of 4, the T-count of its quantum oracle. The construction treats every AND node of the input network as the only source of non-Clifford cost: each AND gate is implemented as a Toffoli computation that consumes 4 T gates, and its uncomputation is carried out with a measurement gadget that costs only Clifford gates, a conditional $Z$ correction. XOR nodes are computed in-place on existing qubit lines with CNOT gates, so they add neither T gates nor ancillae. The paper also gives a SAT-based reversible pebble game on the network that trades ancilla qubits against T-count by recomputing AND gates. On adder circuits, whose smallest networks have known minimum AND count, the method reproduces the best manually designed T-counts.
Load-bearing premise
The construction's 4-T-per-AND count rests on the measurement-based uncompute gadget restoring all ancillae to $|0\rangle$ with only Clifford corrections even when the AND output is entangled with the rest of the circuit; if that gadget does not behave as stated inside arbitrary circuits, the $4c_\land(f)$ bound would not follow.
Editorial extensions
If this is right
- Every XAG with $c$ AND nodes compiles into an oracle with exactly $4c$ T gates and $c$ ancillae, making T-count a literal rescaling of classical AND count.
- For functions with known minimal multiplicative complexity (for example, all symmetric Boolean functions), the construction yields a provably minimum T-count under the stated gate set, because a Toffoli cannot be computed with fewer than 4 T gates.
- Classical results bounding or computing $c_\land(f)$ transfer directly to quantum resource estimates for search-based attacks and other oracle-based algorithms.
- The SAT-based pebble game provides a smooth space/time trade-off: fewer ancillae can be obtained by recomputing AND nodes, at the cost of additional T gates.
- The method matches the best manually designed T-counts for adder circuits, indicating that automatic compilation can reach hand-crafted quality when the input network is minimal in AND count.
Reading between the lines
- By extension, any future improvement in classical logic synthesis that lowers the AND count of a function's network automatically lowers the quantum T-count of its oracle; the quantum search for low-T circuits is thereby reducible to a classical AND-minimization problem.
- By extension, because the T-count bound ignores XOR nodes, two networks with the same AND count can differ substantially in CNOT overhead; XOR-aware rewriting may offer significant total-cost savings once Clifford gates are given a concrete price.
- A structural condition worth testing is whether the measurement-based uncompute correction commutes through the CNOTs of later AND computations in a large cascade; if it does not, the 4-per-AND accounting could miss an accumulated phase-correction cost, a point the paper's Clifford-counting analysis does not explicitly address.
- The same compute-cheap/uncompute-expensive asymmetry appears in other reversible-compilation settings, so the pebble-game formulation may transfer to memory-management problems far beyond oracle synthesis.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents a constructive compilation method for quantum oracle circuits. Given a Boolean function f represented as a 2-regular XOR-AND graph (XAG) over {AND, XOR, NOT}, the proposed Algorithm 1 synthesizes a Clifford+T circuit that realizes U_f: |x>|y>|0>^k -> |x>|y⊕f(x)>|0>^k. Each AND gate costs one 4-T Toffoli computation and one measurement-based Clifford-only uncomputation, yielding T-count at most 4 times the number of AND nodes. The authors interpret this as an upper bound 4 c∧(f) on T-count and k = c∧(f) on ancillae, where c∧(f) is multiplicative complexity. They also propose a SAT-based reversible pebbling method to trade qubits for T gates, and report experimental comparisons with LUT-based hierarchical synthesis and Bennett-based clean-up, plus resource estimates for cryptographic benchmarks.
Significance. The connection drawn between multiplicative complexity of Boolean functions and the T-count of quantum oracles is conceptually attractive and, if established, would transfer a large body of work on multiplicative complexity into quantum resource estimation. The experimental results, e.g., matching the best-known T-count for adders, suggest the underlying implementation is effective and the comparison numbers are useful to the quantum compilation community. The SAT-based pebbling framework is a new angle on the qubit/T-count trade-off. However, the central claim rests on the correctness of Algorithm 1 as a general construction for arbitrary XAGs, and that correctness is not established by the manuscript as written.
major comments (3)
- [Section III, Algorithm 1, lines 12-16] The post-Toffoli NOT operations (lines 15-16) are swapped relative to the pre-Toffoli NOT operations (lines 12-13): line 15 toggles t2 when p=1, while line 12 toggled t1, and line 16 toggles t1 when q=1, while line 13 toggled t2. Consequently, when an AND gate has a complemented fan-in, the qubits t1 and t2 are not restored to their original values before the next iteration. If a subsequently processed AND gate uses any of those qubits (as elements of its ltfi sets), it receives corrupted parities and the computed oracle is wrong. A simple counterexample consists of two consecutive AND gates, the first with one complemented fan-in and the second using that complemented primary input directly. The fix is to apply the undoing NOTs to the same qubits that were toggled before the Toffoli, i.e., 'if p then NOT(t1); if q then NOT(t2)', and to provide a correct-by-construction argument that all fan-in qubits are restored before the loop moves on. This issue is load-bearing because the claimed 4 c∧(f) bound depends on Algorithm 1 being correct for arbitrary XAGs, including complemented fan-ins.
- [Section III, Algorithm 1, lines 21-24] The output-copy step is only well-defined when the final node x_{n+r} is an AND gate. If the network's last step is an XOR node, as in Example 1 (x7 = x2 ⊕ x6), there is no qubit named x_{n+r}; the algorithm as printed would access a nonexistent qubit. The correct procedure is to copy the output parity by applying CNOT(x, y) for every x in ltfi(x_{n+r}), followed by a NOT(y) if the output node's polarity p_{n+r} is 0 (under the paper's x^0 = ¬x convention). Furthermore, line 23 reads the loop-local variable p from the last AND iteration rather than the output node's polarity p_{n+r}. These two values can differ, and the algorithm provides no way to retrieve p_{n+r} at line 23. This is a load-bearing correctness gap because the claim that the construction realizes U_f for arbitrary f depends on a correct output-copy step.
- [Section II-E and Algorithm 1] The polarity convention is internally inconsistent. Section II-E defines x^0 = ¬x and x^1 = x, so a complemented fan-in corresponds to p=0. Yet Algorithm 1 line 12 applies NOT(t1) when p=1, and line 23 applies NOT(y) when p=0. These two uses of p assume opposite meanings of the polarity bit. The authors should settle on a single convention (e.g., p=1 meaning 'complement this fan-in') and update all of Algorithm 1, including the output-copy condition, to use that convention consistently. As written, the pseudocode cannot be executed faithfully even for the non-complemented cases without ambiguity.
minor comments (5)
- [Section II-D, Eq. (5)] Equation (5) appears garbled in the manuscript: the equality involving 'H Z H' is not a well-formed equation as typeset. The measurement-based uncompute circuit would be clearer if drawn as a proper circuit diagram with measurement and classically controlled Clifford corrections.
- [Section II-E, Eq. (7)] The notation x^0 = ¬x and x^1 = x is nonstandard and is a source of the polarity confusion in Algorithm 1. Please either adopt the more common notation x^1 = x and x^0 = ¬x with explicit Boolean notation, or clearly state the convention next to the algorithm.
- [Section V-C, Table II] Table II lists 'mx7x41' twice, with slightly different input/output sizes (14 7 45 40 and 14 7 44 40). One of these appears to be a typo, likely the second should be 'mx7x31' to match the text describing both x^7+x^4+1 and x^7+x^3+1. Please correct the label.
- [Section V-A] The phrase 'Our results have in average about 20.4× smaller T-count' has a grammatical issue; it should read 'Our results have, on average, about 20.4× fewer T gates.'
- [Section III, Algorithm 1] The pseudocode for the L1⊆L2 swap is described in the prose but not commented in the algorithm. Adding a comment at lines 5-7, and also explaining the role of the ltfi decomposition in a few words, would improve readability.
Circularity Check
No circularity: the 4c∧(f) T-count upper bound follows constructively from the definition of multiplicative complexity and external AND-gate implementations.
full rationale
The paper's central bound, 4 c∧(f) T gates with c∧(f) ancillae, is a constructive consequence of a fixed translation: each AND node in an XAG is compiled to a logical-AND compute (4 T gates, from Gidney's circuit) and a measurement-based uncompute (Clifford-only). Since c∧(f) is defined as the minimum number of AND gates over {∧,⊕,1}, a minimal network with exactly c∧(f) AND gates exists by definition; applying Algorithm 1 to that network yields a circuit with exactly 4 c∧(f) T gates and c∧(f) ancillae. This is a derivation, not a fit: no parameter is tuned to match the reported T-counts, and no claimed prediction is constructed from the same data used for comparison. The only self-citations are the Howard–Campbell 4-T lower bound and related compiler papers; the lower bound is an external, parameter-free theorem and is not used to manufacture the upper bound. Algorithm 1's printed polarity and output-copy issues noted by the reviewer are correctness gaps, not circularity. Therefore no circular step is present.
Assumptions & free parameters
assumptions (3)
- domain assumption The Toffoli gate requires at least 4 T gates, and the compute/uncompute gadget from [7] realizes an AND with 4 T gates for compute and 0 for uncompute.
- standard math For any Boolean function f, there exists a logic network over {∧,⊕,1} with exactly c_∧(f) AND gates, i.e., a network achieving the multiplicative complexity.
- domain assumption The reversible pebble game encoding with in-place XOR moves (Section IV) faithfully models the qubit resources and the allowed computations on XAGs.
Cite this review
Pith. "Pith review of The Role of Multiplicative Complexity in Compiling Low T-count Oracle Circuits." pith.science (2026). https://pith.science/paper/PMX3BM3A
@misc{pith2026190801609,
author = {Pith},
title = {Pith review of: The Role of Multiplicative Complexity in Compiling Low T-count Oracle Circuits},
year = {2026},
howpublished = {\url{https://pith.science/paper/PMX3BM3A}},
note = {Machine review of arXiv:1908.01609}
}
abstract
We present a constructive method to create quantum circuits that implement oracles $|x\rangle|y\rangle|0\rangle^k \mapsto |x\rangle|y \oplus f(x)\rangle|0\rangle^k$ for $n$-variable Boolean functions $f$ with low $T$-count. In our method $f$ is given as a 2-regular Boolean logic network over the gate basis $\{\land, \oplus, 1\}$. Our construction leads to circuits with a $T$-count that is at most four times the number of AND nodes in the network. In addition, we propose a SAT-based method that allows us to trade qubits for $T$ gates, and explore the space/complexity trade-off of quantum circuits. Our constructive method suggests a new upper bound for the number of $T$ gates and ancilla qubits based on the multiplicative complexity $c_\land(f)$ of the oracle function $f$, which is the minimum number of AND gates that is required to realize $f$ over the gate basis $\{\land, \oplus, 1\}$. There exists a quantum circuit computing $f$ with at most $4 c_\land(f)$ $T$ gates using $k = c_\land(f)$ ancillae. Results known for the multiplicative complexity of Boolean functions can be transferred. We verify our method by comparing it to different state-of-the-art compilers. Finally, we present our synthesis results for Boolean functions used in quantum cryptoanalysis.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
A fast quantum mechanical algorithm for da tabase search,
L. K. Grover, “A fast quantum mechanical algorithm for da tabase search,” in Symposium on Theory and Computing , 1996, pp. 212–219
work page 1996
-
[2]
Polynomial-time algorithms for prime facto rization and discrete logarithms on a quantum computer,
P . W. Shor, “Polynomial-time algorithms for prime facto rization and discrete logarithms on a quantum computer,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1484–1509, 1997
work page 1997
-
[3]
Quantum algorit hm for linear systems of equations,
A. W. Harrow, A. Hassidim, and S. Lloyd, “Quantum algorit hm for linear systems of equations,” Phys. Rev. Lett. , vol. 103, 2009
work page 2009
-
[4]
A meet-in- the-middle algorithm for fast synthesis of depth-optimal quantum circ uits,
M. Amy, D. Maslov, M. Mosca, and M. Roetteler, “A meet-in- the-middle algorithm for fast synthesis of depth-optimal quantum circ uits,” IEEE Trans. on CAD of Integrated Circuits and Systems , vol. 32, no. 6, pp. 818–830, 2013
work page 2013
-
[5]
On the multiplicat ive complexity of boolean functions over the basis (∧,⊕,1),
J. Boyar, R. Peralta, and D. Pochuev, “On the multiplicat ive complexity of boolean functions over the basis (∧,⊕,1),” Theoretical Computer Science, vol. 235, no. 1, pp. 43–57, 2000
work page 2000
-
[6]
Low-overhead constructions for the fault-to lerant Toffoli gate,
C. Jones, “Low-overhead constructions for the fault-to lerant Toffoli gate,” Physical Review A , vol. 87, no. 2, p. 022328, 2013
work page 2013
-
[7]
Halving the cost of quantum addition,
C. Gidney, “Halving the cost of quantum addition,” Quantum, vol. 2, p. 74, 2018
work page 2018
-
[8]
On the complexity of computing two nonlinear ity measures,
M. G. Find, “On the complexity of computing two nonlinear ity measures,” in Int’l Computer Science Symposium in Russia , 2014, pp. 167–175
work page 2014
Show all 31 references
-
[9]
Tight bounds for the multiplica tive complexity of symmetric functions,
J. Boyar and R. Peralta, “Tight bounds for the multiplica tive complexity of symmetric functions,” Theoretical Computer Science , vol. 396, no. 1–3, pp. 223–246, 2008
2008
-
[10]
Reduci ng the multiplicative complexity in logic networks for crypto graphy and security applications,
E. Testa, M. Soeken, L. Amarú, and G. De Micheli, “Reduci ng the multiplicative complexity in logic networks for crypto graphy and security applications,” in DAC, 2019
2019
-
[11]
Logic minimizat ion techniques with applications to cryptology,
J. Boyar, P . Matthews, and R. Peralta, “Logic minimizat ion techniques with applications to cryptology,” Journal of Cryptology , vol. 26, no. 2, pp. 280–312, 2013
2013
-
[12]
The multiplicati ve complexity of 6-variable Boolean functions,
Ç. Çalik, M. S. Turan, and R. Peralta, “The multiplicati ve complexity of 6-variable Boolean functions,” Cryptography and Communications , vol. 11, no. 1, pp. 93–107, 2019
2019
-
[13]
Time/space trade-offs for reversible c omputation,
C. H. Bennett, “Time/space trade-offs for reversible c omputation,” SIAM Journal on Computing , vol. 18, no. 4, pp. 766–776, 1989
1989
-
[14]
Hi erarchical reversible logic synthesis using LUTs,
M. Soeken, M. Roetteler, N. Wiebe, and G. De Micheli, “Hi erarchical reversible logic synthesis using LUTs,” in Design Automation Conference, 2017, pp. 78:1–78:6
2017
-
[15]
A best-fit mapping algorithm to facilitate ESOP-decomposi tion in Clifford+ T quantum network synthesis,
G. Meuli, M. Soeken, M. Roetteler, N. Wiebe, and G. De Mic heli, “A best-fit mapping algorithm to facilitate ESOP-decomposi tion in Clifford+ T quantum network synthesis,” in Asia and South Pacific Design Automation Conference . IEEE Press, 2018, pp. 664–669
2018
-
[16]
Universal quantum computatio n with ideal Clifford gates and noisy ancillas,
S. Bravyi and A. Kitaev, “Universal quantum computatio n with ideal Clifford gates and noisy ancillas,” Physical Review A, vol. 71, p. 022316, 2005
2005
-
[17]
Quantum computation wi th realistic magic-state factories,
J. O’Gorman and E. T. Campbell, “Quantum computation wi th realistic magic-state factories,” Physical Review A , vol. 95, no. 3, p. 032338, 2017
2017
-
[18]
Reversible pebbling game for quantum memory management,
G. Meuli, M. Soeken, M. Roetteler, N. Bjorner, and G. De M icheli, “Reversible pebbling game for quantum memory management,” in Design, Automation and Test in Europe , 2019
2019
-
[19]
Quantum teleportation i s a universal computational primitive,
D. Gottesman and I. L. Chuang, “Quantum teleportation i s a universal computational primitive,” Nature, vol. 402, pp. 390–393, 1999
1999
-
[20]
Application of a resource th eory for magic states to fault-tolerant quantum computing,
M. Howard and E. Campbell, “Application of a resource th eory for magic states to fault-tolerant quantum computing,” Phys. Rev. Lett., vol. 118, 2017
2017
-
[21]
REVS: A tool fo r space-optimized reversible circuit synthesis,
A. Parent, M. Roetteler, and K. M. Svore, “REVS: A tool fo r space-optimized reversible circuit synthesis,” in Int’l Conf. on Reversible Computation, 2017, pp. 90–101
2017
-
[22]
D. E. Knuth, The Art of Computer Programming, V olume 4, Fascicle 6: Satisfiability . Addison-Wesley, 2015
2015
-
[23]
DAG-awa re AIG rewriting: a fresh look at combinational logic synthesis,
A. Mishchenko, S. Chatterjee, and R. Brayton, “DAG-awa re AIG rewriting: a fresh look at combinational logic synthesis,” in Design Automation Conference, 2006
2006
-
[24]
ESOP-based toffo li gate cascade generation,
K. Fazel, M. A. Thornton, and J. Rice, “ESOP-based toffo li gate cascade generation,” in Pacific Rim Conference on Communications, Computers and Signal Processing , 2007
2007
-
[25]
Applying grover’s algorithm to AES: quantum resource esti mates,
M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwan dt, “Applying grover’s algorithm to AES: quantum resource esti mates,” in Post-Quantum Cryptography, 2016
2016
-
[26]
Q#: Enabling scalable quantum computing and development with a high-lev el DSL,
K. Svore, A. Geller, M. Troyer, J. Azariah, C. Granade, B . Heim, V . Kliuchnikov, M. Mykhailova, A. Paz, and M. Roetteler, “Q#: Enabling scalable quantum computing and development with a high-lev el DSL,” in Real W orld Domain Specific Languages W orkshop , 2018, pp. 7:1–7:10
2018
-
[27]
Z3: an efficient SMT solver ,
L. M. de Moura and N. Bjørner, “Z3: an efficient SMT solver ,” in Int’l Conf. on Tools and Algorithms for the Construction and Analy sis of Systems, 2008, pp. 337–340
2008
-
[28]
Synthesizing shortest linear straight-line programs over GF(2) using SA T,
C. Fuhs and P . Schneider-Kamp, “Synthesizing shortest linear straight-line programs over GF(2) using SA T,” in Int’l Conf. on Theory and Applications of Satisfiability Testing , 2010, pp. 71–84
2010
-
[29]
Aut omated optimization of large quantum circuits with continuous par ameters,
Y . Nam, N. J. Ross, Y . Su, A. M. Childs, and D. Maslov, “Aut omated optimization of large quantum circuits with continuous par ameters,” npj Quantum Information , vol. 4, no. 23, pp. 1–12, 2018
2018
-
[30]
On the CNOT-complex ity of CNOT-phase circuits,
M. Amy, P . Azimzadeh, and M. Mosca, “On the CNOT-complex ity of CNOT-phase circuits,” arXiv preprint arXiv:1712.01859 , 2017
2017 arXiv
-
[31]
SA T-based {CNOT, T} quantum circuit synthesis,
G. Meuli, M. Soeken, and G. De Micheli, “SA T-based {CNOT, T} quantum circuit synthesis,” in Int’l Conf. on Reversible Computation . Springer, 2018, pp. 175–188
2018
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.