Recursive Quantum Relaxation for Combinatorial Optimization Problems
arXiv:2403.02045 · doi:10.22331/q-2025-01-15-1594
Abstract
Quantum optimization methods use a continuous degree-of-freedom of quantum states to heuristically solve combinatorial problems, such as the MAX-CUT problem, which can be attributed to various NP-hard combinatorial problems. This paper shows that some existing quantum optimization methods can be unified into a solver to find the binary solution which is most likely measured from the optimal quantum state. Combining this finding with the concept of quantum random access codes (QRACs) for encoding bits into quantum states on fewer qubits, we propose an efficient recursive quantum relaxation method called recursive quantum random access optimization (RQRAO) for MAX-CUT. Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner using a tensor network technique, show that RQRAO not only outperforms the Goemans-Williamson and recursive QAOA methods, but also is comparable to state-of-the-art classical solvers. The code is available at \url{https://github.com/ToyotaCRDL/rqrao}.
35 pages, 12 figures, 3 tables
References in corpus (28)
- A variational eigenvalue solver on a quantum processor
- The density-matrix renormalization group in the age of matrix product states
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- A Quantum Approximate Optimization Algorithm
- Predicting Many Properties of a Quantum System from Very Few Measurements
- Quantum random access memory
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Quantum Random Access Codes using Single -level Systems
- Hybrid quantum-classical algorithms for approximate graph coloring
- Entanglement assisted random access codes
- A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
- Quantum SDP-Solvers: Better upper and lower bounds
- (4,1)-Quantum Random Access Coding Does Not Exist
- Single-ancilla ground state preparation via Lindbladians
- Noisy intermediate-scale quantum algorithm for semidefinite programming
- Faster quantum and classical SDP approximations for quadratic binary optimization
- Improved Classical and Quantum Random Access Codes
- Quantum Random Access Codes for Boolean Functions
- Unbounded-error One-way Classical and Quantum Communication Complexity
- Variational Quantum Algorithms for Semidefinite Programming
- Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints
- Low-depth Clifford circuits approximately solve MaxCut
- The geometry of Bloch space in the context of quantum random access codes
- Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions
- A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM Framework