Boston University | Center for Computational Science
HomeNews and EventsResearchEducationPeopleSeminarsFacilitiesContact Us

"The Computational Power of Small Quantum Circuits"

Steve Homer
Computer Science Department
Boston University
December 9, 2005
If quantum computational circuits are ever built, they will be relatively small and built from simple quantum gates. The power and limits of resource-bound quantum circuits is examined and compared to their classical counterparts.
In particular it is shown that;
- several of the most interesting quantum algorithms can be carried out using relatively small depth and width quantum circuits. This includes, for example, the efficient computation of the QFT.
- even constant-depth classical circuits are stronger than their classical counterparts. In particular such circuits can compute the parity function, a function which cannot be computed as efficiently classically.
- testing whether a constant depth quantum circuit has non-zero acceptance probability is a provably computationally difficult problem. It is hard for the polynomial time hierarchy.

copyright © 2006, Center for Computational Science | Boston University , MA, 02215