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

By Vicky Siu-Ngan Choi. Quantum Information Processing, 2010

335 citations recorded by the source corpus.

In Choi (Quantum Inf Process, 7:193–209, 2008), 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 $${\mathcal{F}}$$ of graphs, a (host) graph U is called $${\mathcal{F}}$$-minor-universal if for each graph G in $${\mathcal{F}, U}$$ contains a minor-embedding of G. The problem for designing a $${{\mathcal{F}}}$$-minor-universal hardware graph Usparse in which $${{\mathcal{F}}}$$ consists of a family of sparse graphs (e.g., bounded degree graphs) is open.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/7761ab691c0261eca2d3361020047522cec046cf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Evidence for quantum annealing with more than one hundred qubits (2013, methodology): “The tree width of this graph is 17 for the ideal (128 qubit) Rainier chip and scales as √ N for an N -qubit Chimera graph [16, 17].”
Quantum annealing for industry applications: introduction and review (2021, positive): “For QA, this involves encoding variables as chains of multiple physical qubits on a QPU such that they act as a single logical qubit [34, 35].”
Ising formulations of many NP problems (2013, background): “h these Hamiltonians can be encoded onto such a device. These devices may only encode problems via a “chimera” graph. The primary problem with Hamiltonians on a complete graph is that it is ineﬃcient [43, 44] to embed complete graphs onto the chimera graph. A primary diﬃculty is demonstrated by the ”
How "Quantum" is the D-Wave Machine? (2014, background): “Similarly, there are poor correlations [22] with a classical spin dynamics model of reference [23].”
Quantum Optimization of Fully-Connected Spin Glasses (2014, background): “1 shows an embedding of SKM in a triangular portion [27, 28] of the Vesuvius processor: each LB in the original problem of size N is represented by (N/4)+1 qubits connected in a line.”