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 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.
In Feynman's path algorithm, is calculated by summing up the contributions of histories. That is,.
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. 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 Hamiltonian simulation Quantum simulation References