Editing BQP (section)

=== BQP and EXP ===

We begin with an easier containment. To show that <math>\mathsf{BQP} \subseteq \mathsf{EXP}</math>, it suffices to show that APPROX-QCIRCUIT-PROB is in EXP since APPROX-QCIRCUIT-PROB is BQP-complete.

{{Math theorem|name=Claim|<math>\text{APPROX-QCIRCUIT-PROB} \in \mathsf{EXP}</math>}}

{{math proof|1=The idea is simple. Since we have exponential power, given a quantum circuit {{mvar|C}}, we can use classical computer to stimulate each gate in {{mvar|C}} to get the final state. 

More formally, let {{mvar|C}} be a polynomial sized quantum circuit on {{mvar|n}} qubits and {{mvar|m}} gates, where m is polynomial in n. Let <math>|\psi_0\rangle = |0\rangle^{\otimes n}</math> and <math>|\psi_i\rangle</math> be the state after the {{mvar|i}}-th gate in the circuit is applied to <math>|\psi_{i-1}\rangle </math>. Each state <math>|\psi_i \rangle</math> can be represented in a classical computer as a unit vector in <math>\mathbb C^{2^n}</math>. Furthermore, each gate can be represented by a matrix in  <math>\mathbb C^{2^n \times 2^n}</math>. Hence, the final state <math>|\psi_m \rangle </math> can be computed in <math>O(m\cdot 2^{2n})</math> time, and therefore all together, we have an <math>2^{O(n)}</math> time algorithm for calculating the final state, and thus the probability that the first qubit is measured to be one. This implies that <math>\text{APPROX-QCIRCUIT-PROB} \in \mathsf{EXP}</math>.}}

Note that this algorithm also requires <math>2^{O(n)}</math> space to store the vectors and the matrices. We will show in the following section that we can improve upon the space complexity.