Feynman's algorithm

Feynman's algorithm is an algorithm that is used to simulate the operations of a quantum computer on a classical computer. It is based on the Path integral formulation of quantum mechanics, which was formulated by Richard Feynman.

Feynman's algorithm is an algorithm that is used to simulate the operations of a quantum computer on a classical computer. It is based on the Path integral formulation of quantum mechanics, which was formulated by Richard Feynman. ==Overview== An n qubit quantum computer takes in a quantum circuit U that contains m gates and an input state |0\rangle^n . It then outputs a string of bits x \in \{0, 1\} ^n with probability P(x_{m}) = |\langle x_{m}|U|0\rangle^n|^2 . In Schrödinger's algorithm, P(x_{m}) is calculated straightforwardly via matrix multiplication. That is, P(x_{m}) = |\langle x_{m}|U_{m} U_{m-1} U_{m-2} U_{m-3}, ..., U_{1}|0\rangle^n|^2 . The quantum state of the system can be tracked throughout its evolution. In Feynman's path algorithm, P(x_{m}) is calculated by summing up the contributions of (2^{n})^{m-1} histories. That is, P(x_{m}) = |\langle x_{m}|U|0\rangle^n|^2 = \left|\sum_{x_{1}, x_{2}, x_{3}, ... ,x_{m-1} \in \{0, 1\}^n} \prod_{j=1}^{m} \langle x_j|U_{j}|x_{j-1}\rangle\right|^2 . Schrödinger's takes less time to run compared to Feynman's while Feynman's takes more time and less space. More precisely, Schrödinger's takes \sim m 2^{n} time and \sim 2^{n} space while Feynman's takes \sim 4^{m} time and \sim m+n space. ==Example== Consider the problem of creating a Bell state. What is the probability that the resulting measurement will be 00 ? Since the quantum circuit that generates a Bell state is the H (Hadamard gate) gate followed by the CNOT gate, the unitary for this circuit is (H \otimes I) \times CNOT . In that case, P(00) = |\langle 00|(H \otimes I) \times \mathrm{CNOT}|00\rangle|^2 = \frac{1}{2} using Schrödinger's algorithm. So probability resulting measurement will be 00 is \frac{1}{2} . Using Feynman's algorithm, the Bell state circuit contains (2^{2})^{2-1} = 4 histories: 00, 01, 10, 11 . So \begin{align} \left|\sum_{00, 01, 10, 11} \prod_{j=1}^{2} \langle x_j|U_{j}|x_{j-1}\rangle\right|^2 &= \Big| \langle 00| H \otimes I|00\rangle \times \langle 00| \mathrm{CNOT}|00\rangle \\ &\quad + \langle 01| H \otimes I|00\rangle \times \langle 00| \mathrm{CNOT}|01\rangle \\ &\quad + \langle 10| H \otimes I|00\rangle \times \langle 00| \mathrm{CNOT}|10\rangle \\ &\quad + \langle 11| H \otimes I|00\rangle \times \langle 00| \mathrm{CNOT}|11\rangle \Big|^2 \\ &= \left|\frac{1}{\sqrt{2}} + 0 + 0 + 0\right|^2 \\ &= \frac{1}{2} \end{align} ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373019172 under CC BY-SA 4.0; modifications have been made.