Pith. sign in

REVIEW 4 major objections 4 minor 16 references

Optimal T depth quantum circuits for implementing arbitrary Boolean functions

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read For any Boolean function of algebraic degree k, this paper builds a quantum circuit with exact T depth ⌈log₂ k⌉ and claims no circuit can do better.

desk verdict Useful benchmark construction, but the optimality proof rests on an unstated lower bound and the theorem statement has a n/k misprint. read the letter →

arxiv 2506.01542 v1 pith:LSHXQXA7 submitted 2025-06-02 quant-ph

Suman Dutta , Anik Basu Bhaumik , Anupam Chattopadhyay , Subhamoy Maitra This is my paper · ORCID
classification quant-ph MSC 81P6894C10
keywords TdepthBooleanfunctionsAlgebraicNormalFormmulti-controlledToffoliClifford+TAESS-boxoracleconstructionquantumcircuitsynthesis
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

Given any Boolean function written in algebraic normal form — an XOR sum of AND monomials — this paper builds a quantum circuit that evaluates every monomial in parallel. If the function's algebraic degree is $k$, the circuit uses exactly $\lceil \log_2 k \rceil$ layers of T gates, and the paper argues this is the minimum possible. The construction encodes each degree-$d$ monomial as a $d$-controlled Toffoli gate, fans out the input variables with CNOTs so all gates can fire at once, and collects the results onto the output qubits with XORs. The same recipe gives claimed optimal T depths of 3 for the AES S-box and 30, 36, and 42 for round-wise AES-128, AES-192, and AES-256, at the cost of a large ancilla and CNOT overhead. This matters because T gates are the expensive ingredient in fault-tolerant quantum computers, so a provable floor on T depth is a benchmark for all subsequent circuit optimization.

What carries the argument

The load-bearing object is the Algebraic Normal Form (ANF), the unique representation of a Boolean function as an XOR sum of AND monomials over the field with two elements. The mechanism is the exact T-depth bound for multi-controlled Toffoli (MCT) gates: a gate that negates its target only when all $k$ control bits are 1 can be decomposed with T depth exactly $\lceil \log_2 k \rceil$ using a binary tree and measurement-based uncomputation. Around that core, the construction places CNOT fan-out to create enough copies of each input for all monomials to be evaluated in parallel, and an XOR fan-in to merge monomial outputs onto each output qubit. Together these pieces reduce an arbitrary function's T depth to the depth of its largest monomial, namely $\lceil \log_2 k \rceil$.

What would settle it

Exhaustively search all 4-variable Boolean functions of algebraic degree 4 for a Clifford+T circuit of T depth 1: the paper predicts none exists, so finding one would refute the optimality claim. Alternatively, for the AES benchmark, exhibit a round-wise AES-128 circuit that reuses T gates between consecutive rounds and still computes the standard S-box with total T depth below 30; that observation would falsify the claimed 30-depth floor.

Watch

Extended reading notes

Core claim

The central claim is that the T depth of any Boolean function is set by its algebraic degree, not by its number of monomials or outputs. For $f: \mathbb{F}_2^n \to \mathbb{F}_2^m$ of degree $k$, the paper's construction realizes $f$ with a Clifford+T circuit whose T depth is exactly $\lceil \log_2 k \rceil$: each nonlinear ANF monomial is computed by a multi-controlled Toffoli gate, input copies are generated by CNOT fanout so all monomials are evaluated in parallel, and the monomial results are XORed onto the target qubits using a binary-tree decomposition whose T depth is $\lceil \log_2 k \rceil$. Since any degree-$k$ function contains a $k$-variable monomial, and since the imported multi-controlled Toffoli result states that a $k$-MCT gate cannot be implemented in fewer T layers, the paper concludes the depth is optimal. Applied to the AES S-box (degree 7) this gives T depth 3; composed over 10, 12, and 14 sequential rounds it gives AES-128, AES-192, and AES-256 T depths of 30, 36, and 42, with the explicit caveat that this optimality is within the round-wise implementation model.

Load-bearing premise

The optimality claim rests on an imported result stating that a $k$-way AND gate takes exactly $\lceil \log_2 k \rceil$ T layers, and on assuming that no degree-$k$ Boolean function can share T-gate work across its monomials to go below that; the AES numbers also assume the cipher is implemented round by round rather than as one monolithic Boolean function.

Editorial extensions

