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]

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

In Schrödinger's algorithm, ${\displaystyle P(x_{m})}${\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}}${\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})}${\displaystyle P(x_{m})} is calculated by summing up the contributions of ${\displaystyle (2^{n})^{m-1}}${\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}}${\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}}${\displaystyle \sim m2^{n}} time and ${\displaystyle \sim 2^{n}}${\displaystyle \sim 2^{n}} space while Feynman's takes ${\displaystyle \sim 4^{m}}${\displaystyle \sim 4^{m}} time and ${\displaystyle \sim m+n}${\displaystyle \sim m+n} space.^[4]

Consider the problem of creating a Bell state. What is the probability that the resulting measurement will be ${\displaystyle 00}${\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}${\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}}}${\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}${\displaystyle 00} is ${\displaystyle {\frac {1}{2}}}${\displaystyle {\frac {1}{2}}}.

Using Feynman's algorithm, the Bell state circuit contains ${\displaystyle (2^{2})^{2-1}=4}${\displaystyle (2^{2})^{2-1}=4} histories: ${\displaystyle 00,01,10,11}${\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 |\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 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 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 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}}}${\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}}}.

• Hamiltonian simulation
• Quantum simulation

• Quantum algorithms