arxiv: 2604.25058 · v1 · submitted 2026-04-27 · 🪐 quant-ph · math.CO

Recognition: unknown

A SWAP-free Framework for QAOA

Thiago Assis , Pedro Baptista , Laila Lopes , Diego Ferreira , Gabriel Coutinho

Authors on Pith no claims yet

Pith reviewed 2026-05-08 03:39 UTC · model grok-4.3

classification 🪐 quant-ph math.CO

keywords QAOANISQSWAP-freemixed-integer semidefinite programmingLovász numberqubit mappinghardware-aware optimizationindex tracking

0 comments

The pith

QAOA can avoid SWAP noise on sparse hardware by approximating its cost matrix to match the device topology.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that modifying the cost Hamiltonian to fit native hardware interactions, rather than inserting SWAP gates during transpilation, can produce effective QAOA circuits on limited-connectivity NISQ devices. This modification is cast as a mixed-integer semidefinite program that simultaneously approximates the original cost matrix and assigns logical variables to physical qubits. The authors prove the underlying decision problem is NP-complete and link the approximation quality to the original problem loss through the Lovász number of the hardware graph. Spectral heuristics make the approach practical for larger instances, and experiments on a cardinality-constrained quadratic model for index tracking show results competitive with ideal QAOA under SWAP-induced noise. A sympathetic reader cares because current NISQ devices suffer from sparse connectivity that forces deep circuits; a native approximation may reduce depth and error without losing too much solution quality.

Core claim

The central claim is that QAOA remains useful on hardware graphs with limited edges by solving a mixed-integer semidefinite program to select a hardware-compatible approximation of the cost matrix together with an optimal qubit allocation; the decision version of this problem is NP-complete, yet the MISDP objective value bounds the loss in the original optimization problem via the Lovász number of the hardware graph, and spectral heuristics deliver competitive performance on index-tracking instances compared with SWAP-noisy baselines.

What carries the argument

The mixed-integer semidefinite program (MISDP) that selects a hardware-compatible approximation of the cost matrix and optimizes the allocation of logical variables to physical qubits.

If this is right

The Lovász number of the hardware graph provides an explicit theoretical bound on how much the approximated QAOA can degrade relative to the original problem.
Spectral heuristics based on the problem matrix and hardware graph scale the method beyond the small instances solvable by exact MISDP solvers.
On sparse NISQ architectures the hardware-aware approximation can outperform an exact but heavily transpiled implementation under realistic noise.
The approach applies directly to cardinality-constrained quadratic optimization models such as index tracking.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same matrix-approximation idea could extend to other variational quantum algorithms that suffer from connectivity mismatch.
Device topology and problem structure should be co-designed rather than treating hardware as a fixed constraint that must be emulated exactly.
Empirical tests on actual quantum hardware would be needed to quantify whether depth reduction reliably outweighs approximation error.

Load-bearing premise

That a hardware-compatible approximation of the cost matrix preserves sufficient structure of the original optimization landscape for the approximated QAOA to remain useful.

What would settle it

A direct comparison on a real NISQ device measuring whether the solution quality of the MISDP-approximated QAOA exceeds that of the exact Hamiltonian after transpilation with SWAPs, for the same index-tracking instance.

Figures

Figures reproduced from arXiv: 2604.25058 by Diego Ferreira, Gabriel Coutinho, Laila Lopes, Pedro Baptista, Thiago Assis.

**Figure 1.** Figure 1: Comparison of heuristics. The plots show how normalized lambda view at source ↗

**Figure 2.** Figure 2: Optimality gap as a function of n for four algorithms: Perron Connected, Perron Disconnected, Laplacian Connected, and ideal QAOA with SWAP errors. For n > 20, our methods significantly outperform the SWAP-based baseline. This suggests that, as the problem size grows, avoiding SWAPs, even at the cost of imprecise objective functions, becomes more beneficial than relying on standard qubit-allocation stra… view at source ↗

read the original 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\'asz 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a MISDP way to approximate the QAOA cost matrix so it runs natively without SWAPs, plus NP-completeness and Lovasz links, but the bounds do not control the Hamiltonian spectrum that actually drives QAOA performance.

read the letter

