Fast clique minor generation in Chimera qubit connectivity graphs
From MaRDI portal
Abstract: The current generation of D-Wave quantum annealing processor is designed to minimize the energy of an Ising spin configuration whose pairwise interactions lie on the edges of a {em Chimera} graph . In order to solve an Ising spin problem with arbitrary pairwise interaction structure, the corresponding graph must be minor-embedded into a Chimera graph. We define a combinatorial class of {em native clique minors} in Chimera graphs with vertex images of uniform, near minimal size, and provide a polynomial-time algorithm that finds a maximum native clique minor in a given induced subgraph of a Chimera graph. These minors allow improvement over recent work and have immediate practical applications in the field of quantum annealing.
Recommendations
- Graph minors from simulated annealing for annealing machines with sparse connectivity
- Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
Cites work
- Adiabatic quantum programming: minor embedding with hard faults
- Colloquium: Quantum annealing and analog quantum computation
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
- On points drawn from a circle
- Optimization using quantum mechanics: quantum annealing through adiabatic evolution
Cited in
(23)- Quantum solutions for densest \(k\)-subgraph problems
- Analysis of \(D\)-Wave topologies with classical graph metrics
- Hard combinatorial problems and minor embeddings on lattice graphs
- Theory versus practice in annealing-based quantum computing
- Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems
- Solving larger maximum clique problems using parallel quantum annealing
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- Embedding equality constraints of optimization problems into a quantum annealer
- Biclustering with a quantum annealer
- Template-Based Minor Embedding for Adiabatic Quantum Optimization
- Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
- Optimal sufficient requirements on the embedded Ising problem in polynomial time
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
- Efficiently embedding QUBO problems on adiabatic quantum computers
- Quantum annealing versus digital computing. An experimental comparison
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- Towards quantum computing based community detection
- 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
- Embedding of complete graphs in broken Chimera graphs
- Benchmarking the quantum approximate optimization algorithm
- Critical phenomena and Kibble–Zurek scaling in the long-range quantum Ising chain
This page was built for publication: Fast clique minor generation in Chimera qubit connectivity graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q265415)
