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.

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}=|\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 |^{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 m2^{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 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 $|\sum _{00,01,10,11}\prod _{j=1}^{2}\langle x_{j}|U_{j}|x_{j-1}\rangle |^{2}$ = |$\langle 00|H\otimes I|00\rangle \times \langle 00|CNOT|00\rangle$ + $\langle 01|H\otimes I|00\rangle \times \langle 00|CNOT|01\rangle$ + $\langle 10|H\otimes I|00\rangle \times \langle 00|CNOT|10\rangle$ + $\langle 11|H\otimes I|00\rangle \times \langle 00|CNOT|11\rangle |^{2}=|{\frac {1}{\sqrt {2}}}+0+0+0|^{2}={\frac {1}{2}}$.

See also

• Hamiltonian simulation
• Quantum simulation