Proof of efficient, parallelized, universal adiabatic quantum computation

We give a careful proof that a parallelized version of adiabatic quantum computation can efficiently simulate universal gate model quantum computation. The proof specifies an explicit parameter-dependent Hamiltonian $H\left(\lambda \right)$ that is based on ground state quantum computation [Mizel et al., Phys. Rev. A. 63, 040302 (2001)]. We treat both a 1-dimensional configuration in which qubits on a line undergo nearest-neighbor 2-qubit gates and an all-to-all configuration in which every qubit undergoes 2-qubit gates with every other qubit in the system.

Figure 1

Schematic physical apparatus for realizing $H\left(1\right)$ in the case of a single qubit. The $2\times 5$ array of nanocrystals is assumed to contain a single itinerant electron that is free to migrate around the array. Each nanocrystal is imagined to house a single available orbital. Black arrows indicate tunneling matrix elements from orbital to orbital from the beginning of the program to the end. (Since the Hamiltonian is Hermitian, the electron can tunnel along or opposite the arrows.)

Figure 2

Schematic physical apparatus for realizing Hamiltonian (3) in the case $M=2, N=4$. (a) Schematic physical apparatus for realizing the Hamiltonian (3) in the case of $M=2$ qubits. (b) Isolated single time step of (a) in which each qubit undergoes a 1-qubit gate. (c) Isolated single time step, suitable for replacing (b), in which 2 qubits undergo a 2-qubit gate.

Figure 3

Schematic physical apparatus for realizing Hamiltonian (3) in the case that $U=\mathcal{I}$ at every time step. (a) Schematic physical apparatus for realizing Hamiltonian (3) for $M=2$ qubits. Just the $\left|0_{i-1}\right.〉$ to $\left|0_i\right.〉$ transitions are shown; similar figures including $\left|1_{i-1}\right.〉$ to $\left|1_i\right.〉$ transmissions are omitted. (b) Isolated single time step of (a) in which each qubit undergoes a 1-qubit gate. Just the $\left|0_{i-1}\right.〉$ to $\left|0_i\right.〉$ transitions are shown. (c) Isolated single time step, suitable for replacing (b), in which 2 qubits undergo a 2-qubit gate with $U=\mathcal{I}\otimes \mathcal{I}$. Just the $\left|0_{i-1}\right.〉\otimes \left|0_{j-1}\right.〉$ to $\left|0_i\right.〉\otimes \left|0_j\right.〉$ transition is shown.

Figure 4

Schematic physical apparatus for realizing the one-dimensional configuration of Definition 2. The Hamiltonian is assumed to have been simplified using Lemma 2, so a single itinerant electron migrates in each array of 8 nanocrystals. Black lines denote tunneling matrix elements between orbitals housed on different nanocrystals. Yellow lines denote $\lambda$-dependent tunneling matrix elements.

Figure 5

1-dimensional chain.

Figure 6

Graph for a sample 2-dimensional chain with $N_1=N_2=4$.

Figure 7

Sample $\varphi \left(\mathbf{i}\right)$ for 2-dimensional chain.

Figure 8

Sample $\psi \left(\mathbf{i}\right)$ for 2-dimensional chain.

Figure 9

Sample $\psi (P^{\left(2\right)}(\mathbf{i},T^{\left(2\right)}))$ for 2-dimensional chain.

Figure 10

Sample $\psi (P(\mathbf{i},T))$ for 2-dimensional chain.

Figure 11

Schematic physical apparatus for realizing the configuration of Example 4.

Figure 12

$Q^{\left(5\right)}((0,0,1,0,3),t)$. Note $Q^{\left(5\right)}((0,0,1,0,3),t)=Q^{\left(5\right)}((0,0,1,0,3),5)$ for $t=6,\cdots ,10$. (a) Configuration of particles with $i_1=0, i_2=0, i_3=1, i_4=0, i_5=3$, corresponding to point $Q^{\left(5\right)}((0,0,1,0,3),0)=(0,0,1,0,3)$. (b) Configuration of particles with $i_1=0, i_2=0, i_3=0, i_4=1, i_5=3$, corresponding to point $Q^{\left(5\right)}((0,0,1,0,3),1)=(0,0,0,1,3)$. (c) Configuration of particles after downward sweep with $i_1=1, i_2=0, i_3=0, i_4=1, i_5=3$, corresponding to point $Q^{\left(5\right)}((0,0,1,0,3),2)=(1,0,0,1,3)$. (d) Configuration of particles with $i_1=0, i_2=1, i_3=0, i_4=1, i_5=3$, corresponding to point $Q^{\left(5\right)}((0,0,1,0,3),3)=(0,1,0,1,3)$. (e) Configuration of particles with $i_1=0, i_2=0, i_3=1, i_4=1, i_5=3$, corresponding to point $Q^{\left(5\right)}((0,0,1,0,3),4)=(0,0,1,1,3)$. (f) Configuration of particles after upward sweep with $i_1=0, i_2=0, i_3=1, i_4=0, i_5=4$, corresponding to point $Q^{\left(5\right)}((0,0,1,0,3),5)=(0,0,1,0,4)$ in the graph. Value of $i_5$ has advanced by 1 while all other coordinates $i_{\alpha }$ have returned to their initial values.