Towards scalable quantum computing: algorithmic challenges

Date/Time: Mon.18th March 2013 / 15:00-17:30 - ()

Speaker: Prof. Ilia Polian (University of Passau, Germany)

Building a scalable quantum computer that can process a large number of quantum bits (qubits) is one of the grand challenges of modern science. While first small quantum computers have been experimentally demonstrated and a number of implementation technologies have been suggested, all of them encounter difficulties when it comes to scaling. Topological quantum computing is a paradigm that offers a path to scalability. It strikes a balance between systematic, intuitive methods to design large computations, and relatively loose requirements on the vulnerability of individual qubits to errors. The availability of a platform for implementing large quantum algorithm constitutes the need for methods to manage design complexity, many of which are well-known in classical computer engineering. They include automatic synthesis, optimization, compaction, verification and visualization of topological quantum computers. While all these steps can be practically done by hand for very small quantum circuits, non-trivial quantum algorithms will require design automation. The talk will outline the open problems in this emerging area and focus on their similarities and differences compared with the case of classical computers. Topological quantum computers have an intuitive graphical representation that helps to abstract from their technology-specific aspects and allows reduction of individual problems to known methods. For example, compaction of topological quantum computers can be mapped to a variant of constrained three-dimensional bin-packing problem. While the talk will indicate first ideas how to solve some of the problems, the understanding of the appropriate algorithms is limited and many open question that can be answered by collaborative research remain.