Fixed-point adiabatic quantum search
Fixed-point quantum search algorithms succeed at finding one of M target items among N total items even when the run time of the algorithm is longer than necessary. While the famous Grover's algorithm can search quadratically faster than a classical computer, it lacks the fixed-point property—t...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2017
|
| Online Access: | http://hdl.handle.net/1721.1/107805 https://orcid.org/0000-0001-9614-2836 https://orcid.org/0000-0001-7296-523X |
| _version_ | 1826195383040081920 |
|---|---|
| author | Dalzell, Alexander M. Yoder, Theodore James Chuang, Isaac |
| 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 Dalzell, Alexander M. Yoder, Theodore James Chuang, Isaac |
| author_sort | Dalzell, Alexander M. |
| collection | MIT |
| description | Fixed-point quantum search algorithms succeed at finding one of M target items among N total items even when the run time of the algorithm is longer than necessary. While the famous Grover's algorithm can search quadratically faster than a classical computer, it lacks the fixed-point property—the fraction of target items must be known precisely to know when to terminate the algorithm. Recently, Yoder, Low, and Chuang [Phys. Rev. Lett. 113, 210501 (2014)] gave an optimal gate-model search algorithm with the fixed-point property. Previously, it had been discovered by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)] that an adiabatic quantum algorithm, operating by continuously varying a Hamiltonian, can reproduce the quadratic speedup of gate-model Grover search. We ask, can an adiabatic algorithm also reproduce the fixed-point property? We show that the answer depends on what interpolation schedule is used, so as in the gate model, there are both fixed-point and non-fixed-point versions of adiabatic search, only some of which attain the quadratic quantum speedup. Guided by geometric intuition on the Bloch sphere, we rigorously justify our claims with an explicit upper bound on the error in the adiabatic approximation. We also show that the fixed-point adiabatic search algorithm can be simulated in the gate model with neither loss of the quadratic Grover speedup nor of the fixed-point property. Finally, we discuss natural uses of fixed-point algorithms such as preparation of a relatively prime state and oblivious amplitude amplification. |
| first_indexed | 2024-09-23T10:11:48Z |
| format | Article |
| id | mit-1721.1/107805 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:11:48Z |
| publishDate | 2017 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/1078052022-09-26T16:23:29Z Fixed-point adiabatic quantum search Dalzell, Alexander M. Yoder, Theodore James Chuang, Isaac Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Physics Dalzell, Alexander M. Yoder, Theodore James Chuang, Isaac Fixed-point quantum search algorithms succeed at finding one of M target items among N total items even when the run time of the algorithm is longer than necessary. While the famous Grover's algorithm can search quadratically faster than a classical computer, it lacks the fixed-point property—the fraction of target items must be known precisely to know when to terminate the algorithm. Recently, Yoder, Low, and Chuang [Phys. Rev. Lett. 113, 210501 (2014)] gave an optimal gate-model search algorithm with the fixed-point property. Previously, it had been discovered by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)] that an adiabatic quantum algorithm, operating by continuously varying a Hamiltonian, can reproduce the quadratic speedup of gate-model Grover search. We ask, can an adiabatic algorithm also reproduce the fixed-point property? We show that the answer depends on what interpolation schedule is used, so as in the gate model, there are both fixed-point and non-fixed-point versions of adiabatic search, only some of which attain the quadratic quantum speedup. Guided by geometric intuition on the Bloch sphere, we rigorously justify our claims with an explicit upper bound on the error in the adiabatic approximation. We also show that the fixed-point adiabatic search algorithm can be simulated in the gate model with neither loss of the quadratic Grover speedup nor of the fixed-point property. Finally, we discuss natural uses of fixed-point algorithms such as preparation of a relatively prime state and oblivious amplitude amplification. American Society for Engineering Education. National Defense Science and Engineering Graduate Fellowship MIT-Harvard Center for Ultracold Atoms MIT International Science and Technology Initiative National Science Foundation (U.S.) (RQCC Project 1111337) Massachusetts Institute of Technology. Undergraduate Research Opportunities Program (Paul E. Gray Endowed Fund) 2017-03-31T20:39:27Z 2017-03-31T20:39:27Z 2017-01 2016-09 2017-01-11T23:00:04Z Article http://purl.org/eprint/type/JournalArticle 1050-2947 1094-1622 http://hdl.handle.net/1721.1/107805 Dalzell, Alexander M., Theodore J. Yoder, and Isaac L. Chuang. “Fixed-Point Adiabatic Quantum Search.” Physical Review A 95.1 (2017): n. pag. © 2017 American Physical Society https://orcid.org/0000-0001-9614-2836 https://orcid.org/0000-0001-7296-523X en http://dx.doi.org/10.1103/PhysRevA.95.012311 Physical Review A 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 | Dalzell, Alexander M. Yoder, Theodore James Chuang, Isaac Fixed-point adiabatic quantum search |
| title | Fixed-point adiabatic quantum search |
| title_full | Fixed-point adiabatic quantum search |
| title_fullStr | Fixed-point adiabatic quantum search |
| title_full_unstemmed | Fixed-point adiabatic quantum search |
| title_short | Fixed-point adiabatic quantum search |
| title_sort | fixed point adiabatic quantum search |
| url | http://hdl.handle.net/1721.1/107805 https://orcid.org/0000-0001-9614-2836 https://orcid.org/0000-0001-7296-523X |
| work_keys_str_mv | AT dalzellalexanderm fixedpointadiabaticquantumsearch AT yodertheodorejames fixedpointadiabaticquantumsearch AT chuangisaac fixedpointadiabaticquantumsearch |