Quantum computation has been a very active research area for the past decade. Feynman initiated the idea of building a computer that exploits laws of quantum mechanics in order to solve computing problems that could not be solved efficiently on classical computers. Today, two main results lend credence to this model of computation. P. Shor gave a quantum algorithm that, in polynomial time, decomposes any integer into its prime factors [22], whereas no such algorithm is known in the classical models of computation. Indeed, that best classical algorithms need exponential time to factorize. This renders vulnerable to quantum computers the main public key cryptosystems, such as RSA. A few years later, L. Grover designed an algorithm that finds any marked element in an unstructured list [6], and whose running time quadratically improves over the best possible randomized algorithm. The main motivation for a quantum computer, illustrated by the above results, is to solve tasks more efficiently than classically. While the ultimate goal is an exponential improvement, any polynomial speedup can be also very helpful, and certainly are worth of investigation. This research projects targets both of these aspects of quantum computing, among others in the field of group theoretical algorithms and quantum walk based search procedures.

Group theoretical algorithms: Efficient solutions to some cases of the hidden subgroup problem (HSP), a paradigmatic group theoretical problem, constitute probably the most notable success of quantum computing. The problem consists in finding a subgroup H in a finite group G hidden by some function which is constant on each coset of H and is distinct in different cosets. The hiding function can be accessed by an oracle, and in the overall complexity of an algorithm, a query counts as a single computational step. To be efficient, an algorithm has to be polylogarithmic in the order of G. While classically not even query efficient algorithms are known for the HSP, it can be solved efficiently in abelian groups by a quantum algorithm. A detailed description of the so called standard algorithm can be found for example [18]. The main quantum tool of this algorithm is Fourier sampling, based on the efficiently implementable Fourier transform in abelian groups. Factorization and discrete logarithm [22] are special cases of this solution. Since the realization of the importance of the abelian HSP, intensive efforts have been made to solve the hidden subgroup problem also in finite non-abelian groups. The intrinsic mathematical interest of this challenge is increased by the fact that several famous classical algorithmic problems can be cast in this framework, like for example the graph isomorphism problem. The successful efforts for solving the problem can roughly be divided into two categories. The standard algorithm has been extended to some non-abelian groups by Rotteler and Beth [20], Hallgren, Russell and Ta-Shma [7], Grigni, Schulman, Vazirani and Vazirani [5] and Moore, Rockmore, Russell and Schulman [17] using efficient implementations of the quantum Fourier transform over these groups. In a different approach, Ivanyos, Magniez and Santha [8], Friedl, Ivanyos, Magniez, Santha and Sen [4], and Ivanyos, Sanselme and Santha [9] have efficiently reduced the HSP in some non-abelian groups to HSP instances in abelian groups using classical and quantum group theoretical tools, but not the non-abelian Fourier transform. The complexity of some specific cases of the HSP is of particular interest. For example, the hidden subgroup problem in the dihedral group is related to certain lattice problems [19]. For this group, we know that polynomial time quantum Fourier sampling gives out enough information to determine the subgroup. Unfortunately, the known classical algorithms for this task require exponential time. In a somewhat different approach, Kuperberg [11] has shown that there was a subexponential time quantum algorithm for this problem. The design of a polynomial time quantum algorithm for this problem would be a major breakthrough.

Quantum walk based algorithms: Discrete time quantum walks were introduced gradually by Meyer [15,16] in connection with cellular automata, by Watrous in his works related to space bounded computations [24], and by Ambainis et al [2]. They can be thought of as the counterpart of classical random walks. Random walks have many applications in classical algorithms, and it is conjectured that quantum walks will prove equally important for quantum algorithms. Furthermore, given the similarities between classical Markov chains and their quantum counterparts, it is reasonable to suppose that the study of quantum walks will benefit from the vast existing body of knowledge in the classical field. Several quantities of quantum walks, like mixing and hitting times, have already been shown to be faster in quantum walks than in the classical case, sometimes even exponentially. For example, it was shown by Kempe [10] that on the n-dimensional hypercube, reaching the opposite node by a quantum walk has a polynomial hitting time, whereas a random walk requires exponential time. A particulary promising algorithmic application of quantum walks is searching, and several important contributions have been made into this direction. The potential of quantum walks in this direction were first pointed out in [21] where a quantum walk based simulation of Grover search is designed. Ambainis, in his seminal paper [1], used quantum walks on the Johnson graphs to settle the query complexity of the Element Distinctness problems. Inspired by the work of Ambainis, Szegedy [23] designed a general method to quantize classical Markov chains, and developed a systematic theory of quantum walk based search algorithms. A similar approach for the specific case of searching in grids was taken by Ambainis, Kempe and Rivosh [3]. The frameworks of Ambainis and Szegedy have been successfully applied in various contexts to find algorithms with substantial complexity gains over simple Grover search. In particular Magniez, Santha and Szegedy have designed algorithms for finding a triangle in a graph [14], and Magniez and Nayak used quantum walks for deciding if a group operation is commutative [12]. Using phase estimation, Magniez, Nayak, Roland and Santha have proposed a new quantum walk based search method [13] that expanded the scope of the previous approaches. This algorithm is also conceptually simple, and improves various aspects of many walk based algorithms. In the context of quantum walks a particularly intriguing area is the study of the query complexity of monotone graph properties.

Progress

Publications

References

Back