If this is right

  • For any oracle construction — search or period-finding algorithms — the paper fixes a hard floor: no Clifford+T circuit for a degree-$k$ Boolean function can run in fewer than $\lceil \log_2 k \rceil$ T layers, and its construction reaches that floor.
  • S-boxes can now be compared by their maximum algebraic degree: any 8-bit S-box of degree 7, such as AES's, is claimed to have optimal T depth 3, making T depth a predictable function of degree rather than of gate-count heuristics.
  • The AES benchmarks of 30, 36, and 42 are formally optimal only in the round-wise model; the paper itself notes that treating AES as one combinational function gives T depths 8 or 9, so the practical benchmark is for iterative cipher implementations.
  • The construction's exponential ancilla and CNOT costs advertise a trade-off: replacing the T-depth-1 Toffoli decomposition with a logical-AND version saves a large number of ancillas and CNOTs at the price of one additional T layer, showing how other resources can be optimized around the T-depth floor.

Reading between the lines

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

  • A direct proof of the lower bound may not need the imported multi-controlled Toffoli theorem: since each layer of AND gates at most doubles the algebraic degree of every intermediate polynomial, any circuit for a degree-$k$ function requires at least $\lceil \log_2 k \rceil$ AND layers; making that argument explicit would make the optimality self-contained.
  • The ANF-parallelism strategy trades exponential ancillas for logarithmic depth; an open question implied by the paper is whether families like S-boxes admit near-optimal T depth with polynomially many ancillas, or whether the exponential overhead is unavoidable.
  • For AES, the round-wise model treats the key schedule as precomputed; if round keys are generated online inside the circuit, the schedule's XOR and S-box operations would have to be interleaved with the data path, and the paper's depth accounting would need to absorb those costs.
  • Because the T depth depends only on algebraic degree, the same construction transfers to any reversible primitive built from AND and XOR: the relevant benchmark is the analytic degree, so ciphers with lower-degree S-boxes are, in this model, cheaper in T depth.
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.

Referee Report

4 major / 4 minor

Summary. The paper presents a construction for implementing any n-input m-output Boolean function f of algebraic degree k as a Clifford+T circuit with a claimed optimal T depth of ceil(log2 k). The construction is based on the Algebraic Normal Form of f: each degree-k monomial is realized as a k-controlled Toffoli gate, all such gates are executed in parallel using many ancilla qubits, and the individual MCT decompositions follow the authors' earlier work [10]. The paper applies this to the AES S-box and to full AES-128/192/256, claiming optimal T depths of 30, 36, and 42 under a round-wise implementation model.

Significance. The proposed construction is explicit and concrete, with detailed resource counts, circuit diagrams, and a trade-off discussion between T depth and ancilla/CNOT overhead. If the optimality claim is properly established, the paper would provide a useful benchmark for T-depth lower bounds in oracle synthesis and block-cipher implementation. The paper also gives credit where due: it identifies the extension from [10] and is honest about the high ancilla overhead. However, the central optimality assertion is not proved in the manuscript as written; the lower-bound argument is imported from a per-gate result and would need a standard degree-versus-T-depth lemma to be transferred to arbitrary Boolean functions. The AES claims are additionally restricted by the round-wise implementation model, which the paper sometimes states but sometimes overstates.

major comments (4)
  1. [Theorem 1] Theorem 1 as printed states that the Clifford+T decomposition can be realized with optimal T depth of ceil(log2 n). This contradicts the Abstract, the proof, Example 1 (T depth 1 for n=3 and degree 2), and the AES calculation (ceil(log2 7)=3 for the S-box). The intended statement is clearly ceil(log2 k), where k is the algebraic degree of f. The theorem statement must be corrected, because all subsequent lower-bound claims are built on this quantity.
  2. [Proof of Theorem 1] The optimality (lower-bound) half of the proof is not established. The proof invokes [10, Corollary 1] for the T depth of a k-MCT gate, but that is a lower bound for a single multi-controlled Toffoli gate, not for an arbitrary Boolean function of degree k. A degree-k function might be computed without explicitly realizing any k-MCT, for example through cancellation or factorization of monomials, and the paper gives no argument that the per-gate lower bound transfers to the whole function class. To complete the proof, the authors should state and prove a lemma that any exact Clifford+T circuit of T depth d computes Boolean functions of algebraic degree at most 2^d (or an equivalent statement); then T depth at least ceil(log2 k) follows directly. Without such a lemma, the word 'optimal' in Theorem 1 and in the AES section is unsupported.
  3. [Proof of Theorem 1, CNOT depth] The CNOT-depth expression in the proof, ceil(log2( sum_{k=2}^n C(n-1,k-1) - n )) = n-1, is mathematically incorrect. The sum equals 2^{n-1}-1, so the argument of the logarithm is 2^{n-1}-n-1, whose base-2 logarithm is not generally n-1 (for example, n=4 gives log2(3) ≈ 1.58, whose ceiling is 2, not 3). This invalidates the stated CNOT depth in Theorem 1 and propagates to Tables I–III. The CNOT-depth derivation needs to be corrected or the claimed bound removed.
  4. [AES section, Table III, and Conclusions] The paper's claims that T depths 30, 36, and 42 are 'optimal for quantum implementations of AES' are only valid within the artificial restriction that AES rounds are executed sequentially. The paper itself notes that a monolithic AES circuit would have T depth 8 or 9, so the sentence 'no quantum circuit for AES ... can attain a lower T depth' is false without the round-wise caveat. The Conclusions repeat the overstatement and also contain a typo ('30, 46, and 42' should be '30, 36, and 42'). The AES discussion should be rephrased to present these values as optimal within the round-wise implementation model, not as unconditional AES optimality.
