Speedup of Grover’s search algorithm and closed timelike curves
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Sep 17, 2020
- Source ID
- 10.1088/2058-9565/abae7e
Entities
People
- Doyeol Ahn
- Jeongho Bang
- Ki Hyuk Yee
- Paul M. Alsing
- Warner A Miller
Organizations
- Air Force Office of Scientific Research
- Electronics and Telecommunications Research Institute
- Ministry of Science, ICT and Future Planning
- National Research Foundation