Recognition: unknown
A practical heuristic for finding graph minors
read the original abstract
We present a heuristic algorithm for finding a graph $H$ as a minor of a graph $G$ that is practical for sparse $G$ and $H$ with hundreds of vertices. We also explain the practical importance of finding graph minors in mapping quadratic pseudo-boolean optimization problems onto an adiabatic quantum annealer.
This paper has not been read by Pith yet.
Forward citations
Cited by 7 Pith papers
-
Ember: An Extensible Benchmark Suite for Quantum Annealing Embedding Algorithms
Ember introduces a reproducible benchmark suite with 24,016 graph instances for evaluating quantum annealing embedding algorithms across Chimera, Pegasus, and Zephyr topologies.
-
Ember: An Extensible Benchmark Suite for Quantum Annealing Embedding Algorithms
Ember provides the first standardized, reproducible benchmark framework with 24,016 diverse graph instances for quantum annealing embedding algorithms, showing that no single algorithm performs best across all graph families.
-
New minor minimal non-apex graphs
All minimal non-apex graphs with 12 or fewer vertices or 26 or fewer edges are listed, and every 13-vertex graph with minimum degree 6 is shown to be apex or to contain a K6 minor.
-
Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems
Neural networks transform initial embeddings into feasible unit disk configurations for QUBO problems on Rydberg qubits and outperform the Gurobi solver in experiments.
-
Neural and Tensor Networks in the Study of Quantum Annealing Processors
The thesis introduces a topology-aware tensor-network heuristic called SpinGlassPEPS.jl and thermodynamic metrics to benchmark quantum annealers on Ising problems while accounting for dissipation and effective temperature.
-
Playing Dice with the Universe: Programming Quantum Computers to Play Traditional Games
A quantum annealer can play tic-tac-toe by encoding only the game rules and sampling from paths leading to wins or losses.
-
Entangled happily ever after: Wedding reception seating mapped to classical and quantum optimizers
Wedding reception seating was encoded as a cost function network and solved more reliably by classical Monte Carlo than by quantum annealing on D-Wave hardware using mappings previously developed for protein design.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.