The main takeaway is that this work replaces the exact cost Hamiltonian with a hardware-compatible approximation chosen through a mixed-integer semidefinite program. The goal is to eliminate SWAP overhead on sparse NISQ graphs. They prove the decision version is NP-complete and relate the approximation quality to the Lovasz number of the hardware graph. Spectral heuristics make the approach tractable for small cases, and on a cardinality-constrained index-tracking problem the approximated version beats a baseline that includes SWAP noise.

Referee Report

2 major / 2 minor

Summary. The paper proposes a SWAP-free QAOA framework that approximates the cost Hamiltonian via a mixed-integer semidefinite program (MISDP) to ensure native hardware compatibility, avoiding SWAP gates. It proves NP-completeness of the associated decision problem, derives theoretical guarantees linking the MISDP objective to the original optimization loss through the Lovász number of the hardware graph, introduces spectral heuristics for tractability, and reports competitive experimental results on a cardinality-constrained quadratic index-tracking problem relative to a noisy exact-QAOA baseline.

Significance. If the central claims hold, the work offers a practical route to reduce circuit depth on sparse NISQ devices by trading exact Hamiltonian fidelity for hardware-native implementability. The NP-completeness result and Lovász-based bounds provide theoretical grounding, while the heuristics and experiments suggest the approach can outperform transpiled baselines in noisy settings. These elements could influence hardware-aware algorithm design if the approximation preserves sufficient QAOA performance.

major comments (2)

[Theoretical guarantees] Abstract and theoretical guarantees section: the claimed relation between the MISDP objective and original loss via the Lovász number of the hardware graph bounds the combinatorial value but does not control the spectrum or eigenvectors of the approximated cost operator. QAOA success depends on the full time-dependent Hamiltonian landscape (cost + mixer), so an objective-preserving approximation can still alter low-lying eigenstates or introduce level crossings, rendering the guarantee insufficient to ensure competitive performance without additional error propagation analysis from heuristic MISDP solution to QAOA probability.
[Experiments] Experiments section: the reported competitive performance against the SWAP-noise baseline relies on spectral heuristics whose tuning and post-hoc choices are not fully detailed; without explicit sensitivity analysis or error bars on success probability across multiple random seeds, it is unclear whether the results generalize or depend on instance-specific parameter selection.

minor comments (2)

[Abstract] The abstract and introduction would benefit from a clearer statement of the precise form of the approximated cost matrix and how it differs from standard QAOA cost operators.
[Theoretical section] Notation for the hardware graph and its Lovász number should be introduced with an explicit equation or definition early in the theoretical section to aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major point below, with revisions indicated where the manuscript will be updated to improve clarity and completeness.

read point-by-point responses

Referee: [Theoretical guarantees] Abstract and theoretical guarantees section: the claimed relation between the MISDP objective and original loss via the Lovász number of the hardware graph bounds the combinatorial value but does not control the spectrum or eigenvectors of the approximated cost operator. QAOA success depends on the full time-dependent Hamiltonian landscape (cost + mixer), so an objective-preserving approximation can still alter low-lying eigenstates or introduce level crossings, rendering the guarantee insufficient to ensure competitive performance without additional error propagation analysis from heuristic MISDP solution to QAOA probability.

Authors: We agree that the Lovász-based bound addresses the combinatorial objective value rather than directly controlling the spectrum or eigenvectors of the approximated cost operator. The guarantee therefore does not by itself ensure preservation of the QAOA energy landscape or prevent potential level crossings. In the revised manuscript we will add an explicit discussion paragraph in the theoretical guarantees section clarifying the scope of the result and noting that empirical performance on the full QAOA circuit remains the primary validation. We will also state that a full perturbation analysis of heuristic MISDP solutions to QAOA success probability lies beyond the current scope but would be a natural extension. revision: partial
Referee: [Experiments] Experiments section: the reported competitive performance against the SWAP-noise baseline relies on spectral heuristics whose tuning and post-hoc choices are not fully detailed; without explicit sensitivity analysis or error bars on success probability across multiple random seeds, it is unclear whether the results generalize or depend on instance-specific parameter selection.

