Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
arXiv:1307.8041 · doi:10.1002/andp.201300120
Abstract
We develop a resource efficient method by which the ground-state of an arbitrary k-local, optimization Hamiltonian can be encoded as the ground-state of a (k-1)-local optimization Hamiltonian. This result is important because adiabatic quantum algorithms are often most easily formulated using many-body interactions but experimentally available interactions are generally 2-body. In this context, the efficiency of a reduction gadget is measured by the number of ancilla qubits required as well as the amount of control precision needed to implement the resulting Hamiltonian. First, we optimize methods of applying these gadgets to obtain 2-local Hamiltonians using the least possible number of ancilla qubits. Next, we show a novel reduction gadget which minimizes control precision and a heuristic which uses this gadget to compile 3-local problems with a significant reduction in control precision. Finally, we present numerics which indicate a substantial decrease in the resources required to implement randomly generated, 3-body optimization Hamiltonians when compared to other methods in the literature.
arXiv comment11 pages, 2 figures
References in corpus (8)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- On the construction of model Hamiltonians for adiabatic quantum computation and its application to finding low energy conformations of lattice protein models
- Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Perturbative Gadgets at Arbitrary Orders
- QMA-complete problems for stoquastic Hamiltonians and Markov matrices
- Solving the Graph Isomorphism Problem with a Quantum Annealer
Cited by in corpus (22)
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- A case study in programming a quantum annealer for hard operational planning problems
- Adiabatic Quantum Simulation of Quantum Chemistry
- Challenges and Opportunities in Quantum Optimization
- Exploiting locality in quantum computation for quantum chemistry
- A NASA Perspective on Quantum Computing: Opportunities and Challenges
- Bayesian Network Structure Learning Using Quantum Annealing
- Prime factorization using quantum annealing and computational algebraic geometry
- Polymer Physics by Quantum Computing
- Graph isomorphism and adiabatic quantum computing
- Readiness of Quantum Optimization Machines for Industrial Applications
- Hamiltonian gadgets with reduced resource requirements
- Construction of Energy Functions for Lattice Heteropolymer Models: A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization
- Open system quantum annealing in mean field models with exponential degeneracy
- Equation Planting: A Tool for Benchmarking Ising Machines
- Energy landscapes of combinatorial optimization in Ising machines
- Breakdown of the weak coupling limit in quantum annealing
- Ising Machines for Diophantine Problems in Physics
- Solving systems of Boolean multivariate equations with quantum annealing
- Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
- Effective non-local parity-dependent couplings in qubit chains
- Exploring Quantum Annealing for Coarse-Grained Protein Folding