Quadratic Speedup for Spatial Search by Continuous-Time Quantum Walk.

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

Detecting Topological Transitions in Two Dimensions by Hamiltonian Evolution.

We show that the evolution of two-component particles governed by a two-dimensional spin-orbit lattice Hamiltonian can reveal transitions between topological phases. A kink in the mean width of the particle distribution signals the closing of the band gap, a prerequisite for a quantum phase transition between topological phases. Furthermore, for realistic and experimentally motivated Hamiltonians, the density profile in topologically nontrivial phases displays characteristic rings in the vicinity of the origin that are absent in trivial phases. The results are expected to have an immediate application to systems of ultracold atoms and photonic lattices.