Abstract
We propose a novel algorithm for quantum spatial search on a star graph using interleaved continuous-time quantum walks and marking oracle queries. Initializing the system in the star’s central vertex, we determine the optimal quantum walk times to reach full overlap with the marked state using oracle queries, matching the well-known lower bound of Grover’s search. We implement the deterministic search in a database of size seven on photonic quantum hardware, and demonstrate the effective scaling of the approach up to size 115. This is the first experimental demonstration of quantum walk-based search on the highly noise-resistant star graph, which provides new evidence for the applications of quantum walk in quantum algorithms and quantum information processing.
- Received 27 May 2021
- Revised 29 October 2021
- Accepted 10 January 2022
DOI:https://doi.org/10.1103/PhysRevLett.128.050501
© 2022 American Physical Society