Fixed-Point Quantum Search with an Optimal Number of Queries
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, fi...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2014
|
| Online Access: | http://hdl.handle.net/1721.1/91683 https://orcid.org/0000-0001-7296-523X https://orcid.org/0000-0002-6211-982X https://orcid.org/0000-0001-9614-2836 |
| _version_ | 1811070427877867520 |
|---|---|
| author | Low, Guang Hao Yoder, Theodore James Chuang, Isaac L. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Low, Guang Hao Yoder, Theodore James Chuang, Isaac L. |
| author_sort | Low, Guang Hao |
| collection | MIT |
| 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 λ. |
| first_indexed | 2024-09-23T08:35:48Z |
| format | Article |
| id | mit-1721.1/91683 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:35:48Z |
| publishDate | 2014 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/916832022-09-23T13:08:10Z Fixed-Point Quantum Search with an Optimal Number of Queries Low, Guang Hao Yoder, Theodore James Chuang, Isaac L. 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. 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) 2014-11-21T19:47:51Z 2014-11-21T19:47:51Z 2014-11 2014-09 2014-11-18T23:00:02Z Article http://purl.org/eprint/type/JournalArticle 0031-9007 1079-7114 http://hdl.handle.net/1721.1/91683 Yoder, Theodore J., Guang Hao Low, Isaac L. Chuang. "Fixed-point quantum search with an optimal number of queries." Phys. Rev. Lett. 113, 210501 (November 2014). © 2014 American Physical Society https://orcid.org/0000-0001-7296-523X https://orcid.org/0000-0002-6211-982X https://orcid.org/0000-0001-9614-2836 en http://dx.doi.org/10.1103/PhysRevLett.113.210501 Physical Review Letters 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 application/pdf American Physical Society American Physical Society |
| spellingShingle | Low, Guang Hao Yoder, Theodore James Chuang, Isaac L. Fixed-Point Quantum Search with an Optimal Number of Queries |
| title | Fixed-Point Quantum Search with an Optimal Number of Queries |
| title_full | Fixed-Point Quantum Search with an Optimal Number of Queries |
| title_fullStr | Fixed-Point Quantum Search with an Optimal Number of Queries |
| title_full_unstemmed | Fixed-Point Quantum Search with an Optimal Number of Queries |
| title_short | Fixed-Point Quantum Search with an Optimal Number of Queries |
| title_sort | fixed point quantum search with an optimal number of queries |
| url | http://hdl.handle.net/1721.1/91683 https://orcid.org/0000-0001-7296-523X https://orcid.org/0000-0002-6211-982X https://orcid.org/0000-0001-9614-2836 |
| work_keys_str_mv | AT lowguanghao fixedpointquantumsearchwithanoptimalnumberofqueries AT yodertheodorejames fixedpointquantumsearchwithanoptimalnumberofqueries AT chuangisaacl fixedpointquantumsearchwithanoptimalnumberofqueries |