minor comments (4)
  1. [Preliminaries] The text attributes the T-depth-1 Toffoli decomposition of Fig. 1b to 'Soeken's design [12]', but reference [12] is by Jaques et al.; the citation should be corrected or the intended reference added.
  2. [Example 1] The sentence 'the maximum algebraic degree among f1, f2, f3 ∈ B3 is 2' refers to functions defined as f0, f1, f2; the indexing should be made consistent.
  3. [Table IV] The 'Present work' ancilla counts in Table IV (37464, 37480, 37496) do not match the formula in the AES section, which gives 44448 + 128(r-1) for r=10,12,14 (i.e., 45600, 45856, 46112), nor do they match the Fig. 1a resource estimates (32256 + 128(r-1)). The discrepancy between the table and the text should be resolved.
  4. [Proof of Theorem 1] The phrase 'Since, one T depth corresponds to a CNOT depth of 9' is only valid for the specific Toffoli decomposition of [12] used in the resource model; this should be stated explicitly as a model assumption.

Circularity Check

2 steps flagged · score 4.0 of 10

Optimality of ceil(log2 k) is imported from the authors' prior MCT lower bound, but the construction itself is not definitionally circular.

  1. uniqueness imported from authors [Section 'Optimal T depth quantum resource estimation', proof of Theorem 1]
    "Finally, by [10, Corollary 1], the optimal T depth decomposition of each k-MCT gate requires 2(k − 1) ancilla qubits and 9(k−1) CNOT gates, with ancilla qubits made reusable via measurement-based uncomputation."

    The theorem's 'optimal T depth' label is not proved for arbitrary Boolean functions; it is inherited from [10, Corollary 1], which is prior work by the same authors and gives a lower bound only for a single k-MCT gate. The paper asserts, without a lower-bound argument, that any function of degree k must cost as much as its highest-degree monomial, so the optimality half of Theorem 1 reduces to that same-group citation. The upper-bound construction is independent, but the claimed optimality is imported.

  2. self citation load bearing [Section 'Optimal T depth quantum circuit of AES', discussion of Table III]
    "The T depth achieved in this construction is optimal, as no quantum circuit for AES (when the rounds are implemented one after another) can attain a lower T depth, regardless of the number of ancilla qubits or other resource overheads."

    This AES optimality statement is not independently proved; it is derived by multiplying the S-box T depth 3 (from Theorem 1) by the round count. Since Theorem 1's optimality rests on [10]'s MCT lower bound and the unsupported degree-to-MCT transfer, the AES numbers 30, 36, and 42 are optimal only inside the same self-citation chain. The paper even acknowledges the monolithic AES T depth would be 8 or 9, so the 'optimal' claim is conditional on the round-wise model.

full rationale

The paper's derivation is not self-definitional and contains no fitted parameters. The upper bound (parallel k-MCTs with T depth ceil(log2 k)) is a legitimate construction provided [10]'s MCT decomposition is sound. The circularity burden is on the lower-bound half: Theorem 1 labels the T depth 'optimal' solely by citing [10, Corollary 1], a same-group result about single multi-controlled Toffoli gates, and then asserts that every degree-k function inherits that lower bound. No lemma showing that T-depth d circuits compute functions of algebraic degree at most 2^d is proved or cited, and a k-MCT is not a generic degree-k function, so the transfer is asserted rather than derived. The AES claims inherit this gap, and the round-wise optimality is explicitly conditional on the round-wise model. This is a self-citation dependency, not a definitional identity; if [10] is sound and the lower-bound transfer can be supplied, the result would stand. I therefore set 4 rather than 6-8. Note also that Theorem 1 states ceil(log2 n) while the abstract and examples use ceil(log2 k), a correctness mismatch that is outside circularity.

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

No free parameters are fitted; the construction is purely combinatorial. The substantive burden sits in the imported optimality theorem from [10] and in the round-wise model for AES. The paper introduces no new physical entities.

