Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
From MaRDI portal
(Redirected from Publication:544830)
Abstract: In [Choi08], we introduced the notion of minor-embedding in adiabatic quantum optimization. A minor-embedding of a graph G in a quantum hardware graph U is a subgraph of U such that G can be obtained from it by contracting edges. In this paper, we describe the intertwined adiabatic quantum architecture design problem, which is to construct a hardware graph U that satisfies all known physical constraints and, at the same time, permits an efficient minor-embedding algorithm. We illustrate an optimal complete-graph-minor hardware graph. Given a family F of graphs, a (host) graph U is called F-minor-universal if for each graph G in F, U contains a minor-embedding of G. The problem for designing a F-minor-universal hardware graph U_{sparse} in which F consists of a family of sparse graphs (e.g., bounded degree graphs) is open.
Recommendations
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Hard combinatorial problems and minor embeddings on lattice graphs
- Graph minors from simulated annealing for annealing machines with sparse connectivity
- Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
Cites work
- scientific article; zbMATH DE number 5764887 (Why is no real title available?)
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- A partial k-arboretum of graphs with bounded treewidth
- A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
- Colloquium: Quantum annealing and analog quantum computation
- Graph minors. XIII: The disjoint paths problem
- Pseudo-Boolean optimization
- Simulating Quantum Computation by Contracting Tensor Networks
Cited in
(28)- Fast clique minor generation in Chimera qubit connectivity graphs
- Hard combinatorial problems and minor embeddings on lattice graphs
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- An Updated Experimental Evaluation of Graph Bipartization Methods
- QUBO formulation for the contact map overlap problem
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Quantum pattern recognition with multi-neuron interactions
- Template-Based Minor Embedding for Adiabatic Quantum Optimization
- A comparison of approaches for finding minimum identifying codes on graphs
- 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
- Modeling the Costas array problem in QUBO for quantum annealing
- Intersecting longest cycles in Archimedean tilings
- Comparing QUBO models for quantum annealing: integer encodings for permutation problems
- Graph minors from simulated annealing for annealing machines with sparse connectivity
- Optimal sufficient requirements on the embedded Ising problem in polynomial time
- Differential geometric treewidth estimation in adiabatic quantum computation
- Adiabatic quantum programming: minor embedding with hard faults
- Boosting quantum annealer performance via sample persistence
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
- Efficiently embedding QUBO problems on adiabatic quantum computers
- Minor embedding in broken chimera and derived graphs is NP-complete
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- Minimizing minor embedding energy: an application in quantum annealing
- Enhancing quantum annealing performance for the molecular similarity problem
- Building an iterative heuristic solver for a quantum annealer
- Embedding of complete graphs in broken Chimera graphs
- Simulated versus reduced noise quantum annealing in maximum independent set solution to wireless network scheduling
This page was built for publication: Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q544830)
