Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2102.06813 · Quantum Information Processing

Empirical performance bounds for quantum approximate optimization

Phillip C. Lotshaw, Travis S. Humble, Rebekah Herrman, James Ostrowski, George Siopsis

Published Nov 25, 2021• 71 citations
arXivHTMLPDF
DOI
10.1007/s11128-021-03342-3

Related papers

A Hybrid Quantum-Classical Framework for Socioeconomically Weighted Warehouse Facility Location: Novel QUBO Formulation with Automated Repair Mechanisms and Theoretical Performance Guarantees

Yalla Jnan Devi Satya Prasad

This paper introduces a groundbreaking hybrid quantum-classical algorithm for the socioeconomically weighted warehouse facility location problem, addressing critical challenges in modern supply chain optimization. We present a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation with rigorously derived penalty parameters, automated constraint repair mechanisms, and theoretically proven performance guarantees. Our hybrid approach integrates demand-weighted kmedoids clustering with quantum annealing, achieving an 7.92% reduction in total weighted distance over classical baselines while maintaining 95% feasibility rates. Key innovations include: (1) mathematically rigorous penalty parameter bounds ensuring constraint satisfaction, (2) automated quantum solution repair algorithms with bounded objective deterioration, (3) intelligent hybrid merging strategies leveraging complementary classicalquantum strengths, and (4) empirical 95% repair bound and a sufficient computable penalty condition. Experimental validation on real Hyderabad socioeconomic data demonstrates superior performance with approximation ratio 1.11 compared to pure quantum approaches (1.22) and classical methods (1.05), establishing practical quantum advantage for logistics optimization,

•Sep 15, 2025•0 citations

Approaches to Constrained Quantum Approximate Optimization

Zain H. Saleem, Teague Tomesh, Bilal Tariq +1 more

arXiv:2010.06660•SN Computer Science•Jan 30, 2023•37 citations

The computational power of quantum approximate optimization algorithms

Ryan Maamer

•Jan 1, 2022•0 citations

Multi-angle quantum approximate optimization algorithm

Rebekah Herrman, Phillip C. Lotshaw, James Ostrowski +2 more

The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.

arXiv:2109.11455•Scientific Reports•Apr 26, 2022•167 citations

Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods

Elies Gil-Fuster, Matan Ninio, Lennart Bittel +4 more

Optimization problems are among the leading candidates for industrially relevant quantum advantage. Decoded quantum interferometry (DQI) has been proposed to tackle approximate optimization, establishing a connection to classical decoding problems. While previous work has primarily focused on the theoretical complexity of DQI, comparatively little is known about its empirical performance relative to classical algorithms. In this work, we shed further light on the complexity of DQI and investigate numerically whether classical sampling methods can emulate the optimization capabilities of DQI. We first present a simplified analytical characterization of DQI that connects its expected performance to binomial statistics, and we identify concrete obstacles in further studying the complexity of DQI. Exploiting the fact that DQI output probabilities are efficiently computable, we apply Markov chain Monte Carlo (MCMC) techniques, particularly block-Gibbs sampling, to sample from the induced distribution. We study the runtime scaling of these methods for two optimization problems called max-XORSAT, where we reach beyond $1000$ effective qubits; and OPI, where we reach beyond $150$ effective qubits. Our results show that MCMC algorithms can reliably attain the approximation ratios expected from DQI across a broad range of problem sizes. In OPI, in the regime where a super-polynomial advantage is claimed for DQI, we observe an empirical runtime for MCMC that scales approximately as $1.1^{n}$, indicating exponential growth with a comparatively small base. Our findings do not refute existing quantum advantage claims but provide new empirical evidence that classical sampling algorithms can closely match DQI's optimization performance, offering a more nuanced perspective on the practical advantage of DQI.

quant-pharXiv:2607.28120•Jul 31, 2026•5 citations

Quantum Gate-Model Approaches to Exact and Approximate Optimization

Stuart Hadfield

