Report of Miklos Santha

I have been visiting SZTAKI in the framework of the EU contract
ICAI-CT-2000-700025 between October 29 and December 9, 2003.
During my stay I have performed the following tasks:

•	I have finished two papers which were submitted on November 6 to the 36th Annual ACM Symposium on the Theory of Computing to be held in 2004 in Chicago. Discussions with Katalin Friedl and Gábor Ivanyos appeared to be very useful in solving some subproblems of both papers.

The title of the first paper is ``Quantum and Classical Query Complexities of Local Search are Polynomially Related". The paper explores the problem of finding a local minimum in a neighborhood structure. Let f be an integer valued function on a finite set V. The problem of finding a local minimum for f can be phrased as: for a fixed graph G(V,E) find a vertex x such that f(x) is not bigger than any value that f takes on some neighbor of x. The complexity of the algorithm is measured by the number of questions of the form ``what is the value of f on x?'' In the paper it is shown that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This generalizes earlier results of Aldous and Aaronson.

The title of the second paper is ”Quantum Algorithms for the Triangle Problem". Here two new quantum algorithms are presented that either find a triangle in an undirected graph G, or reject if G is triangle free. The first algorithm uses combinatorial ideas with Grover Search, the second algorithm is based on a new design concept of Ambainis that incorporates the benefits of quantum walks into Grover search. Both algorithms solve the problem faster than what was previously known.

•	I have started research on two subjects with Gábor Ivanyos and
Katalin Friedl. The first deals with “Testing Group Operation Tables" and a writeup exists in a preliminary version. The problem we address is the following. Given a binary operation table on a finite set, accept if it is the correct multiplication table of a group, and reject if it is far from a correct multiplication table of any group. The distance here is the standard edit distance. In the case the table is close to a correct multiplication, but does not correspond to an exact one, the algorithm can freely accept or reject. This problem is well studied in the literature,
and currently only algorithms which take polynomial time in the size of the group are known. By introducing new types of tests on randomly selected elements of the set, we solve the problem in polylogarithmic time in the size of the group.
The second work concerns "Quantum Query Complexity of Sperner Lemma" and we have currently only partial results.

•	I have given three talks. On November 14, I gave an overview talk in SZTAKI on ``Introduction to Quantum Computing". This was the introductory talk of my visit to SZTAKI, and was attended by a relatively large number of people from SZTAKI and also from outside institutions. In my talk I gave an overview of the most important results obtained in quantum computing in the last ten years. In particular, I gave a detailed description of Grover's unstructured search algorithm and Shor's factorization. The talk led to discussions with several students attending it. One of them, Miklós Szurdi, came back afterwards on another day, and since he was interested in the subject, we have discussed several possible research direction for him.  Slides of the talk
are available from the web page   	http://www.sztaki.hu/infolab/quantum/santha2003.html

On November 21, I gave a talk in the Algebra seminar of the Eötvös University on the ``Hidden Subgroup Problem in Quantum Computing". This paradigmatical problem in the case of Abelian groups encompasses all the current successes of quantum computing, such as fast factorization or discrete logarithm computation. While the Abelian case is well understood, the non-Abelian case is currently wide open. Progress here would be more than welcome, since important problems, like graph-isomorphism, can be reduced to it. The current approaches for solving the problem use group representation theory, therefore the topics of the talk was well suited for this particular audience.
Finally on December 2, I gave a talk in the Complexity seminar of the Eötvös University on ``Local Search". The talk reported results of the paper described in the first task.

•	With Gábor Ivanyos, Katalin Friedl and Lajos Rónyai we started preliminary discussions on submitting a joint proposal in the EU 6th Framework IIT FET domain. Our proposal needs additional negotiations with other European partners. We will submit our ideas to the prospective partners at the Bratislava QIPC meeting in February 2004.