Editing BQP (section)

=== BQP and PSPACE ===

Sum of histories is a technique introduced by physicist [[Richard Feynman]] for [[path integral formulation]]. APPROX-QCIRCUIT-PROB can be formulated in the sum of histories technique to show that <math>\mathsf{BQP} \subseteq \mathsf{PSPACE}</math>.<ref>E. Bernstein and U. Vazirani. Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997.</ref>

[[File:Sum of histories tree.png|thumb|Sum of Histories Tree]]

Consider a quantum circuit {{mvar|C}}, which consists of {{mvar|t}} gates, <math>g_1, g_2, \cdots, g_m</math>, where each <math>g_j</math> comes from a [[Quantum_logic_gate#Universal_quantum_gates|universal gate set]] and acts on at most two qubits.
To understand what the sum of histories is, we visualize the evolution of a quantum state given a quantum circuit as a tree. The root is the input <math>|0\rangle^{\otimes n}</math>, and each node in the tree has <math>2^n</math> children, each representing a state in <math>\mathbb C^n</math>. The weight on a tree edge from a node in {{mvar|j}}-th level representing a state <math>|x\rangle</math> to a node in <math>j+1</math>-th level  representing a state <math>|y\rangle</math> is <math>\langle y|g_{j+1}|x\rangle</math>, the amplitude of <math>|y\rangle</math> after applying <math>g_{j+1}</math> on <math>|x\rangle</math>. The transition amplitude of a root-to-leaf path is the product of all the weights on the edges along the path. To get the probability of the final state being <math>|\psi\rangle</math>, we sum up the amplitudes of all root-to-leave paths that ends at a node representing <math>|\psi\rangle</math>.

More formally, for the quantum circuit {{mvar|C}}, its sum over histories tree is a tree of depth {{mvar|m}}, with one level for each gate <math>g_i</math> in addition to the root, and with branching factor <math>2^n</math>.

{{Math theorem|1=A history is a path in the sum of histories tree. We will denote a history by a sequence <math>(u_0 =|0\rangle^{\otimes n} \rightarrow u_1 \rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_m = x)</math> for some final state {{mvar|x}}.|name=Define}}

{{Math theorem|1=Let <math>u, v \in \{0,1\}^n</math>. Let amplitude of the edge <math>(|u\rangle, |v\rangle)</math> in the {{mvar|j}}-th level of the sum over histories tree be <math>\alpha_j (u \rightarrow v) = \langle v|g_j |u\rangle</math>. For any history <math>h = (u_0 \rightarrow u_1 \rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_m)</math>, the transition amplitude of the history is the product <math>\alpha_h = \alpha_1(|0\rangle^{\otimes n} \rightarrow u_1 )\alpha_2 (u_1 \rightarrow u_2 ) \cdots \alpha_m(u_{m-1}\rightarrow x)</math>.|name=Define}}

{{Math theorem|1=For a history <math>(u_0 \rightarrow \cdots \rightarrow u_m)</math> . The transition amplitude of the history is computable in polynomial time.|name=Claim}}

{{math proof|1=Each gate <math>g_j</math> can be decomposed into <math>g_j = I \otimes  \tilde{g}_j</math> for some unitary operator <math>\tilde{g}_j</math> acting on two qubits, which without loss of generality can be taken to be the first two. Hence, <math> \langle v|g_j |u\rangle = \langle v_1 , v_2 |\tilde{g}_j |u_1 , u_2 \rangle \langle v_3, \cdots, v_n | u_3, \cdots, u_n\rangle </math> which can be computed in polynomial time in {{mvar|n}}. Since {{mvar|m}} is polynomial in {{mvar|n}}, the transition amplitude of the history can be computed in polynomial time.}}

{{Math theorem|1=Let <math>C|0\rangle^{\otimes n} = \sum_{x \in \{0,1\}^n} \alpha_x |x\rangle</math> be the final state of the quantum circuit. For some <math>x \in \{0,1\}^n</math>, the amplitude <math>\alpha_x</math> can be computed by <math>\alpha_x = \sum_{h= (|0\rangle^{\otimes n} \rightarrow u_1 \rightarrow \cdots \rightarrow u_{t-1} \rightarrow |x\rangle)} \alpha_h</math>.|name=Claim}}

{{math proof|1=We have <math>\alpha_x = \langle x|C|0\rangle ^{\otimes n} =\langle x |g_tg_{t-1}\cdots g_{1} |C|0\rangle ^{\otimes n} </math>. The result comes directly by inserting <math>I = \sum_{x \in \{0,1\}^n} | x \rangle \langle x| </math> between <math>g_1, g_2</math>, and <math>g_2, g_3</math>, and so on, and then expand out the equation. Then each term corresponds to a <math>\alpha_h</math>, where <math>h= (|0\rangle^{\otimes n} \rightarrow u_1 \rightarrow \cdots \rightarrow u_{t-1} \rightarrow |x\rangle)</math>}}

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

Notice in the sum over histories algorithm to compute some amplitude <math>\alpha_x</math>, only one history is stored at any point in the computation. Hence, the sum over histories algorithm uses <math>O(nm)</math> space to compute <math>\alpha_x</math> for any {{mvar|x}} since <math>O(nm)</math> bits are needed to store the histories in addition to some workspace variables.

Therefore, in polynomial space, we may compute <math>\sum_x |\alpha_x|^2</math> over all {{mvar|x}} with the first qubit being {{val|1}}, which is the probability that the first qubit is measured to be 1 by the end of the circuit.

Notice that compared with the simulation given for the proof that <math>\mathsf{BQP} \subseteq \mathsf{EXP}</math>, our algorithm here takes far less space but far more time instead. In fact it takes <math>O(m\cdot 2^{mn} )</math> time to calculate a single amplitude!