Skip to main content
Erschienen in: Quantum Information Processing 7/2020

Open Access 01.07.2020

Minimizing minor embedding energy: an application in quantum annealing

verfasst von: Yan-Long Fang, P. A. Warburton

Erschienen in: Quantum Information Processing | Ausgabe 7/2020

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A significant challenge in quantum annealing is to map a real-world problem onto a hardware graph of limited connectivity. When the problem graph is not a subgraph of the hardware graph, one might employ minor embedding in which each logical qubit is mapped to a tree of physical qubits. Pairwise interactions between physical qubits in the tree are set to be ferromagnetic with some coupling strength \(F<0\). Here we address the theoretical question of what the best value F should be in order to achieve unbroken trees in the pre-quantum-processing. The sum of |F| for each logical qubit is defined as minor embedding energy, and the best value F is obtained when the minor embedding energy is minimized. We also show that our new analytical lower bound on |F| is a tighter bound than that previously derived by Choi (Quantum Inf Process 7:193–209, 2008). In contrast to Choi’s work, our new method depends more delicately on minor embedding parameters, which leads to a higher computational cost.
Hinweise

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

1 Introduction

Quantum annealing is a widely used tool for solving quadratic optimization problems [1, 2]. The problem is mapped to a Hamiltonian, \(H_P\), whose ground state encodes the optimized solution. Exploration of the potential landscape is driven by quantum fluctuations described by a driver Hamiltonian, \(H_D\). The overall system Hamiltonian \(H_\mathrm{total}\) is a time-varying weighted sum of \(H_P\) and \(H_D\) such that at the end of the annealing process the quantum fluctuations are suppressed and \(H_\mathrm{total} = H_P\). A typical annealing schedule is of the form
$$\begin{aligned} H_\mathrm{total}(s)=A(s) H_D+B(s) H_P\;, \end{aligned}$$
(1.1)
where \(0\le s\equiv \frac{t}{t_f}\le 1\), t is time, \(t_f\) is the duration of the anneal, \(A(0)\gg B(0)\) and \(A(1)\ll B(1)\). The origin of quantum annealing goes back to the quantum adiabatic theorem with a gap condition, which was first shown by Born and Fock [3], then Kato [4] simplified the proof of the theorem and extended it to allow degenerate eigenstates and eigenvalue crossings. For closed quantum systems, Farhi et al. [5, 6] proposed adiabatic quantum computation as an alternative to tackle NP-complete problems. For a recent review of the quantum adiabatic theorem, see for example Albash and Lidar [7].
In view of the computational complexity of modelling interacting quantum systems using classical computational resources, a potentially efficient way to find the ground state of \(H_P\) is to engineer a physical system whose dynamics follow that of Eq. (1.1). One such physical system is based on a system of superconducting flux qubits with tunable inductive interactions [8]. In this implementation the problem Hamiltonian is of the Ising form:
$$\begin{aligned} H_P=\sum _i h_i \sigma _i^z +\sum _{ij\in E(G)}J_{ij}\sigma _i^z \sigma _j^z \;. \end{aligned}$$
(1.2)
Here \(\sigma _i^z\) is the quasi-spin of qubit i (corresponding to its flux state) and G is a graph describing all possible two-qubit interactions. The total Hamiltonian is exactly the transverse Ising model introduced by Kadowaki and Nishimori [9], which is a quantum analogue of classical simulated annealing. Moreover, many NP-hard problems can be translated into Ising Hamiltonians [10]. Now the expression (1.1) becomes
$$\begin{aligned} H_\mathrm{total}(s)=A(s) \sum _i {\tilde{h}}_i \sigma _i^x+B(s) \left( \sum _i h_i \sigma _i^z +\sum _{ij\in E(G)}J_{ij}\sigma _i^z \sigma _j^z \right) \;. \end{aligned}$$
(1.3)
One problem for hardware implementation of quantum annealing now becomes immediately apparent: for a system of N qubits it is at best very difficult to engineer direct interactions between all \(\frac{1}{2}N(N-1)\) pairs. In current implementations of flux-qubit quantum annealers the maximum degree of the hardware graph is 6—i.e. each qubit is directly coupled to at most six other qubits1. It is therefore necessary to employ minor embedding—i.e. to embed an Ising problem Hamiltonian whose connectivity graph has degree \(D_P\) onto physical hardware with connectivity graph of degree \(D_H\), where \(D_H < D_P \le N\). The requirement of this embedding is that the ground state of the embedded Hamiltonian of degree \(D_H\) encodes the same solution as the ground state of the problem Hamiltonian of degree \(D_P\).
Choi [11] first proposed a method for minor embedding in which each logical qubit is replaced by a tree of physical qubits. All the physical qubits within each tree are constrained to be in the same spin state (which in turn is the spin state of the logical qubit) by the implementation of ferromagnetic interactions of magnitude |F| at each edge of the tree. In practice it is usual to use a one-dimensional chain of physical qubits as the tree for minor embedding. A logical qubit consisting of a chain of L physical qubits in a hardware graph of degree \(D_H\) can now be directly coupled to \(L (D_H - 2) + 2\) other logical qubits, thereby greatly increasing the connectivity. Figure 1 shows an example of a minor embedding.
If |F| is sufficiently large, for a closed-system quantum annealer it can be assumed that the ferromagnetic bonds between each physical qubit in the embedded logical qubit are never broken, ensuring that all the physical spins are mutually aligned. In a real quantum annealer, however, thermal fluctuations and other noise mechanisms may break ferromagnetic bonds resulting in domain walls between locally aligned regions. In this case the value of the logical spin cannot be unambiguously determined (although majority vote may be used to estimate it). In such a real quantum annealer therefore the probability that the embedded Hamiltonian anneals to the correct ground state depends upon the probability of domain walls forming, which in turn is a function of the strength, F, of the ferromagnetic interaction between the physical qubits in the embedded tree. While at first sight it might appear that the ground-state probability is monotonic in F, in a real quantum annealer the maximum absolute coupling strength between any pair of physical qubits is finite. (In a flux qubit annealer, for example, this maximum coupling is determined by the magnitudes of the persistent current and mutual inductances.) Arbitrary increases in the embedding ferromagnetic coupling strength normalized with respect to the energy scale of the problem Hamiltonian can therefore only be achieved by reducing the latter. This in turn leads to an increase in computational errors from thermal transitions to an excited state. Furthermore, if F is too small, domain walls will be present unavoidably. This suggests that there is an optimum value for the embedding ferromagnetic coupling strength (internal coupling strength) for any given embedding of the problem Hamiltonian. The existence of optimum values for spin-glass problems is shown experimentally in [12]. Furthermore, “Appendix A” also shows experimental confirmation of the existence of an optimum value for a set of random job-shop scheduling problems. Another important feature arises when we use minor-embedding. There may be more than one physical coupler to represent a logical coupler for two adjacent logical qubits, when both of the logical qubits are required to be minor-embedded. Assigning values to these physical couplers is another freedom in the minor-embedding. The only constraint for the physical couplers is that they need to add up to the value of corresponding logical coupler. In fact, this will also affect the performance of minor-embedding (see Remark 2.8 for details).
Several strategies for parameter setting on quantum annealers are developed by Pudenz [13] to understand how the ferromagnetic coupling strength (within embedded chains) would affect the probability of finding ground states on the D-Wave DW2 and DW2X machine. Pudenz’s work focuses on mixed satisfiability problems. It shows that higher ferromagnetic coupling strengths do not increase the chance of finding the ground state on either machine. Moreover, different strategies for setting the logical field magnitude \(h_{i(k)}\) within the chains yield different performance. In particular, the so-called single distribution method is less effective than other methods. This is due to the fact that non-admissible minor embeddings are more likely to be used in the single distribution method—see Remark 3.5 for details. Venturelli et al. [12] studied the Sherrington–Kirkpatrick Model (SKM) on the D-Wave DW2 machine. They experimentally confirmed the non-monotonic dependence of the ground-state probability on F by using the D-Wave quantum annealer for up to \(N = 30\) fully connected logical spins.
In this paper we revisit minor embedding in order to determine the optimum ferromagnetic strength |F| for embedding trees in quantum annealers at finite temperature. We will give a mathematical criterion for the best bound on the value of |F|. As a consequence, the first two theorems by Choi [11] will follow immediately. It is not hard to see that Choi’s first paper in minor embedding [11] gives the foundation for the Chimera architecture of D-Wave machines given in [14]. Moreover, methods to generate minor embedding on the Chimera graph can be found in [15]. Therefore, we focus here on the analysis of minor embeddings rather than on architectures of quantum annealers. Moreover, we will see in Sect. 3.1 that condition (2.4) will influence the bound of |F|. Our results can be applied to any architecture as long as the Ising nature is preserved. Here the Ising nature should be understood in the broad sense, i.e. including higher-order interaction terms. It is known that Hamiltonians with higher-order interactions can be reproduced via a two-body Hamiltonian (see e.g. [16]). There are also other techniques that can be used to reduce higher-order interactions into two-body Hamiltonians (see e.g. [17, 18]). In fact, reducing 3-body interactions to 2-body interactions was introduced by Kolmogorov and Zabih [19]. A more systematic review on reducing higher-order Hamiltonians to two-body Hamiltonians can be found in [20]. In order to achieve multi-body interactions via two-body Ising models, one has to couple logical qubits with ancilla qubits, which certainly increases the (vertex) degree of the corresponding two-body Hamiltonian. Minor embedding is the key tool to convert graphs with higher degrees to graphs with lower degrees (see e.g. [21]). Therefore, our paper will also be useful for generating multi-body interactions.
It still remains open to model the open system effectively. A simplified version can be found in [22], where a system-bath Hamiltonian is studied in detail. The Hamiltonian is given by
$$\begin{aligned} H(t)=H_S(t)+H_B+H_I\,, \end{aligned}$$
where \(H_S\), \(H_B\) and \(H_I\) correspond to the adiabatic system, bath and interaction Hamiltonians, respectively. Note that \(H_I=g\sum A_\alpha \otimes B_\alpha \). This special feature enables us to use a perturbative method for small g as shown in the paper [22]. However, if g depends non-trivially on the strong coupling, F, introduced by \(H_S(t)\), then g might become large for large F. Consequently, small order perturbations will not be enough to analyse the behaviour of the system. Therefore, if \(H_S=H_\mathrm{total}\) and we want to use the model in [22], we need to minimize the strong coupling, F, in \(H_\mathrm{total}\) without destroying the Ising problem \(H_P\) in (1.1). This give another motivation for us to search for the minimum coupling strength in \(H_P\).

