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{⟩}^n$. It then outputs a string of bits $x\in \{0,1{\}}^n$ with probability $P(x_m)=|⟨x_m|U|0{⟩}^n{|}^2$.

In Schrödinger's algorithm, $P(x_m)$ is calculated straightforwardly via matrix multiplication. That is, $P(x_m)=|⟨x_m|U_m{U}_{m-1}{U}_{m-2}{U}_{m-3},...,U_1|0{⟩}^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)=|⟨x_m|U|0{⟩}^n{|}^2=|\sum _{x_1,x_2,x_3,...,x_{m-1}\in \{0,1{\}}^n}\prod _{j=1}^m⟨x_j|U_j|x_{j-1}⟩{|}^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)=|⟨00|(H\otimes I)\times CNOT|00⟩{|}^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⟨x_j|U_j|x_{j-1}⟩{|}^2$ = |$⟨00|H\otimes I|00⟩\times ⟨00|CNOT|00⟩$ + $⟨01|H\otimes I|00⟩\times ⟨00|CNOT|01⟩$ + $⟨10|H\otimes I|00⟩\times ⟨00|CNOT|10⟩$ + $⟨11|H\otimes I|00⟩\times ⟨00|CNOT|11⟩{|}^2=|\frac{1}{\sqrt{2}}+0+0+0{|}^2=\frac{1}{2}$.

See also

• Hamiltonian simulation
• Quantum simulation