Speedup of Grover's search algorithm and closed timelike curves

Ki Hyuk Yee, Jeongho Bang, Paul M. Alsing, Warner A. Miller, Doyeol Ahn

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


The quadratic reduction of query complexity of Grover's search algorithm (GA), while significant, would not be enough to enjoy exponentially fast data searching in large-scale quantum computation. One of the ways to enhance the speedup in the framework of Grover's algorithm is to employ a novel quantum operation, i.e., inversion against an unknown state; however, this is not possible at least in quantum theory. We thus extend the Grover algorithm assisted by closed timelike curves (CTCs), in which the unknown-state inversion is achievable by combining the superposition of two unknown states with cloning. We dubbed this refined algorithm CTC-assisted Grover algorithm (CTC-GA). We show that the CTC-GA can vastly reduce the query complexity compared to the original algorithm; remarkably, from polynomial to poly-logarithmic. These results will provide a broader intuition for exponential quantum speedup of data searching problems.

Original languageEnglish
Article number045011
JournalQuantum Science and Technology
Issue number4
StatePublished - Oct 2020


  • Closed timelike curve
  • Grover algorithm
  • Quantum algorithm
  • Search
  • Speedup


Dive into the research topics of 'Speedup of Grover's search algorithm and closed timelike curves'. Together they form a unique fingerprint.

Cite this