The relatively new field of quantum computing has seen rapid growth in the past two decades. Quantum computing spans the theoretical and applied sides of both computer science and quantum physics. From its beginnings as a thought experiment, its growth into formal system, and finally its detailed analysis and construction, the development of quantum computing has paralleled the early development of classical computing.
In Section 1.1 we briefly examine some of the reasons for interest in quantum computing. We then turn our attention to early results and prominent quantum algorithms in Section 1.2. We review the theory and notation of quantum computing in Section 1.3. Following that we underline the importance of lower bounds in Section 1.4, and summarize our results in Section 1.5.