Deterministic Search on Star Graphs via Quantum Walks

Dengke Qu, Samuel Marsh, Kunkun Wang, Lei Xiao, Jingbo Wang, and Peng Xue
Phys. Rev. Lett. 128, 050501 – Published 1 February 2022
PDFHTMLExport Citation

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 (π/4)N(1/2) 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.

  • Figure
  • Figure
  • Figure
  • 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

Physics Subject Headings (PhySH)

Quantum Information, Science & TechnologyAtomic, Molecular & Optical

Authors & Affiliations

Dengke Qu1,2,*, Samuel Marsh3,*, Kunkun Wang1, Lei Xiao1, Jingbo Wang3,†, and Peng Xue1,‡

  • 1Beijing Computational Science Research Center, Beijing 100084, China
  • 2Department of Physics, Southeast University, Nanjing 211189, China
  • 3Department of Physics, The University of Western Australia, Perth 6009, Australia

  • *These authors contributed equally to this work.
  • jingbo.wang@uwa.edu.au
  • gnep.eux@gmail.com

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 128, Iss. 5 — 4 February 2022

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×