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...
| Κύριοι συγγραφείς: | , , |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Άρθρο |
| Γλώσσα: | English |
| Έκδοση: |
American Physical Society
2014
|
| Διαθέσιμο Online: | 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 |
| Περίληψη: | 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 λ. |
|---|