Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design

2010/01/19 by Vicky Choi · 1 citation
Physics and Astronomy · Computer Science · #quant-ph #cs.CC

paper · pdf · doi:10.1007/s11128-010-0200-3

published as Quantum Information Processing: Volume 10, Issue 3 (2011), Page 343 · 10 pages, 5 figures

arxiv created 2010/01/19 · arxiv updated 2011/06/01

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.

Cited by

• Optimized Quantum Embedding: A Universal Minor-Embedding Framework for Large Complete Bipartite Graph

Related

• Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem
• A practical heuristic for finding graph minors
• Optimized Quantum Embedding: A Universal Minor-Embedding Framework for Large Complete Bipartite Graph
• Hard combinatorial problems and minor embeddings on lattice graphs
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets