Universal Computation by Multiparticle Quantum Walk

See allHide authors and affiliations

Science  15 Feb 2013:
Vol. 339, Issue 6121, pp. 791-794
DOI: 10.1126/science.1229957


A quantum walk is a time-homogeneous quantum-mechanical process on a graph defined by analogy to classical random walk. The quantum walker is a particle that moves from a given vertex to adjacent vertices in quantum superposition. We consider a generalization to interacting systems with more than one walker, such as the Bose-Hubbard model and systems of fermions or distinguishable particles with nearest-neighbor interactions, and show that multiparticle quantum walk is capable of universal quantum computation. Our construction could, in principle, be used as an architecture for building a scalable quantum computer with no need for time-dependent control.

Quantum walk is a versatile and intuitive framework for developing quantum algorithms. Applications of continuous- (1) and discrete-time (2, 3) models of quantum walk include an example of exponential speed-up over classical computation (4) and optimal algorithms for element distinctness (5) and formula evaluation (6).

Quantum walk is also a powerful computational model capable of performing any quantum computation (7). However, the graph used to perform a computation on n qubits is exponentially large as a function of n. Such a quantum walk cannot be efficiently implemented using an architecture where each vertex of the graph occupies a different spatial location. Nevertheless, many nonscalable implementations of quantum walk have been carried out (810) despite substantial overhead that precludes efficient universal quantum computation.

We consider generalizations of quantum walk with many interacting walkers and show that multiparticle quantum walk is universal for quantum computation using a graph of polynomial size. We present efficient universal constructions based on the Bose-Hubbard model, fermions with nearest-neighbor interactions, and distinguishable particles with nearest-neighbor interactions. We also show that almost any interaction gives rise to universality when using indistinguishable particles.

Because our graphs are exponentially smaller than those in reference (7), our construction is amenable to experimental implementation using an architecture where vertices of the graph occupy different spatial locations (although we leave issues of fault tolerance for future work). Current two-particle experiments involve only noninteracting bosons (1114), but other experiments could realize interactions. Specifically, a Bose-Hubbard model of the type we consider could naturally be realized in a variety of systems, including traditional nonlinear optics (15), neutral atoms in optical lattices (16, 17), or photons in arrays of superconducting qubits (18).

Multiparticle quantum walk has been considered as an algorithmic tool for solving graph isomorphism (19), although this technique has known limitations (20). Other previous work has focused on two-particle quantum walk (1114, 2125) and multiparticle quantum walk without interactions (1114, 21, 22, 26). Here, we consider multiparticle quantum walks with interactions, which seem to be required to achieve computational universality (27, 28).

It has been shown that systems of interacting particles on a lattice can perform universal computation with a time-dependent Hamiltonian (29, 30). However, because of the time dependence, such a system should not be considered a quantum walk. In our scheme, the Hamiltonian is time-independent and the computation is encoded entirely in the unweighted graph on which the particles interact.

In a multiparticle quantum walk, particles (either distinguishable or indistinguishable) interact in a local manner on a simple graph G with vertex set V(G) and edge set E(G). The Hilbert space for m distinguishable particles on G is spanned by the basis{|i1,,im:i1,,imV(G)}(1)where iw is the location of the wth particle. A continuous-time multiparticle quantum walk of m distinguishable particles on G is generated by a time-independent HamiltonianHG(m)=w=1m(i,j)E(G)(|ij|w+|ji|w)+i,jV(G)Uij(n^i,n^j)(2)where the subscript w indicates that the operator acts nontrivially only on the location register for the wth particle. Here, the operators n^i and n^j count the numbers of particles at vertices i and j, respectively (explicitly, n^i=w=1m|ii|w).

The first term of Eq. 2 moves particles between adjacent vertices, and the second term is an interaction between particles. We assume that Uij is zero whenever one of its arguments evaluates to zero and that Uii is zero if there is only one particle at vertex i (thus, the Hamiltonian for a single particle reduces to that of a standard quantum walk). We also assume that the interaction Uij only depends on the distance between i and j and has a constant range. Finally, we assume that the norm of each term Uij is upper-bounded by a polynomial in m.

Indistinguishable particles can be represented in the basis specified in Eq. 1 as states that are either symmetric (for bosons) or antisymmetric (for fermions) under the interchange of any two particles. The Hamiltonian preserves both the symmetric and antisymmetric subspaces and, restricted to the appropriate subspace, generates a quantum walk of m bosons or m fermions on G.

This framework includes well-known interacting many-body systems defined on graphs. For example, it includes the Bose-Hubbard model, with interaction Uij(n^i,n^j)=(U/2)δi,jn^i(n^i1). It also includes systems with nearest-neighbor interactions, such as with Uij(n^i,n^j)=Uδ(i,j)E(G)n^in^j.

The dynamics of our scheme can be understood by considering scattering events involving only one or two particles and can be analyzed using a discrete version of scattering theory (31). We first discuss single-particle scattering.

