Minor-embedding in adiabatic quantum computation: I. The parameter setting problem

By Vicky Siu-Ngan Choi. Quantum Information Processing, 2008

424 citations recorded by the source corpus.

We show that the NP-hard quadratic unconstrained binary optimization (QUBO) problem on a graph G can be solved using an adiabatic quantum computer that implements an Ising spin-1/2 Hamiltonian, by reduction through minor-embedding of G in the quantum hardware graph U. There are two components to this reduction: embedding and parameter setting. The embedding problem is to find a minor-embedding Gemb of a graph G in U, which is a subgraph of U such that G can be obtained from Gemb 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/79960db5d258fb4a291169d743b0acbf1a7f8d81

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Quantum Optimization of Fully-Connected Spin Glasses (2014, background): “It is immediately apparent that from the dynamical perspective that the optimal prescription on the value of JF might be tricky to evaluate despite the fact that it is always possible to set its magnitude to be sufficiently high to make sure that the target ground state still lies at the bottom of t”
Quantum annealing for industry applications: introduction and review (2021, neutral): “For QA, this involves encoding variables as chains of multiple physical qubits on a QPU such that they act as a single logical qubit [34, 35].”
Experimental investigation of performance differences between coherent Ising machines and a quantum annealer (2018, methodology): “This requirement adds an upfront computational cost [20, 22, 23] of finding the embedding (unless previously known) and, of most relevance in this study, in general results in the use of multiple physical pseudo-spins to encode each logical spin variable, which can lead to a degradation of time-to-s”
A practical heuristic for finding graph minors (2014, background): “Graph minors are an extremely important theoretical topic due to the work of Robertson and Seymour [18], which implies that when H is fixed, there is a polynomial-time algorithm for determining whether or not G contains H as a minor.”
Architectural Considerations in the Design of a Superconducting Quantum Annealing Processor (2014, background): “graph theory, we want the hardware graph to have largest possible variety of problem graphs as its minors [15].”
Ising formulations of many NP problems (2013, background): “The primary problem with Hamiltonians on a complete graph is that it is inefficient [43, 44] to embed complete graphs onto the chimera graph.”
Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design (2010, methodology): “In [6], we solved the parameter setting problem.”
Evidence for quantum annealing with more than one hundred qubits (2013, methodology): “[33] Choi, V.”