Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1210.8395 · Quantum Information Processing

Adiabatic quantum programming: minor embedding with hard faults

Christine Klymko, Blair D. Sullivan, Travis S. Humble

Published Nov 19, 2013• 104 citations
arXivHTMLPDF
DOI
10.1007/s11128-013-0683-9

Related papers

Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design

Vicky Choi

arXiv:1001.3116•Quantum Information Processing•Oct 13, 2010•297 citations

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

Vicky Choi

arXiv:0804.4884•Quantum Information Processing•Sep 16, 2008•446 citations

Compiling Adiabatic Quantum Programs

Faisal Shah Khan, Nada Elsokkary, Travis S. Humble

We develop a non-cooperative game-theoretic model for the problem of graph minor-embedding to show that optimal compiling of adiabatic quantum programs in the sense of Nash equilibrium is possible.

arXiv:1808.06926•Aug 19, 2018•1 citation

Compiling Adiabatic Quantum Programs

Faisal Shah Khan, Nada Elsokkary, Travis S. Humble

We develop a non-cooperative game-theoretic model for the problem of graph minor-embedding to show that optimal compiling of adiabatic quantum programs in the sense of Nash equilibrium is possible.

IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2018•0 citations

Template-Based Minor Embedding for Adiabatic Quantum Optimization

Thiago Serra, Teng Huang, Arvind U. Raghunathan +1 more

Quantum annealing (QA) can be used to quickly obtain near-optimal solutions for quadratic unconstrained binary optimization (QUBO) problems. In QA hardware, each decision variable of a QUBO should be mapped to one or more adjacent qubits in such a way that pairs of variables defining a quadratic term in the objective function are mapped to some pair of adjacent qubits. However, qubits have limited connectivity in existing QA hardware. This has spurred work on preprocessing algorithms for embedding the graph representing problem variables with quadratic terms into the hardware graph representing qubits adjacencies, such as the Chimera graph in hardware produced by D-Wave Systems. In this paper, we use integer linear programming to search for an embedding of the problem graph into certain classes of minors of the Chimera graph, which we call template embeddings. One of these classes corresponds to complete bipartite graphs, for which we show the limitation of the existing approach based on minimum odd cycle transversals (OCTs). One of the formulations presented is exact and thus can be used to certify the absence of a minor embedding using that template. On an extensive test set consisting of random graphs from five different classes of varying size and sparsity, we can embed more graphs than a state-of-the-art OCT-based approach, our approach scales better with the hardware size, and the runtime is generally orders of magnitude smaller. Summary of Contribution: Our work combines classical and quantum computing for operations research by showing that integer linear programming can be successfully used as a preprocessing step for adiabatic quantum optimization. We use it to determine how a quadratic unconstrained binary optimization problem can be solved by a quantum annealer in which the qubits are coupled as in a Chimera graph, such as in the quantum annealers currently produced by D-Wave Systems. The paper also provides a timely introduction to adiabatic quantum computing and related work on minor embeddings.

arXiv:1910.02179•INFORMS journal on computing•Sep 21, 2021•16 citations

Fault Tolerant Adiabatic Quantum Computation

Daniel A. Lidar

•Jul 2, 2007•0 citations
Quantum annealing (QA) can be used to quickly obtain near-optimal solutions for quadratic unconstrained binary optimization (QUBO) problems. In QA hardware, each decision variable of a QUBO should be mapped to one or more adjacent qubits in such a way that pairs of variables defining a quadratic term in the objective function are mapped to some pair of adjacent qubits. However, qubits have limited connectivity in existing QA hardware. This has spurred work on preprocessing algorithms for embedding the graph representing problem variables with quadratic terms into the hardware graph representing qubits adjacencies, such as the Chimera graph in hardware produced by D-Wave Systems. In this paper, we use integer linear programming to search for an embedding of the problem graph into certain classes of minors of the Chimera graph, which we call template embeddings. One of these classes corresponds to complete bipartite graphs, for which we show the limitation of the existing approach based on minimum odd cycle transversals (OCTs). One of the formulations presented is exact and thus can be used to certify the absence of a minor embedding using that template. On an extensive test set consisting of random graphs from five different classes of varying size and sparsity, we can embed more graphs than a state-of-the-art OCT-based approach, our approach scales better with the hardware size, and the runtime is generally orders of magnitude smaller. Summary of Contribution: Our work combines classical and quantum computing for operations research by showing that integer linear programming can be successfully used as a preprocessing step for adiabatic quantum optimization. We use it to determine how a quadratic unconstrained binary optimization problem can be solved by a quantum annealer in which the qubits are coupled as in a Chimera graph, such as in the quantum annealers currently produced by D-Wave Systems. The paper also provides a timely introduction to adiabatic quantum computing and related work on minor embeddings.