Complexity and Quantum Algorithms

University South Carolina Research Foundation, Columbia SC

Investigators

Abstract

The objectives of this project are (1) to understand the power and limits of quantum algorithms, especially for group theoretic problems, and (2) to find new ways of implementing powerful quantum computing primitives. The project is in theoretical computer science, combining computational complexity theory, algorithms, and quantum informatics. It aims to find new quantum algorithms for important problems, and study the possibilities of ultrafast quantum computation via small-depth quantum circuits. A number of group theoretic algorithms, such as Hidden Subgroup, Hidden Translation, Group Intersection, have quantum algorithms for only a small class of groups. Recent techniques may widen the class of problems amenable to quantum solution. Our goal is to apply these techniques and develop new techniques for exanding the class of groups with fast quantum algorithms. Long quantum computations, corresponding to deep quantum circuits, may be difficult to maintain due to decoherence, The project therefore also focuses on computations that can be performed by very shallow circuits that are (of necessity) enhanced with highly nonlocal interactions (multibit gates) as primitives. One such multibit gate that has been shown to be quite powerful for shallow quantum circuits is the fanout gate, which copies a bit from one register to several other registers in one step. Recent work by the PI has shown that the fanout gate arises naturally from applying certain potentially feasible variants of well-understood spin-spin interactions between particles in a group. The project will study new ways in which fanout and other, similarly powerful, multibit gates may be ultimately implemented. The project will also continue work by the PI and others, studying the intrinsic strengths and weaknesses of shallow quantum circuits in general. Intellectual merit of the proposed activity Results of the project are rigorously mathematical in nature. They will be based both on the PI's expertise in computational complexity theory and on his contact with other computer scientists. The project will contribute to a basic understanding of feasible quantum computation. Broader impacts resulting from the proposed activity The project will promote collaborations between the University of South Carolina, an EPSCoR institution, and other institutions top-tier institutions, as well as collaboration among different departments at USC (Mathematics, Physics, and Computer Science). Graduate students will be intimately involved with the research, contributing to their Masters and Doctoral degrees. Results will be submitted to journals and conferences, and will be quickly disseminated on line in well-known archives such as http://arxiv.org/quant-ph and the Electronic Colloquium for Computational Complexity.