2 Main results

2.1 Preparatory material

Firstly, we give a formal definition for minor embedding.
Definition 2.1
A minor-embedding [11] is a pair of mappings \((\iota ,\tau )=:I\) that maps a graph G to a sub-graph of another graph U. The pair of mappings satisfies the following properties:
  • \(\iota : V(G) \mapsto V(U)\) each vertex i in V(G) is mapped to a set of vertices (denoted by\(\iota (i)\)) of a connected sub-tree of U ,
  • \(\tau : V(G) \times V(G) \mapsto V(U)\) such that for each \(ij\in E(G)\), \(\tau (i,j)\in \iota (i)\) and \(\tau (j,i)\in \iota (j)\) fulfilling \(\tau (i,j)\tau (j,i)\in E(U)\). Note that \(\tau \) induces the mapping of edges, which we also denote by \(\tau \).
Note that given graphs G and U, there may be no minor embedding of G into U or there may exist many \((\iota ,\tau )\)’s that embed G into U. For instance, by Kuratowski’s theorem the complete bipartite graph \(K_{3,3}\) cannot be minor embedded into any planar graph. Figure 1 illustrates how to embed a highly connected graph into a less connected graph.
Let G be the logical graph corresponding to expression (1.2). To show its dependence on G, we suppress the subscript P and rewrite the expression as
$$\begin{aligned} H_G=\sum _{i\in V(G)} h_i \sigma _i^z +\sum _{ij\in E(G)}J_{ij}\sigma _i^z \sigma _j^z \;. \end{aligned}$$
(2.1)
Suppose that there is another graph U, which we can interpret as the hardware graph. Moreover, we assume that graph G can be minor embedded onto graph U. Then Definition 2.1 induces a series of problem Hamiltonians associated with graph \(I(G)\subset U\):
$$\begin{aligned} H_{I(G)}= & {} \sum _{i\in V(G)} \left( \sum _{k\in V(\iota (i))}h_{i(k)} \sigma _{i(k)}^z + \sum _{i_p i_q\in E(\iota (i))} F^{pq}_i \sigma _{i_p}^z\sigma _{i_q}^z\right) \nonumber \\&+ \sum _{ij \in E(G)}J_{ij}\sigma _{\tau (i,j)}^z \sigma _{\tau (j,i)}^z \;, \end{aligned}$$
(2.2)
where
$$\begin{aligned} \sum _{k\in V(\iota (i))}h_{i(k)} = h^\prime _i\,, \end{aligned}$$
and the ferromagnetic coupling strength (also called internal coupling strength) within each sub-tree \(\iota (i)\) is bounded from above.
$$\begin{aligned} F^{pq}_i < -M_i\,, \qquad \hbox { for some non-negative}\ M_i. \end{aligned}$$
(2.3)
In order to match the ground state of Hamiltonian (2.1) and that of Hamiltonian (2.2), we can set \(h^\prime _i = h_i\), which gives
$$\begin{aligned} \sum _{k\in V(\iota (i))}h_{i(k)}= h_i. \end{aligned}$$
(2.4)
We also require that \(M_i\) be sufficiently large that all spins in the ground state of the embedded tree are aligned.
A natural question to ask is: How small can\(M_i\)be?
Let \({\mathscr {E}}_G\) be the energy corresponding to Hamiltonian (2.1) and \({\mathscr {E}}_{I(G)}\) for Hamiltonian (2.2). Then we have
$$\begin{aligned} {\mathscr {E}}_G(s_1,\dots ,s_N)=\sum _{i\in V(G)} h_i s_i +\sum _{ij\in E(G)}J_{ij} s_i s_j \;, \end{aligned}$$
(2.5)
and
$$\begin{aligned}&{\mathscr {E}}_{I(G)}\left( s_{1(1)},\dots ,s_{1(|\iota (1)|)},\dots ,s_{N(|\iota (N)|)}\right) \nonumber \\&\quad =\sum _{i\in V(G)} \left( \sum _{k\in V(\iota (i))}h_{i(k)} s_{i(k)} + \sum _{i_p i_q\in E(\iota (i))} F^{pq}_i s_{i_p} s_{i_q}\right) \nonumber \\&\qquad + \sum _{ij \in E(G)}J_{ij} s_{\tau (i,j)} s_{\tau (j,i)} \;. \end{aligned}$$
(2.6)
Definition 2.2
(Minor embedding energy) Let \(I=(\iota ,\tau )\) be a minor embedding. Then its minor embedding energy (MEE) is defined by
$$\begin{aligned} {\mathscr {E}}_{I_{MEE}}:=\sum _{i_p i_q\in E(\iota (i))} |F^{pq}_i|. \end{aligned}$$
Note that minimizing \(M_i\) for each logical qubit i is equivalent to minimizing the minor embedding energy.

2.2 Main theorem

Our task is to find the mathematical criteria for all the bounds that preserve the ground-state configuration of Hamilton (2.1). Now we will focus on the criteria for tree \(\iota (i)\).
Definition 2.3
(Boundary operator) Let X be a graph and \(2^{X}\) denote the power set of V(X). The boundary operator
$$\begin{aligned} \partial : 2^{X} \mapsto E(X) \end{aligned}$$
is defined as that for any \(W \subset V(X)\), \(\partial W\) gives the boundary edges of W. That is the cut(s) between W and \(X\backslash W\). Moreover, the boundary operator \(\partial \) annihilates both the empty set and the total set V(X).
We will see later that the boundary operator has a strong relationship with the ferromagnetic coupling strength. For a graph with assignments (local h-field) on each vertex, we define the following integral operator.
Definition 2.4
( h -integral operator)
Let X be a graph. The h-integral operator
$$\begin{aligned} h: V(X) \mapsto {\mathbb {R}} \end{aligned}$$
is defined as
$$\begin{aligned} h(W)=\sum _{k\in V(W)} h_k\qquad \qquad \hbox { for any}\ W \subset X. \end{aligned}$$
Similarly, we can define the J-integral operator for other non-negative external field.
Definition 2.5
(J-integral operator) Let X be a graph. The J-integral operator
$$\begin{aligned} J: V(X) \mapsto {\mathbb {R}}_+ \end{aligned}$$
is defined as
$$\begin{aligned} J(W)=\sum _{k\in V(W)} J_k\qquad \qquad \hbox { for any}\ W \subset X. \end{aligned}$$
At least one domain wall is present when there is the presence of an inhomogeneous spin configuration in \(\iota (i)\) or equivalently the presence of an anisotropic magnetization.
Definition 2.6
(Domain wall) If all particles have the same spin in \(W_i\subset \iota (i)\) but opposite spin in \(\iota (i)\backslash W_i\), then \(\partial W_i\) is the domain wall associated with \(W_i\).
We say a domain wall \(\partial W_i\) is positive (negative), if the spins are positive (negative) within \(W_i\).
Let us denote \({\text {Onbh}}(i(k))\) the original neighbourhood of the pre-embedded vertex i that is connected to the embedded vertex i(k).
Now we are ready to state our main theorem.
Theorem 2.7
Let \(h_{i(k)}\) be the local fields and \(J_{i(k)}:=\sum _{l\in {\text {Onbh}}(i(k))}|J_{l,i(k)}|\) be the non-negative external fields on \(\iota (i)\). Let \(M_i\) be the constant defined in (2.3) satisfying
$$\begin{aligned} M_i \ge \underset{W_i}{{\text {max}}}\left( \frac{1}{|\partial W_i|}{\text {min}}\Big \{|h(W_i)-J(W_i)|,|h(W_i)-h_i-J(\iota (i)\backslash W_i)| \Big \}\right) ,\nonumber \\ \end{aligned}$$
(2.7)
where the maximum is taken from all \(\emptyset \ne W_i \subsetneq \iota (i)\). Then we have
$$\begin{aligned} s^*_{i_p}s^*_{i_q}=1\,, \qquad \hbox { for all}\ i_p i_q\in E(\iota (G))\,, \end{aligned}$$
(2.8)
and
$$\begin{aligned} {\text {min}}{\mathscr {E}}_{I(G)}\left( s^*_{1(1)},\dots ,s^*_{1(|\iota (1)|)},\dots ,s^*_{N(|\iota (N)|)}\right) ={\mathscr {E}}_G(s^*_1,\dots ,s^*_N)\,, \end{aligned}$$
(2.9)
where \(s^*_k=s^*_{k(j)}\), for all \(j\in \iota (k)\).
Remark 2.8
  • If certain conditions are satisfied, then the bound given in inequality (2.7) is valid for the worst-case scenario, i.e. it takes into account all possible spin configurations in the neighbourhood of the logical qubit. See Sect. 3 for details.
  • It gives the necessary condition such that \(M_i\) will preserve the equivalence of ground states for \({\mathscr {E}}_{I(G)}\) and \({\mathscr {E}}_G\). Moreover, it is the necessary condition for the \(h_{i(k)}\)’s and \(J_{i(k)}\)’s being pre-defined. Hence, \(M_i\) depends on \(h_{i(k)}\) and \(J_{i(k)}\). In practice, the \(J_{i(k)}\)’s are defined for a given minor embedding. However, the \(h_{i(k)}\)’s need to be determined. Therefore, the true optimal \(M_i\) should be
    $$\begin{aligned} M_i=\min _{h_{i(k)}} M_i\left( h_{i(k)}\right) \,, \end{aligned}$$
    provided that some conditions are satisfied, see Sect. 3.
  • When two minor-embedded qubits have more than one physical coupler between them, one can distribute the value of the original logical coupler over the available physical couplers. Different distributions will have different impacts on the value of \(J(W_i)\) and hence on the value of \(M_i\). How to define the distribution of the physical couplers over a single logical coupler is another meaningful and interesting question to be investigated.
