1. Intellectual Impact Research is proposed on two Areas of Interest in NSF Solicitation 05-501: Development of a broad and general collection of quantum algorithms; Quantum simulation of quantum systems. Specific topics: Hidden subgroup problems: The status of the non-abelian hidden subgroup problem (HSP) is one of the most fundamental open problems in quantum algorithms. In particular, the graph automorphism problem may be formulated as a hidden subgroup problem over the symmetric group S n . The abelian case can be effectively computed with a quantum computer by repetition of coset state preparation and Fourier sampling. The natural generalization of this method to nonabelian groups is commonly referred to as the standard method for the nonabelian HSP. The performance of this algorithm depends upon properties of the irreducible complex representations of the group. However in most cases they do not yet yield useful algorithms. Research is proposed on improving these methods as well as determining in which cases they are bound for failure and other methods are necessitated. Algorithmic cooling: Algorithmic cooling is an inescapable component of quantum algorithms: for example, we can even view fault-tolerant computing as moving heat (random errors) out of the computation registers. These issues are particularly pressing in the context of liquid-state NMR quantum computing as well as ion trap quantum computing, and we have studied them (especially in the NMR context) in the past, obtaining results that are nearly best-possible for closed-system cooling. These results reveal, however, that closed-system cooling cannot be powerful enough to turn warm systems into large-scale quantum computers. We are therefore turning to the study of open-system algorithmic cooling. This requires new algorithmic techniques. Also, since open systems are more sensitive to decoherence than closed systems, more careful modeling of these effects will be required. Fault-tolerant Quantum Comptutation: Decoherence is the major obstacle to the experimen- tal realization of quantum computers. Over the last year there have been two significant break- throughs in the ability to carry out fault-tolerant quantum computation in the presence of deco- herence. The main idea in both cases is the use of uniquely quantum features to limit the exposure of data to decoherence. We plan to explore these ideas further to a) improve the overhead in the number of ancillas discarded and therefore the total number of qubits required b) improve the threshold and decrease computational overhead for more realistic error-models 2. Broader Impact Societal impact: Even if quantum computers are a distant reality, encryption of data today so that it cannot be decrypted at a future time, depends upon the development of cryptosystems resilient to attacks by quantum computers. This in turn demands an understanding of what problems are and are not tractable on quantum computers, a core topic of the proposed research. Educational impact: Ideas from quantum computation and quantum information can poten- tially have a major impact on how basic quantum mechanics is taught (quite apart from teaching quantum computation, which is also part of our efforts). We propose to create course material to make this happen.
