Feynman's algorithm

From Wikipedia, the free encyclopedia

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 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]


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[edit]


  1. ^ Ethan Bernstein and Umesh Vazirani (1997). "Quantum Complexity Theory". SIAM Journal on Computing. 26 (5): 1411–1473. doi:10.1137/S0097539796300921.
  2. ^ Raedt, K. De; Michielsen, K.; Raedt, H. De; Trieu, B.; Lippert, Th.; Watanabe, H.; Ito, N. (2006). "Massively parallel quantum computer simulator". Comput. Phys. Commun. 176 (2): 121–136. arXiv:quant-ph/0608239. doi:10.1016/j.cpc.2006.08.007. S2CID 17463164.
  3. ^ Rudiak-Gould, Ben (2006). "The sum-over-histories formulation of quantum computing". arXiv:quant-ph/0607151. Bibcode:2006quant.ph..7151R. {{cite journal}}: Cite journal requires |journal= (help)
  4. ^ Aaronson, Scott; Chen, Lijie (2016). "Complexity-Theoretic Foundations of Quantum Supremacy Experiments". Proceedings of the 32nd Computational Complexity Conference. Leibniz International Proceedings in Informatics (LIPIcs). 79: 1–67. arXiv:1612.05903. doi:10.4230/LIPIcs.CCC.2017.22. ISBN 9783959770408. S2CID 12591414.