Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem
arXiv:0804.4884
Abstract
We show that the NP-hard quadratic unconstrained binary optimization (QUBO) problem on a graph can be solved using an adiabatic quantum computer that implements an Ising spin-1/2 Hamiltonian, by reduction through minor-embedding of in the quantum hardware graph . There are two components to this reduction: embedding and parameter setting. The embedding problem is to find a minor-embedding of a graph in , which is a subgraph of such that can be obtained from by contracting edges. The parameter setting problem is to determine the corresponding parameters, qubit biases and coupler strengths, of the embedded Ising Hamiltonian. In this paper, we focus on the parameter setting problem. As an example, we demonstrate the embedded Ising Hamiltonian for solving the maximum independent set (MIS) problem via adiabatic quantum computation (AQC) using an Ising spin-1/2 system. We close by discussing several related algorithmic problems that need to be investigated in order to facilitate the design of adiabatic algorithms and AQC architectures.
arXiv comment17 pages, 5 figures, submitted
References in corpus (7)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Robustness of adiabatic quantum computation
- Thermally assisted adiabatic quantum computation
- Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
- Role of Single Qubit Decoherence Time in Adiabatic Quantum Computation
- Scalable Superconducting Architecture for Adiabatic Quantum Computation
- Limitations of some simple adiabatic quantum algorithms