Quantum-Accelerated Gowers U₂ Norm for Bent Boolean Functions
Pith reviewed 2026-05-07 16:36 UTC · model grok-4.3
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.
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
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 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.
Referee Report
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)
- [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.
- [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)
- [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.
- [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
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
-
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
-
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
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
axioms (1)
- domain assumption Quantum circuits can be executed fault-tolerantly with the stated gate counts on future hardware.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.