Theory of Computing, Volume 4 (2008), pp. 169–190 http://theoryofcomputing.org

A Quantum Algorithm for the Hamiltonian NAND Tree

Edward Farhi  Jeffrey Goldstone  Sam Gutmann

Received: June 6, 2008; published: December 23, 2008.

Abstract: We give a quantum algorithm for the binary NAND tree problem in the Hamiltonian oracle model. The algorithm uses a continuous time quantum walk with a running time proportional to \sqrt{N}. We also show a lower bound of Ω(\sqrt{N}) for the NAND tree problem in the Hamiltonian oracle model.

ACM Classification: F.1.2, F.2.2

AMS Classification: 68Q10, 68Q17

Key words and phrases: quantum computing, NAND trees, and-or trees, game trees, quantum walk

1 Introduction

The NAND trees in this paper are complete binary trees of depth n, with N = 2^{n} leaves. Each leaf is assigned a value of 0 or 1 and the value of any other node is the NAND of the two connected nodes just above. The goal is to evaluate the value at the root of the tree. An example is shown in Figure 1. Classically, there is a best possible randomized algorithm that succeeds after evaluating only (with high probability) 𝒪(N^{.753}) of the leaves [10, 11, 12].

As far as we know, no quantum algorithm has been devised which improves on the classical query complexity. However there is a quantum lower bound of Ω(\sqrt{N}) calls to a quantum oracle [2]. In this paper we are not working in the usual quantum query model but rather with a Hamiltonian oracle [6, 8] which encodes the NAND tree instance. We will present a quantum algorithm which evaluates the NAND tree in a running time proportional to \sqrt{N}. We also prove a lower bound of Ω(\sqrt{N}) on the running time for any quantum algorithm in the Hamiltonian oracle model.

Authors retain copyright to their papers and grant “Theory of Computing” unlimited rights to publish the paper electronically and in hard copy. Use of the article is permitted as long as the author(s) and the journal are properly acknowledged. For the detailed

 copyright statement, see http://theoryofcomputing.org/copyright.html.

\begin{matrix}c \\ ◯ \end{matrix} 2008 Edward Farhi, Jeffrey Goldstone, and Sam Gutmann

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann

Figure 1: A classical NAND tree.

Our quantum algorithm uses a continuous time quantum walk on a graph [7]. We start with a perfectly bifurcating tree of depth n and one additional node for each of the N leaves. To specify the input we connect some of these N pairs of nodes. A connection corresponds to an input value of 1 on a leaf in the classical NAND tree and the absence of a connection corresponds to a 0. See the top of Figure 2. Next we attach a long line of nodes to the root of the tree. We call this long line the “runway.” See the bottom of Figure 2. The Hamiltonian for the continuous time quantum walk we use here is minus the adjacency matrix of the graph. As usual with continuous time quantum walks, nodes in the graph correspond to computational basis states.

Figure 2: The full Hamiltonian H_{O}+ H_{D}.

We can decompose this Hamiltonian into an oracle, H_{O}, which is instance dependent and a driver, H_{D}, which is instance independent. H_{D} is minus the adjacency matrix of the perfectly bifurcating tree of depth n whose root is attached to node 0 of the line of nodes running from −M to M. We will take M to be very large. See Figure 3.

Figure 3: The oracle independent driver Hamiltonian H_{D}.

A Quantum Algorithm for the Hamiltonian NAND Tree

H_{O} is minus the adjacency matrix of a graph consisting of the leaves of the bifurcating tree and the parallel set of N other nodes. Each leaf in the tree is connected or not to its corresponding node in the set above. See Figure 4. The quantum problem is: Given the Hamiltonian oracle H_{O}, evaluate the NAND tree with the corresponding input.

Figure 4: The Hamiltonian oracle H_{O}.

Our quantum algorithm evolves with the full Hamiltonian H_{O}+ H_{D}, which is minus the adjacency matrix of the full graph illustrated in Figure 2. The initial state is a carefully chosen right-moving packet of length L localized totally on the left side of the runway with the right edge of the packet at node 0. It will turn out that L is of order \sqrt{N}. We take M to be much larger than L, say of order L^{2}. We now let the quantum system evolve and wait a time L/2 which is the time it would take this packet to move a distance L to the right if the tree were not present. We then measure the projector onto the subspace corresponding to the right side of the runway. If the quantum state is found on the right we evaluate the NAND tree to be 1 and if the quantum state is not on the right we evaluate the NAND tree to be 0.

We have chosen our right-moving packet to be very narrowly peaked in energy around E = 0. (Note that E = 0 is not the ground state but is the middle of the spectrum.) The narrowness of the packet in energy forces the packet to be long. If we did not attach the bifurcating tree at node 0, the packet would just move to the right and we would find it on the right when we measure. The algorithm works because with the tree attached the transmission coefficient at E = 0 is 0 if the NAND tree evaluates to 0 and the transmission coefficient at E = 0 is 1 if the NAND tree evaluates to 1. The transmission coefficient is a rapidly changing function of E but for |E| < 1/(γ\sqrt{N}), where γ is N-independent and large, the transmission coefficient is not far from its value at E = 0. To guarantee that the packet consists mostly of energy eigenstates with their energies in this range, we take L to be γ\sqrt{N}. This determines the 𝒪(\sqrt{N}) run time of the algorithm.

Our algorithm uses the driver Hamiltonian H_{D} to evaluate the NAND tree. An arbitrary algorithm can add any instance independent H_{A}(t) to H_{O} and work in the associated Hilbert space. We will show that for any choice of instance independent H_{A}(t) the running time required to evaluate the NAND tree associated with H_{O} is of order at least \sqrt{N}.

2 Motion on the runway

Here we describe the evolution of a quantum state initially localized on the left side of the runway in Figure 2 headed to the right. M is so large that we can take it to be infinite as is justified by the fact that the speed of propagation is bounded. First consider the infinite runway with integers r labeling the sites. The tree is attached at r = 0. We then have for all r not equal to 0:

H |r⟩ = −|r + 1⟩ − |r − 1⟩  r ≠ 0.  (2.1)

