Pith. sign in

REVIEW 2 major objections 6 minor 23 references

Explicit invertible matrices over the two-element field require at least 4n−o(n) CNOT gates, and the same bound holds for arbitrary local linear gates.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-31 02:38 UTC pith:LUSR5NZW

load-bearing objection Clean constructive jump from 3n to 4n−o(n) for explicit CNOT/row/2-local complexity, plus a usable dictionary from Freedman local-logic gates to AGL(n,2). the 2 major comments →

arxiv 2607.28598 v1 pith:LUSR5NZW submitted 2026-07-30 quant-ph math.CO

Explicit Matrices over mathbb Z₂ with CNOT and Row Complexity 4n-o(n) and Local Logic Gates

Sherry Gong , Andrew Yu This is my paper
classification quant-ph math.CO MSC 68Q1715B3381P68
keywords CNOT complexityrow complexitylocal logic gatesaffine transformationsadditive circuitsreversible circuitsGL(n,Z_2)quantum complexity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives an explicit family of invertible n-by-n matrices over the field with two elements that cannot be reduced to the identity with fewer than roughly 4n elementary row operations, and cannot be built with fewer than roughly 4n CNOT gates. The same lower bound survives even if one is allowed arbitrary invertible linear maps on pairs of coordinates instead of plain CNOTs. The authors further show that the permutations generated by local logic gates on n-bit strings are exactly the invertible affine maps on that space, so the matrix lower bound immediately yields a matching quantum-complexity lower bound for the associated permutations. A sympathetic reader cares because explicit super-linear lower bounds in the CNOT and row-reduction models have been stuck near 3n for a long time; this construction pushes the explicit barrier to 4n while tying the problem cleanly to quantum circuit cost for a natural group of permutations.

Core claim

There is an explicit family of matrices A in GL(m, Z_2), built in block form from a finite-field Vandermonde-type matrix U together with identity blocks, such that any product of 2-local linear gates equaling A has length at least 4m−o(m). The identical asymptotic lower bound therefore holds for ordinary CNOT length and for elementary row complexity. Because the group generated by local logic gates equals the full group of invertible affine transformations, the permutations corresponding to these matrices have quantum complexity at least 4n−o(n).

What carries the argument

The block matrix A = [U I; I U^T] together with the comparison that converts an additive (XOR) circuit lower bound on U⊞U^T into a 2-local-gate lower bound on A, once invertibility is secured by proving that the product U^T U vanishes.

Load-bearing premise

The argument rests on a preexisting lower bound for the number of XOR operations needed to realize a certain explicit block-diagonal matrix built from finite-field Vandermonde data; if that bound fails for the dimensions used here, the 4n claim collapses.

What would settle it

For moderate field degrees (for example p around 12–20), compute or rigorously bound the additive circuit complexity of the concrete matrix U⊞U^T and check whether it grows like 5N, and independently verify by linear algebra that U^T U is the zero matrix for the same parameters.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Explicit matrices over Z_2 now require asymptotically more than the previous 3n-scale CNOT lower bounds.
  • The same 4n−o(n) lower bound holds when arbitrary invertible 2-by-2 linear gates replace CNOTs.
  • The permutations attached to these matrices have quantum complexity at least 4n−o(n).
  • Row-reduction complexity of the same matrices is at least 4n−o(n).
  • Almost all permutations generated by local logic gates still require on the order of n²/log n gates, matching the known upper bound up to constants.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Closing more of the gap between additive-circuit lower bounds and reversible/2-local lower bounds could push explicit reversible constructions toward the full 5n regime.
  • Because local-logic-gate permutations are exactly the affine group, any future improvement in matrix row complexity immediately upgrades quantum-complexity lower bounds for a large, natural family of permutations.
  • The character-sum argument that forces U^T U = 0 may admit other parameter regimes and denser constructions.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

Summary. The paper constructs an explicit family of matrices A in GL(m, Z_2), m = N + ps with N = 2^p − 1 and s = ⌈N^{1/3}⌉, of block form [U I_N; I_ps U^T], where U is Sergeev’s Vandermonde-type matrix over F_{2^p} expanded to Z_2. Using Sergeev’s additive-complexity lower bound L(U ⊞ U^T) ≥ 5N − o(N) together with a new vanishing argument U^T U = 0 (hence A is invertible) and a simulation lemma relating 2-local linear gate length λ_m to additive complexity, the authors obtain λ_m(A) ≥ 4m − o(m), and therefore the same bound for CNOT length and row complexity. Separately, they identify the group G_n generated by Freedman’s local logic gates with AGL(n, 2), show that quantum complexity of affine permutations is controlled by the linear/row complexity of the linear part (up to an additive ⌈n/2⌉), and transfer the 4n − o(n) lower bound to the associated permutations. An O(n^2 / log n) upper bound and a matching counting lower bound for almost all elements of G_n are also given.

