PaperlayerView exact revision on arXiv

Source-linked AI summary

Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem

Vicky Choi

arXiv:0804.4884v1quant-ph

TL;DR

The paper addresses how NP-hard QUBO instances can be implemented on Ising-based adiabatic quantum hardware when the problem graph is minor-embedded. It separates embedding from parameter setting, derives embedded parameters supporting solution correspondence, and discusses remaining efficiency questions.

  • Problem

    Mapping a graph-structured Ising/QUBO problem onto hardware requires both a minor-embedding and correctly chosen embedded biases and coupler strengths.

  • Method

    Assuming a minor-embedding is given, the paper derives qubit biases and ferromagnetic coupler-strength conditions for the embedded Ising Hamiltonian.

  • Results

    The derived parameters establish a one-one correspondence between the ground states of the original and embedded Ising Hamiltonians, with MIS used as an example.

  • Takeaways & Limitations

    Minor-embedding can reduce QUBO/Ising optimization to the hardware graph while preserving the solution under suitable parameter settings.

  • Takeaways & Limitations

    The paper does not address adiabatic runtime because runtime depends on the full system Hamiltonian’s minimum spectral gap, whose estimation is generally hard.

Abstract

from arXiv · show

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 $G^{emb}$ of a graph $G$ in $U$, which is a subgraph of $U$ such that $G$ can be obtained from $G^{emb}$ 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.

1 Introduction

The introduction frames AQC as an optimization model based on evolving Hamiltonians and explains how QUBO/Ising problems can be reduced to hardware through minor-embedding. The paper focuses on setting embedded parameters, while noting unresolved efficiency and runtime questions.

  • AQC background: AQC evolves a system Hamiltonian slowly from Hinit to Hfinal so the final state is predominantly the ground state of Hfinal.The required runtime is determined by the minimum spectral gap.
  • AQC background: Ising minimization is equivalent to QUBO optimization, allowing graph-structured QUBO problems to be addressed with Ising spin-1/2 hardware.The hardware implements a restricted class of transverse-field Ising Hamiltonians.
  • Embedding: Minor-embedding maps logical graph vertices to connected physical-qubit subtrees, with the original graph recovered by contracting embedding edges.The hardware graph has degree constraints, so direct subgraph-embedding may not support arbitrary problem graphs.
  • Reduction scope: The required ferromagnetic coupler strength is a central parameter-setting issue because overly strong couplers may slow AQC and analog hardware permits only limited precision.Earlier work did not specify how strong the couplers must be.
  • Reduction scope: The reduction has two components: finding a minor-embedding and setting the embedded Hamiltonian’s qubit biases and coupler strengths.This paper assumes the embedding is given and studies parameter setting for the final Hamiltonian.
  • Open issues: The paper distinguishes reduction correctness from runtime efficiency, since runtime depends on the minimum spectral gap of the full system Hamiltonian.The paper does not analyze runtime because it focuses only on the final Hamiltonian and spectral-gap estimation is generally hard.

2 Equivalences Between QUBO and the Ising Problem

This section establishes the variable transformation linking QUBO maximization to Ising minimization. It gives the parameter correspondence needed to translate between the two formulations.

  • Variable transformation: The transformation xi = (si + 1)/2 maps Ising spins si ∈ {−1, +1} to binary variables xi ∈ {0, 1}.Thus, xi = 1 corresponds to si = 1, while xi = 0 corresponds to si = −1.
  • Parameter correspondence: Using the variable change, QUBO maximization becomes equivalent to Ising energy minimization on the same graph.The neighborhood nbr(i) collects vertices adjacent to i in G.
  • Parameter correspondence: The parameter mapping is hi = Σj∈nbr(i) Jij − 2ci, equivalently ci = 1/2(Σj∈nbr(i) Jij − hi).This relation connects QUBO coefficients ci with Ising biases hi and couplings Jij.

3 Minor-Embedding

Minor-embedding represents each vertex of G by a connected subtree of the fixed hardware graph U and realizes logical edges through hardware connections. The paper distinguishes subgraph and topological-minor embeddings, while noting that general embedding algorithms are not efficient when G is part of the input.

  • A minor-embedding maps every vertex of G to a connected subtree of U and realizes each logical edge through corresponding hardware edges.
  • Equivalently, G is a minor of U when it can be obtained from a subgraph of U by contracting edges.
  • Subgraph-embedding is the special case where every subtree contains one hardware vertex, making G isomorphic to its embedded subgraph.
  • Topological-minor-embedding is the special case where every subtree is a chain or path of hardware vertices.
  • For fixed G, minor-embedding algorithms run in polynomial time in |V(U)| but have running times exponential in the size of G.The paper also identifies prior randomized polynomial-time work for embeddings in degree-bounded expanders.

4 Parameter Requirement for the Embedded Ising Hamiltonian

