Scalable Clifford-Based Classical Initialization for the Quantum Approximate Optimization Algorithm

arXiv:2602.14327 · quant-ph · Submitted 2026-02-15 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Scalable Clifford-Based Classical Initialization for the Quantum Approximate Optimization Algorithm".

Mira: Here's the gist of the paper. Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA), offer a promising route to tackling optimization problems on near- and intermediate-term quantum devices However, their performance critically depends on the choice of initial parameters, and the limited expressiveness of the QAOA ansatz makes identifying effective initializations both difficult and unscalable.

Kai: To address this, we propose a framework, Scalable Parameter Initialization for QAOA (SPIQ) that employs a relaxed QAOA ansatz to enable classical search over a set of Clifford-preparable quantum states that yield high-quality solutions.

Mira: These states serve as superior QAOA initializations, driving rapid convergence while significantly reducing the quantum circuit evaluations needed to reach high-quality solutions and consequently lowering quantum-device cost.

Kai: The Proposed Framework SPIQ is a scalable, application-agnostic initialization framework that achieves an absolute accuracy improvement of up to 80% over state-of-the-art initialization and reduces initial-state diversity by an average of up to 10, 448× across QUBO, PUBO, and PCBO problems spanning tens to hundreds of qubits.

Title and authors: Kai: So we’re looking at this paper today, it’s called Scalable Clifford-Based Classical Initialization for the Quantum Approximate Optimization Algorithm. It sounds like they are trying to solve a big problem with how you start a quantum optimization run.

Mira: Yeah, that's right. Basically, they are focusing on making the initialization part of QAOA scalable and classical so it doesn't become this huge bottleneck when you actually try to run these things on real hardware.

Lev: From my side, it sounds like they are trying to tame the complexity of finding those good starting points before we even start the actual quantum optimization loop.

Kai: Exactly. It’s about moving away from needing specific problem-solving tricks for every single instance and instead having a general framework that works across different types of problems.

Mira: Right, so they are proposing this Scalable Parameter Initialization for QAOA, or SPIQ, which uses a relaxed QAOA ansatz to let the classical computer search through these high-quality Clifford states.

Lev: That sounds like an attempt to reduce the number of times we have to run the circuit on that physical device before we get a decent answer.

Kai: Right, so it’s about making that initial setup phase much more efficient and less dependent on just guessing parameters.

The paper's summary: Mira: So the paper explains that the main issue with QAOA is that the choice of those initial parameters really dictates how good your final solution will be, and finding good ones is computationally intensive, especially when you are running it on hardware where every single circuit evaluation takes a lot of time.

Kai: And they tackle this by proposing SPIQ, which uses a relaxed QAOA ansatz to set up a classical search over these Clifford-preparable quantum states that have high-quality solutions.

Lev: So the core idea is that instead of guessing parameters directly on the quantum machine, we use classical computation to find states that are already good starting points for the QAOA process.

Mira: Precisely. They show this approach can drive rapid convergence and significantly cut down on how many quantum circuit evaluations you need to get a high-quality solution, which directly lowers those expensive quantum device costs.

Kai: It sounds like they're aiming for a massive improvement in efficiency by replacing brute-force initialization with a targeted classical search.

Lev: So it’s about pruning the search space classically before we commit to running deep quantum circuits, which makes sense for real hardware constraints.

The paper's improvements: Kai: The paper highlights that this framework achieves an absolute accuracy improvement of up to eighty percent over the current state-of-the-art initialization methods. That’s a big jump in solution quality without needing a fundamentally different quantum algorithm.

Mira: And they also show they reduce the diversity of initial states by an average factor of ten thousand four hundred forty-eight across QUBO, PUBO, and PCBO problems that can have tens to hundreds of qubits. That's a massive reduction in the number of bad starting points you have to worry about.

Lev: From an engineering standpoint, having this much better initialization quality means we need far fewer shots on the quantum computer before we see a reliable result.

Kai: And they achieve this by using two complementary strategies to pick these high-quality Clifford points from different parts of the search landscape, which helps them handle non-convexity and device noise better.

Mira: One strategy is a fixed interval selection that sorts candidates by expectation value and picks points evenly spaced along that list. The other is K-GAPS, which uses K-means clustering and gradient norm heuristics to find effective states based on where the landscape is flat or steep.

Lev: I’m interested in the gradient norm idea; if a point has a near zero gradient norm, it means it's already in a stationary region, so that’s probably not a good place to start our optimization anyway.

Conclusion: Kai: So to wrap up, the paper shows that Clifford initialization gives strong overlap with the ground state energy even before we run any quantum optimization steps. This makes it much less susceptible to noise and those tricky barren plateaus we see in other methods.

