Quantum-Accelerated Gowers $U_2$ Norm for Bent Boolean Functions

• URL: http://arxiv.org/abs/2604.25503v2
• Date: Fri, 01 May 2026 12:16:48 GMT
• Title: Quantum-Accelerated Gowers $U_2$ Norm for Bent Boolean Functions
• Abstract summary: We propose a hybrid quantum-classical genetic algorithm (GA) that uses a emphquantum circuit to evaluate the Gowers $U$ norm as the evolutionary fitness function.<n>Our central contribution is the complexity-theoretic separation: the quantum evaluation circuit requires only $3n$ qubits and $bigO(n2)$ two-qubit gates per function query.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency [0.5076419064097732]
  We propose a unitary brick-wall: a $k$-particle fermionic architecture for nearest-neighbor hardware.<n>The brick-wall has dynamical Lie algebra $mathfraku(n)$ and directly parametrizes $U(n)$ via Givens rotations.<n>It achieves similar hardness guarantees at $8klog n$ evaluations per gradient step, the same factor $3n/(8k)$ reduction.
  arXiv  Detail & Related papers  (2026-07-27T05:23:32Z)
• Quantum Advantage in Tolerant Junta Testing [0.5442955439283729]
  We establish the first super-polynomial quantum advantage for the tolerant $k$-junta testing problem in the adaptive setting.<n>We show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $mathrmpoly(k)$ quantum queries.
  arXiv  Detail & Related papers  (2026-06-22T11:42:39Z)
• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices.<n>We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• The classical limit of Quantum Max-Cut [0.16385815610837165]
  We show that the limit of large quantum spin $S$ should be understood as a semiclassical limit.<n>We present two families of classical approximation algorithms for $mathrmQMaxCut_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states.
  arXiv  Detail & Related papers  (2024-01-23T18:53:34Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Emulating Quantum Interference with Generalized Ising Machines [0.0]
  This paper presents an exact and general procedure for mapping any sequence of quantum gates onto a network of probabilistic p-bits. We can view this structure as a Boltzmann machine whose states each represent a Feynman path leading from an initial configuration of qubits to a final configuration. Our results for mapping an arbitrary quantum circuit to a Boltzmann machine with a complex energy function should help push the boundaries of the simulability of quantum circuits with probabilistic resources.
  arXiv  Detail & Related papers  (2020-07-14T22:10:29Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits [0.755972004983746]
  Variational quantum algorithms (VQAs) optimize the parameters $vectheta$ of a parametrized quantum circuit. We prove two results, assuming $V(vectheta)$ is an alternating layered ansatz composed of blocks forming local 2-designs. We illustrate these ideas with large-scale simulations, up to 100 qubits, of a quantum autoencoder implementation.
  arXiv  Detail & Related papers  (2020-01-02T18:18:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.