Curator's Take
This research tackles a fascinating computational bottleneck in cryptography by leveraging quantum computing's pattern-matching strengths to construct bent Boolean functions, which are crucial building blocks for secure cryptographic systems. The key breakthrough lies in using quantum circuits to evaluate the Gowers U2 norm exponentially faster than classical methods, transforming what becomes computationally impossible for systems larger than 25 variables into a tractable quantum algorithm requiring only polynomial resources. While the immediate validation is on small test cases, this work points toward a compelling future application where fault-tolerant quantum computers could dramatically accelerate the discovery of cryptographic primitives that classical computers simply cannot find. The hybrid quantum-classical genetic algorithm approach also demonstrates how quantum advantage might emerge not just in pure quantum algorithms, but in quantum-enhanced optimization workflows that could have broad applications beyond cryptography.
— Mark Eatherly
Summary
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.