Two Classical Queries versus One Quantum Query
| dc.creator | van Dam, Wim | |
| dc.date | 1998-06-27 | |
| dc.date | 1998-08-26 | |
| dc.date.accessioned | 2026-07-07T06:15:16Z | |
| dc.date.available | 2026-07-07T06:15:16Z | |
| dc.description | In this note we study the power of so called query-limited computers. We compare the strength of a classical computer that is allowed to ask two questions to an NP-oracle with the strength of a quantum computer that is allowed only one such query. It is shown that any decision problem that requires two parallel (non-adaptive) SAT-queries on a classical computer can also be solved exactly by a quantum computer using only one SAT-oracle call, where both computations have polynomial time-complexity. Such a simulation is generally believed to be impossible for a one-query classical computer. The reduction also does not hold if we replace the SAT-oracle by a general black-box. This result gives therefore an example of how a quantum computer is probably more powerful than a classical computer. It also highlights the potential differences between quantum complexity results for general oracles when compared to results for more structured tasks like the SAT-problem. | |
| dc.description | 6 pages, LaTeX2e, no figures, minor changes and corrections | |
| dc.identifier | https://arxiv.org/abs/quant-ph/9806090 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/9806090 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/93744 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | Two Classical Queries versus One Quantum Query | |
| dc.type | text |