Authors: We accept that the experimental section requires additional detail for reproducibility. In the revision we will expand the description of the spectral heuristics to include the precise tuning procedure and any post-processing steps. We will also add sensitivity plots with respect to the main heuristic parameters and report success probabilities with error bars computed over multiple random seeds and problem instances. These additions will show that the reported advantage is robust rather than instance-specific. revision: yes

Circularity Check

0 steps flagged

No circularity: external Lovász number and NP-completeness reduction supply independent support

full rationale

The paper formulates the hardware-compatible approximation as an MISDP, proves the decision version NP-complete via (presumably standard) reduction, and invokes the Lovász number of the hardware graph to bound the objective loss. Both the NP-completeness result and the Lovász number are external combinatorial facts, not derived from the present work or fitted to its experimental data. Heuristics are introduced explicitly because exact MISDP solving is intractable; performance is then evaluated on an index-tracking instance against a noisy-SWAP baseline. No equation or claim reduces the reported QAOA advantage to a parameter fitted from the same evaluation set, nor does any load-bearing step collapse to a self-citation or self-definition. The skeptic observation that the Lovász bound addresses objective value rather than full QAOA spectrum is a question of proof strength, not circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The MISDP may implicitly assume that the hardware graph embedding preserves optimization-relevant structure, but this is not detailed.

pith-pipeline@v0.9.0 · 5520 in / 1094 out tokens · 22189 ms · 2026-05-08T03:39:03.481968+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

25 extracted references · 2 canonical work pages · 1 internal anchor

[1]

A qubo formulation of the k-medoids problem

Christian Bauckhage, Nico Piatkowski, Rafet Sifa, Dirk Hecker, and Ste- fan Wrobel. A qubo formulation of the k-medoids problem. InLernen, Wissen, Daten, Analysen, pages 54–63, 2019. 16

2019
[2]

Peptide conformational sampling using the quan- tum approximate optimization algorithm.npj Quantum Information, 9(1):70, 2023

Sami Boulebnane, Xavier Lucas, Agnes Meyder, Stanislaw Adaszewski, and Ashley Montanaro. Peptide conformational sampling using the quan- tum approximate optimization algorithm.npj Quantum Information, 9(1):70, 2023

2023
[3]

Conic programming to understand sums of squares of eigenvalues of graphs

Gabriel Coutinho, Thom´ as Jung Spier, and Shengtong Zhang. Conic programming to understand sums of squares of eigenvalues of graphs. arXiv preprint arXiv:2411.08184, 2024

work page arXiv 2024
[4]

On integrality in semidefinite pro- gramming for discrete optimization.SIAM Journal on Optimization, 34(1):1071–1096, 2024

Frank De Meijer and Renata Sotirov. On integrality in semidefinite pro- gramming for discrete optimization.SIAM Journal on Optimization, 34(1):1071–1096, 2024

2024
[5]

A Quantum Approximate Optimization Algorithm

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Ap- proximate Optimization Algorithm.arXiv preprint arXiv:1411.4028, 2014

work page internal anchor Pith review arXiv 2014
[6]

A framework for solving mixed-integer semidefinite programs.Optimization Methods and Software, 33(3):594–632, 2018

Tristan Gally, Marc E Pfetsch, and Stefan Ulbrich. A framework for solving mixed-integer semidefinite programs.Optimization Methods and Software, 33(3):594–632, 2018

2018
[7]

Michael R Garey and David S. Johnson. The rectilinear steiner tree prob- lem is np-complete.SIAM Journal on Applied Mathematics, 32(4):826– 834, 1977

1977
[8]

Optimized SWAP networks with equivalent circuit av- eraging for QAOA.Physical Review Research, 4(3):033028, 2022

Akel Hashim, Rich Rines, Victory Omole, Ravi K Naik, John Mark Kreikebaum, David I Santiago, Frederic T Chong, Irfan Siddiqi, and Pranav Gokhale. Optimized SWAP networks with equivalent circuit av- eraging for QAOA.Physical Review Research, 4(3):033028, 2022

2022
[9]

Alignment between initial state and mixer improves QAOA performance for constrained optimiza- tion.npj Quantum Information, 9(1):121, 2023

Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun, and Marco Pistoia. Alignment between initial state and mixer improves QAOA performance for constrained optimiza- tion.npj Quantum Information, 9(1):121, 2023

