D-Wave Systems Inc. builds annealing devices that exhibit quantum effects. These devices as well as other physical systems implement a programmable Ising model of the form.
\begin{equation}
H = \sum_i c_i Z_i+\sum_{ ij} c_{ij}Z_iZ_j
\end{equation}
Where zed is the familiar Pauli matrix.
The approach I took program D-Wave’s computer was to encode universal computation into its ground state by relying on specific Hamiltonians that embed logical Boolean operations. This is what I’m going to briefly tell you about here.
Different methods also exist to emulate many-body interactions with two-body Hamiltonians, see the section on many-body to two-body decomposition gadget Hamiltonians. We have sometimes called the Ising formulation of logical functions:
- penalty functions (penalty Hamiltonians)
- classical/energy cost functions
- Ising model many-body decompositions
- ground state spin logic
- gates for adiabatic quantum computing
- classical or exact gadgets
We’ve done various projects that have relied on our development of different embeddings and we’ve focused on developing methods to treat the efficiency of the embedding directly.
Embedding Boolean circuits into Ising spins
The following paper developed the methods to synthesize classical circuits into the ground states of such a system. In slightly different words, it encodes universal computation into the ground states of Ising lattices.
Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
Jacob Biamonte
Physical Review A 77, 052331 (2008)
This work realized all of the basic gates and logical operations and included methods to emulate higher-order couplings with the use of only two-body interactions together with ancillary, slack spins. We later revisited the ideas again, this time focusing on the new results which emerged and their relationship, as well as Hamiltonian symmetry.
Ground State Spin Logic
James Whitfield, Mauro Faccin and Jacob Biamonte
European Physics Letters 99, 57004 (2012)
The idea goes like this. We use diagonal Hamiltonians of $$N$$ spins like this
\begin{equation}
H = \sum_i c_i \sigma_i+\sum_{ ij} c_{ij}
\sigma_i\sigma_j+\sum_{ijk} c_{ijk}\sigma_i\sigma_j\sigma_k+…
\label{eq:H1}
\end{equation}
with $$\sigma \equiv \sigma^z$$ defined by
$$\sigma=\ket{0}\bra{0}-\ket{1}\bra{1}$$.
Since the eigenvalues of $$\sigma$$ are $$\pm 1$$, we identify Boolean
variable, $$x\in\{0,1\}$$, with $$(\id-\sigma)/2$$ instead of $$\sigma$$ itself.
The subscript of each $$\sigma$$ indicates which spin the operator acts on. Terms
such as $$\sigma_i\sigma_j$$ are understood as the tensor product $$\sigma_i\otimes\sigma_j$$.
Limiting the Hamiltonian above to
two-spin interactions yields an
experimentally relevant tunable Ising Hamiltonian which continues to be the primary focus.
The idea of ground state spin logic is to embed Boolean functions, $$f:\{0,1\}^n\rightarrow\{0,1\}^m$$, into the ground state
subspace, $$\LL(H_{f(\mathbf{x})})$$, of spin Hamiltonian
$H_{f(\mathbf{x})}(\sigma_i,\sigma_j,\cdots,\sigma_k)$
acting on the spins $\sigma_i$, $\sigma_j$, \ldots, $\sigma_k$.
As an example, consider the universal \NAND~gate defined by
$\NAND(x,y)=\bar x\lor\bar y$.
The corresponding Hamiltonian, $H_{\bar x\lor\bar y}(\sigma_1,\sigma_2,\sigma_3)$, should
have the following ground state subspace
\begin{eqnarray}
\LL(H_{\bar x\lor\bar y})
&=& \Span\{\ket{x}\ket{y}\ket{{\bar{x}\lor \bar{y}}}\}\\
&=& \Span\{\ket{001},\ket{011},\ket{101},\ket{110}\}\nonumber
\end{eqnarray}
Using the $\sigma$ matrices, such a Hamiltonian is given in \cite{Crosson10} as,
\begin{equation}
H_{\bar{x}\lor\bar{y}}(\sigma_1,\sigma_2,\sigma_3)= 2\id+\left( \id + \sigma_1+\sigma_2 -\sigma_1\sigma_2\right)\sigma_3
\label{eq:nand1}
\end{equation}
This construction uses a three-spin interaction which can be
replaced using the same number of spins and only two-spin
interactions. This was done in~\cite{JDB08,Gu12} by penalizing
and rewarding certain interactions such that the ground state subspace is not
altered while the higher energy eigenstates are.
Physical Review A 77, 052331 (2008)
Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
Jacob Biamonte
Physical Review A 77, 052331 (2008)
Abstract. An algebraic method has been developed which allows one to engineer several energy levels including the low-energy subspace of interacting spin systems. By introducing ancillary qubits, this approach allows k-body interactions to be captured exactly using 2-body Hamiltonians. Our method works when all terms in the Hamiltonian share the same basis and has no dependence on perturbation theory or the associated large spectral gap. Our methods allow problem instance solutions to be embedded into the ground energy state of Ising spin systems. Adiabatic evolution might then be used to place a computational system into it’s ground state.
European Physics Letters 99, 57004 (2012)
Ground State Spin Logic
James Whitfield, Mauro Faccin and Jacob Biamonte
European Physics Letters 99, 57004 (2012)
Abstract. Designing and optimizing cost functions and energy landscapes is a problem encountered in many fields of science and engineering. These landscapes and cost functions can be embedded and annealed in experimentally controllable spin Hamiltonians. Using an approach based on group theory and symmetries, we examine the embedding of Boolean logic gates into the ground-state subspace of such spin systems. We describe parameterized families of diagonal Hamiltonians and symmetry operations which preserve the ground-state subspace encoding the truth tables of Boolean formulas. The ground-state embeddings of adder circuits are used to illustrate how gates are combined and simplified using symmetry. Our work is relevant for experimental demonstrations of ground-state embeddings found in both classical optimization as well as adiabatic quantum optimization.