We will see later how this will give the true optimal bound for a simple example. Now we show that two important theorems of minor embedding by Choi [11] follow as corollaries of our main theorem.
Corollary 2.9
(Choi’s first theorem) Let \(M_i\) be the constant defined in (2.3) satisfying
$$\begin{aligned} M_i \ge |h_i|+\sum _{j\in {\text {nbh}}(i)}|J_{ij}|\,, \end{aligned}$$
(2.10)
where \({\text {nbh}}(i)\) means the neighbourhood of vertex i. We have
$$\begin{aligned} s^*_{i_p}s^*_{i_q}=1\,, \qquad \hbox { for all}\ i_p i_q\in E(\iota (G))\,, \end{aligned}$$
(2.11)
and
$$\begin{aligned} {\text {min}}{\mathscr {E}}_{I(G)}\left( s^*_{1(1)},\dots ,s^*_{1(|\iota (1)|)},\dots ,s^*_{N(|\iota (N)|)}\right) ={\mathscr {E}}_G(s^*_1,\dots ,s^*_N)\,, \end{aligned}$$
(2.12)
where \(s^*_k=s^*_{k(j)}\), for all \(j\in \iota (k)\).
Proof
It suffices to show that
$$\begin{aligned}&|h_i|+\sum _{j\in {\text {nbh}}(i)}|J_{ij}| \ge {\text {max}}_{W_i\subset \iota (i)}\left( \frac{1}{|\partial W_i|}{\text {min}}\Big \{|h(W_i)-J(W_i)|,|h(W_i)\nonumber \right. \\&\quad \left. -h_i-J(\iota (i)\backslash W_i)| \Big \}\right) . \end{aligned}$$
(2.13)
Since for each \(W_i\subset \iota (i)\), we have
$$\begin{aligned} |h_i|+\sum _{j\in {\text {nbh}}(i)}|J_{ij}| \ge |h(W_i)-J(W_i)| \ge \frac{1}{|\partial W_i|} |h(W_i)-J(W_i)|\,, \end{aligned}$$
the inequality (2.13) follows immediately. \(\square \)
In order to get Choi’s tighter bound for the ferromagnetic coupler strengths, one needs to introduce the following object.
$$\begin{aligned} C(i):=\sum _{j\in {\text {nbh}}(i)}|J_{ij}|-|h_i|\,, \qquad \hbox { for all}\ i \in V(G)\,, \end{aligned}$$
(2.14)
which defines whether the spin of particle i is locally determinable or non-determinable. When \(C(i)<0\), the spin of particle i is locally determinable, as the local field \(h_i\) is dominant, whereas when \(C(i) \ge 0\), its spin must be determined globally. Without loss of generality, we can assume \(C(i) \ge 0\). Now, we are ready to state our second corollary.
Corollary 2.10
[Choi’s second theorem] Let \(h_{i(k)}\) satisfy
$$\begin{aligned} h_{i(k)}={\text {sgn}}(h_i)\left\{ \begin{aligned}&\sum _{\tau (j,i)\in {\text {Onhb}}(i(k))}|J_{ij}|-\frac{C(i)}{l(i)} \,, \qquad&\hbox { where } i(k) \hbox { is one of the } l(i)\hbox { leaves of } \iota (i)\,;\\&\sum _{\tau (j,i)\in {\text {Onhb}}(i(k))}|J_{ij}|&\text {otherwise}, \end{aligned}\right. \nonumber \\ \end{aligned}$$
(2.15)
where \({\text {Onbh}}(i(k))\) means the original neighbourhood of vertex \(i(k)\in \iota (i)\).Then
$$\begin{aligned} M \ge \frac{l(i)-1}{l(i)}C(i) \qquad \hbox { for all}\ i \in V(G) \end{aligned}$$
(2.16)
yields the same result as Corollary 2.9.
Remark 2.11
(Comparison between Choi’s two theorems)
  • Corollary 2.9 is independent of the values of the C(i)’s and is certainly larger than the bound given in Corollary 2.10. However, Corollary 2.9 does not assign any value to \(h_{i(k)}\), whereas Corollary 2.10 holds only when the \(h_{i(k)}\)’s satisfy Eq. (2.15).
  • Corollary 2.10 gives the best bound when \(C(i)=0\) for all \(i\in V(G)\).
  • The larger (weaker) bound given by Corollary 2.9 does not require any topological information about the minor embedding, while the smaller (stronger) bound given by Corollary 2.10 depends non-trivially on the topology of the minor embedding.
  • Both proofs for Corollaries 2.9 and 2.10 are quite different, and there is no obvious derivation from Corollaries 2.9 to 2.10.
Now we give a simple proof of Choi’s second theorem as a corollary.
Proof
It suffices to show that
$$\begin{aligned}&\frac{l(i)-1}{l(i)}C(i) \ge {\text {max}}_{W_i\subset \iota (i)}\left( \frac{1}{|\partial W_i|}{\text {min}}\Big \{|h(W_i)-J(W_i)|,\nonumber \right. \\&\quad \left. |h(W_i)-h_i-J(\iota (i)\backslash W_i)| \Big \}\right) \,, \end{aligned}$$
(2.17)
for \(h_{i(k)}\) setting as in Eq. (2.15) and for all \(\emptyset \ne W_i\subsetneq \iota (i)\). Now we have
$$\begin{aligned} |h(W_i)-J(W_i)| = \left| \partial (L(i)\cap W_i)\right| \times \frac{C(i)}{l(i)} \,, \end{aligned}$$
where L(i) is the set of leaves in \(\iota (i)\). As \(|\partial W_i|\ge 1\) for \(\emptyset \ne W_i\subsetneq \iota (i)\), one can easily verify that
$$\begin{aligned} \left| \partial (L(i)\cap W_i)\right| \le |\partial W_i|\left( |\partial L(i)|-1\right) =|\partial W_i|\left( l(i)-1\right) . \end{aligned}$$
Therefore, we have
$$\begin{aligned} \frac{1}{|\partial W_i|}|h(W_i)-J(W_i)|\le \frac{l(i)-1}{l(i)} C(i)\,, \end{aligned}$$
for all \(\emptyset \ne W_i\subsetneq \iota (i)\), which completes the proof. \(\square \)
As it remains open on the tightness of the bound in Corollary 2.10, we will give a simple example in the next subsection, which shows that even for \(h_{i(k)}\)’s given as in Eq. (2.15), the bound is not tight. Furthermore, by relaxing the condition (2.15), one can achieve the best bound.

2.3 An example: existence of a tighter bound

In this subsection, we give an example to show the existence of a tighter bound for the ferromagnetic coupling strength compared with Corollary 2.10. Let us consider the minor embedding of a vertex i as in Fig. 2. For the sake of this example, we set the couplers and local fields such that
$$\begin{aligned} \sum _{1(k)\in {\text {Onbh}}(1)}|J_{1,1(k)}|=\sum _{2(k)\in {\text {Onbh}}(2)}|J_{2,2(k)}|=\sum _{3(k)\in {\text {Onbh}}(3)}|J_{3,3(k)}|=5h>0,\nonumber \\ \end{aligned}$$
(2.18)
and
$$\begin{aligned} h_i=3h. \end{aligned}$$
(2.19)
According to Corollary 2.10, for this example we have
$$\begin{aligned} C(i)=12h\,,\qquad l(i)=3\,,\qquad h_{i(0)}=0\,,\qquad h_{i(1)}=h_{i(2)}=h_{i(3)}=h.\nonumber \\ \end{aligned}$$
(2.20)
More importantly, the bound for the ferromagnetic coupler strengths according to Corollary 2.10 is given by
$$\begin{aligned} F_i<-8h. \end{aligned}$$
(2.21)
Our new tighter bound shows that a better bound exists, i.e.
$$\begin{aligned} F_i<-6h\,, \end{aligned}$$
is sufficient for this toy model. See “Appendix B” for details.
We will show later in Sect. 3 that the best bound for this example is \(F_i<-5h\), if we allow \(h_{i(k)}\) to have different values.

2.4 Proof of the main theorem

In this subsection, we give the full proof of our main theorem.
In order for sufficiently large \(M_i\) to preserve the homogeneity of spins in \(\iota (i)\), we need to find a sufficient condition so that the formation of each domain wall is forbidden. Now we have the following lemma.
Lemma 2.12
$$\begin{aligned} M_i \ge \frac{1}{|\partial W_i|}{\text {min}}\left\{ |h(W_i)-J(W_i)|,|h(W_i)-h_i-J(\iota (i)\backslash W_i)| \right\} \end{aligned}$$
(2.22)
implies \(\partial W_i\) is not a positive domain wall within the ground-state configuration of \({\mathscr {E}}_{I(G)}\).
Proof by contradiction
Let \(W_i(\pm )\) denote the spin configuration for all spins being \(\pm 1\) in \(W_i\) and \({\overline{W}}_i(\cdot )\) be the spin configuration for the complement of \(W_i\) with respect to \(\iota (i)\). Now suppose \(\partial W_i\) is a positive domain wall within the ground-state configuration of \({\mathscr {E}}_{I(G)}\). Then we have
$$\begin{aligned} {\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(-),\dots \right) \le {\mathscr {E}}_{I(G)}\left( W_i(-),{\overline{W}}_i(-),\dots \right) \,, \end{aligned}$$
(2.23)
and
$$\begin{aligned} {\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(-),\dots \right) \le {\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(+),\dots \right) . \end{aligned}$$
(2.24)
However, according to Eq. (2.6), we have
$$\begin{aligned}&{\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(-),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(-),{\overline{W}}_i(-),\dots \right) \nonumber \\&\quad =2\left( \sum _{i(k)\in W_i} h_{i(k)}+\sum _{i(k)\in W_i}\sum _{l\in {\text {Onbh}}(i(k))}J_{i(k)l}\, s_{\tau (l,i(k))}-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) \nonumber \\&\quad \ge 2\left( \sum _{i(k)\in W_i} h_{i(k)}-\sum _{i(k)\in W_i}\sum _{l\in {\text {Onbh}}(i(k))} |J_{i(k)l}|-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) \nonumber \\&\quad = 2\left( h(W_i)-J(W_i)-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) \nonumber \\&\quad > 2\left( h(W_i)-J(W_i)+|\partial W_i|\times M_i \right) \end{aligned}$$
(2.25)
and
$$\begin{aligned}&{\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(-),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(+),\dots \right) \nonumber \\&\quad =2\left( -\sum _{j(k)\in {\overline{W}}_i} h_{j(k)}-\sum _{j(k)\in {\overline{W}}_i}\sum _{l\in {\text {Onbh}}(j(k))}J_{j(k)l}\, s_{\tau (l,j(k))}-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) \nonumber \\&\quad =2\left( -\left( h_i-\sum _{i(k)\in W_i} h_{i(k)}\right) -\sum _{j(k)\in {\overline{W}}_i}\sum _{l\in {\text {Onbh}}(j(k))}J_{j(k)l}\, s_{\tau (l,j(k))}-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) \nonumber \\&\quad \ge 2\left( h(W_i)-h_i-J({\overline{W}}_i)-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) \nonumber \\&\quad > 2\left( h(W_i)-h_i-J({\overline{W}}_i)+|\partial W_i|\times M_i \right) . \end{aligned}$$
(2.26)
Since our assumption also has
$$\begin{aligned} M_i \ge \frac{1}{|\partial W_i|}{\text {min}}\left\{ |h(W_i)-J(W_i)|,|h(W_i)-h_i-J(\iota (i)\backslash W_i)| \right\} \,, \end{aligned}$$
we then have
$$\begin{aligned} {\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(-),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(-),{\overline{W}}_i(-),\dots \right) >0\,, \end{aligned}$$
or
$$\begin{aligned} {\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(-),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(+),\dots \right) >0. \end{aligned}$$
This contradicts inequalities (2.23) and (2.24). Hence, \(\left( W_i(+),{\overline{W}}_i(-),\dots \right) \) is not a positive domain wall within the ground-state configuration of \({\mathscr {E}}_{I(G)}\). \(\square \)
Now we are ready to prove the main theorem.
Proof of the main theorem
To prove
$$\begin{aligned} s^*_{i_p}s^*_{i_q}=1\,, \qquad \hbox { for all}\ i_p i_q\in E(\iota (G)) \end{aligned}$$
and \( \left( s^*_{1(1)},\dots ,s^*_{1(|\iota (1)|)}\right) \) is a ground-state configuration for Hamiltonian (2.2), we can equivalently prove that no positive domain wall is present in the ground-state configuration. Note that the existence of a positive domain wall is equivalent to the existence of a domain wall.
Now, by Lemma 2.12, if \(\emptyset \ne W_i \subsetneq \iota (i)\) and
$$\begin{aligned} M_i \ge \frac{1}{|\partial W_i|}{\text {min}}\left\{ |h(W_i)-J(W_i)|,|h(W_i)-h_i-J(\iota (i)\backslash W_i)| \right\} \end{aligned}$$
we have that \(W_i\) cannot have a positive domain wall \(\partial W_i\) in the ground-state configuration. Therefore,
$$\begin{aligned} M_i \ge \underset{\emptyset \ne W_i \subsetneq \iota (i)}{{\text {max}}}\frac{1}{|\partial W_i|}{\text {min}}\left\{ |h(W_i)-J(W_i)|,|h(W_i)-h_i-J(\iota (i)\backslash W_i)| \right\} \end{aligned}$$
implies that no positive domain wall can be present in the ground-state configuration. Hence, the ground-state configuration has no domain wall in \(\iota (i)\). \(\square \)

3 Tightness of the bound

Now we want to show that, if the condition
$$\begin{aligned} h(W_i)\le h_i+J({\overline{W}}_i)\qquad \text {or}\qquad h({\overline{W}}_i)\le h_i-J(W_i) \end{aligned}$$
(3.1)
is satisfied, then
$$\begin{aligned} M(W_i;h,J):=\frac{1}{|\partial W_i|}{\text {min}}\left\{ |h(W_i)-J(W_i)|,|h(W_i)-h_i-J({\overline{W}}_i)| \right\} \end{aligned}$$
(3.2)
is the best bound for \(\emptyset \ne W_i\subsetneq \iota (i)\). That is for any \(\epsilon >0\) and \(F_i^{pq}=-M(W_i;h,J)+\epsilon \), we have that the ground state of \({\mathscr {E}}_{I(G)}\) has a domain wall in \(\iota (i)\) in the worst scenario. Here, the worst scenario is understood in the following theorem.
Theorem 3.1
Suppose condition (3.1) is satisfied and let \(M(W_i;h,J)\) be defined in Eq. (3.2). For any \(\epsilon >0\), if \(F_i^{pq}=-M(W_i,h,J)+\frac{\epsilon }{|\partial W_i|}\), then \({\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(+),\dots \right) \) and \({\mathscr {E}}_{I(G)}\left( W_i(-),{\overline{W}}_i(-),\dots \right) \) are not the ground-state configurations for some values of \(s_{\tau (i,j)}\) with \(j\in {\text {nbh}}(i)\).
Before giving the proof of Theorem 3.1, we give some remarks and corollaries.
Corollary 3.2
If
$$\begin{aligned} h({\overline{W}}_i)\le h_i+J(W_i)\qquad \text {or}\qquad h(W_i)\le h_i-J({\overline{W}}_i) \end{aligned}$$
(3.3)
is satisfied, then \(M({\overline{W}}_i;h,J)\) is the tightest bound.
Remark 3.3
  • If condition (3.1) is satisfied for all non-empty \(W_i\subsetneq \iota (i)\), then the right-hand side of expression (2.7) is the best constant.
  • If \(h_i\) and \(h(W_i)\) are both positive, then \(M(W_i;h,J)\) is the best constant. Similarly, if \(h_i\) and \(h({\overline{W}}_i)\) are both negative, then \(M({\overline{W}}_i;h,J)\) is the best constant. This can be checked easily via validity of condition (3.1) and (3.3), respectively.
Now we give an easy proof for the best constant for example 2.3. The best bound for the example given in Subsection 2.3 is 5h. Recall in Remark 2.8 that we need to relax the assignment of h-fields. Moreover, in this example, we have only one non-trivial embedding (the green vertices in Fig. 6) and \(h_i=3h>0\). By Remark 3.3, the best bound is given by \(M_i=5h\), if we allow a more general distribution of \(h_{i(k)}\). See “Appendix C” for details.
Now we give the proof of Theorem 3.1.
Proof of Theorem 3.1
As in the proof of the previous lemma, one has
$$\begin{aligned}&{\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(-),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(-),{\overline{W}}_i(-),\dots \right) \\&\quad =2\left( \sum _{i(k)\in W_i} h_{i(k)}+\sum _{i(k)\in W_i}\sum _{l\in {\text {Onbh}}(i(k))}J_{i(k)l}\, s_{\tau (l,i(k))}-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) . \end{aligned}$$
For some \(s_{\tau (l,i(k))}\) with \(i(k)\in V(W_i)\), we have
$$\begin{aligned}&{\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(-),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(-),{\overline{W}}_i(-),\dots \right) \nonumber \\&\quad = 2\left( h(W_i)-J(W_i)-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) = 2\left( h(W_i)-J(W_i)\nonumber \right. \\&\qquad \left. +|\partial W_i|\times M(W_i,h,J)-\epsilon \right) \nonumber \\&\quad \le 2\left( h(W_i)-J(W_i)+|h(W_i)-J(W_i)|-\epsilon \right) . \end{aligned}$$
(3.4)
Case 1:\(h(W_i)-J(W_i)\ge 0\,.\) Let us consider the following difference
$$\begin{aligned}&{\mathscr {E}}_{I(G)}\left( {\overline{W}}_i(+),W_i(-),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(-),{\overline{W}}_i(-),\dots \right) \\&\quad =2\left( \sum _{i(k)\in {\overline{W}}_i} h_{i(k)}+\sum _{j(k)\in {\overline{W}}_i}\sum _{l\in {\text {Onbh}}(j(k))}J_{j(k)l}\, s_{\tau (l,j(k))}-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) . \end{aligned}$$
For some \(s_{\tau (l,j(k))}\) with \(j(k)\in V({\overline{W}}_i)\), we have
$$\begin{aligned}&{\mathscr {E}}_{I(G)}\left( {\overline{W}}_i(+),W_i(-),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(-),{\overline{W}}_i(-),\dots \right) \nonumber \\&\quad = 2\left( h({\overline{W}}_i)-J({\overline{W}}_i)-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) \nonumber \\&\quad = 2\left( h({\overline{W}}_i)-J({\overline{W}}_i)+|\partial W_i|\times M(W_i,h,J)-\epsilon \right) \nonumber \\&\quad \le 2\left( h({\overline{W}}_i)-J({\overline{W}}_i)+|h(W_i)-J(W_i)|-\epsilon \right) \nonumber \\&\quad = 2\left( h_i-J({\overline{W}}_i)-J(W_i)-\epsilon \right) \le -2\epsilon <0. \end{aligned}$$
(3.5)
In the last step we used the fact that \(C(i)\ge 0\) and hence \(|h_i|\le J({\overline{W}}_i)+J(W_i)\). Therefore, \(\left( W_i(-),{\overline{W}}_i(-),\dots \right) \) is not a ground-state configuration. Moreover, one can show that
$$\begin{aligned}&{\mathscr {E}}_{I(G)}\left( W_i(-),{\overline{W}}_i(+),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(+),\dots \right) \nonumber \\&\quad = 2\left( -h(W_i)-\sum _{i(k)\in W_i}\sum _{l\in {\text {Onbh}}(i(k))}J_{i(k)l}\, s_{\tau (l,i(k))} -\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) \nonumber \\&\quad = 2\left( -h(W_i)-\sum _{i(k)\in W_i}\sum _{l\in {\text {Onbh}}(i(k))}J_{i(k)l}\, s_{\tau (l,i(k))}+|\partial W_i|\times M(W_i,h,J)-\epsilon \right) \nonumber \\&\quad \le 2\left( -h(W_i)+J(W_i)+|h(W_i)-J(W_i)|-\epsilon \right) =-2\epsilon <0 \end{aligned}$$
(3.6)
Hence, \(\left( W_i(+),{\overline{W}}_i(+),\dots \right) \) is also not a ground-state configuration.
Case 2:\(h(W_i)-J(W_i)< 0\,.\) We can easily see from Eq. (3.4) that \(\left( W_i(-),{\overline{W}}_i(-),\dots \right) \) is not a ground-state configuration.
Now we show that \(\left( W_i(+),{\overline{W}}_i(+),\dots \right) \) is also not a ground-state configuration. The proof is similar to the previous case, but one needs to take care of the extra asymmetry caused by \(h_i\). Let us start with the following expression
$$\begin{aligned}&{\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(-),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(+),\dots \right) \\&\quad =2\left( -\sum _{j(k)\in {\overline{W}}_i} h_{j(k)}-\sum _{j(k)\in {\overline{W}}_i}\sum _{l\in {\text {Onbh}}(j(k))}J_{j(k)l}\, s_{\tau (l,j(k))}-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) . \end{aligned}$$
For some \(s_{\tau (l,j(k))}\) with \(j(k)\in V({\overline{W}}_i)\), we have
$$\begin{aligned}&{\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(-),\dots \right) - {\mathscr {E}}_{I(G)}\left( W_i(+),{\overline{W}}_i(+),\dots \right) \nonumber \\&\quad = 2\left( -h({\overline{W}}_i)-J({\overline{W}}_i)-\sum _{i_p i_q \in \partial W_i} F_i^{pq} \right) \nonumber \\&\quad = 2\left( h(W_i)-h_i-J({\overline{W}}_i)+|\partial W_i|\times M(W_i,h,J)-\epsilon \right) \nonumber \\&\quad \le 2\left( h(W_i)-h_i-J({\overline{W}}_i)+|h(W_i)-h_i-J({\overline{W}}_i)|-\epsilon \right) . \end{aligned}$$
(3.7)
Case 2.1: If \(h(W_i)-h_i-J({\overline{W}}_i)\le 0\,,\) we can see from Eq. (3.7) that \(\left( W_i(+),{\overline{W}}_i(+),\dots \right) \) is not a ground-state configuration.
Case 2.2: If \(h(W_i)-h_i-J({\overline{W}}_i)>0\,,\) then by condition (3.1), one must have
$$\begin{aligned} h({\overline{W}}_i)\le h_i-J(W_i)\,, \end{aligned}$$
which is equivalent to
$$\begin{aligned} h(W_i)-J(W_i)\ge 0. \end{aligned}$$
Therefore, following the same as Case 1, we complete the proof. \(\square \)

3.1 Admissible minor embeddings

Now we show that conditions (3.1) and (3.3) should be satisfied for any reasonable minor embedding. We call a minor embedding, say (IhJF), admissible if the following condition is satisfied.
  • (IhJF) does not exclude any possible spin configuration for any \(i\in G\) in any embedded Ising problem.
Here F denotes the absolute value of the chain strength. Note that admissible minor embeddings are more suitable for practical purposes, since for general NP-hard problems we do not expect any pre-assignment for any logical qubit in G. It can be shown that the condition for admissible minor embeddings implies conditions (3.1) and (3.3).
Proof
(Verification)
$$\begin{aligned} \lnot \text {condition }(3.1) \vee \lnot \text {condition }(3.3) \end{aligned}$$
is equivalent to
$$\begin{aligned}&\left[ \left( -J({\overline{W}}_i)>h({\overline{W}}_i)\right) \wedge \left( J(W_i)>h(W_i)\right) \right] \nonumber \\&\quad \vee \left[ \left( -J(W_i)>h(W_i)\right) \wedge \left( J({\overline{W}}_i)>h({\overline{W}}_i)\right) \right] \\&\quad \implies h(W_i)<J(W_i) \quad \text {for some }W_i\subset \iota (i). \end{aligned}$$
By the Case 2 analysis in the proof of theorem 3.1, we see that \(\left( W_i(+),{\overline{W}}_i(+),\dots \right) \) is the only possible ground-state configuration for some problems, if \(F_i^{pq}>-M(W_i,h,J)\). This is a pre-assignment for the i-th logical qubit. Hence, it is not an admissible minor embedding. \(\square \)
Now, an immediate consequence of Theorem 3.1 gives
Theorem 3.4
Let (IhJF) be an admissible minor embedding and \(M(W_i;h,J)\) be defined in Eq. (3.2). Then \(M(W_i;h,J)\) is the best constant for all \(W_i\subset \iota (i)\). Hence,
$$\begin{aligned} \underset{W_i}{{\text {max}}}\left( \frac{1}{|\partial W_i|}{\text {min}}\Big \{|h(W_i)-J(W_i)|,|h(W_i)-h_i-J(\iota (i)\backslash W_i)| \Big \}\right) \end{aligned}$$
is the tightest bound for admissible minor embeddings.
Remark 3.5
(Importance of the distribution of\(h_{i(k)}\)) An admissible minor embedding (IhJF) can be viewed as a minimum requirement for perfect (non-broken) chains in the worst scenario. The minimum strength of \(F_i^{pq}\) is determined by \(h_{i(k)}\) and J via the expression of \(M(W_i;h,J)\). However, if we fix the values of the \(F_i^{pq}\)’s, we cannot choose the distribution of \(h_{i(k)}\) arbitrarily, even with condition (2.4) (\(\sum h_{i(k)}= h_i\)) satisfied. This will not cause any trouble if the \(F_i^{pq}\)’s are sufficiently large. However, when the \(F_i^{pq}\)’s are small compared with \(h_{i(k)}\), one needs to be more careful. More precisely, if we define \(C(W_i):=J(W_i)+|\partial (W_i)|\times F-|h(W_i)|\), then \(C(W_i)\) has to be greater or equal to zero for admissible minor embeddings. In other words, we must have \(|h(W_i)|\le J(W_i)+|\partial (W_i)|\times F\), which is an upper bound for \(h_{i(k)}\). This condition can be easily violated when \(h_{i(k)}\) is concentrated in a single physical qubit and F is comparably small. This is the situation when we apply the single distribution method as defined in [13]. Therefore, there are likely to be some non-admissible minor embeddings in the single distribution method.

4 Experimental results

In this subsection, we will compare different methods for estimating the optimum internal coupling strength to show how close they are to the experimental optima. We use the experimental data from Venturelli et al. [12], where fully connected Sherrington–Kirkpatrick spin-glass problems are implemented on the D–Wave DW2X machine. As we are only interested in optimal values of the internal coupling strength without broken chains, we extract the optimal values without any majority-vote post-processing. In Fig. 3, Choi’s first method is used in the comparison, since Choi’s second method does not match the h(i)-distribution used in [12]. All the h(i)’s are set to zero in [12], which violates condition (2.15). Therefore, only Choi’s first method and our work can be used to compare with the experimental results in [12]. As we can see from Fig. 3, our new tighter bound approaches more closely to the true experimental optima.

5 Conclusions and future work

There are many challenges for realizing a quantum annealer capable of outperforming classical computation for some classes of problems. Our work shows the importance of optimal ferromagnetic coupling strength and gives the best theoretical bound in our main Theorem 2.7. However, this is valid under the condition given in our second Theorem 3.1. In fact, we can give the best bound when the logical qubit has non-negative \(h_{i(k)}\)-fields. Our bound is certainly tighter than Choi’s bounds as shown in our toy example 2.3. We have introduced the concept of admissible minor embeddings, which means that condition (2.4) (\(\sum h_{i(k)} = h_i\)) is not sufficient to guarantee an admissible minor embedding when \(F_i^{pq}\) is small compared with \(h_{i(k)}\). Note that having an admissible minor embedding is necessary for practical reasons. For non-admissible minor embeddings, one could in theory achieve a better bound and obtain a correct ground state under quantum annealing, but this requires a pre-knowledge of the ground-state configuration of logical problem. The existence of an optimal coupling strength is shown in “Appendix A”.
Experimental results from quantum annealers show that our new method can be used to reduce the time-to-solution (TTS). However, this comes at a cost. The computational effort to calculate our new bound is \(O(D2^L)\) per logical qubit, where D is the degree of the logical qubit and L is the chain length. Note that for Choi’s two bounds, the computational effort are O(D) and O(DL), respectively. There are also other techniques that can be used to reduce TTS. For instance, the majority vote is one of the most popular “error-correction” methods used in the post-quantum-processing procedure for quantum annealers. As our method is a pre-quantum-processing procedure, one can employ both procedures to reduce TTS even further. Finally, we leave two open questions for further investigations.
  • How to assign admissible \(h_{i(k)}\)-fields to yield the best performance?
  • How to find the best distributions of physical couplers corresponding to the logical coupler for two adjacent minor-embedded logical qubits?

Acknowledgements

The research is based upon work (partially) supported by EPSRC (Grant Reference EP/R020159/1) and the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via the U.S. Army Research Office contract W911NF-17-C-0050. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. The authors would like to thank S. Severini for discussions and feedback on the first draft of the paper and N. Dattani for bring our attention to some related work. The authors are grateful to the referee for raising other important factors in minor-embedding and some valuable suggestions.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Anhänge

Appendix A: Job-shop scheduling problems on the D-Wave 2000Q machine

We will now show some experimental results obtained on the D-Wave quantum annealer. These illustrate the dependence on the internal coupling strength \(F_i^{pq}\) and show that there is an optimum value for it. In this subsection, we will use the performance of the NP-hard job-shop scheduling problem (JSP) on the D–Wave 2000Q to illustrate the importance of the best bound. Here we will follow the methodology introduced by the NASA Ames team [2325]. We will use time-to-solution as a benchmarking metric.
A typical job-shop scheduling problem (JSP) consists of a set of N jobs \(J = \{j_1,\dots , j_N \}\) that must be scheduled on a set of machines \(M =\{ m_1,\dots , m_P \}\). Each job consists of a sequence of operations that must be performed in a predefined order \(j_n = \{ O_{n,1}\rightarrow O_{n,2} \rightarrow \dots \rightarrow O_{n,L_n} \}\), where each job jn has \(L_n\) operations. Each operation \(O_{n,k}\) has a non-negative integer execution time \(\tau _{n,k}\) and has to be executed by an assigned machine \(m_{n,k}\in M\). The goal of solving JSP is to find an optimal scheduling that minimizes the makespan, i.e. the minimum time to finish all the jobs.
A generalized tabular representation of job shop scheduling problems is shown in Table 1.
Table 1
M-table and P-table for JSP
 
\(\text {Operation}_{*,1}\)
\(\text {Operation}_{*,2}\)
\(\dots \)
\(\text {Operation}_{*,K}\)
(a)Machine allocation
   \(\text {j}_1\)
\(\text {m}_{1,1}\)
\(\text {m}_{1,2}\)
\(\dots \)
\(\text {m}_{1,K}\)
   \(\text {j}_2\)
\(\text {m}_{2,1}\)
\(\text {m}_{2,2}\)
\(\dots \)
\(\text {m}_{2,K}\)
   \(\vdots \)
\(\vdots \)
\(\vdots \)
\(\ddots \)
\(\vdots \)
   \(\text {j}_N\)
\(\text {m}_{N,1}\)
\(\text {m}_{N,2}\)
\(\dots \)
\(\text {m}_{N,K}\)
(b) Time (per unit) spent on each operation
   \(\text {j}_1\)
\(\tau _{1,1}\)
\(\tau _{1,2}\)
\(\dots \)
\(\tau _{1,K}\)
   \(\text {j}_2\)
\(\tau _{2,1}\)
\(\tau _{2,2}\)
\(\dots \)
\(\tau _{2,K}\)
   \(\vdots \)
\(\vdots \)
\(\vdots \)
\(\ddots \)
\(\vdots \)
   \(\text {j}_N\)
\(\tau _{N,1}\)
\(\tau _{N,2}\)
\(\dots \)
\(\tau _{N,K}\)
For any job-shop scheduling problem, we can easily write it in the above representation by setting \(\tau _{n,k}=0\) for non-given operations and \(K=\max \limits _n L_n\). To translate the problem into an Ising Hamiltonian, we follow the method proposed by Venturelli et al. [25] and assign a set of binary variables for each operation, corresponding to the various possible discrete starting times the operation can have:
$$\begin{aligned} x_{n,k;t}=\left\{ \begin{aligned}&1\,:\qquad \text {operation}\,\, O_{n,k}\,\, \text {starts at time}\,\, t\,,\\&0\,:\qquad \text {otherwise}. \end{aligned} \right. \end{aligned}$$
Here t is bounded from above by the timespan T, which represents the maximum time we allow for all jobs to be completed. The resulting classical objective function (Hamiltonian) is given by
$$\begin{aligned} H_T(x)=E_{\text {problem}} \left( h_1(x)+h_2(x) +h_3(x) + h_4(x)\right) \,, \end{aligned}$$
(A.1)
where \(E_{\text {problem}}\) is the energy scaling parameter and each penalty term is explained briefly as follows.
  • \(h_1(x)=\sum _{n,k}\left( \sum _tx_{n,k;t}-1 \right) ^2\,\), checks that an operation must start once and only once.
  • \(h_2(x)=\sum _{n}\sum _{k<n}\left( \sum _{t+\tau _{n,k}>t^\prime }\, x_{n,k;t}\,x_{n,k+1;t^\prime }\right) \,\), ensures that the order of the operations within a job is preserved.
  • \(h_3(x)=\sum _{t+\tau _{nK}>T}\,x_{n,K;t}\,\), guarantees that the last operation in each job finishes by time T.
  • \(h_4(x)=\sum _{m}\left( \sum _{(n,k;t|n^\prime ,k^\prime ;t^\prime )\in R_m}x_{n,k;t}\,x_{n^\prime ,k^\prime ;t^\prime }\right) \,\), \(R_m\) consists of two penalty sets given in the following.
    • Forbidding operation \(O_{n^\prime ,k^\prime }\) from starting at \(t^\prime \) if there is another operation \(O_{n,k}\) still running.
    • Two operations cannot start at the same time, unless at least one of them has an execution time equal to zero.
Due to the detailed structure of the JSP Hamiltonian, we have [from Eq. (2.14)]:
$$\begin{aligned} C(i)=\frac{1}{2}E_\mathrm{problem}\,, \end{aligned}$$
and the spectral gap is given by
$$\begin{aligned} \Delta =E_\mathrm{problem}. \end{aligned}$$
Hence, an easy follow-up from Corollary 2.10 can be derived (or see [11]). i.e. If topological embeddings are chosen to embed the job shop scheduling problem Hamiltonian, we find that \(|F|\ge \frac{1}{2}(C(i)+\Delta )=\frac{3}{4} E_\mathrm{problem}\) is a sufficient lower bound which preserves the spectral gap of the original Hamiltonian.
Theorem 2.7 and Corollary 2.10 are based on an ideal quantum annealer. It is clear that l(i) depends only on the number of leaves in sub-trees of a minor embedding, which is independent of the lengths of branches within the trees. This is a consequence of Lagrange multiplier method, where a constrained optimization is equivalent to an unconstrained one by replacing the corresponding constraints into a penalty term with a large multiplier. In other words, in the ideal case there is no difference between short chains and long chains as long as Eqs. (2.15) and (2.16) are satisfied. However, this is not the case in the D-Wave 2000Q. Long chains are more often to be found broken [26], even if conditions (2.15) and (2.16) are satisfied. This is because of the noise from the environment. Due to engineering limitations, there is an upper bound, say \(\lambda \), for both logical and internal coupling strengths in the actual machine. Therefore, one has to rescale (i.e. decrease) the strength of the logical interaction in order for it to fit into the confined range. This leads us to the existence of an optimal coupling strength for chains in reality.
Figure 4 shows the importance of the optimal bound in the D-Wave 2000Q machine, as the shortest time to solution is achieved close to the theoretical bound that we derived in the previous sections.
The data is obtained by running 200 random JSPs with size \(N=3\), \(K=3\) and \(T=8\) on the D-Wave 2000Q machine. For each instance five minor embeddings are randomly generated. At each value of the internal coupling strength the probability of finding the correct JSP solution is experimentally determined by running the annealer 10,000 times for each embedding. The time-to-solution (TTS) is defined as the expected time taken to find the solution with probability \(p=99.9\%\) and is given by [27]:
$$\begin{aligned} \text {TTS}=t_a \left( \frac{\log [1-p]}{\log [1-s]} \right) \,, \end{aligned}$$
where s is the success probability for each embedding and \(t_a\) is the single-run annealing time, which is equal to \(2\mu s\) in our experiments. For each instance the minimum TTS for the five embeddings is recorded. The same procedure is conducted for the 200 random instances and then the mean TTS is the data shown in Fig. 4. Error bars are obtained by bootstrapping method and the confidence intervals are chosen to be \(95\%\). Figure 5 shows the main procedures in our experiments.
Note that the geometry of minor-embedding also affects the TTS. We therefore need to keep each minor-embedding unchanged when varying internal coupling strengths. Here we use the minimum TTS as it is more suitable when comparing with a classical computer. One could also use the average TTS over the five random embeddings, which will give a similar result. As it still remains an open question how to choose a good minor-embedding, the embeddings corresponding to our minimum TTS are by no means the best embeddings. Our task is to see the dependence of TTS on internal coupling strengths when the embedding is fixed.
We expect that the theoretical optimal bound plays an important role in a general quantum annealer and it is not constrained to JSPs.

Appendix B: An example for the existence of a better bound

Here we show that tighter bounds exists than those given in [11] by continuing the toy example of Fig. 2. According to Corollary 2.16, the assignments of local \(h_{i(k)}\) are given as in Fig. 6.
Let \(\left( {\begin{matrix} &{}s_1&{}\\ &{}s_0&{} \\ s_2&{} &{}s_3\end{matrix}}\right) \) denote the assignments of spin values for vertices 0, 1, 2 and 3. For example
$$\begin{aligned} \left( {\begin{matrix} &{}s_1&{}\\ &{}s_0&{} \\ s_2&{} &{}s_3\end{matrix}}\right) =\left( {\begin{matrix} &{}-&{}\\ &{}+&{} \\ +&{} &{}+\end{matrix}}\right) \end{aligned}$$
means that the spin value is \(-1\) for vertex 1 and the spin values are equal to \(+1\) for the other vertices.

Case 1 inequality

Now we have the following inequalities.
$$\begin{aligned} \frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}-&{}\\ &{}+&{} \\ +&{} &{}+\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}-&{}\\ &{}-&{} \\ -&{} &{}-\end{matrix}}\right) \right] \ge 2\times h-2\times 5h - F = -8h - F \end{aligned}$$
(B.1)
and
$$\begin{aligned} \frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}-&{}\\ &{}+&{} \\ +&{} &{}+\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}+&{} \\ +&{} &{}+\end{matrix}}\right) \right] \ge -h -5h -F = -6h - F. \end{aligned}$$
(B.2)
If the configuration \(\left( {\begin{matrix} &{}-&{}\\ &{}+&{} \\ +&{} &{}+\end{matrix}}\right) \) is not part of the ground-state configuration, then we must have the right-hand side of either inequality (B.1) or inequality (B.2) greater than zero. That is
$$\begin{aligned} F<-6h. \end{aligned}$$
(B.3)
Due to the symmetric property of our example, we have that \(\left( {\begin{matrix} &{}+&{}\\ &{}+&{} \\ -&{} &{}+\end{matrix}}\right) \) and \(\left( {\begin{matrix} &{}+&{}\\ &{}+&{} \\ +&{} &{}-\end{matrix}}\right) \) cannot be part of the ground-state configuration if \(F<-6h\).

