Properties and Application of Nondeterministic Quantum Query Algorithms

Details Properties and Application of Nondeterministic Quantum Query Algorithms Properties and Application of Nondeterministic Quantum Query Algorithms

2006-06-30

arxiv.org/abs/quant-ph/0606248v2

Physics

Quantum Physics

12 pages, 9 figures

Scientific paper

10.1117/12.720641

Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, zero-error, bounded-error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a fresh notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function.

Affiliated with

Also associated with

No associations

Rating

Properties and Application of Nondeterministic Quantum Query Algorithms 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 Properties and Application of Nondeterministic Quantum Query Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Properties and Application of Nondeterministic Quantum Query Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-117709