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:2209.03386 · Quantum

Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs

Bence Bakó, Adam Glos, Özlem Salehi, Zoltán Zimborás

Published Mar 20, 2025• 36 citations
arXivHTMLPDF

Abstract

Current state-of-the-art quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent cost Hamiltonian suitable for the quantum device. Implementing each term of the cost Hamiltonian separately often results in high redundancy, significantly increasing the resources required. Instead, we propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits, eliminating the reliance on the binary optimization problem representation. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Program-based QAOA (Prog-QAOA). We exploit this idea for optimization tasks like the Travelling Salesman Problem and Max- K -Cut and obtain circuits that are near-optimal with respect to all relevant cost measures, e.g., number of qubits, gates, and circuit depth. While we demonstrate the power of Prog-QAOA only for a particular set of paradigmatic problems, our approach is conveniently applicable to generic optimization problems.

DOI
10.22331/q-2025-03-20-1663

Related papers

Quantum Approximate Optimization Algorithm (QAOA) for Solving NP-Hard Problems

Srikanth Kilaru, Thota Sravya Vardhani, Attluri Udaya Lakshmi +2 more

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.

IEEE Nexo-Tech International Conference on Advanced Technologies and Innovations (ICATI)•May 8, 2026•0 citations

QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem

Yiren Lu, Guojing Tian, Xiaoming Sun

Maximum cut (Max-Cut) problem is one of the most important combinatorial optimization problems because of its various applications in real life, and recently Quantum Approximate Optimization Algorithm (QAOA) has been widely employed to solve it. However, as the size of the problem increases, the number of qubits required will become larger. With the aim of saving qubits, we propose a coupling framework for designing QAOA circuits to solve larger-scale Max-Cut problem. This framework relies on a classical algorithm that approximately solves a certain variant of Max-Cut, and we derive an approximation guarantee theoretically, assuming the approximation ratio of the classical algorithm and QAOA. Furthermore we design a heuristic approach that fits in our framework and perform sufficient numerical experiments, where we solve Max-Cut on various $24$-vertex Erdős-Rényi graphs. Our framework only consumes $18$ qubits and achieves $0.9950$ approximation ratio on average, which outperforms the previous methods showing $0.9778$ (quantum algorithm using the same number of qubits) and $0.9643$ (classical algorithm). The experimental results indicate our well-designed quantum-classical coupling framework gives satisfactory approximation ratio while reduces the qubit cost, which sheds light on more potential computing power of NISQ devices.

arXiv:2307.15260•Jul 28, 2023•10 citations

Real-Time Combinatorial Optimization with QuantumEdge: A Scalable Extension of QAOA

Pradeep Kumar Muthukamatchi, Manoj Varthan Velumani, M Kasiselvanathan +4 more

The solution of large-scale combinatorial optimization problems, which are exorbitantly complex and resource-consuming, is one of the most significant challenges that computing systems face. Traditional algorithms often provide suboptimal results when confronted with bigger issues. This research aims to bring attention to these problems by introducing the Extending Quantum Approximate Optimization Algorithm (EQAOA) framework, which improves scalability, parameter optimization, and error resilience. Fundamental to the EQAOA methodology is repeatedly optimizing solution states via adaptive-depth, parameter-tuned quantum circuits. EQAOA also employs the method of converting combinatorial problems into cost Hamiltonians. Similar problems are shown in the Max-Cut and Graph Coloring programs. The experiments were conducted on several benchmark circumstances using real NISQ hardware and quantum simulators. The enhanced EQAOA outperforms baseline versions in terms of convergence time and solution quality. The efficient integration of dynamic circuit depth with hybrid classical-quantum parameter approaches applied to increasingly complicated problem scenarios and yielded good results. According to the study's findings, applying the proposed QAOA extension to practical combinatorial contexts yields a quantum advantage. The future of this field is bright, with researchers aiming to improve its interaction with traditional optimizers and extend its usage to other practical optimization areas.

International Conference on Cyber Resilience (ICCR)•Jul 3, 2025•0 citations

A SWAP-free Framework for QAOA

Thiago Assis, Pedro Baptista, Laila Lopes +2 more

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.

quant-pharXiv:2604.25058•Apr 29, 2026•0 citations

Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem

Gavin E. Crooks

The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.

arXiv:1811.08419•Bulletin of the American Physical Society•Nov 20, 2018•340 citations

Hierarchical Improvement of Quantum Approximate Optimization Algorithm for Object Detection: (Invited Paper)

Junde Li, Mahabubul Alam, Abdullah Ash Saki +1 more

