Lectures on Fast Quantum Algorithms
Abstract
We provide an overview of the most important
computational problems in which quantum computers appear to have
exponential advantage over classical randomized algorithms.
These include the most striking results in the field such as
factoring integers, calculating discrete logarithms (Shor's
polynomial time methods), computing unit groups and class groups
of number fields (Hallgren and independently Schmidt and Vollmer).
We will also discuss some of the most significant open problems in this
area, especially the noncommutative case of the Hidden Subgroup Problem
(as a possible approach to the Graph Isomorphism problem). We shall also
outline the basic tools used in the existing fast quantum algorithms as well
as some promising results including the sources of motivation for the
computational algebra problems discussed in the conference talk given
by the lecturer (see
slides).
Outline
-
Introduction, basic tools
- Simon's problem, The Quantum Fourier Transform,
phase estimation, period finding, QFT over abelian groups.
- Reading:
-
D.R. Simon, "On the power of quantum computation", Proc. FOCS 1994, SIAM J.
COMPUT 1997.
-
R. Cleve, A. Ekert, C. Macchiavello and M. Mosca, "Quantum algorithms
revisited", Proc. R. Soc. Lond. A 1998,
arXiv:quant-ph/9708016.
-
The (finite) Abelian HSP
- The HSP, examples, coset states, Abelian Fourier Sampling,
applications: discrete log and generalizations
- Reading:
-
R. Jozsa, "Quantum factoring, discrete logarithms and the hidden
subgroup problem", Computing in Science and Engineering 2001,
arXiv:quant-ph/0112084
-
K. K. H. Cheung, M. Mosca, "Decomposing Finite Abelian Groups",
arXiv:cs/0101004v1
(2001)
-
J. Watrous,
"Quantum algorithms for solvable groups", Proc. STOC 2001,
arXiv:quant-ph/0011023
- G. Ivanyos, F. Magniez, M. Santha,
"Efficient quantum algorithms for some instances of the non-Abelian hidden
subgroup problem", Proc. SPAA 2001,
arXiv:quant-ph/0102014
-
Infinite Abelian HSPs
- HSP in lattices, hidden real lattices, computing the unit group of
number fields,
open problems
- Reading:
-
R. Jozsa, "Quantum computation in algebraic number theory:
Hallgren's efficient quantum algorithm for solving Pell's equation",
Annals of Physics 2003,
arXiv:quant-ph/0302134
-
S. Hallgren, "Fast quantum algorithms for computing the unit group
and class group of a number field",
Proc. STOC 2005.
-
A. Schmidt, U. Vollmer, "Polynomial time quantum algorithm for the computation of the unit group of a
number field",
Proc. STOC 2005.
-
Hidden shifts and related problems
- Query complexity of the HSP,
a possible reduction to subgroups and factors,
dihedral HSP,
Kuperberg's algorithm, disequation-based approach,
open problems
- Reading:
-
M. Ettinger, P. Høyer, E. Knill,
"The quantum query complexity of the hidden subgroup problem is
polynomial",
Information Processing Letters 2004,
arXiv:quant-ph/0401083
-
O. Regev, "Quantum computation and lattice problems",
SIAM Journal on Computing 2004,
arXiv:cs/0304005.
-
G. Kuperberg,
"A subexponential-time quantum algorithm for the dihedral hidden
subgroup problem",
SIAM Journal on Computing 2006,
arXiv/quant-ph/0302112.
- K. Friedl, G. Ivanyos, F. Magniez, M. Santha, P. Sen,
Hidden translation and orbit coset in quantum computing,
Proc. STOC 2003,
arXiv:quant-ph/0211091.
Hidden polynomials, subgroups and relaxed sytems
of equations
- PGM-based algorithms for hidden polynomials and
the HSP in cyclic/abelian groups, etc. (Not discussed.)
- Reading:
- D. Bacon, A. M. Childs, W. van Dam,
"From optimal measurement to efficient quantum algorithms for the
hidden subgroup problem over semidirect product groups", FOCS 2005,
arXiv:quant-ph/0504083]
-
T. Decker, J. Draisma, P. Wocjan,
"Efficient quantum algorithm for identifying hidden polynomials",
QIC 2009,
arXiv:0706.1219[quant-ph].
-
G. Ivanyos, L. Sanselme, M. Santha,
"An efficient quantum algorithm for the hidden subgroup problem in nil-2
groups", Proc. LATIN 2008,
arXiv:0707.1260[quant-ph].
-
Further topics (not discussed)
- Other shift problems (character sums, subsets, boolean functions);
estimating Gauss sums; simulation and BQP-complete problems;
non-commutative QFT; limitations of certain approaches to the HSP;
etc.
Slides:
Further reading:
-
M. Batty, S. L. Braunstein, A. J. Duncan, S. Rees,
"Quantum Algorithms in Group Theory",
In:
Combinatorial and Experimantal Group Theory, AMS 2004,
arXiv:quant-ph/0310133.
- A. M. Childs, W. van Dam,
"Quantum algorithms for algebraic problems", to appear,
arXiv:0812.0380[quant-ph].
Slides and literature for a related course (2006).
Page created by Gábor Ivanyos.