October 2022

Dr. Shantanav Chakraborty’s research work on Quadratic Speedup for Spatial Search by Continuous-Time Quantum Walk was published in Physical Review Letters. The other authors of this paper are Simon Apers,  IRIF, CNRS, Paris, France; Leonardo Novo, INL, International Iberian Nanotechnology Laboratory, Braga, Portugal  and Jérémie Roland, QuIC, Ecole Polytechnique de Bruxelles, Université libre de Bruxelles, Brussels, Belgium.

Research work as explained by the authors: 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 which, for a given Hamiltonian H, only requires evolving H  for time scaling as . 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.

Full paper: https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.129.160502.