Physics – Quantum Physics
Scientific paper
1998-06-27
Physics
Quantum Physics
6 pages, LaTeX2e, no figures, minor changes and corrections
Scientific paper
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.
No associations
LandOfFree
Two Classical Queries versus One Quantum Query does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Two Classical Queries versus One Quantum Query, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two Classical Queries versus One Quantum Query will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-142463