pith. machine review for the scientific record. sign in

arxiv: 2604.25503 · v2 · submitted 2026-04-28 · 🪐 quant-ph

Recognition: unknown

Quantum-Accelerated Gowers U₂ Norm for Bent Boolean Functions

Rajdeep Dwivedi , C. A Jothishwaran , Sugata Gangopadhyay , Vishvendra Singh Poonia
Authors on Pith no claims yet

Pith reviewed 2026-05-07 16:36 UTC · model grok-4.3

classification 🪐 quant-ph
keywords bent Boolean functionsGowers U2 normquantum genetic algorithmquantum circuit complexityBoolean function constructionhybrid quantum classical optimization
0
0 comments X

The pith

Quantum circuit evaluates Gowers U2 norm using 3n qubits and O(n^2) gates for bent function search

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

The paper introduces a hybrid genetic algorithm that employs a quantum circuit to calculate the Gowers U2 norm as the fitness function when searching for bent Boolean functions. These functions are special because they provide the strongest resistance to linear approximations, but finding them grows difficult with more variables. The quantum circuit achieves this with only 3n qubits and a quadratic number of gates per evaluation, while classical methods require an exponential number of operations that become impractical beyond about 25 variables. Experiments on 6 and 8 variables confirm that the method finds functions exactly at the theoretical bent limit, and the quantum results track the classical ones closely despite noise. This complexity advantage opens the door to larger searches once suitable quantum hardware is available.

Core claim

Bent Boolean functions are found by evolving populations where fitness is the Gowers U2 norm, computed quantumly with a circuit needing 3n qubits and O(n^2) gates, versus classical O(2^{2n}) cost. For eight variables the algorithm attains the exact bent value of 2 to the minus n over 4, and quantum sampling reproduces the classical evolution path.

What carries the argument

Quantum circuit for Gowers U2 norm evaluation, which estimates the norm from measurements on a superposition state prepared from the Boolean function, used as the fitness evaluator.

Load-bearing premise

The sampling noise in the quantum circuit does not prevent the genetic algorithm from identifying functions that meet or exceed the bent threshold.

What would settle it

If the quantum circuit for n=8 produces fitness values that systematically differ from the exact classical U2 norm by more than the predicted sampling variance, causing the GA to miss the 0.25 threshold.

Figures

Figures reproduced from arXiv: 2604.25503 by C. A Jothishwaran, Rajdeep Dwivedi, Sugata Gangopadhyay, Vishvendra Singh Poonia.

Figure 1
Figure 1. Figure 1: Fitness evolution for n = 6 variables. The theoretical bent threshold is U2(f) 4 = 0.3536. Both methods converge to this vicinity; the quantum run exhibits wider generation-to￾generation variation due to finite-sample shot noise. For n = 6, the target bent threshold is 2−6/4 ≈ 0.3536. The classical GA converges to U2(f) 4 ≈ 0.3536 after 250 generations, essentially touching the bent bound. The quantum-assi… view at source ↗
Figure 2
Figure 2. Figure 2: Fitness evolution for n = 8 variables. The classical GA converges to best fitness U2(f) 4 = 0.2500 the exact theoretical bent threshold by around generation 165, and holds steady thereafter. The quantum run (250 generations) reaches U2(f) 4 ≈ 0.2829, consistent with the classical trajectory at the same generation count view at source ↗
read the original abstract

Bent Boolean functions extremal objects that maximally resist affine approximation are notoriously hard to construct for large numbers of variables. We propose a hybrid quantum-classical genetic algorithm (GA) that uses a \emph{quantum circuit} to evaluate the Gowers $U_2$ norm as the evolutionary fitness function. Our central contribution is a complexity-theoretic separation: the quantum evaluation circuit requires only $3n$ qubits and $\bigO(n^2)$ two-qubit gates per function query, whereas the classical computation of the exact Gowers $U_2$ norm demands $\bigO(2^{2n})$ arithmetic operations an exponential overhead that renders it infeasible for $n \gtrsim 25$. We validate the framework on $n=6$ and $n=8$ variable systems. For $n=8$, our classical GA run extended to 1000 generations achieves best fitness $\Utwof = 0.250000$ \emph{exactly} the theoretical bent threshold $2^{-n/4}$ with average fitness $0.257267$, confirming that the Gowers $U_2$ norm is a superior fitness criterion over Walsh-Hadamard spectral flatness. Quantum-assisted evaluation faithfully reproduces the classical trajectory up to finite-sampling noise, and our complexity analysis demonstrates that for $n > 25$ the quantum evaluator provides a decisive computational advantage on fault-tolerant hardware.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a hybrid quantum-classical genetic algorithm for constructing bent Boolean functions, using a quantum circuit to evaluate the Gowers U2 norm as the fitness function. It asserts a complexity-theoretic separation in which the quantum evaluator requires only 3n qubits and O(n²) two-qubit gates per query, while classical exact computation of the U2 norm requires O(2^{2n}) operations and becomes infeasible for n ≳ 25. The approach is validated on n=6 and n=8, where a classical GA run reaches the exact bent threshold 2^{-n/4} and the quantum-assisted version reproduces the trajectory within sampling noise.