Significance. Explicit superlinear lower bounds for CNOT/row complexity of matrices in GL(n, Z_2) have been stuck near 3n for some time; pushing an explicit family to 4n − o(n), and showing the bound survives the stronger 2-local linear gate model, is a genuine advance on a problem highlighted by Gowers. The reduction of local-logic-gate quantum complexity to matrix row complexity is clean and useful, and the concurrent Jørgensen construction is properly disclosed. The algebraic core (trace-sum vanishing for U^T U = 0, and the reversible-to-additive simulation losing only n gates) is self-contained and checkable. Strengths include an explicit, deterministically constructible family (via Shoup irreducibles) and a clear transfer of the bound to the quantum-complexity setting proposed by Freedman.

major comments (2)
  1. [§2.2, Theorem 2.8 / Theorem 2.3] §2.2, Theorem 2.8 and the appeal to Theorem 2.3: the claim L(U ⊞ U^T) ≥ 5N − o(N) for s = ⌈N^{1/3}⌉ is asserted as “easy to check” from Sergeev, but the error term in Theorem 2.3 is O(a log a / k) with k = ⌊s/2⌋ ≍ N^{1/3}. The manuscript should write the resulting o(N) (or O(N^{2/3} log N)) explicitly and confirm that Sergeev’s hypotheses (no weight-1 rows; every 2k rows Z_2-independent) hold after bit-expansion of the F_{2^p}-Vandermonde matrix for this thinner parameter choice, not only for Sergeev’s original s ≍ √N. This is load-bearing for the constant 4.
  2. [§2.2, Lemma 2.7] Lemma 2.7 (U^T U = 0): the case split j − i ≤ p/2 vs > p/2 and the size bounds t, u ≤ s ≍ 2^{p/3} are correct in outline, but the written inequalities use somewhat arbitrary exponents 0.35 and 0.55. Replacing them by the sharp comparison 2^{p/3} + 2^{5p/6} < 2^p − 1 (for large p) would make the argument fully rigorous and remove any doubt that the character sums vanish for all admissible i, j, t, u. Since invertibility of A rests entirely on this lemma, the write-up should be tightened.
minor comments (6)
  1. [§1] Page 2, line 3 of the asymptotic-theory paragraph: duplicated phrase “A classical counting A classical counting argument”.
  2. [§2] Notation for row complexity oscillates between ℓ_row, l_row, and “row complexity” without a single definitional display; fix one symbol (e.g. ℓ_row) and use it consistently from §2 onward.
  3. [§3, Theorem 3.4] Theorem 3.4 upper bound is written 2n^2/(log_2 n − 1) + //; the displayed formula in the abstract/intro and the proof citation to [13] should be aligned, and the additive ⌈n/2⌉ term for translations stated once cleanly.
  4. [§4] In §4 the counting lower bound q_n uses log_2(12n(n−1)); a one-line remark that the same asymptotic is Ω(n^2 / log n) would help readers compare with the classical CNOT counting bound cited in §1.
  5. [§1 and References] Several references (e.g. Jørgensen arXiv:2607.22248, Sergeev Math. Notes 2025) are very recent; ensure final bibliographic data and that the comparison sentence in §1 accurately reflects the difference in technique (direct invertibility vs embedding).
  6. [§5, Example 5.5] Example 5.5 is helpful but the claim “the inequality cannot be improved to an equality” is already clear from the ±⌈n/2⌉ sandwich in Corollary 5.4; the example can be shortened.

Circularity Check

0 steps flagged

No significant circularity: 4n−o(n) lower bound is external Sergeev plus an independent algebraic vanishing argument

full rationale

The paper’s central claim is a lower bound λ_m(A)≥4m−o(m) for an explicit invertible matrix A=[U I; I_ps U^T]. The derivation is one-directional: Sergeev’s external additive-complexity bound L(U⊞U^T)≥5N−o(N) is transferred to the reversible/2-local model by the elementary inequality L(A+P)≤λ_m(A)+m (Lemma 2.6) after the paper proves U^T U=0 by a direct Galois-trace character-sum case analysis (Lemma 2.7), which makes A invertible. Neither step feeds the target quantity back into the hypothesis, fits a parameter to data, nor relies on a load-bearing self-citation. The identification G_n≅ AGL(n,2) and the QC-to-row-complexity comparison are proved from first principles inside the paper; background self-citations (Aaronson survey, Yu’s prior permutation-complexity note) are not used to force the 4n−o(n) bound. Concurrent Jørgensen work is disclosed rather than hidden. The derivation is therefore self-contained against its external benchmark and exhibits no circular reduction.

