Source-linked AI summary
A Quantum Algorithm for the Hamiltonian NAND Tree
E. Farhi, J. Goldstone, S. Gutmann
TL;DR
The paper asks whether NAND trees can be evaluated efficiently in the Hamiltonian oracle model, where prior quantum-query improvements were unavailable. It constructs a continuous-time quantum walk whose transmission distinguishes the NAND value and establishes a matching runtime lower bound for the model.
Problem
No quantum algorithm was known to improve on the classical query complexity for NAND trees, motivating evaluation in the Hamiltonian oracle model.
Method
The paper uses a time-independent Hamiltonian HO + HD, implemented as a continuous-time quantum walk on a graph with an input-dependent tree and an instance-independent driver.
Results
The transmission coefficient near E = 0 distinguishes NAND value 0 from NAND value 1, allowing the tree to be evaluated from the wave packet’s measured location.
Takeaways & Limitations
The algorithm’s runtime is optimal up to a constant for NAND-tree evaluation in the Hamiltonian oracle model.
Takeaways & Limitations
The lower-bound model restricts access to the input string to Hamiltonian evolution using g(t)HO + HA(t), with HA(t) instance independent and |g(t)| ≤ 1.
Abstract
from arXiv · showhide
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 run time proportional to sqrt N. We also show a lower bound of sqrt N for the NAND tree problem in the Hamiltonian oracle model.
1 Introduction
The paper formulates NAND-tree evaluation in the Hamiltonian oracle model and presents a continuous-time quantum-walk algorithm using a tree, oracle-dependent leaf connections, and a runway. The algorithm encodes the tree value in transmission through the attached tree, while the paper also establishes a lower bound on runtime.
- Problem: NAND trees have N leaves, depth n = log2(N), and leaf values combined by NAND gates to determine the root.A classical randomized algorithm succeeds after evaluating N^.753 leaves with high probability, and this is best possible.
- Algorithm: The quantum algorithm uses a continuous-time quantum walk on a graph containing a perfectly bifurcating tree, input-encoding leaf connections, and a runway attached to the root.The Hamiltonian is minus the graph’s adjacency matrix, and graph nodes represent computational basis states.
- Hamiltonian model: The Hamiltonian splits into an instance-dependent oracle HO and an instance-independent driver HD.HD is the negative adjacency matrix of the bifurcating tree and runway, while HO represents the input-dependent leaf connections.
- Algorithm: A narrowly energy-peaked wave packet starts on the runway and is measured on its right side after evolution under HO + HD.The packet’s length is chosen so its energy lies near E = 0, where the tree’s transmission distinguishes the NAND value.
- Lower bound: The paper claims a runtime lower bound for any algorithm using the Hamiltonian oracle together with an arbitrary instance-independent Hamiltonian.This lower bound matches the algorithm’s runtime up to a constant, according to the paper’s contribution statements.
2 Motion on the Runway
The algorithm sends a right-moving wave packet along a runway into the attached tree and reads the NAND value from transmission to the right. Near E=0, the tree’s transmission coefficient distinguishes NAND outputs, allowing a measurement after the packet traverses the runway.
- Scattering and transmission: A right-moving packet incident from the left scatters from the tree, producing reflected and transmitted components on the runway.The packet is a finite superposition of energy eigenstates incident on node 0.
- Scattering and transmission: The transmission coefficient T(E) is determined by the structure of the attached tree and related to the quantity y(E).The paper derives y(E) recursively and uses it to characterize transmission.
- Scattering and transmission: At E=0, NAND output 1 gives T(0)=1, whereas NAND output 0 gives T(0)=0.These values follow from y(0)=0 for output 1 and y(0)=∞ for output 0.
- Measurement: After time t>L/2, the transmitted packet on the right is multiplied by T(0), so T(0)=1 and T(0)=0 can be distinguished by measuring the right side.The transmitted packet moves with group velocity 2 at θ=π/2, up to small corrections.
3 Evaluating the transmission coefficient near E=0.
The paper recursively computes a ratio Y through the bifurcating tree and shows that its E=0 recursion implements the NAND gate. Bounds on the recursion near zero preserve this encoding sufficiently close to E=0 for the transmission analysis.
- Recursive evaluation: The quantity y(E) is the Y ratio at the tree bottom, obtained by recursively combining values from the top.For a middle node, the recursion uses Y=a/d, Y′=b/a, and Y′′=c/a.
- Boundary values: The top of the tree has three possible Y values, and the symmetry Y(−E)=−Y(E) permits restricting the analysis to E>0.The top values are obtained by applying the Hamiltonian to the boundary configurations.
- Recursive evaluation: At E=0, the initial values Y=−∞ and Y=0 represent logical 0 and 1, and the recursion is a NAND gate.Thus y(0) at the bottom equals the NAND-tree value specified by the inputs at the top.
- Bounds near E=0: Near E=0, Y(E) is represented as either a(E)E or −1/(b(E)E), with coefficients increasing from the two edges above under boundedness conditions.The monotonicity supports recursive bounds on how coefficients grow through the tree.
- Bounds near E=0: After n/2 recursive iterations, the bottom value remains either small, bounded by c∗E, or large, bounded below by 1/(c∗E).The coefficient-growth analysis also justifies the inductive assumption used at each step.
- Bounds near E=0: The coefficient-growth analysis identifies a most dangerous case because coefficients can barely more than double over two levels of the tree.The other cases yield smaller coefficients.
4 Putting it all together
The algorithm constructs a full Hamiltonian from the oracle and driver, evolves an instance-independent initial packet, and measures the runway to infer the NAND-tree value. Its error probability can be made small by choosing γ sufficiently large.
- Algorithm: The algorithm constructs the full Hamiltonian HO + HD and an initial state, then evolves the state before measuring the right side of the runway.The measurement result 1 is interpreted as NAND-tree value 1, and result 0 as value 0.
- Algorithm: γ is chosen as an N-independent constant with γ ≫ 1, and increasing γ makes the success probability arbitrarily close to 1.The construction uses a right-moving packet localized on the left side of the runway.
- Algorithm: The algorithm’s error probability is bounded by an O-term derived from the parameter choices and appendix estimates.The supplied passage does not preserve the exponent of the displayed bound.
5 A lower bound for the Hamiltonian NAND tree problem via the Hamiltonian Parity problem
The lower-bound argument embeds Hamiltonian parity into the Hamiltonian NAND-tree problem. A general parity lower bound then implies an order-√N lower bound for NAND-tree evaluation in the Hamiltonian oracle model.
- NAND-tree lower bound: An arbitrary driver Hamiltonian cannot evaluate the Hamiltonian NAND tree in time smaller than the stated order-√N bound.The lower bound applies to evolution using HO + HA(t).
- Embedding parity: N variables of parity can be embedded into a NAND tree with N leaves, because the tree evaluates to the parity expression represented in the construction.The two- and four-variable examples evaluate to (1 + a + b) mod 2 and (1 + a + b + c + d) mod 2.
- Embedding parity: The Hamiltonian oracle represents each input-dependent edge by coefficient 0 or −1, corresponding respectively to an absent or present edge.This converts the parity embedding into the Hamiltonian oracle used for the NAND tree.
- NAND-tree lower bound: Because the Hamiltonian parity problem embeds into the Hamiltonian NAND-tree problem, the parity lower bound transfers to the NAND-tree oracle considered here.The paper states that the embedding also applies to the more general Hamiltonian NAND-tree oracle described in the conclusion.
- Hamiltonian parity bound: The parity oracle acts on orthogonal subspaces, with each Hj having two possible operators selected by the input bit aj.The algorithm has no other access to the input string in this oracle model.
- Hamiltonian parity bound: Starting from an instance-independent state and evolving with an arbitrary driver, successful parity computation requires evolution time of order K.The proof compares states for parity instances differing by one element and derives the bound by summing over such pairs.
Conclusion
The paper’s model permits evolution under a bounded oracle coefficient and any instance-independent driver Hamiltonian. Its continuous-time quantum-walk algorithm runs in order-√N time, matching the problem’s lower bound up to a constant.
- Model: The Hamiltonian oracle consists of orthogonal-subspace operators Hj, each selected by one input bit bj of the NAND-tree instance.The programmer may evolve using g(t)HO + HA(t), with |g(t)| ≤ 1 and HA(t) instance independent.
- Algorithm: The algorithm uses a time-independent HO + HD equal to minus the adjacency matrix of a graph, making it a continuous-time quantum walk.The input is accessed only through the Hamiltonian oracle under the stated model.
- Conclusion: Order-√N running time matches the lower bound for Hamiltonian NAND-tree evaluation up to a constant.The paper also notes a later N^(1/2+ε) quantum-query algorithm that used this algorithm as a building block.
A Appendix
The appendix bounds approximation errors under small-parameter assumptions and justifies the simplified state description used in the main analysis. It also connects these approximations to estimating right-side measurement probabilities and the algorithm’s failure probability.
- Approximation bounds: The approximation |ψ1(t)⟩ ≈ |ψ(t)⟩ is justified using bounds summarized with O(a, b), defined as O of the larger argument.This establishes that the simplified evolving state is a very good approximation to the true state.
- Measurement estimate: The right-side measurement probability can be estimated with |ψA(t)⟩ by first approximating ⟨r|ψA(t)⟩ with ar(t).The appendix frames this estimate around measuring |ψ(t)⟩ on the right side of the runway.
- Assumptions: The assumption Lε^3 ≪ 1 supports the translation property in (2.18) and, because ε ≪ 1, also implies Lε^5 ≪ 1.The analysis takes trun near L/2 under this small-parameter regime.
- Approximation chain: For r > 0, ⟨r|ψ(t)⟩, ⟨r|ψ1(t)⟩, ⟨r|ψA(t)⟩, and ar(t) form a justified chain of approximations supporting (2.18).The appendix explicitly states that each successive quantity is well approximated by the next, with ar(t) having the form (A.42).
- Failure probability: For t > L/2, the derived bounds can be used to estimate the algorithm’s failure probability.The estimate combines the appendix’s preceding bounds and formulas.