Many of the most challenging computational problems arising in practical applications are tackled by heuristic algorithms which have not been rigorously proven to outperform other approaches but rather have been empirically demonstrated to be effective. While quantum heuristics have been proposed since the early days of quantum computing, true empirical evaluation of the real-world performance of these algorithms is only becoming possible now as increasingly powerful quantum gate-model devices continue to come online.In this talk, I will give an overview of the NASA QuAIL team's ongoing investigation into quantum gate-model heuristic algorithms for exact and approximate optimization. In particular, we consider the performance of the Quantum Approximate Optimization Algorithm on NP-hard optimization problems, and describe algorithm parameter setting strategies for real-world quantum hardware. We then show a generalization of QAOA circuits, the Quantum Alternating Operator Ansatz, especially suitable for low-resource implementations of QAOA for problems with hard (feasibility) constraints. The talk will conclude with a discussion of research challenges, particularly for optimization and sampling applications of QAOA, and the potential of more general quantum heuristics to give advantages over classical computers.

Bulletin of the American Physical Society•Mar 5, 2019•0 citations
This paper introduces a groundbreaking hybrid quantum-classical algorithm for the socioeconomically weighted warehouse facility location problem, addressing critical challenges in modern supply chain optimization. We present a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation with rigorously derived penalty parameters, automated constraint repair mechanisms, and theoretically proven performance guarantees. Our hybrid approach integrates demand-weighted kmedoids clustering with quantum annealing, achieving an 7.92% reduction in total weighted distance over classical baselines while maintaining 95% feasibility rates. Key innovations include: (1) mathematically rigorous penalty parameter bounds ensuring constraint satisfaction, (2) automated quantum solution repair algorithms with bounded objective deterioration, (3) intelligent hybrid merging strategies leveraging complementary classicalquantum strengths, and (4) empirical 95% repair bound and a sufficient computable penalty condition. Experimental validation on real Hyderabad socioeconomic data demonstrates superior performance with approximation ratio 1.11 compared to pure quantum approaches (1.22) and classical methods (1.05), establishing practical quantum advantage for logistics optimization,
The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.
Optimization problems are among the leading candidates for industrially relevant quantum advantage. Decoded quantum interferometry (DQI) has been proposed to tackle approximate optimization, establishing a connection to classical decoding problems. While previous work has primarily focused on the theoretical complexity of DQI, comparatively little is known about its empirical performance relative to classical algorithms. In this work, we shed further light on the complexity of DQI and investigate numerically whether classical sampling methods can emulate the optimization capabilities of DQI. We first present a simplified analytical characterization of DQI that connects its expected performance to binomial statistics, and we identify concrete obstacles in further studying the complexity of DQI. Exploiting the fact that DQI output probabilities are efficiently computable, we apply Markov chain Monte Carlo (MCMC) techniques, particularly block-Gibbs sampling, to sample from the induced distribution. We study the runtime scaling of these methods for two optimization problems called max-XORSAT, where we reach beyond 100010001000 effective qubits; and OPI, where we reach beyond 150150150 effective qubits. Our results show that MCMC algorithms can reliably attain the approximation ratios expected from DQI across a broad range of problem sizes. In OPI, in the regime where a super-polynomial advantage is claimed for DQI, we observe an empirical runtime for MCMC that scales approximately as 1.1n1.1^{n}1.1n, indicating exponential growth with a comparatively small base. Our findings do not refute existing quantum advantage claims but provide new empirical evidence that classical sampling algorithms can closely match DQI's optimization performance, offering a more nuanced perspective on the practical advantage of DQI.
Many of the most challenging computational problems arising in practical applications are tackled by heuristic algorithms which have not been rigorously proven to outperform other approaches but rather have been empirically demonstrated to be effective. While quantum heuristics have been proposed since the early days of quantum computing, true empirical evaluation of the real-world performance of these algorithms is only becoming possible now as increasingly powerful quantum gate-model devices continue to come online.In this talk, I will give an overview of the NASA QuAIL team's ongoing investigation into quantum gate-model heuristic algorithms for exact and approximate optimization. In particular, we consider the performance of the Quantum Approximate Optimization Algorithm on NP-hard optimization problems, and describe algorithm parameter setting strategies for real-world quantum hardware. We then show a generalization of QAOA circuits, the Quantum Alternating Operator Ansatz, especially suitable for low-resource implementations of QAOA for problems with hard (feasibility) constraints. The talk will conclude with a discussion of research challenges, particularly for optimization and sampling applications of QAOA, and the potential of more general quantum heuristics to give advantages over classical computers.