Significance. If the quantum circuit correctly implements the U2 norm and the complexity claims are accurate, the framework could enable GA-based searches for bent functions at scales where the volume of fitness evaluations renders classical methods impractical. The explicit demonstration that the Gowers U2 norm yields exact bent functions on n=8 (where Walsh-Hadamard spectral flatness does not) is a concrete positive result. However, the overstated classical complexity reduces the strength of the claimed separation.

major comments (2)
  1. [Abstract] Abstract and complexity analysis: the central claim that classical exact Gowers U2 norm computation requires O(2^{2n}) arithmetic operations is incorrect. Since ||f||_{U2}^4 = ∑_a |ˆf(a)|^4, the Fast Walsh-Hadamard Transform obtains all Walsh-Hadamard coefficients ˆf(a) in O(n 2^n) time, after which the sum of fourth powers costs O(2^n). This is feasible on standard hardware up to n≈30, so the stated exponential overhead and the infeasibility threshold n≳25 do not hold. The complexity separation asserted for the quantum evaluator is therefore weaker than presented and requires revision.
  2. [Abstract] Abstract: the manuscript states that the quantum circuit requires only 3n qubits and O(n²) two-qubit gates per function query, yet supplies neither a circuit diagram nor a derivation of the gate count. Because this resource bound is load-bearing for the claimed advantage over classical evaluation, an explicit construction or reference to the circuit must be added.
minor comments (2)
  1. [Validation on n=6 and n=8] The validation section reports that the classical GA reaches U2 = 0.250000 exactly on n=8, but does not specify the population size, selection mechanism, or mutation rate used; these parameters should be stated for reproducibility.
  2. [Abstract] The abstract refers to 'our complexity analysis' without citing a specific section or equation; add an explicit pointer to the relevant derivation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments, which have helped us identify and correct inaccuracies in our complexity claims. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract and complexity analysis: the central claim that classical exact Gowers U2 norm computation requires O(2^{2n}) arithmetic operations is incorrect. Since ||f||_{U2}^4 = ∑_a |ˆf(a)|^4, the Fast Walsh-Hadamard Transform obtains all Walsh-Hadamard coefficients ˆf(a) in O(n 2^n) time, after which the sum of fourth powers costs O(2^n). This is feasible on standard hardware up to n≈30, so the stated exponential overhead and the infeasibility threshold n≳25 do not hold. The complexity separation asserted for the quantum evaluator is therefore weaker than presented and requires revision.

    Authors: We fully agree with the referee that our stated classical complexity of O(2^{2n}) was incorrect. The Fast Walsh-Hadamard Transform indeed computes the full Walsh spectrum in O(n 2^n) time, after which the U2 norm (via sum of fourth powers) is obtained in additional O(2^n) time. We will revise the abstract, introduction, and complexity analysis sections to replace the erroneous bound with the correct O(n 2^n) scaling, remove the claim of infeasibility for n ≳ 25, and qualify the quantum advantage as a polynomial improvement in gate count (O(n²) vs. O(n 2^n)) rather than an exponential separation. The core contribution of the quantum circuit for fitness evaluation in the GA remains valid, but we acknowledge the separation is weaker than originally presented. revision: yes

  2. Referee: [Abstract] Abstract: the manuscript states that the quantum circuit requires only 3n qubits and O(n²) two-qubit gates per function query, yet supplies neither a circuit diagram nor a derivation of the gate count. Because this resource bound is load-bearing for the claimed advantage over classical evaluation, an explicit construction or reference to the circuit must be added.

    Authors: We accept that the abstract asserts the 3n-qubit and O(n²)-gate bounds without an accompanying diagram or derivation. In the revised manuscript we will insert a dedicated subsection (or appendix) containing the explicit quantum circuit for the Gowers U2 evaluator, together with a gate-by-gate count derivation showing how the 3n qubits and O(n²) two-qubit gates are obtained. This will make the resource claim self-contained and verifiable. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper defines the Gowers U2 norm as an external mathematical quantity (||f||_U2^4 = sum |hat f(a)|^4) and proposes a quantum circuit to evaluate it for use as a fixed fitness function in a genetic algorithm. No step reduces the claimed quantum complexity advantage or the bent-function threshold to a fitted parameter, self-citation, or ansatz imported from the authors' prior work. The classical complexity statement is presented as a premise rather than derived from the quantum circuit itself. Validation on n=6,8 simply reproduces the known bent threshold 2^{-n/4} without circular redefinition. The chain remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces no new free parameters, axioms, or invented entities beyond standard quantum computing assumptions and the pre-existing definitions of the Gowers norm and bent functions.

