Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Quantum Query Algorithms for AND and OR Boolean Functions

Speaker: Alina Vasilieva
Slot: Array, 11:20-11:40, col. 1


Quantum algorithms can be analyzed in a query model to compute Boolean functions
where input is given in a black box and the aim is to compute function value for
arbitrary input using as few queries as possible. We concentrate on quantum
query algorithm designing tasks in this paper. The main aim of the research was
to find new efficient algorithms and develop general algorithm designing
techniques. In this article we propose quantum algorithm constructing methods.
Given algorithms for the set of sub-functions, our methods use them to build a
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. Methods offer constructions for computing AND
and OR kinds of Boolean functions.

websites: Arnold Beckmann 2008-05-19