A SWAP-free Framework for QAOA

Authors per arXiv listing · arXiv:2604.25058 · new submission, quant-ph (math.CO secondary) · score 8/10

Abstract

The performance of the Quantum Approximate Optimization Algorithm (QAOA) on noisy intermediate-scale quantum (NISQ) devices is strongly limited by sparse qubit connectivity. When interactions required by QAOA Hamiltonians are not aligned to the hardware topology, transpilation introduces SWAP gates, increasing circuit depth and noise. We propose a SWAP-free QAOA framework based on modifying the cost Hamiltonian so that it can be implemented natively on the hardware. We formulate this as a mixed-integer semidefinite program (MISDP) that selects a hardware-compatible approximation of the original cost matrix and optimizes the allocation of logical variables to physical qubits. We prove that the associated decision problem is NP-complete and derive theoretical guarantees relating the MISDP objective to the loss in the original optimization problem through the Lovász number of the hardware graph. Since solving MISDPs is practical only for small instances, we introduce heuristics based on spectral properties of the problem matrix and hardware graph. Our experiments on a cardinality-constrained quadratic optimization model for index tracking show competitive performance against a baseline representing ideal QAOA under SWAP-induced noise. These results indicate that, on sparse NISQ architectures, a hardware-aware approximation of the objective may be more effective than an exact but heavily transpiled Hamiltonian implementation.

Executive summary

A SWAP-free QAOA framework that modifies the cost Hamiltonian to fit the hardware connectivity graph rather than transpiling SWAPs to fit the original problem. The selection of hardware-compatible interactions is cast as a mixed-integer semidefinite program (MISDP) that jointly chooses a hardware-conformant approximation of the cost matrix and an optimal logical-to-physical qubit assignment. The associated decision problem is shown NP-complete; the MISDP loss is bounded via the Lovász number of the hardware graph. Spectral heuristics (Perron- and Laplacian-based eigenvector orderings) are introduced for scaling. Experiments on cardinality-constrained k-medoids index tracking show the SWAP-free formulation outperforming an idealised SWAP-laden QAOA baseline at realistic noise levels — directly relevant to Y2/Y3 portfolio QAOA pipelines.

Main contribution

The framework's central trade-off is novel: exchange formulation fidelity (the cost Hamiltonian only approximates the original) for circuit shallowness (no SWAPs needed). The argument is that on sparse NISQ hardware, the noise from SWAP-induced depth dominates the loss from the approximation, especially at QAOA-layer depths beyond a few. The MISDP formulation makes the trade-off precise: it's a single optimisation that simultaneously selects which interactions to keep (fitting the hardware graph) and how to relabel logical qubits to physical qubits. Cardinality constraints are handled via a Hamming-weight-preserving XY mixer with a Dicke initial state — exactly Y2's hard-mixer-for-feasibility template.

Key theorems / results / algorithms

NP-completeness: the SWAP-free QAOA decision problem (does there exist a hardware-graph-compatible cost approximation with loss below threshold?) is NP-complete.
Theoretical guarantee via Lovász theta: the MISDP objective is bounded in terms of the Lovász number of the hardware graph, relating the maximum allowable approximation loss to a graph-theoretic quantity computable from the hardware topology alone.
Heuristics: three spectral heuristics — Perron Connected, Perron Disconnected, Laplacian Connected — order qubits by eigenvectors of (matrix-Laplacian or cost-matrix Perron vectors) and select hardware-compatible interactions in that order.
Algorithm — heuristic permutation: connectivity-aware heuristic that chooses a permutation matrix (logical-to-physical qubit mapping) by aligning spectral orderings of the hardware Laplacian and the cost matrix.
Cardinality-constrained QAOA setup: XY mixer H_M = (1/2) sum_{ij in E(G)} (X_i X_j + Y_i Y_j), Dicke initial state |D_k^n>; the k-excitation subspace is invariant under both cost and mixer evolutions, enforcing cardinality without penalty terms.

Detailed walkthrough

The setup (Sec. II) is a cardinality-constrained QUBO arising from k-medoids index-tracking: select k assets that are mutually dissimilar (large x^T C x) while remaining representative of the universe (small 1^T C x). The QAOA encoding uses an XY mixer that preserves Hamming weight and a Dicke initial state, so cardinality is enforced by symmetry rather than by penalty terms. This is exactly Y2's quasi-binary-encoding philosophy in a different problem.