Case 2 inequality

Using the same method, one can derive that
$$\begin{aligned} \frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}-&{} \\ -&{} &{}-\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}-&{}\\ &{}-&{} \\ -&{} &{}-\end{matrix}}\right) \right] \ge h- 5h - F = -4h - F \end{aligned}$$
(B.4)
and
$$\begin{aligned} \frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}-&{} \\ -&{} &{}-\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}+&{} \\ +&{} &{}+\end{matrix}}\right) \right] \ge -2\times h -2\times 5h -F = -12h - F. \end{aligned}$$
(B.5)
That is
$$\begin{aligned} F<-4h. \end{aligned}$$
(B.6)
Again, due to the symmetric property of our example, we have that \(\left( {\begin{matrix} &{}-&{}\\ &{}-&{} \\ +&{} &{}-\end{matrix}}\right) \) and \(\left( {\begin{matrix} &{}-&{}\\ &{}-&{} \\ -&{} &{}+\end{matrix}}\right) \) cannot be part of the ground-state configuration if \(F<-4h\).

Case 3 inequality

Using the same method, one can derive that
$$\begin{aligned} \frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}-&{} \\ +&{} &{}-\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}-&{}\\ &{}-&{} \\ -&{} &{}-\end{matrix}}\right) \right] \ge 2\times h -2\times 5h -2\times F = -12h - 2F \end{aligned}$$
(B.7)
and
$$\begin{aligned} \frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}-&{} \\ +&{} &{}-\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}+&{} \\ +&{} &{}+\end{matrix}}\right) \right] \ge -h - 5h -2\times F = -6h - 2F. \end{aligned}$$
(B.8)
That is
$$\begin{aligned} F<-3h. \end{aligned}$$
(B.9)
The symmetric property of our example tells us that \(\left( {\begin{matrix} &{}-&{}\\ &{}-&{} \\ +&{} &{}+\end{matrix}}\right) \) and \(\left( {\begin{matrix} &{}+&{}\\ &{}-&{} \\ -&{} &{}+\end{matrix}}\right) \) cannot be part of the ground-state configuration if \(F<-3h\).