Consider a single-particle quantum walk on an infinite graph G obtained by attaching a semi-infinite path to each of N chosen vertices of an arbitrary (N + m)–vertex graph G^ (Fig. 1A). A particle is initially prepared in a state that moves (under Schrödinger time evolution) toward the subgraph G^ along one of the semi-infinite paths. After scattering through the subgraph, the particle moves away from, in superposition along the semi-infinite paths. To understand this process, we discuss the scattering eigenstates of the Hamiltonian HG(1).

Fig. 1

(A) The infinite graph G. The vertices labeled (1, j) belong to Embedded Image. (B) Encoded Embedded Image (left) and Embedded Image (right).

Given the graphG^, for each momentum k(π,0) and path j{1,2,N}, there is a scattering state |scj(k) with amplitudesx,q|scj(k)=eikxδqj+eikxSqj(k)(3)on the semi-infinite paths [with the labeling (x,q) of vertices on the paths as in Fig. 1A], where S(k) is an N by N unitary matrix called the S-matrix [see section S1 of (32)]. The state |scj(k) is an eigenstate of HG(1) with energy 2 cos k.

A wave packet is a normalized state with most of its amplitude on scattering states with momenta close to some particular value. The scattering state |scj(k) gives us information about how a wave packet with momenta near k located on path j scatters from G^. The wave packet initially moves toward the graph with speed |dEdk|=|2sink|. After scattering, the amplitude associated with finding the wave packet on path q is Sqj(k). This picture of the scattering process remains valid when the finite extent of the wave packets is taken into account and when the infinite paths are truncated to be long but finite [section S5 of (32)].

We now consider scattering of two indistinguishable particles on an infinite path. Translation symmetry makes this system easier to analyze than more general two-particle quantum walks (33). Consider two indistinguishable particles initially prepared in spatially separated wave packets moving toward each other along a path with momenta k1(π,0) and k2(0,π). After scattering, the particles move apart with momenta k1 and k2 (by conservation of energy and momentum). The effect of the interaction is to change the global phase of the wave function after scattering (relative to the case with no interaction). This phase can be calculated given the two momenta, the interaction U, and the particle type [section S2 of (32)]. In our scheme, we use k1 = –π/2 and k2 = π/4, and we write eiθ for the phase acquired at these momenta. This picture of the two-particle scattering process holds even on a long (but finite) path and with finite wave packets [section S5 of (32)].

We now describe our scheme for universal computation by multiparticle quantum walk. We encode n logical qubits into the locations of n indistinguishable particles on a graph of size poly(n) [see section S3.2 of (32) for a refinement of our scheme using distinguishable particles]. In addition to these n particles, we use another particle to encode an ancilla qubit that facilitates two-qubit gates. We call the original n qubits computational qubits, and we call the ancilla qubit the mediator qubit. Time evolution of a simple initial state with the Hamiltonian corresponding to a suitably chosen graph G implements a quantum circuit on this encoded data.

The quantum circuit to be simulated (on the n computational qubits) is given as a product of gates from a universal set consisting of single-qubit gates along with the two-qubit controlled phase gate CP = diag(1,1,1,–i). A controlled phase between computational qubits i and j can be expanded as the following sequence of gates also acting on the mediator qubit m.CPij|ai,bj,0m=CNOTimCPjmCNOTim|ai,bj,0m=HmCPim2HmCPjmHmCPim2Hm|ai,bj,0mWriting the controlled phase gate in this way, we transform the given n-qubit circuit into an (n + 1)–qubit circuit with only single-qubit gates on computational qubits, Hadamard gates H on the mediator qubit, and controlled phase gates between the mediator qubit and arbitrary computational qubits.

We represent each of the n + 1 qubits using a dual-rail encoding with two paths that run through the graph (Fig. 1B). The encoded state |0 has a particle moving along the top path, whereas the encoded state |1 has a particle moving along the bottom path. The particle moves as a wave packet with momentum near k. For the n computational qubits we choose k = –π/4, and for the mediator qubit we choose k = –π/2 (for concreteness).

To implement single-qubit unitaries, we design the graph so that the particles scatter through a series of small subgraphs while remaining far apart. When the particles are all far from each other, the interaction term in the Hamiltonian is negligible and the n + 1 wave packets propagate independently [our analysis in section S4 of (32) accounts for the error in this approximation]. In this case, the multiparticle quantum walk can be viewed as a single-particle quantum walk for each of the particles.

To apply a one-qubit unitary U to an encoded qubit, we insert an associated graph G^ into the paths representing the qubit as follows. We attach two long "input" paths and two long "output" paths to four suitably chosen vertices of G^ so that the S-matrix at the relevant momentum has the formS=(0UU0)(4)A particle incident on the input paths with the relevant momentum transmits perfectly to the output paths, with amplitudes determined by the 2 by 2 unitary matrix U.

Graphs G^ that implement a phase gate and a basis-changing gate at momentum –π/4 are shown in Fig. 2, A and B, respectively (7). The input and output paths are attached to the vertices denoted by open circles. The S-matrices at momentum –π/4 for these graphs are of the form given in Eq. 4, with lower-left 2 by 2 submatrices. Uphase=(eiπ/4001)Ubasis=i2(1ii1)These two gates allow us to approximate arbitrary single-qubit unitaries on each of the n computational qubits.

