Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
From MaRDI portal
Publication:544830
DOI10.1007/S11128-010-0200-3zbMATH Open1216.81048arXiv1001.3116OpenAlexW3098146626MaRDI QIDQ544830FDOQ544830
Authors: Vicky Choi 
Publication date: 16 June 2011
Published in: Quantum Information Processing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1001.3116
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
graph minoradiabatic quantum computationuniversal graphadiabatic quantum architecture designminor-embedding
Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Mathematical problems of computer architecture (68M07)
Cites Work
- A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
- A partial k-arboretum of graphs with bounded treewidth
- Graph minors. XIII: The disjoint paths problem
- Colloquium: Quantum annealing and analog quantum computation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Pseudo-Boolean optimization
- Simulating Quantum Computation by Contracting Tensor Networks
- Title not available (Why is that?)
Cited In (28)
- Hard combinatorial problems and minor embeddings on lattice graphs
- Fast clique minor generation in Chimera qubit connectivity graphs
- An Updated Experimental Evaluation of Graph Bipartization Methods
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- QUBO formulation for the contact map overlap problem
- Quantum pattern recognition with multi-neuron interactions
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- 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
- Adiabatic quantum programming: minor embedding with hard faults
- Differential geometric treewidth estimation in adiabatic quantum computation
- Minor embedding in broken chimera and derived graphs is NP-complete
- 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
- 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)