Axiom & Free-Parameter Ledger

1 free parameters · 4 axioms · 1 invented entities

The central lower bound rests on one external deep theorem (Sergeev) plus standard finite-field and linear-algebra facts. No numeric parameters are fitted to data; the exponent 1/3 in s=⌈N^{1/3}⌉ is a free design choice that only needs to satisfy k≫log N and sp=o(N). No physical or speculative entities are introduced.

free parameters (1)
  • s = ⌈N^{1/3}⌉ (row-block width exponent) = N^{1/3}
    Chosen by the authors so that k=⌊s/2⌋≫log N while sp=o(N); any exponent in a suitable open range would work. Not fitted to empirical data.
axioms (4)
  • domain assumption Sergeev’s additive-complexity lower bound L*(B)≥a+((2k−4)/(2k−1))a^{1−1/k}−b for matrices with no weight-1 rows and every 2k rows independent (and the transposition principle L(B^T)≥L*(B)+a−b).
    Invoked verbatim as Theorem 2.3; the entire 5N−o(N) additive lower bound is imported from [17].
  • standard math Existence of irreducible degree-p polynomials over Z_2 constructible in deterministic polynomial time (Shoup).
    Used to make the finite-field matrix U fully explicit (Example 2.5).
  • standard math Standard facts: GL(n,Z_2) order, AGL(n,2) structure, every element of GL(2,Z_2) is a product of at most two elementary matrices, field trace as sum of Galois conjugates, cyclic multiplicative group of F_{2^p}.
    Used throughout §§2–5; none are novel to the paper.
  • domain assumption Every local logic gate (arbitrary permutation of two bits acting on a coordinate pair) is an affine map whose linear part lies in GL(2,Z_2).
    Lemma 3.1 / Definition 3.2; elementary counting shows |AGL(2,2)|=24=4!.
invented entities (1)
  • Local logic gate σ_{i,j} (Freedman) independent evidence
    purpose: Generate the permutation group G_n whose quantum complexity is under study.
    Definitional packaging of an arbitrary 2-bit permutation acting on coordinates i,j; not a new physical object. Independent evidence is immediate from the definition.

pith-pipeline@v1.2.0-daily-grok45 · 18762 in / 3525 out tokens · 85247 ms · 2026-07-31T02:38:35.779674+00:00 · methodology

0 comments
read the original abstract

