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 qubit quantum computer takes in a quantum circuit that contains gates and an input state . It then outputs a string of bits with probability .

In Schrödinger's algorithm, is calculated straightforwardly via matrix multiplication. That is, . The quantum state of the system can be tracked throughout its evolution.[2]

In Feynman's path algorithm, is calculated by summing up the contributions of histories. That is, . [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 time and space while Feynman's takes time and space.[4]

Example

Consider the problem of creating a Bell state. What is the probability that the resulting measurement will be ?

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 . In that case, using Schrödinger's algorithm. So probability resulting measurement will be is .

Using Feynman's algorithm, the Bell state circuit contains histories: . So = | + + + .

See also

References