Quantum computers can quickly solve some problems which take ordinary computers millions of years or more. While a few quantum algorithms are known, there are not general methods for quickly solving problems on a quantum computer. This project is pursuing several promising avenues of research to develop new powerful quantum algorithms.
Current quantum algorithms generally consist of operations which are common to current computers, such as NANDs, XORs, and other logic operations, with the addition of one purely quantum operation: a Hadamard transform. A Hadamard matrix is a unitary matrix with each element of equal magnitude. Hadamard matrices arise naturally when considering group structures. Some classes of functions are easy to describe in terms of Hadamard matrices. We are studying these classes for various groups to produce new algorithms for quantum computers. We believe that the cases where quantum computers outperform classical computers is related to cases where the Hadamard matrices have a low complexity, and thus enable efficient quantum algorithms.
Hadamard matrices are not only applicable to quantum computing, they are also relevant to quantum communication. When one wants to characterize a particular quantum state, the most efficient measurements one can make form a special set of Hadamard matrices which are said to be mutually unbiased. These measurements have much in common with combinatorial designs, which have been used for the design of classical experiments. It is an important open problem to know if all quantum systems can be efficiently measured in using such mutually unbiased Hadamard matrices. We are pursuing a more general formulation of this problem which encompasses both quantum measurements as well as classical designs called mutually orthogonal Latin squares. This relationship should lead to new constructions of quantum measurements and new quantum algorithms.
The third part of this proposal is uncovering the role quantum entanglement plays in constructions of mutually unbiased Hadamard matrices. Quantum entanglement is perhaps the most unusual aspect of quantum systems. Indeed, it was Einstein who (along with coauthors) described an experiment so strange he believed it was evidence against the validity quantum mechanics. Ironically, the states described, known as EPR pairs, are now used in many quantum communication protocols. Until now, there has been very little study of Hadamard matrices to consider their entanglement. We have identified several problems which relate the non-existence of complete sets of unbiased Hadamards to the inability to find certain entangled states. This relationship, once explored, may yield new insights into the power of quantum entanglement in both quantum communication and quantum computing.
