Symmetry-Preserving Hierarchical Quantum Approximate Optimization Algorithm with Subproblems Beyond the Qubit Limit

Abstract

The quantum approximate optimization algorithm (QAOA) is a paradigmatic variational quantum algorithm for combinatorial optimization problems, yet on current quantum devices the available qubit count and achievable circuit depth remain the main bottlenecks to its practical application. Divide-and-merge reduces the number of variables encoded in a single quantum circuit, while contraction based on coarse graining extends the effective range of shallow circuits, but existing work has not addressed both challenges simultaneously. We propose symmetry-preserving hierarchical QAOA (SP-HQAOA), in which parity sector contraction preserves the zero-field Ising structure of the effective objective at every contraction step, thereby addressing both within a single algorithm. We further prove that this reduction is the unique one with this property. Successive contractions further decouple the maximum leaf block size $B$ from the qubit limit $Q$ per quantum call, so every quantum circuit uses at most $Q$ qubits even when $B>Q$. We also establish a deterministic repair-risk bound on the possible loss in optimal value caused by each sector restriction, and the resulting bounds can be summed across contraction steps and levels of the recursive hierarchy. With depth $p=1$, SP-HQAOA attains $99.4\%$ to $99.7\%$ of the exact optimum on $N=40$ random regular MaxCut leaf blocks and, with at most $10$ qubits per circuit, $96\%$ of the classical reference for $N=500$. SP-HQAOA demonstrates the capacity to use shallow quantum circuits to address combinatorial optimization problems whose variable count far exceeds the qubit limit of a single quantum call, and may enable practical quantum optimization advantages in the near term.

The paper asks how to combine QAOA divide-and-merge methods, which limit register size, with recursive contraction, which extends the effective range of shallow circuits. Its symmetry-preserving hierarchical QAOA contracts matched pairs by fixing $z_i z_j=\eta$ and substituting $z_i=s$, $z_j=\eta s$. This preserves zero-field signed Ising objectives, allowing contraction and block-flip merging to recur. A uniqueness result applies specifically to deterministic two-spin-to-one-spin reductions retaining two computational-basis assignments on a nonzero edge. Sector choices use QAOA $ZZ$ correlations and a deterministic repair-risk bound: restricting edge $(i,j)$ to parity $\eta$ raises the minimum energy by at most $R_{ij}(\eta)=2[S_{ij}^{\min}+J_{ij}\eta]_+$, where $S_{ij}^{\min}$ is the smaller endpoint external absolute coupling sum. Risks add across matchings and contraction steps. Conditional-expectation merging guarantees cutting at least half the between-block edge weight. These statements follow algebraically and are checked by exhaustive enumeration on small instances. Depth-$p=1$ simulations on $N=40$ random regular graphs reach $96.5\%$–$97.1\%$ of the exact optimum without classical refinement and $99.4\%$–$99.7\%$ with refinement. With at most ten qubits per call and leaf blocks of size 80, hierarchy outputs reach $95.6\%$ and $87.0\%$ of a classical multistart-local-search reference at $N=500$ and $1000$, respectively. The repair bounds are generally loose. Main quality benchmarks impose no finite risk budget; truncated local-circuit probabilities have only heuristic selection meaning. Hardware noise robustness remains untested, and extending the framework to objectives with one-body fields is left open.