## Abstract

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 (*8*–*10*) 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 (*11*–*14*), 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 (*11*–*14*, *21*–*25*) and multiparticle quantum walk without interactions (*11*–*14*, *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*i _{w}* is the location of the

*w*th particle. A continuous-time multiparticle quantum walk of

*m*distinguishable particles on

*G*is generated by a time-independent Hamiltonian

*w*indicates that the operator acts nontrivially only on the location register for the

*w*th particle. Here, the operators

*i*and

*j*, respectively (explicitly,

The first term of Eq. 2 moves particles between adjacent vertices, and the second term is an interaction between particles. We assume that *U _{ij}* is zero whenever one of its arguments evaluates to zero and that

*U*is zero if there is only one particle at vertex

_{ii}*i*(thus, the Hamiltonian for a single particle reduces to that of a standard quantum walk). We also assume that the interaction

*U*only depends on the distance between

_{ij}*i*and

*j*and has a constant range. Finally, we assume that the norm of each term

*U*is upper-bounded by a polynomial in

_{ij}*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

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

Given the graph*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 *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 *k* located on path *j* scatters from *q* is *S _{qj}*(

*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 *k*_{1} and *k*_{2} (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 *k*_{1} = –π/2 and *k*_{2} = π/4, and we write *e ^{i}*

^{θ}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.*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 *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 *U*.

Graphs *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.
*n* computational qubits.

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 submatrix*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 *e ^{i}*

^{θ}), where

*e*

^{i}^{θ}is the two-particle scattering phase. For some models, such as the Bose-Hubbard model with

*e*

^{i}^{θ}= –

*i*[section S2 of (

*31*)]. For nearest-neighbor interactions with fermions, the choice

*e*

^{i}^{θ}=

*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

*e*

^{ia}^{θ}≈–

*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

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 *e ^{i}*

^{θ}.

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.

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*(*n*^{12}*g*^{4}), the total number of vertices in the graph to be *O*(*n*^{13}*g*^{5}), and the total evolution time to be *O*(*n*^{12}*g*^{5}). 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

www.sciencemag.org/cgi/content/full/339/6121/791/DC1

Materials and Methods

Supplementary Text

Figs. S1 to S10

References

## References and Notes

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
Materials and methods are available as supplementary materials on
*Science*Online. - ↵
- ↵
**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.