| Title: |
Fixed-Point Quantum Search with an Optimal Number of Queries |
| Authors: |
Low, Guang Hao; Yoder, Theodore James; Chuang, Isaac L. |
| Contributors: |
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science; Massachusetts Institute of Technology. Department of Physics; Yoder, Theodore James; Low, Guang Hao; Chuang, Isaac L. |
| Source: |
American Physical Society |
| Publisher Information: |
American Physical Society |
| Publication Year: |
2014 |
| Collection: |
DSpace@MIT (Massachusetts Institute of Technology) |
| Description: |
Grover’s quantum search and its generalization, quantum amplitude amplification, provide a quadratic advantage over classical algorithms for a diverse set of tasks but are tricky to use without knowing beforehand what fraction λ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction but, as a consequence, lose the very quadratic advantage that makes Grover’s algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of λ. ; National Science Foundation (U.S.) (RQCC Project 1111337) ; United States. Army Research Office (Quantum Algorithms Program) ; National Science Foundation (U.S.). Integrative Graduate Education and Research Traineeship (Interdisciplinary Quantum Information Science and Engineering Integrative Graduate Education and Research Traineeship) |
| Document Type: |
article in journal/newspaper |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
http://dx.doi.org/10.1103/PhysRevLett.113.210501; Physical Review Letters; https://hdl.handle.net/1721.1/91683 |
| Availability: |
https://hdl.handle.net/1721.1/91683 |
| Rights: |
Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. ; American Physical Society |
| Accession Number: |
edsbas.3F01F174 |
| Database: |
BASE |