ASSESSMENT OF CURRENT RESULTS AND OUTLOOK ON FUTURE EFFORTS
QUANTUM INFORMATION SCIENCE THEORY
QUANTUM ALGORITHMS & COMPLEXITY
Following Deutsch's fundamental work in 1985 that demonstrated the potential power of quantum algorithms and quantum computers, Shor demonstrated in 1994 that integers can be efficiently factorized on a quantum computer. Factoring is the task of decomposing an integer, say 15, into a product of prime numbers: 15=3*5. Its importance is immense because many modern cryptographic protocols (for instance the famous RSA cryptosystem) are based on the fact that factoring large integers, as well as computing discrete logarithms, is a hard problem on a classical computer. Shor's result means that quantum computers could crack most classical public-key cryptosystems used at present. It has lead to extensive work on developing new quantum algorithms. Progress has been made on the Hidden Subgroup problem (which generalizes Shor's algorithm) in the case of non-Abelian groups, like affine groups, the dihedral group, or solvable groups with small exponent. A quantum algorithm was discovered for finding solutions to Pell's equation, which is an important problem in algebraic number theory. Strong links have been established between known quantum algorithms and lattice problems. Finally Grover's quantum "data base" search algorithm allows a quantum computer to perform an unstructured search quadratically faster than any classical algorithm.
In parallel with the development of new quantum algorithms, new algorithmic techniques have been developed. Examples of these are adiabatic quantum computing which is a very versatile method of approaching virtually any computational task; and quantum random walks which have enabled important generalizations of Grover's search algorithm. There has also been considerable development of new protocols for quantum communication. The objective may be to carry out a task which is possible classically, but with significantly less communication, such as Quantum Fingerprinting or the Hidden Matching problem. Or it may be to realize tasks which are impossible classically such as biased Coin Tossing and Quantum Bit String Generation, resilient and unconditionally secure Digital Signatures, or Private Information Retrieval. The importance of these latter tasks lies in their application to "mistrustful cryptography", this is the field of cryptography dealing with the problem of two or more people who do not trust each other, but must accomplish some goal together (for instance concluding a commercial deal, consulting a data base, etc.).We expect that the existing protocols will be improved and will gradually be implemented in the laboratory (as was recently the case for quantum bit string generation). We also expect the development of new protocols for quantum communication.
Key references
[1] D. Deutsch, Quantum Theory, the Church-Turing principle and the universal quantum computer, Proc. R. Soc. Lond. A 400, 97 (1985).
[2] P.W. Shor, Algorithms for quantum computation, discrete log and factoring, FOCS'35, 124 (1994).
[3] L. Grover, A fast quantum mechanical algorithm for database search, STOC'28, 212 (1996).
[4] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, Quantum fingerprinting, Phys. Rev. Lett. 87, 167902 (2001).
[5] L. P. Lamoureux, E. Brainis, D. Amans, J. Barrett, and S. Massar, Provably secure experimental quantum bit string generation, Phys. Rev. Lett. 94, 050503 (2005)
