Block and stream ciphers need Boolean functions (tables that map an $n$-bit input to one output bit) that sit far from every linear function. If a function is close to some linear function, an attacker can approximate the cipher with linear equations and recover key bits. This attack is called linear cryptanalysis. The distance to the nearest linear function is called nonlinearity, and finding functions with high nonlinearity is a hard search problem. For odd $n \ge 9$ nobody knows the maximum value, and general-purpose evolutionary search stops producing competitive functions beyond $n = 9$. In parallel, hybrid quantum-classical optimizers have been proposed for exactly this kind of rugged binary search. These are short quantum circuits whose knobs are tuned by a classical optimizer. Their record on standard benchmarks is sobering: they are often matched by greedy search.
This note proposes a clean way to put the two problems together and answer an honest question. Write each function's truth table as a string of ±1 spins. Each Walsh coefficient, which measures correlation with one linear function, is then a linear combination of those spins. A fourth or higher moment of the Walsh spectrum is therefore a small-degree spin Hamiltonian, meaning a cost defined on spins that a quantum circuit can apply directly. Its lowest-energy states are exactly the bent functions (the maximally nonlinear ones) when those exist. We restrict to rotation-symmetric functions, which shrinks the problem to 6 to 60 spins for $n = 4$ to $9$. At $n \le 7$ that reduced space can be enumerated exhaustively. The result is a family of instances with known optima and cryptographic meaning. On it we can measure, with no guesswork about the optimum, whether a constraint-preserving quantum ansatz samples good functions faster than classical annealing run on the same Hamiltonian.
Core Claim
Let $s_x = (-1)^{f(x)}$ be the spin for input $x$. The Walsh coefficient at frequency $\omega$ is then $W_f(\omega) = \sum_x s_x (-1)^{\omega \cdot x}$. We define the moment cost
$$H_{2k}(s) = \sum_{\omega \in \{0,1\}^n} W_f(\omega)^{2k},$$
a $2k$-body diagonal spin Hamiltonian. The case $k = 1$ is constant by Parseval's identity, which says the squared Walsh coefficients always sum to the same value. For $k = 2$, expanding the sum gives
$$H_4 = 2^n \sum_{x \oplus y \oplus z \oplus w = 0} s_x s_y s_z s_w,$$
whose minimum $2^{3n}$ is reached exactly by bent functions. As $k$ grows, $H_{2k}$ approaches the largest Walsh coefficient, which is what nonlinearity actually depends on. The spectrum-aware fitness shown by Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean Functions to beat raw nonlinearity is a heuristic relative of this cost. Our contribution is the exact spin-polynomial form, which quantum circuits and physics-style annealers can apply natively.
Rotation symmetry means the function is unchanged when the input bits are cyclically shifted. Under that symmetry, spins in the same rotation orbit are tied together, and $W_f$ is constant on orbits of $\omega$. The problem collapses to $g_n$ orbit spins: 6, 8, 14, 20, 36, 60 for $n = 4, \dots, 9$, where the last two agree with the $2^{20}$ and $2^{60}$ subspace sizes reported in A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes.
The claim to be tested is this. On these known-optimum instances, a Quantum Alternating Operator Ansatz, whose mixing step never leaves the feasible set, either does or does not reach optimal-nonlinearity functions in fewer objective evaluations than simulated annealing and parallel tempering on the identical Hamiltonian. We find out which, and we find out how the answer scales with $n$.
Research Program
Hamiltonian. The first piece of work is compiling $H_4$ and $H_6$ over orbit spins. Each orbit spin carries a weight equal to its orbit size, and each frequency orbit carries a multiplicity. We will report term counts and circuit depth of the phase step $e^{-i\gamma H}$ per $n$. We deliberately avoid quadratization. The distributed approach of Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems reduces higher-order terms to pairwise ones and then splits variables into communities. That method supplies the obvious alternative, and it constrains us too: every spin enters every Walsh coefficient, so we expect the interaction graph to have essentially no community structure. We will check this by computing its modularity, a standard score for how well a graph splits into clusters.
Mixers. The second piece is designing the ansatz's mixing step, following From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz. That paper built mixers preserving feasibility for coloring and scheduling. Its XY mixers preserve Hamming weight only when every variable counts equally. For rotation-symmetric functions, the truth-table weight is an orbit-size-weighted sum of orbit spins, so the plain XY mixer breaks balancedness. Balancedness, meaning an equal number of 0 and 1 outputs, is required for stream-cipher use. We therefore build a weighted-weight-preserving mixer. It applies XY swaps among orbits of equal size, which covers almost all orbits since most have size $n$. It also applies compound moves that exchange one full-size orbit against a combination of short orbits with equal total size. We will prove this mixer connects the feasible set, or report where it fails to.
Parameter tuning. The third piece reuses the parameter-concentration idea of Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems. That paper found that good circuit parameters learned on small Max-Cut graphs transfer to larger ones. We will fit a kernel-density prior over circuit angles at $n = 5, 6$ and test whether it transfers to $n = 7, 8$. That paper worked on graph problems; whether cryptographic landscapes concentrate parameters is unknown.
Simulation. All quantum runs are exact state-vector simulations up to 20 qubits ($n \le 7$). We use matrix-product-state simulation, an approximate compressed representation, at 36 qubits ($n = 8$). No hardware claims are made.
Baselines
The naive reference point is uniform random sampling in the rotation-symmetric subspace, which we can score exactly by enumeration for $n \le 7$. Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice showed this reference is not trivial. Shallow variational circuits on 11-node Max-Cut often lost to it, even though they found the exact optimum with over 75% probability. Beating random sampling means a higher probability, per evaluation, of drawing an optimal-nonlinearity function.
The strongest existing classical competitor is the rotation-symmetric truth-table evolutionary algorithm with exhaustive single-bit-flip local search (TT-RI-LS1) of A Systematic Study on the Design of Odd-Sized Highly Nonlinear Boolean Functions via Evolutionary Algorithms. It reached nonlinearity 241 at $n = 9$, beating the long-standing 240 barrier. For balanced functions, the strongest reported classical method is local search with revert plus spectrum-aware fitness from Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean Functions. It consistently reached nonlinearity 116 at $n = 8$, while a standard genetic algorithm plateaued at 112 to 114. No reported result was found on Lacuna for evaluations-to-optimum of either method on $n \le 8$ rotation-symmetric instances, so we rerun both from published descriptions.
The ablation that isolates the quantum ingredient is simulated annealing and parallel tempering (many annealing copies at different temperatures that swap states) on exactly the same $H_4$ and $H_6$ over orbit spins. They use moves restricted to the same feasible set as our mixer. A second ablation replaces the constraint-preserving mixer with the standard single-spin-flip mixer plus a balancedness penalty. A third follows the protocol of Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice: greedy local search started from the same initial point as each quantum run.
Fairness. Every method gets the same budget of objective evaluations, up to $10^6$, matching that paper and Discovering Rotation Symmetric Self-dual Bent Functions with Evolutionary Algorithms. One measured circuit sample counts as one evaluation, and every classical optimizer call to the circuit also counts. Each method receives the same hyperparameter-tuning budget on $n = 5$ and is then frozen. Beating a baseline means a lower median number of evaluations to first sample a target-nonlinearity function, with a bootstrap confidence interval excluding parity over at least 50 seeds, at two or more consecutive $n$.
Why not just…?
Why not just run simulated annealing on your Hamiltonian and skip the quantum circuit? This is the most serious threat, and the experiment is built around it. The Walsh-moment Hamiltonian and the weighted balance-preserving moves are equally usable by classical annealers, and they may be most of the value. Schwägerl et al. found variational circuits' edge over greedy search peaked at 31 nodes and shrank by 61 nodes, which predicts annealing will match the quantum ansatz here too. If it does, we report that plainly. We then run parallel tempering on $H_6$ at $n = 9$ and $n = 11$ (188 orbit spins), where the only open question is classical: can it match 241 and approach the 996 construction record that evolutionary algorithms have not reached? This way the project produces a usable result under either outcome.
Why not just improve the evolutionary algorithm's fitness function? The spectrum-aware fitness already exists in Digging Deeper, and it already brings local search to 116. It did not fix the scaling wall: self-dual bent rotation-symmetric functions were not found for $n \ge 10$ within $10^6$ evaluations in Discovering Rotation Symmetric Self-dual Bent Functions with Evolutionary Algorithms. The same paper reports crossover to be no better than mutation near the optimum. Our annealing arm is effectively the best-tuned version of this alternative, so the comparison is built in rather than argued away.
Why not use Grover search, as in the quantum Boolean equation solver? Resource Efficient Boolean Function Solver on Quantum Computer finds inputs that satisfy a given quadratic system, solving 21 equations in 20 variables on 25 qubits. Our task is the reverse: synthesizing a function. A Grover oracle for "nonlinearity at least 241" would have to compute the whole Walsh transform coherently. Even over the $2^{60}$ symmetric subspace, a quadratic speedup still leaves on the order of $2^{30}$ deep iterations. That regime is out of reach for the simulations or near-term devices this study targets.
Why not quadratize and use distributed QAOA on larger $n$? We will test the premise directly by measuring the modularity of the orbit-spin interaction graph and the number of extra variables quadratization adds. If the graph shows real community structure, we will add the distributed method as a baseline at $n = 8$ rather than dismiss it.
Proposed Experiments
The instance set covers $n = 4$ to $8$ in the rotation-symmetric subspace. We target bent functions (nonlinearity 120 at $n = 8$, known to exist in this subspace per A New Angle: On Evolving Rotation Symmetric Boolean Functions), self-dual bent functions at $n = 6, 8$, the value 56 at $n = 7$, and the best balanced value at $n = 8$. For $n \le 7$ we enumerate the full space, so each solver is scored against exact optimum sets and exact energy-nonlinearity rankings. This also answers a question no prior work addresses: how well does minimizing $H_4$ or $H_6$ track true nonlinearity at odd $n$, where no bent functions exist?
Decisive check 1. We fit how median evaluations-to-target grows with $n$ for the constraint-preserving ansatz, the penalty ansatz, parallel tempering on the same Hamiltonian, and TT-RI-LS1. A quantum advantage claim survives only if the ansatz's growth curve is flatter than parallel tempering's across $n = 5$ to $8$.
Decisive check 2. We check whether transferred angle priors cut the ansatz's evaluation count relative to COBYLA (a standard derivative-free optimizer), as they did in Khairy et al.'s graph setting. That paper reported up to a 30.15-fold smaller optimality gap than Nelder-Mead.
Decisive check 3. Whatever wins, we run it on $H_6$ at $n = 9$ against the 241 record and report the best nonlinearity found under the $10^6$-evaluation budget.
References
- Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean Functions
- A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes
- Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
- Benchmarking variational quantum algorithms for combinatorial optimization in practice
- A systematic study on the design of odd-sized highly nonlinear boolean functions via evolutionary algorithms
- Discovering Rotation Symmetric Self-dual Bent Functions with Evolutionary Algorithms
- Resource Efficient Boolean Function Solver on Quantum Computer
- A New Angle: On Evolving Rotation Symmetric Boolean Functions