QAOA on the infinite SK model maps exactly to a spin-boson Hamiltonian whose ground-state energy can be computed with matrix-product states, yielding numerical evidence that depth O(n/ε^1.13) suffices for (1-ε) approximation in the average case.
Iterative Interpolation Schedules for Quantum Approximate Optimization Algorithm
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
abstract
Quantum Approximate Optimization Algorithm (QAOA) is a promising quantum heuristic with empirical evidence of speedup over classical state-of-the-art for some problems. QAOA uses a parameterized circuit with $p$ layers, where higher $p$ yields better solutions, but requires optimizing $2p$ independent parameters, which is challenging at large $p$. We present an iterative interpolation method that exploits the smoothness of optimal parameter schedules by expressing them in a basis of orthogonal functions, generalizing the work of Zhou et al. By optimizing a small number of basis coefficients and iteratively increasing both circuit depth and coefficient count until convergence, our method constructs high-quality schedules for large $p$. We provide theoretical justification using Jackson's theorem and Lipschitz continuity to bound the required number of basis coefficients for a given accuracy. Our approach achieves better performance with fewer optimization steps than existing methods across three benchmark problems: the Sherrington-Kirkpatrick (SK) model, portfolio optimization, and Low Autocorrelation Binary Sequences (LABS). For the largest LABS instance, we achieve near-optimal merit factors with schedules exceeding 1000 layers, an order of magnitude beyond previous methods. Additionally, we observe that a mild growth in QAOA depth suffices to solve the SK model exactly, a result of independent theoretical interest.
fields
quant-ph 6representative citing papers
SAFE ma-QAOA achieves 64.3% fewer active parameters and 94.5% lower estimated QPU workload via surrogate pre-training and parameter distillation on Sherrington-Kirkpatrick, 2D spin glass, and Max-Cut instances.
QAOA on qudit-encoded integer graph problems outperforms the Frieze-Jerrum SDP for Max-k-Cut at p≤4 in regimes k=3 d≤10 and k=4 d≤40, while a new degree-of-saturation heuristic beats both on GSet but may be overtaken by QAOA at p≤20.
Tensor network simulations act as effective surrogate models for training QAOA on large 2D lattices, overcoming limits of parameter transfer from small instances and remaining classically feasible with moderate bond dimensions.
Systematic numerical study of QAOA parameter transfer on heavy-hex Ising models with local cubic terms shows transferred angles from small instances yield improving expectation values up to 49 layers on instances up to 156 qubits, with hardware runs confirming gains up to p=10.
QAOA-based QuSO achieves end-to-end speedup over classical baselines for power grid unit commitment with up to 14 qubits using 16 layers in high-load scenarios via efficient classical pre-computation.
citing papers explorer
-
Spin-Boson Mapping of the Quantum Approximate Optimization Algorithm
QAOA on the infinite SK model maps exactly to a spin-boson Hamiltonian whose ground-state energy can be computed with matrix-product states, yielding numerical evidence that depth O(n/ε^1.13) suffices for (1-ε) approximation in the average case.
-
SAFE ma-QAOA: Surrogate-Assisted and Fine-Tuning Enhanced Multi-Angle QAOA with Parameter Distillation
SAFE ma-QAOA achieves 64.3% fewer active parameters and 94.5% lower estimated QPU workload via surrogate pre-training and parameter distillation on Sherrington-Kirkpatrick, 2D spin glass, and Max-Cut instances.
-
Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut
QAOA on qudit-encoded integer graph problems outperforms the Frieze-Jerrum SDP for Max-k-Cut at p≤4 in regimes k=3 d≤10 and k=4 d≤40, while a new degree-of-saturation heuristic beats both on GSet but may be overtaken by QAOA at p≤20.
-
Tensor network surrogate models for variational quantum computation
Tensor network simulations act as effective surrogate models for training QAOA on large 2D lattices, overcoming limits of parameter transfer from small instances and remaining classically feasible with moderate bond dimensions.
-
Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
Systematic numerical study of QAOA parameter transfer on heavy-hex Ising models with local cubic terms shows transferred angles from small instances yield improving expectation values up to 49 layers on instances up to 156 qubits, with hardware runs confirming gains up to p=10.
-
End-to-End Speedup for Quantum Simulation-Based Optimization in Power Grid Management
QAOA-based QuSO achieves end-to-end speedup over classical baselines for power grid unit commitment with up to 14 qubits using 16 layers in high-load scenarios via efficient classical pre-computation.