|
Click on a theme or a project in the table below for more information.
Project leader:
Prof.dr. Harry Buhrman (CWI)
Consortium:
CWI
Industrial partners (non-exhaustive):
University of Calgary, Waterloo, Paris-Sud, Berkeley, ULB Brussel
Total FTE: 2.30 (heads: faculty: 3, PhD: 2)
Key BRICKS publications:
| • |
Buhrman, Spalek: "Quantum verification of matrix products" In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006., pages 880-889
|
| • |
Brassard, Buhrman, Linden, Méthot, Tapp, Unger: "Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial" In: Physical Review Letters, 96, 250401 (2006)
|
| • |
Buhrman, Cleve, Laurent, Linden, Schrijver, Unger: "New Limits on Fault-Tolerant Quantum Computation" In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA. IEEE Computer Society 2006 pages 411-419
|
| • |
Buhrman, Christandl, Hayden, Hoi-Kwong Lo and Wehner : "Security of Quantum Bit String Commitment depends on the information measure" In: Physical Review Letters, 97, 250501 (2006)
|
| • |
Buhrman, Christandl, Unger, Wehner, and Winter: "Implications of Superstrong Nonlocality for Cryptography" In: Proceedings of the Royal Society A, vol. 462 (2071), pages 1919-1932 (2006)
|
|
Project AFM1: Quantum Information Processing
Many computational problems that turn up in industry, operations
research, network design, artificial intelligence, simulation of
physical systems, logic, number theory, combinatorics, algebra, and
computational biology, lack a fast or feasible algorithmic
solution. The best known algorithms for these problems are
horrendously slow. One of the central open problems in computer
science is the question of whether this slowness is inherent in
these problems or that we simply lack good programming techniques.
This question is known as the P versus NP question. The hardest
computational problems of the above type are called NP-complete
problems. It is widely believed that a feasible algorithmic
solution for these NP-complete problems does not exist.
Quantum computing devices are computing devices that take advantage
of the laws of quantum mechanics, whereas classical computers only
use classical mechanics. Quantum computers can outperform our
current, classical, technology of computing, due to the possibility
of massive exponential parallelism (the superposition principle)
and interference.
Quantum computing gained momentum after the break through result of
Peter Shor who demonstrated that the factoring problem can be
efficiently solved on a quantum computer, whereas no classical
algorithm is known that solves this problem quickly. His results
give some evidence that quantum computers can solve certain
computational problems more efficiently than classical computers.
One might hope that quantum computers can also efficiently solve
the above mentioned NP-complete problems. Indeed this would be of
tremendous impact on society and science. Although no feasible
classical solutions are known, the factoring problem is not an
NP-complete problem: it seems to be of an intermediate complexity.
The main question that needs to be solved in quantum computing,
apart from physical implementations, is whether there are other
computational problems or settings besides factoring that allow
efficient solutions on a quantum computer and for which no
efficient classical algorithm/procedure exists. Research questions
include:
- Find new fast quantum algorithms for problems for which no
fast classical algorithm is known, e.g. Hidden Subgroup
Problems for non Abelian groups
- Understand the power of quantum information processing:
when are quantum computing devices more efficient than
classical and when not?
- Find applications of quantum information processing in
classical computing, like the recent result in classical
coding theory via quantum computing
Note: Because of a late start of the two PhD's the results reported
here are obtained in closely related ongoing projects.
Industrial cooperation
The project has close cooperation with IBM, research institute in
Yorktown Heights, and with IDquantique in Geneva.
International cooperation
We work in close cooperation with University of
Calgary, Waterloo, Paris-Sud, Berkeley, ULB Brussels,
Bristol, Cambridge, Geneva and Aarhus. Recently we
started a project, in order to implement our
quantum string commitment protocol, with the
experimental quantum optics group at the Niels
Bohr Institute in Copenhagen.
Highlights 2006
Research highlights
Development of a new cryptographic protocol: quantum string
commitment; new fault tolerant thresholds due to unexpected
connection with non-locality and the EPR-paradox; development of an
efficient quantum matrix multiplication algorithm, and study of bit
commitment in the presence of sup strong, but still no local
correlations.
Economic & societal impact
Quantum Information Processing has the potential to revolutionarize
information processing and cryptography. The economical and
societal impact of quantum computing devices will be enormous.
Future work 2007-2009
Develop quantum cryptographic primitives, in particular make the
quantum string commitment protocols more efficient. Improve noise
threshold for quantum as well as for classical information
processing. Develop new quantum algorithms and communication
protocols and establish new lower bound techniques. Find
applications of quantum computations and simulations possibly
within the bio-computing area.
AFM1 Researchers funded by BRICKS
- Dr. Ben Toner (CWI)
- Dr. Nitin Saxena (CWI)
- Dr. Ronald de Wolf (CWI)
For more information, please refer to the publications and posters of this project.
|
