Elsevier

Theoretical Computer Science

Volume 292, Issue 3, 31 January 2003, Pages 597-610
Theoretical Computer Science

One complexity theorist's view of quantum computing

https://doi.org/10.1016/S0304-3975(01)00377-2Get rights and content
Under an Elsevier user license
open archive

Abstract

The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. The tools of computational complexity theory should come to bear on these important questions.

Quantum computing often scares away many potential researchers in computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic.

This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it.

Cited by (0)

Based on a talk first presented at the Second Workshop on Algorithms in Quantum Information Processing at DePaul University, Chicago, January 21, 1999. A preliminary version appeared in Proceedings of Computing: The Australasian Theory Symposium 2000. www.neci.nj.nec.com/homepages/fortnow.