The development of new quantum algorithms.

The first objective of this project is to obtain new efficient quantum algorithms and on the long term achieve a form of quantum programming, i.e. a way to derive quantum algorithms. The second objective is to investigate which aspects of 'superposition' - the noncausal aspects, such as realized by the quantum entanglement of the different entities, or the pure algebraic aspects, as realized by the linearity of the quantum state space - lie at the heart of the superior performance of the quantum computer, with a view to proving this superiority and/or deriving new classical parallel algorithms with a superior performance. Although quantum computing is generally considered as a new promising research area [1], it is not understood clearly at this moment how existing successful algorithms like Shor's algorithm [2] and Grover's algorithm [3] manage to exploit the properties of quantum computers to make computations more efficient. The state of a quantum computer working with n quantum bits (qubits) is described by a very large (2n-dimensional) Hilbert space on which unitary operations are performed. The challenge of quantum computing is to exploit this size of the state space to obtain efficient algorithms. It is difficult however to make this search in a broad spectrum of possibilities manageable and transparent without losing the required complexity that leads to the intrinsic computational power of quantum computers. Recently, the research group ESAT-SCD of the K.U.Leuven developed an approach that should make this possible, using advanced linear algebra techniques in binary vector spaces (over GF(2)). To prove the intrinsic computational advantage and/or to derive new classical methods using the same techniques we rely on the know how of the group FUND-CLEA of the V.U.B where an important model was developed in which quantum and classical systems can be studied in a unified framework.