Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
arXiv:2209.03386 · doi:10.22331/q-2025-03-20-1663
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--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.
References in corpus (36)
- Quantum Computing in the NISQ era and beyond
- Quantum Machine Learning
- A variational eigenvalue solver on a quantum processor
- Ising formulations of many NP problems
- A Quantum Approximate Optimization Algorithm
- Adiabatic Quantum Computing
- Noise-Induced Barren Plateaus in Variational Quantum Algorithms
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- The Bravyi-Kitaev transformation for quantum computation of electronic structure
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Theory of variational quantum simulation
- A Race Track Trapped-Ion Quantum Processor
- Synthesis and Optimization of Reversible Circuits - A Survey
- Error-mitigated digital quantum simulation
- Stochastic gradient descent for hybrid quantum-classical optimization
- -mixers: analytical and numerical results for QAOA
- Quantum arithmetic with the Quantum Fourier Transform
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Resource-efficient digital quantum simulation of -level systems for photonic, vibrational, and spin- Hamiltonians
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- Deterministic Preparation of Dicke States
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
- Generalized swap networks for near-term quantum computing
- Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
- Error mitigation for variational quantum algorithms through mid-circuit measurements
- Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
- Experimental quantum annealing: case study involving the graph isomorphism problem
- Linear-depth quantum circuits for multiqubit controlled gates
- Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
- Combinatorial optimisation via highly efficient quantum walks
- Performance analysis of multi-shot shadow estimation
- Modular Parity Quantum Approximate Optimization
- Knapsack Problem variants of QAOA for battery revenue optimisation
- Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
- Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization