QnTM: Collaborative Research: Quantum Algorithms

点击翻译按钮获取中文摘要

1. Intellectual ImpactResearch is proposed on two Areas of Interest in NSF Solicitation 05-501: Development of a broadand general collection of quantum algorithms; Quantum simulation of quantum systems. Specifictopics: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 graphautomorphism problem may be formulated as a hidden subgroup problem over the symmetricgroup S n . The abelian case can be effectively computed with a quantum computer by repetitionof coset state preparation and Fourier sampling. The natural generalization of this method tononabelian groups is commonly referred to as the standard method for the nonabelian HSP. Theperformance of this algorithm depends upon properties of the irreducible complex representationsof the group. However in most cases they do not yet yield useful algorithms. Research is proposedon improving these methods as well as determining in which cases they are bound for failure andother 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 thecomputation registers. These issues are particularly pressing in the context of liquid-state NMRquantum computing as well as ion trap quantum computing, and we have studied them (especiallyin the NMR context) in the past, obtaining results that are nearly best-possible for closed-systemcooling. These results reveal, however, that closed-system cooling cannot be powerful enough toturn warm systems into large-scale quantum computers. We are therefore turning to the studyof open-system algorithmic cooling. This requires new algorithmic techniques. Also, since opensystems are more sensitive to decoherence than closed systems, more careful modeling of theseeffects 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 exposureof data to decoherence. We plan to explore these ideas further to a) improve the overhead in thenumber of ancillas discarded and therefore the total number of qubits required b) improve thethreshold and decrease computational overhead for more realistic error-models2. Broader ImpactSocietal impact: Even if quantum computers are a distant reality, encryption of data today so thatit cannot be decrypted at a future time, depends upon the development of cryptosystems resilientto attacks by quantum computers. This in turn demands an understanding of what problems areand 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 teachingquantum computation, which is also part of our efforts). We propose to create course material tomake this happen.