Driver Hamiltonians for constrained optimization in quantum annealing
arXiv:1602.07942 · doi:10.1103/PhysRevA.93.062312
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.
arXiv comment9 pages, 3 figures
References in corpus (24)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Bounds for the adiabatic approximation with applications to quantum computation
- A case study in programming a quantum annealer for hard operational planning problems
- Quantum annealing of the Traveling Salesman Problem
- First order phase transition in the Quantum Adiabatic Algorithm
- 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
- Experimental determination of Ramsey numbers
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Quantum Annealing Correction with Minor Embedding
- Quantum Annealing for Constrained Optimization
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Ramsey numbers and adiabatic quantum computing
- Experimental quantum annealing: case study involving the graph isomorphism problem
- Graph isomorphism and adiabatic quantum computing
- Tunneling spectroscopy using a probe qubit
- Solving the Graph Isomorphism Problem with a Quantum Annealer
- XX model on the circle
- Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
- Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
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