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

edit

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

edit

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

References

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.