assumptions (4)
  • domain assumption Clifford+T gate set is universal and T depth is the primary fault-tolerant cost metric.
    Motivates the optimization objective; standard in the quantum resource estimation literature.
  • domain assumption A k-controlled Toffoli gate has optimal T depth ceil(log2 k) (Corollary 1 of [10]).
    The entire optimality claim for arbitrary Boolean functions and AES depends on this imported theorem by the same authors; not proved or reproduced here.
  • domain assumption The AES S-box coordinate functions have algebraic degree 7 and their combined ANF contains all monomials of degrees 2 through 7 on 8 variables.
    Used for the S-box resource estimates and per-round T depth 3; standard property of AES, stated without derivation.
  • domain assumption Quantum error-corrected circuits can implement arbitrary CNOT fanout and measurement-based uncomputation of ancillas.
    Needed for the parallel monomial construction and for ancilla reuse across AES rounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal T depth quantum circuits for implementing arbitrary Boolean functions." pith.science (2026). https://pith.science/paper/LSHXQXA7

@misc{pith2026250601542,
  author       = {Pith},
  title        = {Pith review of: Optimal T depth quantum circuits for implementing arbitrary Boolean functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LSHXQXA7}},
  note         = {Machine review of arXiv:2506.01542}
}
abstract

In this paper we present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary $n$-input $m$-output Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}^m$ having algebraic degree $k\leq n$, and it achieves an exact Toffoli (and T) depth of $\lceil \log_2 k \rceil$. This is a broader generalization of the recent result establishing the optimal Toffoli (and consequently T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function. Obtaining a benchmark for the minimum T depth of such circuits are of prime importance for efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations, for example AES.

Figures

Figures reproduced from arXiv: 2506.01542 by the authors.

Figure 1
Figure 1. FIG. 1: Toffoli decomposition using four T gates, (a) [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2: Quantum circuit implementing a 3-bit S-box (used in LowMC) with T depth 1. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3: Quantum circuit implementing [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

  1. [10]

    Dutta, S

    S. Dutta, S. Wang, A. Baksi, A. Chattopadhyay, and S. Maitra, Phys. Rev. A 111, 052611 (2025)

    work page 2025

  2. [1]

    R. P. Feynman, Foundations of Physics 16, 507 (1986)

    work page 1986

  3. [2]

    Deutsch and R

    D. Deutsch and R. Jozsa, Proceedings of the Royal Soci- ety A: Mathematical, Physical and Engineering Sciences 439, 553 (1992)

    work page 1992

  4. [3]

    L. K. Grover, in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC ’96 (1996) pp. 212–219

    work page 1996

  5. [4]

    D. R. Simon, SIAM J. Comput. 26, 1474 (1997)

    work page 1997

  6. [5]

    P. W. Shor, SIAM J. Comput. 26, 1484 (1997)

    work page 1997

  7. [6]

    Jones, Phys

    C. Jones, Phys. Rev. A 87, 022328 (2013)

    work page 2013

  8. [7]

    Bravyi and A

    S. Bravyi and A. Kitaev, Phys. Rev. A 71, 022316 (2005)

    2005

Show all 16 references
  1. [8]

    Selinger, Phys

    P. Selinger, Phys. Rev. A 87, 042302 (2013)

    2013

  2. [9]

    M. Amy, D. Maslov, M. Mosca, and M. Roetteler, Trans. Comp.-Aided Des. Integ. Cir. Sys. 32, 818–830 (2013)

    2013

  3. [11]

    Gidney, Quantum 2, 74 (2018)

    C. Gidney, Quantum 2, 74 (2018)

    2018

  4. [12]

    Jaques, M

    S. Jaques, M. Naehrig, M. Roetteler, and F. Virdia, in Advances in Cryptology – EUROCRYPT 2020 (2020) pp. 280–310

    2020

  5. [13]

    M. R. Albrecht, C. Rechberger, T. Schneider, T. Tiessen, and M. Zohner. in Advances in Cryptology - EURO- CRYPT 2015 (2015) pp. 430–454

    2015

  6. [14]

    Y. Yuan, W. Wu, T. Shi, L. Zhang, and Y. Zhang, IACR Trans. Symmetric Cryptol. 2024, 322–347 (2024)

    2024

  7. [15]

    Huang and S

    Z. Huang and S. Sun, in Advances in Cryptology – ASI- ACRYPT 2022 (2022) pp. 614–644

    2022

  8. [16]

    Q. Liu, B. Preneel, Z. Zhao, and M. Wang, in Advances in Cryptology – ASIACRYPT 2023 (2023) pp. 67–98

    2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.