Share Email Print

Proceedings Paper

Properties and application of nondeterministic quantum query algorithms
Author(s): Alina Dubrovska
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

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, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new 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. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.

Paper Details

Date Published: 25 April 2007
PDF: 12 pages
Proc. SPIE 6573, Quantum Information and Computation V, 657310 (25 April 2007); doi: 10.1117/12.720641
Show Author Affiliations
Alina Dubrovska, Univ. of Latvia (Latvia)

Published in SPIE Proceedings Vol. 6573:
Quantum Information and Computation V
Eric J. Donkor; Andrew R. Pirich; Howard E. Brandt, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?