Mira: And because of this robust starting point, SPIQ provides initial points that help speed up convergence and save a lot of money by reducing those repeated quantum executions. It works well across different problem structures like Max-Cut, Knapsack, and even real medical datasets.

Lev: For real hardware running these algorithms, this robustness is critical because it means the overhead from the initialization phase is much lower than what we’d expect with less effective warm-starts.

Kai: So essentially, this Scalable Clifford-Based Classical Initialization for the Quantum Approximate Optimization Algorithm gives us a way to get higher quality solutions faster and use fewer quantum resources.

Mira: It’s a framework that moves away from problem-specific heuristics by using general techniques to find good starting points classically.

Lev: I think the main thing here is that it’s robust enough across different problem types, which is hard to achieve with specialized initialization methods.

Kai: Yeah, so this paper gives us a much more reliable and efficient way to tackle these optimization problems on near-term devices.

University of Michigan · University of Maryland

quant-ph

Submitted: 2026-02-15

Updated: 2026-08-23

Comments: IEEE QCE 2026 Camera Ready Submission

Journal ref: Proceedings of IEEE QCE 2026

Code: https://github.com/d-bharadwaj/SPIQ

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 91/100

The gist: Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA), offer a promising route to tackling optimization problems on near- and intermediate-term quantum…

Key concepts

Variational Quantum Algorithms (VQAs)
These are methods used on near- and intermediate-term quantum devices to solve optimization problems. They work by iteratively adjusting parameters on a quantum circuit, using classical feedback to minimize an objective function, aiming to find the best possible solution.
QAOA Ansatz
This is the specific structure of the quantum circuit used within VQAs like QAOA. The authors use a 'relaxed' version of this ansatz, allowing independent rotation angles in each layer. This relaxation makes it easier for classical computers to find high-quality initial states.
Clifford-Preparable States
These are specific quantum states that can be created using only Clifford gates (a restricted set of quantum operations). The paper searches through a large space of these states classically because they are proven to yield superior starting points for the QAOA optimization process.

Terminology

Summary

Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA), offer a promising route to tackling optimization problems on near- and intermediate-term quantum devices However, their performance critically depends on the choice of initial parameters, and the limited expressiveness of the QAOA ansatz makes identifying effective initializations both difficult and unscalable. p. 0 To address this, we propose a framework, Scalable Parameter Initialization for QAOA (SPIQ) that employs a relaxed QAOA ansatz to enable classical search over a set of Clifford-preparable quantum states that yield high-quality solutions. p. 0 These states serve as superior QAOA initializations, driving rapid convergence while significantly reducing the quantum circuit evaluations needed to reach high-quality solutions and consequently lowering quantum-device cost. p. 0

The Proposed Framework

SPIQ is a scalable, application-agnostic initialization framework that achieves an absolute accuracy improvement of up to 80% over state-of-the-art initialization and reduces initial-state diversity by an average of up to 10, 448× across QUBO, PUBO, and PCBO problems spanning tens to hundreds of qubits. The framework involves a workflow that includes generating a problem instance, building a multi-angle ansatz, searching the Clifford space for high-quality states classically using a Genetic Algorithm (GA) optimizer, strategically selecting these points using two complementary methods, and finally performing optimization from selected points. p. 3

The Role of Ansatz Expressivity

To overcome the limitations of direct Clifford-based initialization strategies to QAOA, the authors leverage the expressive structure of multi-angle QAOA (ma-QAOA) which allows independent rotation angles within each layer without increasing circuit depth. This ma-QAOA structure results in a total of (m + n) ∗ p parameters, where m is the number of clauses and n is the number of qubits. p. 4 The authors demonstrate that relaxing the correlation between QAOA parameters substantially improves the circuit’s capacity to generate high-quality Clifford states on classical compute. p. 1

Strategies for High-Quality Seed Selection

The SPIQ framework introduces two complementary strategies for selecting high-quality Clifford points from different regions of the landscape to seed a multi-start optimization. The first strategy is the Fixed-Interval Selection method, which orders candidates by expectation value and picks points at regular intervals along this sorted list. p. 4 The second strategy is K-GAPS (K-means Gradient-Aware Point Selection), which leverages K-means clustering and gradient-norm heuristics to identify effective Clifford states. p. 4 The authors note that the gradient norm quantifies the steepness of the landscape at a point, and a near-zero gradient norm indicates that a point already lies in a stationary region, making it a poor candidate for subsequent optimization. p. 4

Performance Across Benchmarks

Evaluations across diverse problem instances show strong performance, with SPIQ consistently achieving high proximity to the true ground state energy across Max-Cut, Knapsack, and real-world medical higher-order interaction datasets. For instance, on Max-Cut problems over 10 instances of 3-regular graphs with sizes ranging from 50 to 800 qubits, the relative improvement reaches up to 10,000× over random initialization and a reduction factor of up to 48,132× in the number of solution states compared to random initialization on 3-regular Max-Cut instances. p. 7

