Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Query algorithms for detecting Hamming and Reed-Solomon codes

Edit abstract data

Speaker: Ruben Agadzanyan
Slot: Mon, 12:00-12:20, Drakopoulos (col. 1)

Abstract

In this talk we will compare quantum and classical query complexity of some
Boolean functions. This is the model where the Boolean function is known,
but its arguments are unknown. So, to compute the function, the query
algorithm asks for values of particular arguments. The complexity of the
algorithm is the number of queries. Up to now there have been discovered
some, though few, Boolean functions whose quantum query algorithm is better
than classical. Here we will talk about another group of such functions,
based on Hamming and Reed-Solomon error-correcting codes. There is a 25%
improvement with the quantum algorithm for the Hamming codes and a 50%
improvement for the Reed-Solomon codes (which repeats the previously best
known achievement).

websites: Arnold Beckmann 2008-05-19 Valid HTML 4.01! Valid CSS!