Principal Investigator: Dr Miklos Santha
The Project
The University of Paris-South is mainly involved in the subproject Theory.
We collaborate with many partners within QAP and publish very frequently in
the highly competitive Symposium on Theory of Computing (STOC) and Symposium
on the Foundations of Computer Science (FOCS), as well as in the highly
competitive journal Physical Review Letters. Our work covers most aspects of
the theory of quantum information, including quantum algorithms, quantum
communication and quantum complexity and thus serves as an important support
for the other, more applied, subprojects, but also for all the QIPC
initiatives in Europe.
Algorithmic Methods
We coordinate the workpackage Algorithmic Methods and collaborate with many
QAP partners, including TAU, CWI, IPSAS, Waterloo, ULB. It is clear that in
order to obtain substantial progress on algorithmic questions new
algorithmic techniques have to be developed. To date, there are only a few
such techniques, and most efficient quantum algorithms rely on the quantum
Fourier transform. But some promising new techniques have been introduced
recently, such as quantum random walks, adiabatic quantum computing, and the
use of perturbation theory in quantum algorithms. This workpackage will be
devoted to research into new algorithmic techniques and further study of
existing methods. Specifically, we use quantum walks for state generation,
and as an algorithmic tool. Moreover, we want to apply adiabatic computation
as a tool in algorithmic construction and investigate its usefulness for
fault tolerance. Last, we would like to investigate the power of
perturbation theory as a tool in constructing quantum proofs and quantum
algorithms. Results from this workpackage will serve as input for
workpackage 5.1.
Algorithms and Complexity
We are a main collaborator in the workpackage Algorithms and Complexity,
whose goal is the fundamental work on quantum algorithms, simulation of
quantum systems, complexity classes, and other areas of theoretical quantum
information. We would like to develop new quantum algorithms for lattice
problems, for the hidden subgroup problem and for graph problems.
Furthermore, we would like to improve our understanding of quantum
complexity classes and quantum communication complexity. Last, we are very
interested in continuing to obtain results on classical computation using
quantum techniques.
Other QAP Related Activities
Researchers at the University of Paris South are also involved in other workpackages, including Testing quantum systems and Protocols for Quantum Commerce.
UPS have organised five meetings and conferences in 2006, listed below:
- QIP'06 - Jan 16-20, 2006, ninth workshop in Quantum Information Processing - largest conference in this area - 250 participants, organised by LRI-group (see www.lri.fr/ qip06)
- IHP trimester in QUANTUM INFORMATION, COMPUTATION AND COMPLEXITY - trimester at the Poincare Institute, Paris, Jan. 9- April 7, 2006, co-organised by Miklos Santha, LRI, about 150 participants
- QAP kick-off meeting - IHP Paris, Feb. 12, 2006, co-organised by LRI
- QIPC cluster meeting - IHP Paris, Feb. 13-15, 2006, co-organised by LRI
- QAP-RESQ meeting - IHP, Paris, March 6-8, 2006, co-organised by LRI
Julia Kempe, member of LRI, has received two prestigous awards:
- Prix Irene Joliot-Curie de la jeune femme scientifique (best young female researcher of the year 2006 cross all sciences, given by the French Ministry of Science)
- Medaille Bronze du CNRS (best young computer scientist of the year 2006 in France)
We have written a vulgarization article on quantum computing that was published in the highly regarded journal La Recherche (the French equivalent of Scientific American).
List of Publications
QAP
J. Degorre, S. Laplante and J. Roland, Simulation of bipartite qudit correlations, accepted for publication in Phys. Rev. A quant-ph/0608064
D. Gavinsky, J. Kempe I. Kerenidis et al, Exponential separations for one-way quantum communication complexity, with applications to cryptography (2006) quant-ph/0611209
D. Gavinsky, J. Kempe and R. de Wolf, Exponential separation of quantum and classical one-way communication complexity for a Boolean Function (2006) quant-ph/0607174
P. Hoyer, T. Lee and R. Spalek, Negative weights make adversaries (2006) quant-ph/0611054
J. Kempe, L. Pyber and A. Shalev, Permutation groups, minimal degrees and quantum computing (2006) quant-ph/0607204
I. Kerenidis and R. Raz, The one-way communication complexity of the Boolean Hidden Matching Problem (2006) quant-ph/0607173
F. Magniez, A. Nayak, J. Roland et al, Search via quantum walk (2006) quant-ph/0608026
W. van Dam, F. Magniez, M. Mosca and M. Santha,, Self-Testing of universal and fault-tolerant sets of quantum gates, accepted for publication in SIAM. J. Computing
I. Kerenidis, Quantum multiparty communication complexity and circuit lower bounds, accepted for publication in Mathematical Structures in CS. (sp. issue)
F. Magniez, A. Nayak, J. Roland, and M. Santha., Search via quantum walk, accepted for publication in STOC. 2007
A. Chailloux and I. Kerenidis, Honest Verifier Quantum Statistical Zero Knowledge for all Interactive Proofs, submitted to conference
A. Chailloux and I. Kerenidis, The role of help in Classical and Quantum Zero-Knowledge, submitted to conference
A. Childs and T. Lee, Optimal quantum adversary lower bounds for ordered search (2007) quant-ph/0708.3396
J. Degorre, M. Kaplan, S. Laplante et al, The communication complexity of non-signaling distributions (2008) quant-ph/0804.4859
D. Gavinsky, J. Kempe I. Kerenidis et al, Exponential separations for one-way quantum communication complexity, with applications to cryptography, accepted for publication in SIAM. J. Computing
P. Richter, Two remarks on the local Hamiltonian problem (2007) quant-ph/0712.4274
Related work
N. J. Cerf, J. Clavareau, C. Macchiavello et al, Quantum entanglement enhances the capacity of bosonic channels with memory, Phys. Rev. A 72 042330 (2006)
Julien Degorre, Sophie Laplante, and Jeremie Roland, Simulating quantum correlations as a distributed sampling problem, Phys. Rev. A 72 062314 (2006) quant-ph/0507120
Julia Kempe, Approaches to Quantum Error Correction, book chapter in Decoherence, Birkhaeuser (2006)
E. Kashefi and I. Kerenidis, Statistical Zero Knowledge and quantum one-way functions, PQCrypto 2006 (2006) quant-ph/0511266
J. Fern, J. Kempe, S. Simic et al, Fault-tolerant quantum computation -- a dynamical systems approach, IEEE. TAC 51.3 448-459 (2006) quant-ph/0409084
P. Hoyer, T. Lee and R. Spalek, Tight adversary bounds for composite functions (2006) quant-ph/0509067
S. Iblisdir and J. Roland, Optimal finite measurements and Gauss quadratures., accepted for publication in Phys. Lett. A quant-ph/0410237
I. Kerenidis and D. Nagaj, On the Optimality of Quantum Encryption Schemes, Journal of Mathematical Physics 47 092102 (2006) quant-ph/0509169
J. Kempe, A. Kitaev and O. Regev, The Complexity of the Local, SIAM. J. Computing 355 1070-1097 (2006)
F. Magniez, D. Mayers, M. Mosca et al, Self-Testing of Quantum Circuits, Proceedings of 33rd ICALP (2006) quant-ph/0512111
J. Kempe, Quantum Algorithms: book chapter in "Lectures on Quantum Information", Whiley-VCH (2006)
G. Ivanyos, L. Sanselme and M. Santha, An efficient quantum algorithm for the hidden subgroup problem in nil-$2$ groups (2007) quant-ph/07071260
A. Chailloux, D. Ciocan, I. Kerenidis et al., Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model, Theory Cryptography Conference TCC (2008)
P. Richter, The quantum complexity of Markov chain Monte Carlo, Logic and Theory Algorithms 5028 (2008)
P. Richter, Quantum algorithms for triangle finding, Springer-Verlag (2008)
P. Richter, M. Szegedy, Quantization of Markov chains, Springer-Verlag (2008)
M. Santha, Quantum walk based search algorithms, 5th Int Conf TAMC, LNCS. 4978 (2008)