Case 4 inequality

Using the same method, one can derive that
$$\begin{aligned} \frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}+&{} \\ -&{} &{}-\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}-&{}\\ &{}-&{} \\ -&{} &{}-\end{matrix}}\right) \right] \ge h - 5h -2\times F = -4h - 2F \end{aligned}$$
(B.10)
and
$$\begin{aligned}&\frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}+&{} \\ -&{} &{}-\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}+&{} \\ +&{} &{}+\end{matrix}}\right) \right] \nonumber \\&\quad \ge -2\times h - 2\times 5h -2\times F = -12h - 2F. \end{aligned}$$
(B.11)
That is
$$\begin{aligned} F<-2h. \end{aligned}$$
(B.12)
According to the symmetric property of our example, we have that \(\left( {\begin{matrix} &{}-&{}\\ &{}+&{} \\ +&{} &{}-\end{matrix}}\right) \) and \(\left( {\begin{matrix} &{}-&{}\\ &{}+&{} \\ -&{} &{}+\end{matrix}}\right) \) cannot be part of the ground-state configuration if \(F<-2h\).

Case 5 inequality

Using the same method, one can derive that
$$\begin{aligned} \frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}-&{}\\ &{}+&{} \\ -&{} &{}-\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}-&{}\\ &{}-&{} \\ -&{} &{}-\end{matrix}}\right) \right] \ge 0\times h - 3\times F = - 3F \end{aligned}$$
(B.13)
and
$$\begin{aligned}&\frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}-&{}\\ &{}+&{} \\ -&{} &{}-\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}+&{} \\ +&{} &{}+\end{matrix}}\right) \right] \nonumber \\&\quad \ge -3\times h - 3\times 5h -3\times F = -18h - 3F. \end{aligned}$$
(B.14)
That is
$$\begin{aligned} F<0. \end{aligned}$$
(B.15)

