NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization
arXiv:2305.14197 · doi:10.22331/q-2023-11-21-1186
Abstract
Quantum algorithms are getting extremely popular due to their potential to significantly outperform classical algorithms. Yet, applying quantum algorithms to optimization problems meets challenges related to the efficiency of quantum algorithms training, the shape of their cost landscape, the accuracy of their output, and their ability to scale to large-size problems. Here, we present an approximate gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding. We show how simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms. We employ numerical simulations to test it on MaxCut problems with complete weighted graphs with thousands of nodes and run the algorithm on a superconducting quantum processor. We find that for unconstrained MaxCut problems with more than 1000 nodes, the hybrid approach combining our algorithm with a classical solver called CPLEX can find a better solution than CPLEX alone. This demonstrates that hybrid optimization is one of the leading use cases for modern quantum devices.
arXiv commentAccepted for publication in Quantum
References in corpus (33)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Variational Quantum Algorithms
- The theory of variational hybrid quantum-classical algorithms
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- Strong quantum computational advantage using a superconducting quantum processor
- Evaluating analytic gradients on quantum hardware
- Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms
- Theory of Quantum Annealing of an Ising Spin Glass
- Connecting ansatz expressibility to gradient magnitudes and barren plateaus
- Hybrid quantum-classical algorithms and quantum error mitigation
- Simulating quantum computation by contracting tensor networks
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Trading classical and quantum computational resources
- Differentiable Learning of Quantum Circuit Born Machine
- Hybrid Quantum-Classical Approach to Quantum Optimal Control
- Warm-starting quantum optimization
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
- Training of Quantum Circuits on a Hybrid Quantum Computer
- Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
- Hyper-optimized tensor network contraction
- Hardware-efficient variational quantum algorithms for time evolution
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Average fidelity between random quantum states
- Sequential Generation of Matrix-Product States in Cavity QED
- Benchmarking the Quantum Approximate Optimization Algorithm
- Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
- Expressibility of the alternating layered ansatz for quantum computation
- Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
- Benchmarking simulated and physical quantum processing units using quantum and hybrid algorithms
- Riemannian geometry and automatic differentiation for optimization problems of quantum physics and quantum technologies
- Qubit-efficient encoding schemes for binary optimisation problems
- Hybrid Quantum-Classical Unit Commitment