2023
[10]

Market Graph Clustering via QUBO and Digital Annealing.Journal of Risk and Financial Management, 14:34, 2021

Seo Woo Hong, Pierre Miasnikof, Roy Kwon, and Yuri Lawryshyn. Market Graph Clustering via QUBO and Digital Annealing.Journal of Risk and Financial Management, 14:34, 2021

2021
[11]

IBM Quantum Compute Resources: Miami Backend,

IBM Quantum. IBM Quantum Compute Resources: Miami Backend,
[12]

2-qubit error rate of 0.638% retrieved on February 3, 2026. 17

2026
[13]

Approximate graph coloring by semidefinite programming.Journal of the ACM (JACM), 45(2):246–265, 1998

David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming.Journal of the ACM (JACM), 45(2):246–265, 1998

1998
[14]

The unconstrained binary quadratic programming problem: a survey.J

Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng L¨ u, Haibo Wang, and Yang Wang. The unconstrained binary quadratic programming problem: a survey.J. Comb. Optim., 28(1):58–81, 2014

2014
[15]

On the shannon capacity of a graph.IEEE Transactions on Information theory, 25(1):1–7, 1979

L´ aszl´ o Lov´ asz. On the shannon capacity of a graph.IEEE Transactions on Information theory, 25(1):1–7, 1979

1979
[16]

Ising formulations of many NP problems.Frontiers in physics, 2:74887, 2014

Andrew Lucas. Ising formulations of many NP problems.Frontiers in physics, 2:74887, 2014

2014
[17]

Localization and centrality in networks.Physical review E, 90(5):052808, 2014

Travis Martin, Xiao Zhang, and Mark EJ Newman. Localization and centrality in networks.Physical review E, 90(5):052808, 2014

2014
[18]

Preparing Dicke States on a Quantum Computer, 01 2020

Chandra Mukherjee, Subhamoy Maitra, Vineet Gaurav, and Dibyendu Roy. Preparing Dicke States on a Quantum Computer, 01 2020

2020
[19]

Quantum computing for finance: Overview and prospects.Reviews in Physics, 4:100028, 2019

Rom´ an Or´ us, Samuel Mugel, and Enrique Lizaso. Quantum computing for finance: Overview and prospects.Reviews in Physics, 4:100028, 2019

2019
[20]

Quantum Computing in the NISQ era and beyond.Quan- tum, 2:79, 2018

John Preskill. Quantum Computing in the NISQ era and beyond.Quan- tum, 2:79, 2018

2018
[21]

A benchmarking study of quantum algorithms for combinatorial optimization.npj Quantum Information, 10(1):64, 2024

Krishanu Sankar, Artur Scherer, Satoshi Kako, Sam Reifenstein, Navid Ghadermarzy, Willem B Krayenhoff, Yoshitaka Inui, Edwin Ng, Tat- suhiro Onodera, Pooya Ronagh, et al. A benchmarking study of quantum algorithms for combinatorial optimization.npj Quantum Information, 10(1):64, 2024

2024
[22]

Duality and optimality con- ditions

Alexander Shapiro and Katya Scheinberg. Duality and optimality con- ditions. InHandbook of Semidefinite Programming: Theory, Algorithms, and Applications, pages 67–110. Springer, 2000

2000
[23]

Qubit allocation

Marcos Yukio Siraichi, Vin´ ıcius Fernandes dos Santos, Caroline Collange, and Fernando Magno Quint˜ ao Pereira. Qubit allocation. InProceedings of the 2018 international symposium on code generation and optimization, pages 113–125, 2018. 18

2018
[24]

Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. Quantum Approximate Optimization Algorithm: Per- formance, Mechanism, and Implementation on Near-Term Devices.Phys. Rev. X, 10(2):021067, 2020

2020
[25]

An exact qubit allo- cation approach for nisq architectures.Quantum Information Processing, 19(11):391, 2020

Pengcheng Zhu, Xueyun Cheng, and Zhijin Guan. An exact qubit allo- cation approach for nisq architectures.Quantum Information Processing, 19(11):391, 2020. 19

2020