Quantum Annealing for Constrained Optimization

Abstract

Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealers that promise to solve certain combinatorial optimization problems of practical relevance faster than their classical analogues. The applicability of such devices for many theoretical and real-world optimization problems, which are often constrained, is severely limited by the sparse, rigid layout of the devices' quantum bits. Traditionally, constraints are addressed by the addition of penalty terms to the Hamiltonian of the problem, which in turn requires prohibitively increasing physical resources while also restricting the dynamical range of the interactions. Here, we propose a method for encoding constrained optimization problems on quantum annealers that eliminates the need for penalty terms and thereby reduces the number of required couplers and removes the need for minor embedding, greatly reducing the number of required physical qubits. We argue the advantages of the proposed technique and illustrate its effectiveness. We conclude by discussing the experimental feasibility of the suggested method as well as its potential to appreciably reduce the resource requirements for implementing optimization problems on quantum annealers, and its significance in the field of quantum computing.

7 pages, 3 figures

References in corpus (7)

• Bounds for the adiabatic approximation with applications to quantum computation
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Quantum Annealing Correction with Minor Embedding
• Experimental quantum annealing: case study involving the graph isomorphism problem
• Tunneling spectroscopy using a probe qubit

Cited by in corpus (38)

• Noisy intermediate-scale quantum (NISQ) algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Domain wall encoding of discrete variables for quantum annealing and QAOA
• Driver Hamiltonians for constrained optimization in quantum annealing
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Constrained mixers for the quantum approximate optimization algorithm
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Constrained quantum annealing of graph coloring
• Analytical Framework for Quantum Alternating Operator Ansätze
• Using quantum annealing to design lattice proteins
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• A Quantum N-Queens Solver
• Towards Finding an Optimal Flight Gate Assignment on a Digital Quantum Computer
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Parity Quantum Optimization: Encoding Constraints
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval
• Superconducting qubit circuit emulation of a vector spin-1/2
• Deep learning optimal quantum annealing schedules for random Ising models
• Symmetry-Protected Quantum Adiabatic Evolution in Spontaneous Symmetry-Breaking Transitions
• Realizable Quantum Adiabatic Search
• A Hybrid Quantum-Classical Approach to the Electric Mobility Problem
• Finding Optimal Pathways in Chemical Reaction Networks Using Ising Machines
• Dynamical chaotic phases and constrained quantum dynamics
• Bounding first-order quantum phase transitions in adiabatic quantum computing
• Localization in the constrained quantum annealing of graph coloring
• Quantum optimization with linear Ising penalty functions for customer data science
• Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems
• Quantum Annealing based Power Grid Partitioning for Parallel Simulation
• Quantum annealing in the NISQ era: railway conflict management
• Quantum Annealing with chaotic driver Hamiltonians
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• A scalable 2-local architecture for quantum annealing of Ising models with arbitrary dimensions
• Limits of Short-Time Evolution of Local Hamiltonians
• Signatures of quantum chaos and complexity in the Ising model on random graphs
• Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
• Quantum approximate optimization of finite-state bosonic systems