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.^[1]

Overview

An ${\displaystyle n}$ qubit quantum computer takes in a quantum circuit ${\displaystyle U}$ that contains ${\displaystyle m}$ gates and an input state ${\displaystyle |0\rangle ^{n}}$. It then outputs a string of bits ${\displaystyle x\in \{0,1\}^{n}}$ with probability ${\displaystyle P(x_{m})=|\langle x_{m}|U|0\rangle ^{n}|^{2}}$.

In Schrödinger's algorithm, ${\displaystyle P(x_{m})}$ is calculated straightforwardly via matrix multiplication. That is, ${\displaystyle 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.^[2]

In Feynman's path algorithm, ${\displaystyle P(x_{m})}$ is calculated by summing up the contributions of ${\displaystyle (2^{n})^{m-1}}$ histories. That is, ${\displaystyle 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}}$. ^[3]

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 ${\displaystyle \sim m2^{n}}$ time and ${\displaystyle \sim 2^{n}}$ space while Feynman's takes ${\displaystyle \sim 4^{m}}$ time and ${\displaystyle \sim m+n}$ space.^[4]

Example

Consider the problem of creating a Bell state. What is the probability that the resulting measurement will be ${\displaystyle 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 ${\displaystyle (H\otimes I)\times CNOT}$. In that case, ${\displaystyle 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 ${\displaystyle 00}$ is ${\displaystyle {\frac {1}{2}}}$.

Using Feynman's algorithm, the Bell state circuit contains ${\displaystyle (2^{2})^{2-1}=4}$ histories: ${\displaystyle 00,01,10,11}$ . So ${\displaystyle |\sum _{00,01,10,11}\prod _{j=1}^{2}\langle x_{j}|U_{j}|x_{j-1}\rangle |^{2}}$ = |${\displaystyle \langle 00|H\otimes I|00\rangle \times \langle 00|CNOT|00\rangle }$ + ${\displaystyle \langle 01|H\otimes I|00\rangle \times \langle 00|CNOT|01\rangle }$ + ${\displaystyle \langle 10|H\otimes I|00\rangle \times \langle 00|CNOT|10\rangle }$ + ${\displaystyle \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

References