Driver Hamiltonians for constrained optimization in quantum annealing

Abstract

One of the current major challenges surrounding the use of quantum annealers for solving practical optimization problems is their inability to encode even moderately sized problems---the main reason for this being the rigid layout of their quantum bits as well as their sparse connectivity. In particular, the implementation of constraints has become a major bottleneck in the embedding of practical problems, because the latter is typically achieved by adding harmful penalty terms to the problem Hamiltonian --- a technique that often requires an `all-to-all' connectivity between the qubits. Recently, a novel technique designed to obviate the need for penalty terms was suggested; it is based on the construction of driver Hamiltonians that commute with the constraints of the problem, rendering the latter constants of motion. In this work we propose general guidelines for the construction of such driver Hamiltonians given an arbitrary set of constraints. We illustrate the broad applicability of our method by analyzing several diverse examples, namely, graph isomorphism, not-all-equal 3SAT, and the so-called Lechner, Hauke and Zoller constraints. We also discuss the significance of our approach in the context of current and future experimental quantum annealers.

9 pages, 3 figures

References in corpus (9)

• Bounds for the adiabatic approximation with applications to quantum computation
• Probing for quantum speedup in spin glass problems with planted solutions
• 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
• Quantum Annealing for Constrained Optimization
• Experimental quantum annealing: case study involving the graph isomorphism problem
• Tunneling spectroscopy using a probe qubit

Cited by in corpus (29)

• Noisy intermediate-scale quantum (NISQ) algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Domain wall encoding of discrete variables for quantum annealing and QAOA
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Constrained mixers for the quantum approximate optimization algorithm
• Constrained Optimization via Quantum Zeno Dynamics
• 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
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Modular Parity Quantum Approximate Optimization
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Multi-round QAOA and advanced mixers on a trapped-ion 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
• Symmetry-Protected Quantum Adiabatic Evolution in Spontaneous Symmetry-Breaking Transitions
• Quantum approximate algorithm for NP optimization problems with constraints
• Dynamical chaotic phases and constrained quantum dynamics
• Realizable Quantum Adiabatic Search
• A Hybrid Quantum-Classical Approach to the Electric Mobility Problem
• Localization in the constrained quantum annealing of graph coloring
• Quantum optimization with linear Ising penalty functions for customer data science
• Quantum Annealing with chaotic driver Hamiltonians
• Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms
• A scalable 2-local architecture for quantum annealing of Ising models with arbitrary dimensions
• Performance of Domain-Wall Encoding for Quantum Annealing
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Quantum approximate optimization of finite-state bosonic systems