Case 6 inequality

Using the same method, one can derive that
$$\begin{aligned} \frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}-&{} \\ +&{} &{}+\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}-&{}\\ &{}-&{} \\ -&{} &{}-\end{matrix}}\right) \right] \ge 3\times h -3\times 5h - 3\times F = -12h - 3F\nonumber \\ \end{aligned}$$
(B.16)
and
$$\begin{aligned} \frac{1}{2}\left[ {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}-&{} \\ +&{} &{}+\end{matrix}}\right) - {\mathscr {E}}\left( {\begin{matrix} &{}+&{}\\ &{}+&{} \\ +&{} &{}+\end{matrix}}\right) \right] \ge -0\times h -3\times F = - 3F . \end{aligned}$$
(B.17)
That is
$$\begin{aligned} F<0. \end{aligned}$$
(B.18)
Now from inequalities (B.3), (B.6), (B.9), (B.12), (B.15) and (B.18), we have that if
$$\begin{aligned} F<-6h\,, \end{aligned}$$
(B.19)
only homogeneous configurations within \(\iota (i)\) (i.e. \(s_0=s_1=s_2=s_3\)) are possible for the ground-state configuration. Note that this is a better bound that the one (2.21) given by Corollary 2.10.

Appendix C: Best bound on the example

Here we show how to derive the best bound on the internal coupling strength using the toy model of Fig. 2 as an example. By Remark 3.3, we have that the best bound is given by
$$\begin{aligned} M_i=\min _{h_{i(k)}} M_i\left( h_{i(k)}\right) . \end{aligned}$$
Now let \(h_{i(k)}=\{a,b,c,d\}\,\) and we have the example as shown in Fig. 7. Now follow the same method as in “Appendix B”, we conclude from Case 1 and 2 inequalities that
$$\begin{aligned} \left\{ \begin{aligned}&F<-(5h+a)\,,\\&F<-(5h-a). \end{aligned} \right. \end{aligned}$$
(C.1)
Therefore we have \(F<-5h\) regardless of what value of a takes. This shows that the best constant is \(M_i=5h\,\).
Fußnoten
1
Experiments are currently underway on a flux-qubit annealer with degree 15
 
Literatur
1.
Zurück zum Zitat Harris, R., Sato, Y., Berkley, A.J., Reis, M., Altomare, F., Amin, M.H., Boothby, K., Bunyk, P., Deng, C., Enderud, C., Huang, S., Hoskinson, E., Johnson, M.W., Ladizinsky, E., Ladizinsky, N., Lanting, T., Li, R., Medina, T., Molavi, R., Neufeld, R., Oh, T., Pavlov, I., Perminov, I., Poulin-Lamarre, G., Rich, C., Smirnov, A., Swenson, L., Tsai, N., Volkmann, M., Whittaker, J., Yao, J.: Phase transitions in a programmable quantum spin glass simulator. Science 361, 162–165 (2018)ADSMathSciNetCrossRef Harris, R., Sato, Y., Berkley, A.J., Reis, M., Altomare, F., Amin, M.H., Boothby, K., Bunyk, P., Deng, C., Enderud, C., Huang, S., Hoskinson, E., Johnson, M.W., Ladizinsky, E., Ladizinsky, N., Lanting, T., Li, R., Medina, T., Molavi, R., Neufeld, R., Oh, T., Pavlov, I., Perminov, I., Poulin-Lamarre, G., Rich, C., Smirnov, A., Swenson, L., Tsai, N., Volkmann, M., Whittaker, J., Yao, J.: Phase transitions in a programmable quantum spin glass simulator. Science 361, 162–165 (2018)ADSMathSciNetCrossRef
2.
Zurück zum Zitat King, A.D., Carrasquilla, J., Raymond, J., Ozfidan, I., Andriyash, E., Berkley, A., Reis, M., Lanting, T., Harris, R., Altomare, F., Boothby, K., Bunky, P.I., Enderud, C., Frechette, A., Hoskinson, E., Ladizinsky, N., Oh, T., Poulin-Lamarre, G., Rich, C., Sato, Y., Smirnov, A.Y., Swenson, L.J., Volkmann, M.H., Whittaker, J., Yao, J., Ladizinsky, E., Johnson, M.W., Hilton, J., Amin, M.H.: Observation of topological phenomena in a programmable lattice of 1,800 qubits. Nature 560, 456–460 (2018)ADSCrossRef King, A.D., Carrasquilla, J., Raymond, J., Ozfidan, I., Andriyash, E., Berkley, A., Reis, M., Lanting, T., Harris, R., Altomare, F., Boothby, K., Bunky, P.I., Enderud, C., Frechette, A., Hoskinson, E., Ladizinsky, N., Oh, T., Poulin-Lamarre, G., Rich, C., Sato, Y., Smirnov, A.Y., Swenson, L.J., Volkmann, M.H., Whittaker, J., Yao, J., Ladizinsky, E., Johnson, M.W., Hilton, J., Amin, M.H.: Observation of topological phenomena in a programmable lattice of 1,800 qubits. Nature 560, 456–460 (2018)ADSCrossRef
3.
Zurück zum Zitat Born, M., Fock, V.A.: Beweis des Adiabatensatzes. Zeitschrift für Physik A 51, 165–180 (1928)ADSCrossRef Born, M., Fock, V.A.: Beweis des Adiabatensatzes. Zeitschrift für Physik A 51, 165–180 (1928)ADSCrossRef
4.
Zurück zum Zitat Kato, T.: On the adiabatic theorem of quantum mechanics. J. Phys. Soc. Jpn. 5, 435–439 (1950)ADSCrossRef Kato, T.: On the adiabatic theorem of quantum mechanics. J. Phys. Soc. Jpn. 5, 435–439 (1950)ADSCrossRef
6.
Zurück zum Zitat Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., Preda, D.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–476 (2001)ADSMathSciNetCrossRef Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., Preda, D.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–476 (2001)ADSMathSciNetCrossRef
8.
Zurück zum Zitat Kafri, D., Quintana, C., Chen, Y., Shabani, A., Martinis, J.M., Neven, H.: Tunable inductive coupling of superconducting qubits in the strongly nonlinear regime. Phys. Rev. A 95, 052333 (2017)ADSCrossRef Kafri, D., Quintana, C., Chen, Y., Shabani, A., Martinis, J.M., Neven, H.: Tunable inductive coupling of superconducting qubits in the strongly nonlinear regime. Phys. Rev. A 95, 052333 (2017)ADSCrossRef
9.
Zurück zum Zitat Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355 (1998)ADSCrossRef Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355 (1998)ADSCrossRef
10.
Zurück zum Zitat Lucas, A.: Ising formulations of many NP problems. Front. Phys. 2, 5 (2014)CrossRef Lucas, A.: Ising formulations of many NP problems. Front. Phys. 2, 5 (2014)CrossRef
11.
Zurück zum Zitat Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7, 193–209 (2008)MathSciNetCrossRef Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7, 193–209 (2008)MathSciNetCrossRef
12.
Zurück zum Zitat Venturelli, D., Mandrà, S., Knysh, S., O’Gorman, B., Biswas, R., Smelyanskiy, V.: Quantum optimization of fully connected spin glasses. Phys. Rev. X 5, 031040 (2015) Venturelli, D., Mandrà, S., Knysh, S., O’Gorman, B., Biswas, R., Smelyanskiy, V.: Quantum optimization of fully connected spin glasses. Phys. Rev. X 5, 031040 (2015)
13.
Zurück zum Zitat Pudenz, K.L.: Parameter setting for quantum annealers. In: 20th IEEE High Performance Embedded Computing Workshop Proceedings. arxiv:1611.07552 (2016) Pudenz, K.L.: Parameter setting for quantum annealers. In: 20th IEEE High Performance Embedded Computing Workshop Proceedings. arxiv:​1611.​07552 (2016)
14.
Zurück zum Zitat Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10, 343–353 (2011)MathSciNetCrossRef Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10, 343–353 (2011)MathSciNetCrossRef
15.
Zurück zum Zitat Boothby, T., King, A., Roy, A.: Fast clique minor generation in Chimera qubit connectivity graphs. Quantum Inf. Process. 15, 495–508 (2016)ADSMathSciNetCrossRef Boothby, T., King, A., Roy, A.: Fast clique minor generation in Chimera qubit connectivity graphs. Quantum Inf. Process. 15, 495–508 (2016)ADSMathSciNetCrossRef
16.
Zurück zum Zitat Chancellor, N., Zohren, S., Warburton, P.A.: Circuit design for multi-body interactions in superconducting quantum annealing systems with applications to a scalable architecture. npj Quantum Inf. 3:21, 1–7 (2017) Chancellor, N., Zohren, S., Warburton, P.A.: Circuit design for multi-body interactions in superconducting quantum annealing systems with applications to a scalable architecture. npj Quantum Inf. 3:21, 1–7 (2017)
17.
Zurück zum Zitat Tanburn, R., Okada, E., Dattani, N.: Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 1: The “deduc-reduc” method and its application to quantum factorization of numbers. arxiv:1508.04816 (2015) Tanburn, R., Okada, E., Dattani, N.: Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 1: The “deduc-reduc” method and its application to quantum factorization of numbers. arxiv:​1508.​04816 (2015)
18.
Zurück zum Zitat Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 2: the “split-reduc” method and its application to quantum determination of Ramsey numbers. arxiv:1508.07190 (2015) Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 2: the “split-reduc” method and its application to quantum determination of Ramsey numbers. arxiv:​1508.​07190 (2015)
19.
Zurück zum Zitat Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26, 147–159 (2004)CrossRef Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26, 147–159 (2004)CrossRef
22.
Zurück zum Zitat Albash, T., Boixo, S., Lidar, D.A., Zanardi, P.: Quantum adiabatic Markovian master equations. New J. Phys. 14, 123016 (2012)ADSMathSciNetCrossRef Albash, T., Boixo, S., Lidar, D.A., Zanardi, P.: Quantum adiabatic Markovian master equations. New J. Phys. 14, 123016 (2012)ADSMathSciNetCrossRef
23.
Zurück zum Zitat Rieffel, E.G., Venturelli, D., Do, M., Hen, I., Frank, J.: Parametrized Families of Hard Planning Problems from Phase Transitions. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence AAAI-14 (2014) Rieffel, E.G., Venturelli, D., Do, M., Hen, I., Frank, J.: Parametrized Families of Hard Planning Problems from Phase Transitions. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence AAAI-14 (2014)
24.
Zurück zum Zitat Rieffel, E.G., Venturelli, D., O’Gorman, B., Do, M.B., Prystay, E.M., Smelyanskiy, V.N.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf. Process. 14, 1–36 (2015)ADSCrossRef Rieffel, E.G., Venturelli, D., O’Gorman, B., Do, M.B., Prystay, E.M., Smelyanskiy, V.N.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf. Process. 14, 1–36 (2015)ADSCrossRef
25.
Zurück zum Zitat Venturelli, D., Marchand, D., Rojo, G.: Job Shop Scheduling Solver based on Quantum Annealing. COPLAS-16 292. arxiv:1506.08479 (2016) Venturelli, D., Marchand, D., Rojo, G.: Job Shop Scheduling Solver based on Quantum Annealing. COPLAS-16 292. arxiv:​1506.​08479 (2016)
26.
Zurück zum Zitat Vinci, W., Albash, T., Paz-Silva, G., Hen, I., Lidar, D.A.: Quantum annealing correction with minor embedding. Phys. Rev. A 92, 042310 (2015)ADSCrossRef Vinci, W., Albash, T., Paz-Silva, G., Hen, I., Lidar, D.A.: Quantum annealing correction with minor embedding. Phys. Rev. A 92, 042310 (2015)ADSCrossRef
27.
Zurück zum Zitat Ronnow, T.F., Wang, Z., Job, J., Boixo, S., Isakov, S.V., Wecker, D., Martinis, J.M., Lidar, D.A., Troyer, M.: Defining and detecting quantum speedup. Science 345, 420–424 (2014)ADSCrossRef Ronnow, T.F., Wang, Z., Job, J., Boixo, S., Isakov, S.V., Wecker, D., Martinis, J.M., Lidar, D.A., Troyer, M.: Defining and detecting quantum speedup. Science 345, 420–424 (2014)ADSCrossRef
Metadaten
Titel
Minimizing minor embedding energy: an application in quantum annealing
verfasst von
Yan-Long Fang
P. A. Warburton
Publikationsdatum
01.07.2020
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 7/2020
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-020-02681-x

Weitere Artikel der Ausgabe 7/2020

Quantum Information Processing 7/2020 Zur Ausgabe

Neuer Inhalt