The MISDP formulation (Sec. III) chooses a hardware-compatible matrix Ĉ' that minimises the approximation loss to the true Ĉ subject to: only entries (i,j) with edge in the hardware graph G are non-zero, and the choice is consistent with a permutation matrix encoding the logical-to-physical mapping. This is a mixed-integer semidefinite program: linear matrix inequalities + linear constraints on entries + integrality on the permutation. The program has polynomial size in the input data but is NP-hard.

The theoretical anchor is the bound via the Lovász theta number theta(G) of the hardware graph (Sec. III). Intuitively, theta(G) controls how rich the set of hardware-compatible interaction patterns is: a graph with high theta admits more flexible hardware-conformant approximations and so smaller approximation loss. This ties the algorithmic question (how good is SWAP-free QAOA?) to a graph parameter computable from the hardware connectivity alone.

Because solving MISDPs is impractical at scale, Section IV develops three spectral heuristics. The Perron Connected heuristic orders logical qubits by the entries of the Perron eigenvector of the cost matrix Ĉ and assigns them to physical qubits ordered by the Perron of the hardware graph. The Laplacian Connected variant uses the largest-eigenvalue eigenvector of the Laplacian L_G. The Disconnected variants relax the connectivity constraint. Section IV.C evaluates the heuristics on small graphs (n=8) and reports that the Laplacian heuristic dominates on dense graphs, while Perron variants are competitive on sparse ones (Fig. n_8_lambda_normalized, n_8_opt_gap).

The benchmark (Sec. V) compares heuristically-selected SWAP-free QAOA against an ideal QAOA simulation that includes SWAP-induced noise modelled by depolarising channels. On real index-tracking data with n=10–60 assets, the SWAP-free framework matches or beats the ideal-QAOA-with-SWAPs baseline as soon as SWAP overhead becomes non-trivial (Fig. n_10_60_opt_gap_2 and n_10_60_opt_gap_swaps). The optimality gap of the ideal SWAPped QAOA grows monotonically with n, while the SWAP-free version flattens — the regime crossover where SWAP-free wins arrives early on sparse architectures.

The paper's conclusion is sharp: on sparse NISQ hardware, fidelity to the original Hamiltonian is the wrong objective. A hardware-aware approximation of the cost matrix, even one that NP-hard-ly trades approximation quality for circuit depth, can deliver better end-to-end solution quality than an exact-but-heavily-transpiled implementation. For Y3-style portfolio QAOA, where SWAP overhead on Heron r2 is non-trivial for fully-connected portfolio Hamiltonians, this is a directly relevant alternative.

Figures

Figure 1. Normalised lambda values for the three heuristics across graph density at n=8 — comparison of Perron Connected, Perron Disconnected, and Laplacian Connected.

Figure 2. Optimality gap as a function of graph density at n=8 for the same three heuristics.

Figure 3. Optimality gap as a function of n for the three SWAP-free heuristics versus ideal QAOA with SWAP-induced noise.

Figure 4. SWAP-overhead growth with n for the ideal-QAOA baseline — the noise driver that the SWAP-free formulation eliminates.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y2. Direct method overlap. Y2's quasi-binary encoding + XY-mixer for portfolio QAOA enforces cardinality without penalty terms; this paper uses exactly the same XY-mixer + Dicke initial state for the cardinality-constrained k-medoids index-tracking problem. The SWAP-free angle is novel — Y2 didn't address hardware topology — but the encoding philosophy is identical.

Y3. Direct scope overlap. Y3 ran QAOA for the DGMVP portfolio problem and found thermal relaxation precludes quantum advantage in the hardware-noise regime. SWAP-related depth is one of the noise drivers Y3 contended with. This paper offers a concrete mitigation: avoid the SWAPs by accepting an approximated cost Hamiltonian whose error is bounded via Lovász theta.

Y4. Light scope overlap. Y4's ADMM hybrid solves cardinality-constrained binary optimisation with provable epsilon-approximation. This paper accepts a similar approximation regime (Hamiltonian fidelity loss in exchange for hardware compatibility) but on the QAOA rather than Grover side.

Recommended action for Yuan

Adapt for DGMVP (Y3). Re-run Y3's portfolio QAOA experiments using the Laplacian-Connected heuristic for the hardware graph of Heron r2; compare end-to-end solution quality with and without SWAP-free approximation. Direct test of whether the regime crossover applies to the portfolio problem.
Cite in next portfolio paper. The Lovász-theta bound is the kind of theoretical guarantee that elevates a hardware-compatibility heuristic to a principled approximation result — useful whenever Y2/Y3 argue about hardware-aware QAOA design.
Read deeper, especially Sec. III. The MISDP formulation is more general than the index-tracking application here and could in principle be combined with Y2's quasi-binary encoding for a SWAP-free constrained-portfolio QAOA.