The section derives ferromagnetic coupler-strength requirements that make an embedded Ising problem equivalent to the original problem. It first gives an easy bound, then a tighter bias-dependent bound that preserves ground-state correspondence and controls the embedded spectral gap.

  • Parameter-setting objective: The parameter-setting goal is a one-to-one correspondence between minima of the original energy and embedded energy.The embedded formulation must recover the original Ising optimum, and thus the QUBO optimum.
  • Embedding construction: Physical qubits in each tree Ti are coupled ferromagnetically so the tree acts as one logical qubit.Consistency requires all physical spins representing logical qubit i to have the same sign.
  • 4.1 An Easy Upper Bound for the Ferromagnetic Coupler Strengths: The easy-bound analysis uses a penalty or multiplier method to enforce the equality constraints within embedding trees.The constrained minimization is converted into unconstrained minimization by adding sufficiently strong ferromagnetic penalties.
  • 4.1 An Easy Upper Bound for the Ferromagnetic Coupler Strengths: Theorem 4.1 establishes sufficient ferromagnetic strengths for the unconstrained embedded problem to recover the constrained optimum.Its proof argues that any inconsistent physical-spin assignment can be improved, contradicting optimality.
  • 4.2 A Tighter Bound for the Ferromagnetic Coupler Strengths: The tighter analysis reduces the required coupling magnitude by choosing the physical-qubit biases appropriately.The construction redistributes each logical bias across its tree and analyzes energy changes from flipping leaves or segments.
  • 4.2 A Tighter Bound for the Ferromagnetic Coupler Strengths: Theorem 4.2 guarantees one-to-one correspondence between embedded and original optima when its coupling condition holds.It also states that choosing couplings with slack gi makes the embedded spectral gap the minimum of the original gap and mini∈V(G) gi.
  • 4.2 A Tighter Bound for the Ferromagnetic Coupler Strengths: The tighter bound remains open to improvement because the paper asks whether a better bound can be obtained without solving the original problem.The parameterization also permits flexibility useful when hardware parameter precision is limited.

5 Weighted Maximum Independent Set (WMIS) Problem

The paper formulates weighted maximum independent set (WMIS) as a QUBO problem and derives conditions ensuring its maximizer is an independent set. It then specializes the embedded Ising parameters to unweighted MIS and notes the importance of strictly stronger couplers.

  • 5.1 Formulate WMIS Problem As a Special Case of QUBO: WMIS is formulated as a QUBO, whose optimizer defines the selected vertex set.
  • 5.1 Formulate WMIS Problem As a Special Case of QUBO: WMIS maximizes the total weight of an independent vertex set in a vertex-weighted graph.
  • 5.1 Formulate WMIS Problem As a Special Case of QUBO: If Jij ≥ min{ci, cj} on every edge, the QUBO maximum equals the total WMIS weight.
  • 5.1 Formulate WMIS Problem As a Special Case of QUBO: If Jij > min{ci, cj} on every edge, the maximizing selected vertices form an independent set.
  • 5.2 Embedded Ising Hamiltonian for Solving MIS: For unweighted MIS, choosing Jij = 1 + ǫ for every edge suffices, whereas Jij = 1 guarantees size but not necessarily independence.
  • 5.2 Embedded Ising Hamiltonian for Solving MIS: For unweighted MIS embeddings, the parameter condition becomes Fi < −1; with degree-3 hardware, J = 1 + ǫ and F = −(1 + ǫ) yield six parameter values.

6 Discussion

The paper frames minor-embedding in AQC as a reduction with embedding and parameter-setting components, then identifies unresolved algorithmic problems affecting reduction efficiency and AQC complexity.

  • 6 Discussion: Minor-embedding reduces NP-hard QUBO problems to Ising spin-1/2 Hamiltonians implemented by an adiabatic quantum computer.The reduction has two components: finding an embedding and setting the corresponding Hamiltonian parameters.
  • 6 Discussion: Given a minor-embedding, the paper derives embedded parameters, including an upper bound on the ferromagnetic coupler strength.
  • 6 Discussion: The efficiency of the reduction remains linked to adiabatic-algorithm complexity through the minimum spectral gap, which may be as hard to determine as solving the original problem.
  • 6 Discussion: Open problems include measuring embedding quality and designing an embedding-dependent initial Hamiltonian that preserves the original algorithm’s efficiency.
  • 6 Discussion: Hardware-graph design seeks compact F-minor-universal graphs that satisfy physical constraints, embed every graph in F, and support efficiently computable good embeddings.

A Energy Function of the Ising Hamiltonian

This section connects the Ising Hamiltonian’s operator form to a classical spin energy function by evaluating σz eigenvalues on computational-basis states and replacing them with spin variables.

  • A Energy Function of the Ising Hamiltonian: The Ising Hamiltonian energy function is obtained by replacing each σz_i operator with a binary spin variable s_i ∈ {−1, +1}.
  • A Energy Function of the Ising Hamiltonian: The mapping uses σz|0⟩ = (+1)|0⟩ and σz|1⟩ = (−1)|1⟩, with computational-basis states represented explicitly.
  • A Energy Function of the Ising Hamiltonian: The tensor-product property extends the single-qubit eigenvalue relation to basis states |z⟩ = |z1⟩ ⊗ ··· ⊗ |zn⟩.
  • A Energy Function of the Ising Hamiltonian: For basis labels zi ∈ {0, 1}, replacing (−1)^zi with si ∈ {+1, −1} yields the classical energy expression for Hfinal.
  • A Energy Function of the Ising Hamiltonian: Figure 4 presents corresponding parameters for the embedded Ising model under positive and general coupler-sign cases.
  • A Energy Function of the Ising Hamiltonian: Figure 5 gives energy-change bounds for flipping a leaf spin or segment under positive and mixed-sign couplers and either bias sign.
Loading 0804.4884v1…