Quantum Approximate Optimization Algorithm (QAOA) provides approximate solution to combinatorial optimization problems. It encodes the cost function using a$p$-level quantum circuit where each level consists a problem Hamiltonian followed by a mixing Hamiltonian. Despite the promises, few real-world applications (besides the pedagogical MaxCut problem) have exploited QAOA. The success of QAOA relies on the classical optimizer, variational parameter setting, and quantum circuit design and compilation. In this study, we implement QAOA and analyze its performance for a broader Quadratic Unconstrained Binary Optimization (QUBO) formulation to solve real-word applications such as, partially occluded object detection problem. Furthermore, we analyze the effects of above influential factors on QAOA performance. We propose a 3-level improvement of hybrid quantum-classical optimization for object detection. We achieve more than 13X execution speedup by choosing L-BFGS-B as classical optimizer at the first level and 5.50X additional speedup by exploiting parameter symmetry and more than 1.23X acceleration using parameter regression at the second level. We empirically show that the circuit will achieve better fidelity by optimally rescheduling gate operations (especially for deeper circuits) at the third level.

International Symposium on Quality Electronic Design (ISQED)•Mar 1, 2020•10 citations
Current state-of-the-art quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent cost Hamiltonian suitable for the quantum device. Implementing each term of the cost Hamiltonian separately often results in high redundancy, significantly increasing the resources required. Instead, we propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits, eliminating the reliance on the binary optimization problem representation. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Program-based QAOA (Prog-QAOA). We exploit this idea for optimization tasks like the Travelling Salesman Problem and Max- K -Cut and obtain circuits that are near-optimal with respect to all relevant cost measures, e.g., number of qubits, gates, and circuit depth. While we demonstrate the power of Prog-QAOA only for a particular set of paradigmatic problems, our approach is conveniently applicable to generic optimization problems.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.
Maximum cut (Max-Cut) problem is one of the most important combinatorial optimization problems because of its various applications in real life, and recently Quantum Approximate Optimization Algorithm (QAOA) has been widely employed to solve it. However, as the size of the problem increases, the number of qubits required will become larger. With the aim of saving qubits, we propose a coupling framework for designing QAOA circuits to solve larger-scale Max-Cut problem. This framework relies on a classical algorithm that approximately solves a certain variant of Max-Cut, and we derive an approximation guarantee theoretically, assuming the approximation ratio of the classical algorithm and QAOA. Furthermore we design a heuristic approach that fits in our framework and perform sufficient numerical experiments, where we solve Max-Cut on various 242424-vertex Erdős-Rényi graphs. Our framework only consumes 181818 qubits and achieves 0.99500.99500.9950 approximation ratio on average, which outperforms the previous methods showing 0.97780.97780.9778 (quantum algorithm using the same number of qubits) and 0.96430.96430.9643 (classical algorithm). The experimental results indicate our well-designed quantum-classical coupling framework gives satisfactory approximation ratio while reduces the qubit cost, which sheds light on more potential computing power of NISQ devices.
The solution of large-scale combinatorial optimization problems, which are exorbitantly complex and resource-consuming, is one of the most significant challenges that computing systems face. Traditional algorithms often provide suboptimal results when confronted with bigger issues. This research aims to bring attention to these problems by introducing the Extending Quantum Approximate Optimization Algorithm (EQAOA) framework, which improves scalability, parameter optimization, and error resilience. Fundamental to the EQAOA methodology is repeatedly optimizing solution states via adaptive-depth, parameter-tuned quantum circuits. EQAOA also employs the method of converting combinatorial problems into cost Hamiltonians. Similar problems are shown in the Max-Cut and Graph Coloring programs. The experiments were conducted on several benchmark circumstances using real NISQ hardware and quantum simulators. The enhanced EQAOA outperforms baseline versions in terms of convergence time and solution quality. The efficient integration of dynamic circuit depth with hybrid classical-quantum parameter approaches applied to increasingly complicated problem scenarios and yielded good results. According to the study's findings, applying the proposed QAOA extension to practical combinatorial contexts yields a quantum advantage. The future of this field is bright, with researchers aiming to improve its interaction with traditional optimizers and extend its usage to other practical optimization areas.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.
Quantum Approximate Optimization Algorithm (QAOA) provides approximate solution to combinatorial optimization problems. It encodes the cost function using appp-level quantum circuit where each level consists a problem Hamiltonian followed by a mixing Hamiltonian. Despite the promises, few real-world applications (besides the pedagogical MaxCut problem) have exploited QAOA. The success of QAOA relies on the classical optimizer, variational parameter setting, and quantum circuit design and compilation. In this study, we implement QAOA and analyze its performance for a broader Quadratic Unconstrained Binary Optimization (QUBO) formulation to solve real-word applications such as, partially occluded object detection problem. Furthermore, we analyze the effects of above influential factors on QAOA performance. We propose a 3-level improvement of hybrid quantum-classical optimization for object detection. We achieve more than 13X execution speedup by choosing L-BFGS-B as classical optimizer at the first level and 5.50X additional speedup by exploiting parameter symmetry and more than 1.23X acceleration using parameter regression at the second level. We empirically show that the circuit will achieve better fidelity by optimally rescheduling gate operations (especially for deeper circuits) at the third level.