Minor embedding in broken chimera and derived graphs is NP-complete

DOI10.1016/j.tcs.2023.114369arXiv2110.08325OpenAlexW4390350981MaRDI QIDQ6201320

Annette Lutz, Elisabeth Lobe

Publication date: 20 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

quantum annealingHamiltonian cycle problemgraph minor embeddingChimera graphPegasus graphZephyr graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
• Faster parameterized algorithms for minor containment
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Optimizing adiabatic quantum program compilation using a graph-theoretic framework
• Fast minor testing in planar graphs
• Graph minors. XIII: The disjoint paths problem
• A case study in programming a quantum annealer for hard operational planning problems
• Adiabatic quantum programming: minor embedding with hard faults
• Embedding of complete graphs in broken Chimera graphs
• Graph Theory
• Branch decompositions and minor containment
• Hamilton Paths in Grid Graphs
• Quantum Annealing versus Digital Computing
• Combinatorial optimization. Theory and algorithms

This page was built for publication: Minor embedding in broken chimera and derived graphs is NP-complete