Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black
box, but the aim is to compute function value for arbitrary input using as few queries as possible. In this paper we
concentrate on quantum query algorithm designing tasks. The main aim of research was to find new efficient algorithms
and develop general algorithm designing techniques. We present several exact quantum query algorithms for certain
problems that are better than classical counterparts. Next we introduce algorithm transformation methods that allow
significant enlarging of sets of exactly computable functions. Finally, we propose quantum algorithm designing methods.
Given algorithms for the set of sub-functions, our methods use them to design more complex one, based on algorithms
described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error
probability and number of queries.
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.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.