Fig. 2

(A) Phase gate at –π/4. (B) Basis-changing gate at –π/4. (C) Hadamard gate at –π/2.

The Hadamard gate is the only single-qubit gate we apply to the mediator qubit. We implement this gate using the graph in Fig. 2C, which has S-matrix at momentum k = –π/2 of the form in Eq. 4, with lower-left submatrixUH=eiπ/42(1111)which is the Hadamard gate up to an irrelevant global phase (34).

To implement a controlled phase gate between the mediator qubit and a computational qubit, we use a subgraph that routes two particles toward each other and causes them to interact on a long path for a short time. After scattering, the system returns to a state where the particles are all far apart. We route a computational particle and the mediator particle toward each other along a long path only when the two associated qubits are in state |11. This allows us to implement the two-qubit gate Cθ = diag(1,1,1,eiθ), where eiθ is the two-particle scattering phase. For some models, such as the Bose-Hubbard model with U=2+2, we have Cθ = CP because eiθ = –i [section S2 of (31)]. For nearest-neighbor interactions with fermions, the choice U=22 gives eiθ = i, so CP = (Cθ)3. Although tuning the interaction strength makes the CP gate easier to implement, almost any interaction between indistinguishable particles allows for universal computation. We can approximate the required CP gate by repeating the Cθ gate a times, where eiaθ ≈–i (which is possible for most values of θ, assuming θ is known).

We route particles using a subgraph we call the momentum switch (Fig. 3A). The S-matrices for this graph at momenta –π/4 and –π/2 are Sswitch(π/4)=(00eiπ/4010eiπ/400)Sswitch(π/2)=(100001010) (5)The momentum switch has perfect transmission between vertices 1 and 3 at momentum –π/4 and perfect transmission between vertices 2 and 3 at momentum –π/2. Thus, the path a particle follows through the switch depends on its momentum: A particle with momentum –π/2 follows the double line in Fig. 3A, whereas a particle with momentum –π/4 follows the single line.

Fig. 3

(A) Momentum switch. (B) Cθ gate.

The graph used to implement the Cθ gate is shown in Fig. 3B [see section S4 of (32) for the numbers of vertices on each of the paths]. To see why this graph implements a Cθ gate, consider the movement of two particles as they pass through the graph. If either particle begins in the state |0in, it travels along a path to the output without interacting with the second particle. When either particle begins in the state |1in, it is routed onto the vertical path as it passes through the first momentum switch and is routed to the right as it passes through the second switch. If both particles begin in the state |1in, they interact on the vertical path and the wave function acquires a phase eiθ.

To implement a circuit, the subgraphs representing circuit elements are connected by paths. Figure 4 depicts a graph corresponding to a simple two-qubit computation. Timing is important: Wave packets must meet on the vertical paths for interactions to occur. We achieve this by choosing the numbers of vertices on each of the segments in the graph appropriately, taking into account the different propagation speeds of the two wave packets [see section S4 of (32)]. In section S3.1 of (32), we present a refinement of our scheme using planar graphs with maximum degree four.

Fig. 4

Schematic depiction of a graph simulating B2CP1,2T1 on two qubits for the Bose-Hubbard model with interaction strength Embedded Image. The dotted lines represent paths, and the single-qubit unitary gates represent their corresponding subgraphs.

By analyzing the full (n + 1)–particle interacting many-body system, we prove that our algorithm performs the desired quantum computation up to an error term that can be made arbitrarily small (32). Our analysis goes beyond the scattering theory discussion presented above; we take into account the fact that both the wave packets and the graphs are finite. Specifically, we prove that by choosing the size of the wave packets, the number of vertices in the graph, and the total evolution time to be polynomial functions of both n and g, the error in simulating an n-qubit, g-gate quantum circuit is bounded above by an arbitrarily small constant [section S5 of (32)]. For example, for the Bose-Hubbard model and for the nearest-neighbor interaction model, we prove that the error can be made arbitrarily small by choosing the size of the wave packets to be O(n12g4), the total number of vertices in the graph to be O(n13g5), and the total evolution time to be O(n12g5). The bounds we prove, although almost certainly not optimal, are sufficient to establish universality with only polynomial overhead. Because it is also possible to efficiently simulate a multiparticle quantum walk of the type we consider using a universal quantum computer, this model exactly captures the power of quantum computation.

Supplementary Materials

Materials and Methods

Supplementary Text

Figs. S1 to S10


References and Notes

  1. Materials and methods are available as supplementary materials on Science Online.
  2. Acknowledgments: This work was supported in part by MITACS; Natural Sciences and Engineering Research Council of Canada; the Ontario Ministry of Research and Innovation; the Ontario Ministry of Training, Colleges, and Universities; and the U.S. Army Research Office.
View Abstract

Stay Connected to Science

Navigate This Article