An Introduction to Quantum Complexity Theory
Richard Cleve · WORLD SCIENTIFIC eBooks · 2001
We give a basic overview of computational complexity, query complexity, and communication complexity, with quantum information incorporated into each of these scenarios. The aim is to provide simple but clear definitions, and to highlight the interplay between the three scenarios and currently-known quantum algorithms.