For θ > 0,e^{irθ} and e^{−irθ} correspond to the same energy (nonnormalized) eigenstate of equation (2.1) with energy

E(θ) = −2 cos θ

but the first is a right-moving wave and the second is a left-moving wave. We are interested in a packet, that is, a spatially finite superposition of energy eigenstates, which is incident from the left on the node 0 and the attached tree. This packet will reflect back and also transmit to the right side of the runway. The packet is dominated by energy eigenstates, |E⟩, of the form on the runway

⟨r|E⟩ = \{ \begin{matrix}[e^{irθ} + R(E)e^{−irθ} ] & for r ≤ 0 , \\ T (E)e^{irθ} & for r ≥ 0 . \end{matrix}  (2.2)

(The states |E⟩ do not vanish in the tree.) There are other energy eigenstates, but we will not need them after the discussion in the next paragraph.

Our ultimate aim is to calculate matrix elements ⟨r|e^{−iHt}|s⟩, where r and s label sites on the runway. To this end we need a completeness relation involving all of the energy eigenstates. Standard scattering theory strongly suggest that this will be

1 = ∫_{0}^{π} \frac{dθ}{2π} |E(θ)⟩⟨E(θ)| + contributions of other eigenstates,  (2.3)

i. e., that the way the scattering states are normalized is not changed by the presence of the finite tree scatterer. We now demonstrate this.^{1} For the sake of brevity we make use of the special properties of our Hamiltonian, though the result is much more general. For the rest of this paragraph only, we relabel the states defined in (2.2)as |E,→⟩. There are also states, which can be superposed to make left-moving packets, incident on the tree from the right. Now H commutes with the reflection operator, Π, defined by

Π|r⟩ = | − r⟩ where r labels a site on the runway
Π|i⟩ = |i⟩  where i labels a site on the tree.  (2.4)

We can obtain the left-moving energy eigenstate |E,←⟩ by

|E,←⟩ = Π|E,→⟩,  (2.5)

so that on the runway

⟨r|E,←⟩ = \{ \begin{matrix}T (E)e^{−irθ} & for r ⩽ 0, \\ [e^{−irθ} + R(E)e^{irθ}] & for r ⩾ 0. \end{matrix}  (2.6)

The states |E,±⟩ = |E,←⟩ ± |E,→⟩ are simultaneous eigenstates of H and Π. There might also be a finite set of orthonormal energy eigenstates {|E_{k}⟩}, either bound states with ⟨r|E_{k}⟩ → 0 exponentially as |r| → ∞, or states entirely confined to the tree, i. e., with ⟨r|E_{k}⟩ = 0 on the runway. Since H and Π are commuting self-adjoint operators, the spectral theorem asserts that there are measures f_{±} (θ)dθ such that

1The reader who is already convinced should skip to the sentence starting above (2.15).

Theory of Computing, Volume 4 (2008), pp. 169–190 172

\begin{aligned}1 = & ∫_{0}^{π} f_{+} (θ)dθ |E(θ),+⟩⟨E(θ),+| + ∫_{0}^{π} f_{−} (θ)dθ |E(θ),−⟩⟨E(θ),−| \\ & + ∑_{k} |E_{k}⟩⟨E_{k}|. \end{aligned}  (2.7)

We are assuming here that the measures are absolutely continuous with respect to Lebesgue measure. In terms of the left and right-moving states (2.7) becomes

\begin{aligned}1 & = ∫_{0}^{π} f(θ)dθ \{ |E(θ),→⟩⟨E(θ),→ | + |E(θ),←⟩⟨E(θ),← |\} \\ & + ∫_{0}^{π} g(θ)dθ \{ |E(θ),→⟩⟨E(θ),← | + |E(θ),←⟩⟨E(θ),→ |\} \\ & + ∑_{k} |E_{k}⟩⟨E_{k}|. \end{aligned}  (2.8)

We determine f(θ) and g(θ) by calculating ⟨r|1|s⟩ = δ_{r,s} in the two cases r → −∞,s → −∞, with the difference r − s = m fixed, and r → −∞, s → +∞, with r + s = m fixed, making use of the relations

|R(E)|^{2}+ |T (E)|^{2} = 1
R(E)T^{∗}(E) + R^{∗}(E)T (E) = 0.  (2.9)

These follow from the self-adjointness and reflection symmetry of H, but for our special H can be seen from the explicit expressions for T (E) and R(E) in terms of a real function y(E) that we have in (2.15) and (2.17). With r < 0, s < 0, we find

\begin{aligned}⟨r|1|s⟩ = & ∫_{0}^{π} f(θ)dθ[e^{i(r−s)θ} + e^{−i(r−s)θ} + R(E)e^{i(r+s)θ} + R^{∗}(E)e^{i(r+s)θ} ] \\ & + ∫_{0}^{π} g(θ)dθ[T (E)e^{−i(r+s)θ} + T^{∗}(E)e^{i(r+s)θ} ] + ∑_{k} ⟨r|E_{k}⟩⟨E_{k}|s⟩. \end{aligned}  (2.10)

When r,s → −∞, the integrals linear in R(E) and T (E) go to zero by the Riemann-Lebesgue Lemma, and the terms involving |E_{k}⟩ also go to zero, so with r − s = m we obtain

2∫_{0}^{π} f(θ)cos mθ dθ = δ_{m,0}.  (2.11)

This determines f(θ) = 1/2π. With r < 0, s > 0, we find

⟨r|1|s⟩ = ∫_{0}^{π} f(θ)dθ[T (E)e^{−i(r−s)θ} + T^{∗}(E)e^{i(r−s)θ} ]

+ ∫_{0}^{π} g(θ)dθ[e^{i(r+s)θ} + e^{−i(r+s)θ} + R(E)e^{−i(r−s)θ} + R^{∗}(E)e^{i(r−s)θ} ]

+ ∑_{k} ⟨r|E_{k}⟩⟨E_{k}|s⟩. (2.12)

When r → −∞, s → +∞ with r + s = m, we obtain

2∫_{0}^{π} g(θ)dθ cos mθ = 0.  (2.13)

Thus determines g(θ) = 0, so that we have the desired completeness relation

1 = \frac{1}{2π} ∫_{0}^{π} dθ [|E,→⟩⟨E,→ | + |E,←⟩⟨E,← |] + ∑_{k} |E_{k}⟩⟨E_{k}|.  (2.14)

We will use this completeness relation to prove our results. In particular we will only get relevant contributions from the first term and we go back to (2.2) with the symbol → dropped.

Returning to (2.2) and looking at r = 0 we see that

1 + R(E) = T (E).  (2.15)

The transmission coefficient T (E) is determined by the structure of the tree. In particular let

y(E) = \frac{⟨root|E⟩}{⟨r = 0|E⟩}  (2.16)

where “root” is the node immediately above r = 0 on the runway, see Figure 2. Applying the Hamiltonian at |r = 0⟩ gives

H|r = 0⟩ = −|r = −1⟩ − |r = 1⟩ − |root⟩

and taking the inner product with |E⟩ gives

T (E) = \frac{2i sinθ}{2i sinθ + y(E)} .  (2.17)

In the next section we will show how to calculate y(E) and show that if the NAND tree evaluates to 1 then y(0) = 0 meaning that T (0) = 1 and if the NAND tree evaluates to 0 then y(0) = ∞ and T (0) = 0. Unfortunately we cannot build a state with only E = 0 since it would be infinitely long. Instead we build a finite packet that is long enough so that it is effectively a superposition of the states |E⟩ with E close enough to 0 that T (E) is close to T (0). We introduce two parameters ε and D for which

|T (E) − T (0)| < D|E| for |E| < ε .  (2.18)

The parameters ε and D do depend on the size of the tree, but for the remainder of this section we only use ε ≪ 1.

The initial state we consider, |ψ(0)⟩, is given on the runway as

⟨r|ψ(0)⟩ = \{ \begin{matrix}\frac{1}{\sqrt{L}}e^{irπ/2} & for −L + 1 ≤ r ≤ 0 , \\ 0 & for r ≤ −L and r > 0 . \end{matrix}  (2.19)

and vanishes in the tree. For this state

⟨ψ(0)|H|ψ(0)⟩ = 0
and ⟨ψ(0)|H^{2}|ψ(0)⟩ = \frac{5}{L}  (2.20)

so the spread in energy about 0 is of order 1/\sqrt{L}. However, for our purpose we will see that this state is effectively more narrowly peaked in energy, and (2.20) is really an artifact of its sharp edge. In fact most of the probability in energy is contained in a peak around 0 of width 1/L. Because we take π/2 and not −π/2 in (2.19) we have a right-moving packet with energies near 0.

Evolving with the full Hamiltonian of the graph we have

|ψ(t)⟩ = e^{−iHt}|ψ(0)⟩.

We decompose |ψ(t)⟩ into two orthogonal parts,

|ψ(t)⟩ = |ψ_{1}(t)⟩ + |ψ_{2}(t)⟩

where

|ψ_{1}(t)⟩ = ∫_{\frac{π}{2}−ε}^{\frac{π}{2}+ε} \frac{dθ}{2π} e^{−itE(θ)} |E(θ)⟩⟨E(θ)|ψ(0)⟩  (2.21)

and |E(θ)⟩ is given in (2.2) with the completeness relation (2.3). The state |ψ_{2}(t)⟩ is a superposition of the other eigenstates of H, that is, states incident from the left with 0 < θ < \frac{π}{2} − ε and \frac{π}{2} + ε < θ < π, states incident from the right and bound states with |E| > 2 and ⟨r|E⟩ → 0 exponentially as r → ±∞ on the runway. We do not need the details of |ψ_{2}(t)⟩ since we will show in Section 5 that the norm of |ψ_{1}(t)⟩ is close to 1 so the norm of |ψ_{2}(t)⟩ is near 0. In other words, |ψ_{1}(t)⟩ is a very good approximation to |ψ(t)⟩. To ensure this we need

L ≫ \frac{1}{ε} .

We would then expect that at late enough times we will see on the right a packet like the incident packet, but multiplied by T (0) and moving to the right, with the group velocity dE/dθ evaluated at θ = π/2 which is 2. In Section 5 we show, if t is not too big, that for r > 0

⟨r|ψ(t)⟩ = T (0)⟨r − 2t|ψ(0)⟩  (2.22)

plus small corrections. (In Section 5 we also make sense of this equation for 2t not an integer.) To ensure (2.22) we also need

L ≫ D^{2}ε .

Since |ψ(0)⟩ is a normalized state localized between r = −L + 1 and r = 0, (2.22) implies that for t > L/2

∑_{r>0} |⟨r|ψ(t)⟩|^{2} = |T (0)|^{2}

plus small corrections so the cases T (0) = 1 and T (0) = 0 can be distinguished by a measurement on the right at t > L/2.

3 Evaluating the transmission coefficient near E = 0

From the last section, equation (2.17), we see that we can find T (E) if we know y(E). We now show how the structure of the tree recursively determines y(E). Consider the tree in Figure 2 ignoring the runway but including the runway node at r = 0. Except at the top or bottom of this tree every node is connected to two nodes above and one below. See Figure 5 where a, b, c and d are the amplitudes of |E⟩ at the corresponding nodes.

Figure 5: The amplitudes at 4 nodes in the middle of the tree in an energy eigenstate.

Applying H at the middle node yields:

E a = −b − c − d

from which we get

Y = −\frac{1}{E + Y′+ Y′′}

where Y = a/d,Y′= b/a and Y′′= c/a. This is shown pictorially in Figure 6. The y we seek is Y at

Figure 6: The recursion for Y.

the bottom of the tree. To find it we recurse down from the top of the tree. At the top of the tree there are 3 possibilities with the respective values of Y obtained by applying the Hamiltonian. The results are shown in Figure 7. From Figures 6 and 7 we see that Y (−E) = −Y (E) so we can restrict attention to E > 0.

We now show that the recursive formula for computing the the values Y at E = 0 is in fact the NAND gate. Looking at Figure 7 and taking E → 0 positively we get Figure 8. We see that when we begin our

Figure 7: The values of Y at the top of tree.

Figure 8: The values of Y at the top of the tree as E → 0^{+} .

recursion as E → 0+ there are two initial values of Y which are -∞ and 0. Returning to Figure 6 with the different possibilities for Y′ and Y′′we get Figure 9. Identifying Y = 0 with the logical value 1 and Y = −∞ with the logical value 0 we see that Figure 9 is a NAND gate. Accordingly the value of y(0) = Y (0) at the bottom of the tree (see (2.16) and Figure 2) is the value of the NAND tree with the input specified at the top.

Figure 9: The recursion for Y at E = 0 implements the NAND gate.

We now move away from E = 0 to see how far from E = 0 we can go and still have the value of the NAND tree encoded in y(E) at the bottom. Near E = 0 it is convenient to write Y (E) either as a(E)E or as −1/(b(E)E) and we will find bounds on how large a(E) and b(E) can become as we move down the tree. We observe that the coefficient of E in Y (E) (here we mean either a(E) or b(E)) on any edge is an increasing function of the coefficients on the two edges above, as long as |aE|, |a′E|, |bE| and |b′E| are not too big. To see this use the recursive formula in Figure 6. There are three cases and we obtain figure (10) which makes the increasingness clear.

Figure 10: The coefficient of E in Y is an increasing function of a, a′, b and b′.

Now consider a piece of the bifurcating tree as depicted in Figure 11. There are 4 different values of

Figure 11: Y determined by four values of Y above.

Y at the top of the piece, which determine Y at the bottom of the piece. Suppose for 0 < E < 2^{−n/2} /16 each of the Y at the top of the piece obeys

0 ≤ Y_{i}(E) ≤ cE  or 0 ≤ \frac{−1}{Y_{i}(E)}≤ cE

for some positive c with c + 1 ≤ 4 · 2^{j} where j ≤ n/2. We will show

0 ≤ Y (E) ≤ c^{∗}E  or 0 ≤ \frac{−1}{Y (E)}≤ c^{∗}E  (3.1)

where

(c^{∗}+ 1) = \frac{2(c + 1)}{1 − 2^{−n+2j} /4} .  (3.2)

There are six cases to consider and here we exhibit the most dangerous case; see Figure 12.

The reason we can use the coefficient c on the four top edges is the increasingness referred to earlier. Here Y (E) = d(E)E. Using the recursion from Figure 10 we get

d(E) = \frac{2c + 1}{1 − ( 1 + \frac{c}{1−(1+c)cE^{2}} ) (2c + 1)E^{2}} ≤ \frac{2c + 1}{1 − (1 + 2c)(2c + 1)E^{2}}

Theory of Computing, Volume 4 (2008), pp. 169–190 178

Figure 12: The most dangerous case.

using (1 + c) ≤ 4 · 2^{n/2} and E^{2} ≤ \frac{1}{16^{2}} 2^{−n}. So

d(E) ≤ \frac{2c + 1}{1 − 4(1 + c)^{2}E^{2}} ≤ \frac{2(c + 1)}{1 − 4(1 + c)^{2}E^{2}} − 1 ≤ \frac{2(c + 1)}{1 − 2^{2j−n} /4} − 1,  (3.3)

using 1 + c ≤ 4 · 2^{j} and E ≤ 2^{−n/2} /16. From (3.3) we get the left side of (3.1) with c^{∗} given in (3.2). (From Figure 10, the bounds on c and E also imply that the coefficients remain positive from one level to the next, so 0 ≤ Y (E).) The other cases yield smaller coefficients and we will not run through them here.

At the top of the full tree Y (E) = E/(1 − E^{2}) or Y (E) = −1/E as can be seen from Figure 7. Given the restriction O < E < 2^{−n/2} /16 we can take

c_{top} = \frac{1}{1 − 2^{−n}} .  (3.4)

Moving down the tree we get after n/2 iterations of (3.2) with j = 1,2,...n/2,

(c_{bottom}^{∗}+ 1) = (c_{top}+ 1) ( \frac{2}{1 − 2^{2−n} /4} ) ( \frac{2}{1 − 2^{4−n} /4} ) ...( \frac{2}{1 − 2^{n−n}/4} ) .  (3.5)

Therefore

c_{bottom}^{∗}≤ \frac{(1 + \frac{1}{1−2^{−n}} ) 2^{n/2}}{1 − \frac{1}{4} ∑ _{j=1}^{n/2} 2^{2j−n}} ≤ \frac{(1 + \frac{1}{1−2^{−n}} ) 2^{n/2}}{1 − \frac{1}{3}} ≤ 4 · 2^{n/2}

also justifying the assumption c ≤ 4 · 2^{j} at each step.

This means that |y(E)| at the bottom is either less than |c_{bottom}^{∗}E| or greater than |1/(c_{bottom}^{∗}E)| for |E| < 2^{−n/2} /16. The crucial \sqrt{N} arose because the coefficients of Y (E) could barely more than double as we moved two levels down the tree.

Going back to the relation between y(E) and the transmission coefficient given in (2.17) we summarize our results for this section:

NAND = 0 (reflect) |y| > \frac{1}{4\sqrt{N}|E|}  |T | < 8\sqrt{N}|E|  for |E| < \frac{1}{16\sqrt{N}}
NAND = 1 (transmit) |y| < 4\sqrt{N}|E| |T − 1| < 3\sqrt{N}|E| for |E| < \frac{1}{16\sqrt{N}}

4 Putting it all together

Here we combine the results of Sections 2 and 3 and state the algorithm. First, the algorithm. Given the Hamiltonian oracle corresponding to an instance of the NAND tree problem we construct the full Hamiltonian H_{O}+ H_{D} which is minus the adjacency matrix of the graph in Figure 2. We then build the initial state

|ψ(0)⟩ = \frac{1}{\sqrt{L}} ∑_{r=−L+1}^{0} e^{irπ/2}|r⟩  (4.1)

where r is on the runway. We choose

L = γ\sqrt{N}  (4.2)

with γ ≫ 1 a constant independent of N. We let the state evolve for a time

trun = \frac{L}{2}  (4.3)

and then measure the projector P_{+} onto the right side of the runway

P_{+} = ∑_{r=1}^{M} |r⟩⟨r|.  (4.4)

If the measurement yields 1 we evaluate the NAND tree to be 1 and if the measurement yields 0 we evaluate the NAND tree to be 0.

According to the results stated in Section 2, the probability of getting a measurement result of 1 is very near |T (0)|^{2} if

L ≫ \frac{1}{ε} and L ≫ D^{2}ε .  (4.5)

From the table at the end of Section 3 we can take

ε = \frac{1}{16\sqrt{N}}  (4.6)

and

D = 8\sqrt{N}  (4.7)

and then the choice γ ≫ 1 ensures (4.5). At the end of section 5 we will see that the error probability of the algorithm is O( \frac{1}{\sqrt{Lε}}, D\sqrt{\frac{ε}{L}}, ( \frac{ε}{L})^{1/4}) which is O( \sqrt{\frac{1}{γ}}) for large N. By choosing γ large enough we can make the success probability as close to 1 as desired.

5 Technical details

Here we flesh out the claims made in Section 2 and put bounds on the corrections to the stated results. Since we work with θ close to π/2 it is convenient to write

θ = φ + π/2

A Quantum Algorithm for the Hamiltonian NAND Tree

and

E (φ + π/2) = 2sinφ

so (2.21) becomes

|ψ_{1}(t)⟩ = ∫_{−ε}^{ε} \frac{dφ}{2π} e^{−2it sinφ} |E(φ + π/2)⟩⟨E(φ + π/2)|ψ(0)⟩

where ε is the small parameter introduced in (2.18). Using (2.2) gives

⟨E(φ + π/2)|ψ(0)⟩ = \frac{1}{\sqrt{L}} ∑_{r=0}^{L−1} \{e^{irφ} + (−1)^{r}R^{∗}(E)e^{−irφ} \} .

We now break |ψ_{1}(t)⟩ into two pieces

|ψ_{1}(t)⟩ = |ψ_{A}(t)⟩ + |ψ_{B}(t)⟩

where

|ψ_{A}(t)⟩ = ∫_{−ε}^{ε} \frac{dφ}{2π} e^{−2it sinφ} A(φ)|E(φ + π/2)⟩  (5.1)

with

A(φ) = \frac{1}{\sqrt{L}} ∑_{r=0}^{L−1} e^{irφ} = \frac{1}{\sqrt{L}} \frac{e^{iLφ} − 1}{e^{iφ} − 1}  (5.2)

and

|ψ_{B}(t)⟩ = ∫_{−ε}^{ε} \frac{dφ}{2π} e^{−2it sinφ} R^{∗}(E)B(φ) |E(φ + π/2)⟩

with

B(φ) = \frac{1}{\sqrt{L}} ∑_{r=0}^{L−1} (−1)^{r}e^{−irφ} = \frac{1}{\sqrt{L}} \frac{1 − (−1)^{L}e^{−iLφ}}{1 + e^{−iφ}} .

Note that |ψ_{A}(t)⟩ and |ψ_{B}(t)⟩ are not orthogonal. Now

|B(φ)|^{2} < \frac{1}{Lcos^{2} \frac{1}{2}ε} for |φ| < ε

and |R(E)| ≤ 1 so

⟨ψ_{B}(t)|ψ_{B}(t)⟩ = ∫_{−ε}^{ε} \frac{dφ}{2π} |R(E)|^{2}|B(φ)|^{2}

is of order ε/L and we have

|||ψ_{B}(t)⟩|| = O( \sqrt{\frac{ε}{L}}) .  (5.3)

Theory of Computing, Volume 4 (2008), pp. 169–190 181

On the other hand

⟨ψ_{A}(t)|ψ_{A}(t)⟩ = ∫_{−ε}^{ε} \frac{dφ}{2π} |A(φ)|^{2}.  (5.4)

Now

∫_{−π}^{π} \frac{dφ}{2π} |A(φ)|^{2} = \frac{1}{L} ∑_{r=0}^{L−1} 1 = 1  (5.5)

while

∫_{−π}^{−ε} \frac{dφ}{2π} |A(φ)|^{2}+ ∫_{ε}^{π} \frac{dφ}{2π} |A(φ)|^{2} = \frac{1}{π} ∫_{ε}^{π} dφ \frac{1}{L} ( \frac{sin \frac{1}{2}Lφ}{sin \frac{1}{2}φ} ) ^{2} < \frac{π}{Lε}  (5.6)

since sin \frac{φ}{2} > \frac{φ}{π} and (sin \frac{1}{2}Lφ)^{2} < 1. Combining (5.4), (5.5) and (5.6) gives

1 − \frac{π}{Lε} < ⟨ψ_{A}(t)|ψ_{A}(t)⟩ ≤ 1

so

|||ψ_{A}(t)⟩|| = 1 − O( \frac{1}{Lε}) .  (5.7)

We now require

L ≫ \frac{1}{ε}

so the norm of |ψ_{A}(t)⟩ is close to 1.

Now

|||ψ_{1}(t)⟩|| ≥ |||ψ_{A}(t)⟩||− |||ψ_{B}(t)⟩||

so

|||ψ_{1}(t)⟩|| = 1 − O( \frac{1}{Lε},\sqrt{\frac{ε}{L}})

where O(a,b) means O of the larger of a and b. This justifies our claim in Section 2 that |ψ_{1}(t)⟩ is a very good approximation to the true evolving state |ψ(t)⟩. Since

|||ψ_{1}(t)⟩||^{2}+ |||ψ_{2}(t)⟩||^{2} = 1

we also have

|||ψ_{2}(t)⟩|| = O( \frac{1}{\sqrt{Lε}},( \frac{ε}{L})^{1/4}) .  (5.8)

We measure the state |ψ(t)⟩ on the right side of the runway, so we need a good estimate of

⟨ψ(t)|P_{+} |ψ(t)⟩ = ∑_{r>0} |⟨r|ψ(t)⟩|^{2}.

Using

|ψ(t)⟩ = |ψ_{A}(t)⟩ + |ψ_{B}(t)⟩ + |ψ_{2}(t)⟩

A Quantum Algorithm for the Hamiltonian NAND Tree

and the bounds on the norms (5.3), (5.7) and (5.8) we get

⟨ψ(t)|P_{+} |ψ(t)⟩ = ⟨ψ_{A}(t))|P_{+} |ψ_{A}(t)⟩ + O( \frac{1}{\sqrt{Lε}},( \frac{ε}{L})^{1/4})  (5.9)

so we can use |ψ_{A}(t)⟩ to estimate the probability of finding the state on the right at time t.

Now for r ≥ 0 from (2.2) and (5.1)

⟨r|ψ_{A}(t)⟩ = ∫_{−ε}^{ε} \frac{dφ}{2π} e^{−2it sinφ} T (E)A(φ)i^{r}e^{irφ} .

Let

a_{r}(t) = T (0)i^{r} ∫_{−π}^{π} \frac{dφ}{2π} e^{i(r−2t)φ} A(φ).  (5.10)

We want to show that a_{r}(t) is a good approximation to ⟨r|ψ_{A}(t)⟩. We can write

⟨r|ψ_{A}(t)⟩ = a_{r}(t) + b_{r}(t) + c_{r}(t) + d_{r}(t)  (5.11)

with

b_{r}(t) = −i^{r}T (0)\{ ∫_{−π}^{−ε} \frac{dφ}{2π} + ∫_{ε}^{π} \frac{dφ}{2π} \} e^{i(r−2t)φ} A(φ),
c_{r}(t) = i^{r}T (0)∫_{−ε}^{ε} \frac{dφ}{2π} (e^{−2it sinφ} − e^{−2itφ} ) e^{irφ} A(φ)

and

d_{r}(t) = i^{r} ∫_{−ε}^{ε} \frac{dφ}{2π} (T (E) − T (0))e^{−2it sinφ} e^{irφ} A(φ).

We now show that b_{r}(t),c_{r}(t) and d_{r}(t) are small. First

∑_{r=0}^{∞} |b_{r}(t)|^{2} < ∑_{−∞}^{∞} |b_{r}(t)|^{2} = |T (0)|^{2}· 2 · ∫_{ϵ}^{π} \frac{dφ}{2π} |A(φ)|^{2}

by Parseval’s Theorem. Using (5.6) we have

∑_{r=0}^{∞} |b_{r}(t)|^{2} = O( \frac{1}{Lε}) .  (5.12)

Theory of Computing, Volume 4 (2008), pp. 169–190 183

Similarly

∑_{r=0}^{∞} |c_{r}(t)|^{2}< |T (0)|^{2}∫_{−ε}^{ε} \frac{dφ}{2π} |e^{2it(φ−sinφ)} − 1|^{2}|A(φ)|^{2}

= |T (0)|^{2}∫_{−ε}^{ε} \frac{dφ}{2π} \{ \frac{1}{9} t^{2}φ^{6}+ ⋯\} \frac{1}{L} \frac{sin^{2} \frac{1}{2} Lφ}{sin^{2} \frac{1}{2} φ} .

(5.13)

However we take t_{run} to be near L/2. As long as Lε^{3} ≪ 1 we have

∑_{r=0}^{∞} |c_{r}(t)|^{2} = O(Lε^{5}).  (5.14)

To keep this small we need Lε^{5} ≪ 1, but this follows from our assumption that Lε^{3} ≪ 1 since ε ≪ 1. The assumption that Lε^{3} ≪ 1 helps us to establish the translation property in (2.22) which simplifies the picture of what is going on. Also

∑_{r=0}^{∞} |d_{r}(t)|^{2} < ∫_{−ε}^{ε} \frac{dφ}{2π} |T (E) − T (0)|^{2}|A(φ)|^{2}.

Using |T (E) − T (0)| < D|E| for |E| < ε we get

∑_{r=0}^{∞} |d_{r}(t)|^{2} < D^{2}∫_{−ε}^{ε} \frac{dφ}{2π} 4sin^{2}φ \frac{1}{L} \frac{sin^{2}(\frac{1}{2}Lφ)}{sin^{2}(\frac{1}{2}φ)}  (5.15)

= O( \frac{D^{2}ε}{L})  (5.16)

from which we get our condition

L ≫ D^{2}ε .

Now from (2.19) and (5.2) we have

⟨r|ψ(0)⟩ = i^{r} ∫_{−π}^{π} A(φ)e^{irφ} d φ .  (5.17)

So from (5.10) we see that

a_{r}(t) = T (0) ⟨r − 2t|ψ(0)⟩  (5.18)

but only when 2t is an integer. However if 2t = m + τ with m an integer and 0 ≤ τ < 1,

∑_{−∞}^{∞} |a_{r}(t) − a_{r}( \frac{m}{2}) |^{2} = |T (0)|^{2} ∫_{−π}^{π} \frac{dφ}{2π} \frac{1}{L} \frac{sin^{2} \frac{1}{2}Lφ}{sin^{2} \frac{1}{2}φ} |e^{iτφ} − 1|^{2}

= O( \frac{1}{L}) .  (5.19)

We have shown that for r > 0,⟨r|ψ(t)⟩ is well approximated by ⟨r|ψ_{1}(t)⟩ which is well approximated by ⟨r|ψ_{A}(t)⟩ which is well approximated by a_{r}(t) which has the form (5.18) so (2.22) is justified.

Furthermore, using (5.9), (5.11), (5.12), (5.14), (5.16) and (5.18) we have for t > L/2

⟨ψ(t)|P_{+} |ψ(t)⟩ = |T (0)|^{2} + O( \frac{1}{\sqrt{Lε}}, D\sqrt{\frac{ε}{L}}, ( \frac{ε}{L})^{1/4})  (5.20)

which can be used to estimate the failure probability of the algorithm.

6 A lower bound for the Hamiltonian NAND tree problem via the Hamiltonian Parity problem

Here we show that if the input to a NAND tree problem is given by the Hamiltonian oracle H_{O} described in Section 1 then for an arbitrary driver Hamiltonian H_{A}(t), evolution using H_{O}+ H_{A}(t) cannot evaluate the NAND tree in a time of order less than \sqrt{N}. This means that our algorithm which takes time \sqrt{N} is optimal up to a constant.

In the usual query model, the parity problem with \sqrt{N} variables can be embedded in a NAND tree with N leaves [2]. To see this first consider 2 variables, a and b, and the 4 leaf NAND tree given in Figure 13 which evaluates to (1 + a + b) mod2. Using this we see that with 4 variables a, b, c, d the NAND tree in Figure 14 evaluates to (1 + a + b + c + d) mod2. This clearly continues. Since we know that the parity problem for \sqrt{N} variables cannot be solved with less than of order \sqrt{N} quantum queries, we know that the NAND tree problem cannot be solved with fewer than of order \sqrt{N} quantum queries.

Figure 13: This NAND tree evaluates to (1 + a + b) mod2.

Figure 14: This NAND tree evaluates to (1 + a + b + c + d) mod2.

In our Hamiltonian oracle model the input in Figure 14 becomes the oracle depicted in Figure 15. Here the labels on the vertical edges on the top are always 0 or −1. A label 0 means that the edge is not included (just as in Figure 4) and accordingly the corresponding Hamiltonian matrix element is 0. A label −1 means that the edge is there (just as in Figure 4) and the corresponding matrix element of the Hamiltonian oracle is −1.

Figure 15: The Hamiltonian oracle for the NAND tree set up to evaluate (1 + a + b + c + d) mod2. The coefficients are 0 or −1 corresponding to the edge present or not.

We see that the Hamiltonian parity problem can be embedded in the Hamiltonian NAND tree problem. We did this for the Hamiltonian NAND tree oracle considered in this paper, but it can also be done for the more general Hamiltonian NAND tree oracle described in the Conclusion.

We will now prove a lower bound for the Hamiltonian parity problem, in a general setting (see also [8]), which can be used to obtain a \sqrt{N} lower bound for the Hamiltonian NAND tree problem. The oracle for the parity problem is a Hamiltonian of this form:

H_{OP}= ∑_{j=1}^{K} H_{j} .  (6.1)

The H_{j} operate on orthogonal subspaces V_{j} with

H_{j} = P_{j} H_{j} P_{j}

where P_{j} is the projection onto V_{j}. Furthermore we assume ∥H_{j}∥ ≤ 1. For each j there are two possible operators H_{j}^{(a_{j})}, a_{j} = 0 or 1. The string a_{1},a_{2},...,a_{K} is the input to the parity problem to be solved. In the Hamiltonian oracle model, an algorithm can use (6.1), but has no other access to the string a. This is the most general form for the parity oracle Hamiltonian that we can imagine and it certainly includes the oracle we used to embed Hamiltonian parity in the Hamiltonian NAND tree.

Choose an arbitrary driver Hamiltonian H_{A}(t). Let S be an instance of parity, that is, a subset of 1,2,...,K with a_{j} = 1 iff j is an element of S. Starting in an instance independent state |ψ(0)⟩ we evolve for time T according to the Schrödinger equation

i \frac{d}{dt}|ψ_{S}(t)⟩ = H_{S}(t)|ψ_{S}(t)⟩

using the total Hamiltonian H_{S}(t)

H_{S}(t) = g(t)H_{OP}+ H_{A}(t)

where |g(t)| ≤ 1. With the inclusion of the coefficient g(t) it is clear that the Hamiltonian oracle model includes the quantum query model.

Let |ψ_{S}(T)⟩ be the state reached at time T. A successful algorithm for parity must have

∥|ψ_{S}(T)⟩ − |ψ_{S′}(T)⟩∥ ≥ δ

for some K independent δ > 0 if the parity of S and S′differ. We now show that this suffices to force T to be of order K. Our approach is an analogue to the analog analogue [6] of the BBBV method [3]. We write S ∼ S′if S and S′differ by one element. Summing on (S,S′) which differ by one element gives

\frac{d}{dt} ∑_{S∼S′}∥|ψ_{S}(t)⟩ − |ψ_{S′}(t)⟩∥^{2} = ∑_{S∼S′} 2Im⟨ψ_{S}(t)| (H_{S}(t) − H_{S′}(t))|ψ_{S′}(t)⟩

= ∑_{S∼S′} 2Im⟨ψ_{S}(t)| ± △_{j(S,S′)}|ψ_{S′}(t)⟩

where j (S,S′) is the element by which S and S′differ, and △_{j} = g(t)( H_{j}^{(1)}− H_{j}^{(0)}) . The + sign means that j(S,S′) ∈ S whereas the − sign means that j(S,S′) ∈ S′. Now we have

\frac{d}{dt} ∑_{S∼S′}∥|ψ_{S}(t)⟩ − |ψ_{S′}(t)⟩∥^{2} ≤ 2 ∑_{S∼S′} |⟨ψ_{S}(t)|P_{j(S,S′)}△_{j(S,S′)}P_{j(S,S′)}|ψ_{S′}(t)⟩|

≤ 4 ∑_{S∼S′}∥P_{j(S,S′)}|ψ_{S}(t)⟩∥· ∥P_{j(S,S′)}|ψ_{S′}(t)⟩∥

since ∥△_{j}∥ ≤ 2. Using ab ≤ ( \frac{1}{2} a^{2}+ \frac{1}{2} b^{2}) gives

\frac{d}{dt} ∑_{S∼S′}∥|ψ_{S}(t)⟩ − |ψ_{S′}(t)⟩∥^{2} ≤ 2 ∑_{S∼S′} [ ∥P_{j(S,S′)}|ψ_{S}(t)⟩∥^{2}+ ∥P_{j(S,S′)}|ψ_{S′}(t)⟩∥^{2}].

For fixed S′, j(S,S′) runs over {1,2,...,K} so

∑_{S∼S′,S′fixed}∥P_{j(S,S′)}|ψ_{S′}(t)⟩∥^{2} ≤ 1

and similarly for fixed S and thus we have

∑_{S∼S′} [ ∥P_{j(S,S′)}|ψ_{S}(t)⟩∥^{2}+ ∥P_{j(S,S′)}|ψ_{S′}(t)⟩∥^{2}]≤ 2 · 2^{K}

since there 2^{K} possibilities for S′(or S).

We’ve shown that

\frac{d}{dt} ∑_{S∼S′}∥ |ψ_{S}(t)⟩ − |ψ_{S′}(t)⟩∥^{2} ≤ 4 · 2^{K},

and since

∑_{S∼S′}∥|ψ_{S}(0)⟩ − |ψ_{S′}(0)⟩∥^{2} = 0

we can integrate to obtain

∑_{S∼S′}∥|ψ_{S}(T)⟩ − |ψ_{S′}(T)⟩∥^{2} ≤ 4 · 2^{K}· T .

For each S′there are K choices of S, so a successful algorithm requires

∑_{S∼S′}∥|ψ_{S}(T)⟩ − |ψ_{S′}(T)⟩∥^{2} ≥ 2^{K}· K · δ

and we have the desired bound

T ≥ K δ/4.

Conclusion

We are not working in the quantum query model but rather in the quantum Hamiltonian oracle model. In this model the programmer is given a Hamiltonian oracle of the form

H_{O} = ∑_{j=1}^{N} H_{j}

where the H_{j} operate in orthogonal subspaces. Each H_{j} is one of two possible operators H_{j}^{(b_{j})} with b_{j} = 0 or 1 and the string b_{1}··· b_{N} is the input to the classical NAND tree that is to be evaluated. The quantum programmer is allowed to evolve states using any Hamiltonian of the form g(t)H_{O}+ H_{A}(t) where the coefficient g(t) satisfies |g(t)| ≤ 1 and H_{A}(t) is any instance independent Hamiltonian. The programmer has no other access to the string b.

The algorithm presented in this paper uses a time independent H_{O}+ H_{D} which is (minus) the adjacency matrix of a graph, so our algorithm is a continuous time quantum walk. We evaluate the NAND tree in time of order \sqrt{N} which is (up to a constant) the lower bound for this problem.

After the arXiv version of this paper appeared, corresponding results in the discrete-query model were obtained [1, 4]. Further generalizations to other formulas can be found in [5, 9].

Acknowledgement

Two of the authors gratefully acknowledge support from the National Security Agency (NSA) and the Disruptive Technology Office (DTO) under Army Research Office (ARO) contract W911NF-04-1-0216.

We also thank Richard Cleve for repeatedly encouraging us to connect continuous time quantum walks with NAND trees, and for discussions about the Hamiltonian oracle model. We thank Andrew Landahl for earlier discussions of the NAND tree problem.

References

[1] * Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, and Shengyu Zhang: Any AND-OR formula of size N can be evaluated in time n^{1/2+o(1)} on a quantum computer. In Proc. 48th FOCS, pp. 363–372. IEEE Computer Society, 2007. [doi:10.1109/FOCS.2007.57]. 6 [2] * Howard Barnum and Michael Saks: A lower bound on the quantum query

complexity of read-once functions. J. Comput. System Sci., 69(2):244–258, 2004. [doi:10.1016/j.jcss.2004.02.002]. 1, 6

[3] * Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani:

Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. [doi:10.1137/S0097539796300933]. 6

[4] * Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yeung: Discrete-query quantum algorithm for NAND trees, 2007. [arXiv:quant-ph/0702160]. 6

[5] * Richard Cleve, Dmitry Gavinsky, and David L. Yeung: Quantum algorithms for evaluating MIN-MAX trees, 2007. [arXiv:0710.5794]. 6

[6] * Edward Farhi and Sam Gutmann: An analog analogue of a digital quantum computation. Phys. Rev. A, 57:2403, 1998. [doi:10.1103/PhysRevA.57.2403]. 1, 6

[7] * Edward Farhi and Sam Gutmann: Quantum computation and decision trees. Phys. Rev. A, 58:915, 1998. [doi:10.1103/PhysRevA.58.915]. 1

[8] * Carlos Mochon: Hamiltonian oracles. Phys. Rev. A, 75:042313, 2007. [doi:10.1103/PhysRevA.75.042313]. 1, 6

[9] * Ben W. Reichardt and Robert Špalek: Span-program-based quantum algorithm for evaluating formulas. In Proc. 40th STOC, pp. 103–112. ACM, 2008. [doi:10.1145/1374376.1374394]. 6

[10] * Michael Saks and Avi Wigderson: Probabilistic boolean trees and the complexity of evaluating game trees. In Proc. 27th FOCS, pp. 29–38. IEEE Computer Society, 1986. 1

[11] * Miklos Santha: On the Monte Carlo Boolean decision tree complexity of read-once formulae. Random Structures Algorithms, 6(1):75–87, 1995. [doi:10.1002/rsa.3240060108]. 1

[12] * Marc Snir: Lower bounds on probabilistic decision trees. Theoret. Comput. Sci., 38:69–82, 1985. [doi:10.1016/0304-3975(85)90210-5]. 1

AUTHORS

Edward Farhi [About the author]

Cecil and Ida Green Professor of Physics Massachusetts Institute of Technology Cambridge, MA 02139 farhi mit edu

 http://web.mit.edu/physics/facultyandstaff/faculty/edward farhi.html

Jeffrey Goldstone [About the author]

Cecil and Ida Green Professor of Physics, Emeritus Massachusetts Institute of Technology Cambridge, MA 02139 goldston mit edu

http://web.mit.edu/physics/facultyandstaff/faculty/jeffrey goldstone.html

Sam Gutmann [About the author]

Department of Mathematics Northeastern University, Boston MA sgutm neu edu

http://www.math.neu.edu/^{∼} Gutmann/

ABOUT THE AUTHORS

Edward Farhi is a professor of physics and the director of the Center for Theoretical Physics at MIT. He is a lapsed particle physicist hoping to return to his roots when data from experiments offers new insight into how the world really works. Meanwhile he works on quantum computation, primarily focusing on algorithm design. He started collaborating with Sam in high school and with Jeffrey at MIT.

Jeffrey Goldstone, after 25 years at Cambridge University and 30 at MIT, is now Professor of Physics Emeritus. He worked on many-body theory and in the prehistoric eras of the standard model and string theory. He has been helping Eddie and Sam search for quantum algorithms for the last 10 years.

Sam Gutmann crosses the river (from the math department at Northeastern University) to work with Eddie and Jeffrey.