Red-QAOA: Efficient Variational Optimization through Circuit Reduction
arXiv:2407.14490 · doi:10.1145/3620665.3640363
Abstract
The Quantum Approximate Optimization Algorithm (QAOA) addresses combinatorial optimization challenges by converting inputs to graphs. However, the optimal parameter searching process of QAOA is greatly affected by noise. Larger problems yield bigger graphs, requiring more qubits and making their outcomes highly noise-sensitive. This paper introduces Red-QAOA, leveraging energy landscape concentration via a simulated annealing-based graph reduction. Red-QAOA creates a smaller (distilled) graph with nearly identical parameters to the original graph. The distilled graph produces a smaller quantum circuit and thus reduces noise impact. At the end of the optimization, Red-QAOA employs the parameters from the distilled graph on the original graph and continues the parameter search on the original graph. Red-QAOA outperforms state-of-the-art Graph Neural Network (GNN)-based pooling techniques on 3200 real-world problems. Red-QAOA reduced node and edge counts by 28% and 37%, respectively, with a mean square error of only 2%.
References in corpus (26)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Variational Quantum Algorithms
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum Chemistry in the Age of Quantum Computing
- Trapped-Ion Quantum Computing: Progress and Challenges
- Fast Graph Representation Learning with PyTorch Geometric
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- High-dimensional Ising model selection using -regularized logistic regression
- Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- Warm-starting quantum optimization
- Tightening LP Relaxations for MAP using Message Passing
- Variational quantum simulation of general processes
- ADAPT: Mitigating Idling Errors in Qubits via Adaptive Dynamical Decoupling
- Empirical performance bounds for quantum approximate optimization
- Graph neural network initialisation of quantum approximate optimisation
- JigSaw: Boosting Fidelity of NISQ Programs via Measurement Subsetting
- QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
- HAMMER: boosting fidelity of noisy Quantum circuits by exploiting Hamming behavior of erroneous outcomes
- 2QAN: A quantum compiler for 2-local qubit Hamiltonian simulation algorithms
- Quality, Speed, and Scale: three key attributes to measure the performance of near-term quantum computers
- CAFQA: A classical simulation bootstrap for variational quantum algorithms
- Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry
- Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits
- FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot Nodes
- VarSaw: Application-tailored Measurement Error Mitigation for Variational Quantum Algorithms