axioms (1)
  • domain assumption Quantum circuits can be executed fault-tolerantly with the stated gate counts on future hardware.
    Required for the claimed O(n^2) per-query cost to translate into practical advantage for n>25.

pith-pipeline@v0.9.0 · 5602 in / 1410 out tokens · 68934 ms · 2026-05-07T16:36:16.613412+00:00 · methodology

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

13 extracted references · 9 canonical work pages

  1. [1]

    A quantum algorithm to estimate the gowers u2 norm and linearity testing of boolean functions

    Jothishwaran Arunagiri, Anton Tkachenko, Sugata Gangopadhyay, Constanza Riera, and Pante St˘ anic˘ a. A quantum algorithm to estimate the gowers u2 norm and linearity testing of boolean functions. 06 2020. doi: 10.48550/arXiv.2006.16523

    work page doi:10.48550/arxiv.2006.16523 2020

  2. [2]

    Simpler methods for generating better boolean functions with good cryptographic properties

    Linda Burnett, Andrew Clark, Ed Dawson, and William Millan. Simpler methods for generating better boolean functions with good cryptographic properties. 29, 01 2004

    2004

  3. [3]

    Evolutionary algorithms- assisted construction of cryptographic boolean functions

    Claude Carlet, Domagoj Jakobovic, and Stjepan Picek. Evolutionary algorithms- assisted construction of cryptographic boolean functions. InProceedings of the Genetic and Evolutionary Computation Conference, GECCO ’21, page 565–573, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383509. doi: 10.1145/3449639.3459362

    work page doi:10.1145/3449639.3459362 2021

  4. [4]

    John F. Dillon. A survey of Bent functions. InProceedings of the American Mathe- matical Society, 1972

    1972

  5. [5]

    Gowersu2 norm as a measure of nonlinearity for boolean functions and their generalizations.Advances in Mathematics of Communications, 15(2):241–256, 2021

    Sugata Gangopadhyay, Constanza Riera, and Pantelimon St˘ anic˘ a. Gowersu2 norm as a measure of nonlinearity for boolean functions and their generalizations.Advances in Mathematics of Communications, 15(2):241–256, 2021. ISSN 1930-5346. doi: 10.3934/amc.2020056. Quantum-Accelerated GowersU 2 Norm for Bent Boolean Functions11

    work page doi:10.3934/amc.2020056 2021

  6. [6]

    Quantum advantage in cryptography with a low-connectivity quantum annealer

    Feng Hu, Lucas Lamata, Chao Wang, Xi Chen, Enrique Solano, and Mikel Sanz. Quantum advantage in cryptography with a low-connectivity quantum annealer. Phys. Rev. Appl., 13:054062, May 2020. doi: 10.1103/PhysRevApplied.13.054062

    work page doi:10.1103/physrevapplied.13.054062 2020

  7. [7]

    Kirkpatrick and C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983. doi: 10.1126/science.220.4598.671

    work page doi:10.1126/science.220.4598.671 1983

  8. [8]

    A genetic algorithm for evolving plateaued cryptographic boolean functions

    Luca Mariot and Alberto Leporati. A genetic algorithm for evolving plateaued cryptographic boolean functions. In Adrian-Horia Dediu, Luis Magdalena, and Carlos Mart´ ın-Vide, editors,Theory and Practice of Natural Computing, pages 33–45, Cham,

  9. [9]

    ISBN 978-3-319-26841-5

    Springer International Publishing. ISBN 978-3-319-26841-5

  10. [10]

    Generalized bent functions with large dimension.Advances in Mathematics of Communications, 18(5):1514–1530, 2024

    Wilfried Meidl. Generalized bent functions with large dimension.Advances in Mathematics of Communications, 18(5):1514–1530, 2024. ISSN 1930-5346. doi: 10.3934/amc.2023004

    work page doi:10.3934/amc.2023004 2024

  11. [11]

    Evolving algebraic constructions for designing bent boolean functions

    Stjepan Picek and Domagoj Jakobovic. Evolving algebraic constructions for designing bent boolean functions. InProceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO ’16, page 781–788, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450342063. doi: 10.1145/2908812.2908915

    work page doi:10.1145/2908812.2908915 2016

  12. [12]

    On “bent” functions.Journal of Combinatorial Theory, Series A, 20(3): 300–305, 1976

    O.S Rothaus. On “bent” functions.Journal of Combinatorial Theory, Series A, 20(3): 300–305, 1976. ISSN 0097-3165. doi: https://doi.org/10.1016/0097-3165(76)90024-8

    work page doi:10.1016/0097-3165(76)90024-8 1976

  13. [13]

    Turner, J

    Fengrong Zhang, Enes Pasalic, Amar Bapi´ c, and Baocang Wang. Constructions of several special classes of cubic bent functions outside the completed maiorana- mcfarland class.Inf. Comput., 297(C), March 2024. ISSN 0890-5401. doi: 10.1016/j. ic.2024.105149

    work page doi:10.1016/j 2024