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

DOI10.1007/S11128-008-0082-9zbMATH Open1160.81326arXiv0804.4884OpenAlexW2129874988MaRDI QIDQ1007120FDOQ1007120

Vicky Choi

Publication date: 27 March 2009

Published in: Quantum Information Processing (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0804.4884

zbMATH Keywords

Graph minorAdiabatic quantum computationIsing HamiltonianQuadratic unconstrained binary optimization

Mathematics Subject Classification ID

Quantum computation (81P68) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Applications of graph theory to circuits and networks (94C15)

Cites Work

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Graph minors. XIII: The disjoint paths problem
• Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
• Title not available (Why is that?)
• Approximation algorithms for NP-complete problems on planar graphs
• Title not available (Why is that?)
• Pseudo-Boolean optimization
• The quantum adiabatic optimization algorithm and local minima
• Title not available (Why is that?)
• The Complexity of the Local Hamiltonian Problem
• LIMITATIONS OF SOME SIMPLE ADIABATIC QUANTUM ALGORITHMS
• Title not available (Why is that?)

Cited In (38)

• Deep learning optimal quantum annealing schedules for random Ising models
• Hard combinatorial problems and minor embeddings on lattice graphs
• Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
• Fast clique minor generation in Chimera qubit connectivity graphs
• Solving larger maximum clique problems using parallel quantum annealing
• Treating the independent set problem by 2D Ising interactions with adiabatic quantum computing
• The effects of the problem Hamiltonian parameters on the minimum spectral gap in adiabatic quantum optimization
• Optimizing adiabatic quantum program compilation using a graph-theoretic framework
• QUBO formulation for the contact map overlap problem
• Embedding equality constraints of optimization problems into a quantum annealer
• Support vector machines on the D-wave quantum annealer
• Template-Based Minor Embedding for Adiabatic Quantum Optimization
• Quantum Annealing versus Digital Computing
• Quantum adiabatic machine learning
• A comparison of approaches for finding minimum identifying codes on graphs
• Inter-generational comparison of quantum annealers in solving hard scheduling problems
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
• A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
• Garden optimization problems for benchmarking quantum annealers
• Modeling the Costas array problem in QUBO for quantum annealing
• Comparing QUBO models for quantum annealing: integer encodings for permutation problems
• Performing fully parallel constraint logic programming on a quantum annealer
• Graph minors from simulated annealing for annealing machines with sparse connectivity
• Optimal sufficient requirements on the embedded Ising problem in polynomial time
• Adiabatic quantum programming: minor embedding with hard faults
• Differential geometric treewidth estimation in adiabatic quantum computation
• Minor embedding in broken chimera and derived graphs is NP-complete
• Boosting quantum annealer performance via sample persistence
• Efficiently embedding QUBO problems on adiabatic quantum computers
• Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
• A case study in programming a quantum annealer for hard operational planning problems
• Minimizing minor embedding energy: an application in quantum annealing
• Enhancing quantum annealing performance for the molecular similarity problem
• Quadratic unconstrained binary optimization problem preprocessing: theory and empirical analysis
• Building an iterative heuristic solver for a quantum annealer
• Simulated versus reduced noise quantum annealing in maximum independent set solution to wireless network scheduling
• High-dimensional graphs convolution for quantum walks photonic applications
• Constructing SAT Filters with a Quantum Annealer

   Recommendations

• Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design 👍 👎
• Hard combinatorial problems and minor embeddings on lattice graphs 👍 👎
• Treating the independent set problem by 2D Ising interactions with adiabatic quantum computing 👍 👎
• Efficiently embedding QUBO problems on adiabatic quantum computers 👍 👎
• Graph minors from simulated annealing for annealing machines with sparse connectivity 👍 👎

This page was built for publication: Minor-embedding in adiabatic quantum computation. I: The parameter setting problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007120)