In this article, we present an explicit family of invertible $n\times n$ matrices over $\mathbb Z_2$ whose CNOT and row complexity is at least $4n-\text{o}(n)$; equivalently, reducing these matrices to the identity requires at least $4n-\text{o}(n)$ elementary row operations. Moreover, the same complexity lower bound holds in the stronger computational model where the CNOT gates are replaced by arbitrary local linear logic gates, namely arbitrary invertible linear transformations acting on pairs of coordinates. Let $G_n$ denote the permutation group generated by local logic gates acting on the set of binary strings of length $n$. We prove that $G_n$ is naturally isomorphic to the group of all invertible affine transformations of the vector space $\mathbb Z_2^n$, thus reducing the problem of estimating the quantum complexity of permutations in $G_n$ to the row reduction complexity of invertible matrices over $\mathbb Z_2$. As an application, we show that the permutations associated with our explicit matrices have quantum complexity at least $4n-\text{o}(n)$.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 6 linked inside Pith

  1. [1]

    A. R. Brown,A Quantum Complexity Lowerbound from Differential Geometry, arXiv:2112.05724 [hep-th], 2021

    Pith/arXiv arXiv 2021

  2. [2]

    A. R. Brown, M. H. Freedman, H. W. Lin and L. Susskind,Effective Geometry, Complexity, and Universality,arXiv:2111.12700v1 [hep-th], 2021

    Pith/arXiv arXiv 2021

  3. [3]

    K. Bu, R. J. Garcia, A. Jaffe, D. E. Koh, L. Li,Complexity of Quantum Circuits via Sensitivity, Magic, and Coherence,Communications in Math.Phys. 405 (2024) 7, 161. 2024

    2024

  4. [4]

    C. M. Dawson and M. Nielsen,The Solovay-Kitaev Algorithm,Quantum Information & Computation. 6: 81–95. 2006. arXiv:quant-ph/0505030

    Pith/arXiv arXiv 2006

  5. [5]

    M. H. Freedman, A. Kitaev, M. J. Larsen, and Z. Wang,Topological Quantum Computa- tion,Bull. Amer. Math. Soc. 40, 31-38. 2003

    2003

  6. [6]

    Lower bounds for the CNOT-complexity of linear reversible operators,

    S. F. Jørgensen, “Lower bounds for the CNOT-complexity of linear reversible operators,” 2026,arXiv:2607.22248 [quant-ph]

    Pith/arXiv arXiv 2026

  7. [7]

    A. Y. Kitaev,Quantum Computations: Algorithms and Error Correction,Russian Math- ematical Surveys. 52 (6): 1191–1249. 1997

    1997

  8. [8]

    Nielsen,A Geometric Approach to Quantum Circuit Lower Bounds,Quantum Infor- mation & Computation, vol

    M. Nielsen,A Geometric Approach to Quantum Circuit Lower Bounds,Quantum Infor- mation & Computation, vol. 6, no. 3, pp. 213–262, 2006. arXiv:quantph/0502070

    arXiv 2006

  9. [9]

    Nielsen and I

    M. Nielsen and I. Chuang,Quantum Computation and Quantum Information.Cambridge University Press, 2000

    2000

  10. [10]

    Nielsen, M

    M. Nielsen, M. R. Dowling, M. Gu, and A. C. Doherty,Quantum Computation as Geom- etry,Science 311, 1133 (2006), arXiv:quant-ph/0603161

    Pith/arXiv arXiv 2006

  11. [11]

    P. W. Shor,Algorithms for Quantum Computation: Discrete Logarithms and Factoring, Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press: 124–134, 1994

    1994

  12. [12]

    H. W. Lin,Cayley graphs and complexity geometry,Journal of High Energy Physics volume 63, 2019

    2019

  13. [13]

    Scott Aaronson,The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes,arXiv:1607.05256, 2016

    Pith/arXiv arXiv 2016

  14. [14]

    Andr´ en, L

    D. Andr´ en, L. Hellstr¨ om, K. Markstr¨ om,On the complexity of matrix reduction over finite fields,Advances in Applied Mathematics, 39(4):428-452. 2007

    2007

  15. [15]

    Gowers,Rough Structure and Classification,79-117, GAF A Special Volume, Vision in Mathematics, 2000

    T. Gowers,Rough Structure and Classification,79-117, GAF A Special Volume, Vision in Mathematics, 2000

    2000

  16. [16]

    Gowers,A conversation about complexity lower bounds,Gowers’ webblog, 2009

    T. Gowers,A conversation about complexity lower bounds,Gowers’ webblog, 2009. 22 SHERRY GONG AND ANDREW YU

    2009

  17. [17]

    I. S. Sergeev,Lower Bounds for Additive Complexity of Linear Operators and Bilinear Algorithms for Matrix and Polynomial Multiplication overGF(2),848–862, Mathematical Notes, Vol. 118, No. 4, 2025

    2025

  18. [18]

    A. Bu, E. Fan, R. Joo,Minimum synthesis cost of CNOT circuits,Quantum Information Processing, 24(7), article number 208, 2025

    2025

  19. [19]

    Yu,Quantum Complexity of Permutations,575-595, Pure and Applied Mathematics Quarterly, Volume 19, Number 2, 2023

    A. Yu,Quantum Complexity of Permutations,575-595, Pure and Applied Mathematics Quarterly, Volume 19, Number 2, 2023

    2023

  20. [20]

    K. N. Patel, I. L. Markov, J. P. Hayes,Optimal synthesis of linear reversible circuits, Quantum Information & Computation, 8(3–4):282–294, 2008

    2008

  21. [21]

    Bataille,Quantum circuits of CNOT gates: Optimization and entanglement,Quantum Information Processing, 21(7):269, 2022

    M. Bataille,Quantum circuits of CNOT gates: Optimization and entanglement,Quantum Information Processing, 21(7):269, 2022

    2022

  22. [22]

    J. E. Christensen, S. F. Jørgensen, A. Pavlogiannis, J. van de Pol,On exact sizes of minimal CNOT circuits,InReversible Computation: 17th International Conference (RC 2025), Lecture Notes in Computer Science, Vol. 15716, pp. 71–88, Springer, 2025

    2025

  23. [23]

    Shoup,New Algorithms for Finding Irreducible Polynomials over Finite Fields,Math- ematics of Computation, 54 (189), 435–447, 1990

    V. Shoup,New Algorithms for Finding Irreducible Polynomials over Finite Fields,Math- ematics of Computation, 54 (189), 435–447, 1990. SG: Texas A&M University, College Station, TX 77840 USA Email address:sgongli@tamu.edu AY: Harvard University, Cambridge, MA 02138 USA Email address:andrewyu45@gmail.com

    1990