Uselessness for an Oracle Model with Internal Randomness
We consider a generalization of the standard oracle model in which the oracle acts on the target with a permutation selected according to internal random coins. We describe several problems that are impossible to solve classically but can be solved by a quantum algorithm using a single query; we sho...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Rinton Press
2014
|
| Online Access: | http://hdl.handle.net/1721.1/88450 https://orcid.org/0000-0003-3220-7682 |
| _version_ | 1826212185658884096 |
|---|---|
| author | Harrow, Aram W. Rosenbaum, David J. |
| author2 | Massachusetts Institute of Technology. Department of Physics |
| author_facet | Massachusetts Institute of Technology. Department of Physics Harrow, Aram W. Rosenbaum, David J. |
| author_sort | Harrow, Aram W. |
| collection | MIT |
| description | We consider a generalization of the standard oracle model in which the oracle acts on the target with a permutation selected according to internal random coins. We describe several problems that are impossible to solve classically but can be solved by a quantum algorithm using a single query; we show that such infinity-vs-one separations between classical and quantum query complexities can be constructed from much weaker separations. We also give conditions to determine when oracle problems--either in the standard model, or in any of the generalizations we consider--cannot be solved with success probability better than random guessing would achieve. In the oracle model with internal randomness where the goal is to gain any nonzero advantage over guessing, we prove (roughly speaking) that k quantum queries are equivalent in power to 2k classical queries, thus extending results of Meyer and Pommersheim. |
| first_indexed | 2024-09-23T15:17:23Z |
| format | Article |
| id | mit-1721.1/88450 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:17:23Z |
| publishDate | 2014 |
| publisher | Rinton Press |
| record_format | dspace |
| spelling | mit-1721.1/884502022-09-29T13:56:42Z Uselessness for an Oracle Model with Internal Randomness Harrow, Aram W. Rosenbaum, David J. Massachusetts Institute of Technology. Department of Physics Harrow, Aram W. We consider a generalization of the standard oracle model in which the oracle acts on the target with a permutation selected according to internal random coins. We describe several problems that are impossible to solve classically but can be solved by a quantum algorithm using a single query; we show that such infinity-vs-one separations between classical and quantum query complexities can be constructed from much weaker separations. We also give conditions to determine when oracle problems--either in the standard model, or in any of the generalizations we consider--cannot be solved with success probability better than random guessing would achieve. In the oracle model with internal randomness where the goal is to gain any nonzero advantage over guessing, we prove (roughly speaking) that k quantum queries are equivalent in power to 2k classical queries, thus extending results of Meyer and Pommersheim. National Science Foundation (U.S.) (Grant CCF-0916400) National Science Foundation (U.S.) (Grant CCF-1111382) United States. Army Research Office (Contract W911NF-12-1-0486) United States. Intelligence Advanced Research Projects Activity (QCS program D11PC20167) 2014-07-22T12:07:54Z 2014-07-22T12:07:54Z 2014-05 2013-09 Article http://purl.org/eprint/type/JournalArticle 1533-7146 http://hdl.handle.net/1721.1/88450 Aram W. Harrow and David J. Rosenbaum. 2014. Uselessness for an oracle model with internal randomness. Quantum Info. Comput. 14, 7&8 (May 2014), 608-624. https://orcid.org/0000-0003-3220-7682 en_US http://dl.acm.org/citation.cfm?id=2638687 Quantum Information & Computation Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Rinton Press arXiv |
| spellingShingle | Harrow, Aram W. Rosenbaum, David J. Uselessness for an Oracle Model with Internal Randomness |
| title | Uselessness for an Oracle Model with Internal Randomness |
| title_full | Uselessness for an Oracle Model with Internal Randomness |
| title_fullStr | Uselessness for an Oracle Model with Internal Randomness |
| title_full_unstemmed | Uselessness for an Oracle Model with Internal Randomness |
| title_short | Uselessness for an Oracle Model with Internal Randomness |
| title_sort | uselessness for an oracle model with internal randomness |
| url | http://hdl.handle.net/1721.1/88450 https://orcid.org/0000-0003-3220-7682 |
| work_keys_str_mv | AT harrowaramw uselessnessforanoraclemodelwithinternalrandomness AT rosenbaumdavidj uselessnessforanoraclemodelwithinternalrandomness |