Algorithms and Complexity

Designing quantum software for future quantum computers, using fundamentally different techniques and approaches based on superposition, interference and entanglement.
Our research group designs software for the computing technology of the future, especially quantum computing. Based on the laws of quantum mechanics, which tell us that systems and particles can be in multiple states at once, quantum computing is radically different from computing as we know it. Our quantum software requires fundamentally different techniques and approaches based on superposition, interference and entanglement. Ultimately, our research will result in better, faster and more reliable computer systems for society. Our research group is involved in QuSoft, the new Dutch research centre for quantum software.
 
Leader of the group Algorithms and Complexity (A&C): Harry Buhrman.

There is great progress and opportunity in nonclassical computational technologies and algorithmics. These include exploiting novel computational aspects of physical phenomena, using nonclassical algorithms, or using classical algorithmics in a nonclassical manner. Key issues are feasibility of technology, efficiency of algorithms, and theoretical basics.

Novel technologies comprise coherent quantum mechanical and reversible low-energy computing. Example nonclassical improvements by quantum computing are:

  • Fast factoring (compromising current cryptosystems;) and
  • Square-root unordered search (enabling to quickly search unstructured databases.)
  • Better-than-classical communication complexity in computing certain functions by two or more parties (work done at CWI.)
  • Reversible computing is the only known technology to enable continuing advances in computing power by miniaturization in the medium long term (15-20 years) and mobilization of computing in the short term.

Novel aspects of classical algorithms include

  • distributed networking, security,
  • bio-informatics algorithmics and
  • automatic learning by compression.

The work programme in quantum algorithmics includes the design and analysis of new algorithms in the communication and the "black box'' model, and development of new tools to establish complexity bounds of such algorithms. We plan to test such algorithms collaborating with experimental groups in the USA. In reversible computing we develop new reversible simulations that simultaneously use less time and memory than any currently known algorithm. In machine learning we continue our work on algorithmic minimal sufficient statistics and minimal description length learning (MDL). Applications of algorithmic information theory (aka Kolmogorov complexity) in mathematics and algorithms are investigated and consolidated in a 3rd edition of the related textbook. A new research strain is planned and started in theoretical analysis and applications of computational biology. In particular in sequencing, analyzing genomic material in secondary and tertiary structure.

Some former group members
Rudi Cilibrasi, Wim van Dam, Lance Fortnow, Peter Gacs, Jaap-Henk Hoepman, Hartmut Klauck, Michal KouckýTroy Lee, Zvi Lotker, Hein Röhrig, Steven de Rooij, Nitin Saxena, Robert Spalek, Barbara TerhalBen Toner, John Tromp, Falk Unger, Stephanie Wehner.

Partners: 
  • NeuroCOLT ESPRIT working group in neural and computational learning.
  • IPA, the Institute for Programming Research and Algorithmics.
  • OzsL, the Dutch Graduate School in Logic.
  • Cooperation with 12 other sites in the EU QAIP project
  • ILLC, the Institute for Logic, Language and Computation

 

Seminars: 

Our group hosts a seminar which meets roughly bi-weekly.