Conclusion on Initialization Quality

The results demonstrate that Clifford initialization yields strong overlap with the ground state energy, showing effectiveness even before any quantum optimization is performed. The authors conclude that SPIQ provides starting points that reduce susceptibility to noise and barren plateaus, enabling faster convergence and substantial economic savings due to reduced repeated quantum executions. p. 9 This framework is robust across diverse problem structures, including non-graph benchmarks like Knapsack and higher-order interaction models. p. 8 The authors further note that Red-QAOA is limited to graph-structured problems, whereas SPIQ exhibits robust performance across diverse problem structures. p. 8

Acknowledgment

We thank Teague Tomesh and Frederic Chong for helpful and insightful discussions. This material is based upon work supported by the U. p. 9S. Department of Energy, Office of Science, Office of Scientific Computing Research, Accelerated Research in Quantum Computing under Award Number DESC0025633. p. 9 This research used resources of the National Energy Research Scientific Computing Center, a DOE Office of Science User Facility supported by the Office of Science of the U. p. 9S. Department of Energy under Contract No. p. 9 DE-AC02-05CH11231 using NERSC award ASCR-ERCAP0033197 and NERSC DDR-ERCAP0035341. p. 9

References

[4] D. Bharadwaj, “SPIQ: A scalable, clifford-driven initialization framework for qaoa,” 2026, software repository

[5] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, “Quantum machine learning,” Nature

[6] K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K Pandya and A Summer “A review on quantum approximate optimization algorithm” Physics Reports

[7] E. Boros and P. L Hammer “Pseudo-boolean optimization” Discrete Applied Mathematics

[8] E. Boros, P. L Hammer, and G Tavares “Local search heuristics for quadratic unconstrained binary optimization (qubo)” Journal of Heuristics

[9] M Cerezo, A Arrasmith, R Babbush et al “Variational Quantum Algorithms” Nature Reviews Physics

[10] M H. Cheng, K E. Khosla et al “Clifford circuit initialisation for variational quantum algorithms” 2022

[11] C.-N Chou, P J Love et al “Quantum computing with qiskit” 2024

[13] E Farhi, J Goldstone, and S Gutmann “A Quantum Approximate Optimization Algorithm” Nov. 2014

[15] E Farhi, J Goldstone et al “The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size” Quantum

[26] R Herrman, P C Lotshaw et al “Multi-angle quantum approximate optimization algorithm” 2021

[31] A Javadi-Abhari, M Treinish et al “Quantum computing with qiskit” 2024

[39] C Y.-Y. Lin and Y Zhu “Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree” arXiv, Jan. p. 5 2016

[45] National Energy Research Scientific Computing Center (NERSC), “Perlmutter system” 2025

[47] J. B Odili “Combinatorial optimization in science and engineering” Current Science, pp. p. 9

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Scalable Parameter Initialization for QAOA (SPIQ) can be integrated into variational quantum algorithms to drive rapid convergence while significantly reducing quantum circuit evaluations needed to reach high-quality solutions and consequently lowering quantum-device cost. This allows AI systems to tackle combinatorial optimization problems on near- and intermediate-term devices more efficiently.

  2. The framework enables absolute accuracy improvement of up to 80% over state-of-the art initialization and reduces initial-state diversity by an average of up to 10,448 times across QUBO, PUBO, and PCBO problems spanning tens to hundreds of qubits. This capability allows AI systems to maintain high solution quality even as problem size increases beyond current limitations.

  3. The system can perform a classical search over a set of Clifford-preparable quantum states that yield high-quality solutions, effectively pruning the QAOA solution space and eliminating a large fraction of non-optimal states. This leads to more focused and efficient exploration during the subsequent quantum optimization phase.

  4. By introducing two complementary strategies for selecting high-quality Clifford points from different regions of the landscape (Fixed-Interval Selection and K-GAPS), the system can mitigate non-convexity and device noise, increasing the likelihood of reaching high quality solutions. This allows AI systems to improve convergence in noisy settings without requiring extensive prior problem-specific heuristics.

  5. The framework demonstrates robust performance across diverse problem structures, including MaxCut, Knapsack, and real-world medical higher-order interaction datasets (PCBO), consistently achieving higher overlap with the ground state energy compared to prior warm-start methods like RedQAOA. This versatility allows AI systems to be applied effectively across a broader spectrum of combinatorial optimization tasks.

  6. The system provides a Reduction Factor (RF) metric that quantifies the reduction in the number of solution states between initial points, showing a maximum reduction of 48,132 times on 3-regular Max-Cut instances. This allows AI systems to quantify and optimize the efficiency gains achieved by using high-quality initialization strategies.

Sources

Related papers