Training A Quantum Optimizer
arXiv:1605.05370 · doi:10.1103/PhysRevA.94.022309
Abstract
We study a variant of the quantum approximate optimization algorithm [ E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028] with slightly different parametrization and different objective: rather than looking for a state which approximately solves an optimization problem, our goal is to find a quantum algorithm that, given an instance of MAX-2-SAT, will produce a state with high overlap with the optimal state. Using a machine learning approach, we chose a "training set" of instances and optimized the parameters to produce large overlap for the training set. We then tested these optimized parameters on a larger instance set. As a training set, we used a subset of the hard instances studied by E. Crosson, E. Farhi, C. Yen-Yu Lin, H.-H. Lin, and P. Shor (CFLLS) [arXiv:1401.7320]. When tested on the full set, the parameters that we find produce significantly larger overlap than the optimized annealing times of CFLLS. Testing on other random instances from to bits continues to show improvement over annealing, with the improvement being most notable on the hardest instances. Further tests on instances of MAX-3-SAT also showed improvement on the hardest instances. This algorithm may be a possible application for near-term quantum computers with limited coherence times.
10 pages, 5 figures
References in corpus (4)
Cited by in corpus (46)
- Variational Quantum Algorithms
- Machine learning and the physical sciences
- Barren plateaus in quantum neural network training landscapes
- Noisy intermediate-scale quantum (NISQ) algorithms
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- Compiling quantum circuits to realistic hardware architectures using temporal planners
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Intel Quantum Simulator: A cloud-ready high-performance simulator of quantum circuits
- Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
- Multistart Methods for Quantum Approximate Optimization
- NISQ Computers: A Path to Quantum Supremacy
- Two-step approach to scheduling quantum circuits
- qTorch: The Quantum Tensor Contraction Handler
- Optimal control of superconducting gmon qubits using Pontryagin's minimum principle: preparing a maximally entangled state with singular bang-bang protocols
- The Power of Adiabatic Quantum Computation with No Sign Problem
- An entanglement perspective on the quantum approximate optimization algorithm
- Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
- Analytical Framework for Quantum Alternating Operator Ansätze
- Probing Geometric Excitations of Fractional Quantum Hall States on Quantum Computers
- Application of Pontryagin's Minimum Principle to Grover's Quantum Search Problem
- On Circuit Depth Scaling For Quantum Approximate Optimization
- Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
- Variational quantum Gibbs state preparation with a truncated Taylor series
- A double-slit proposal for quantum annealing
- Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
- Minimal Constraints in the Parity Formulation of Optimization Problems
- Customized quantum annealing schedules
- Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
- From Ansätze to Z-gates: a NASA View of Quantum Computing
- Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
- Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
- Tensor network method for reversible classical computation
- Optimally Stopped Variational Quantum Algorithms
- Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
- The Short Path Algorithm Applied to a Toy Model
- Statistical evaluation and optimization of entanglement purification protocols
- Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem
- EQNN: Enhanced Quantum Neural Network
- Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers
- Topological and geometric patterns in optimal bang-bang protocols for variational quantum algorithms: application to the model on the square lattice