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 [math]\displaystyle{ n }[/math] qubit quantum computer takes in a quantum circuit [math]\displaystyle{ U }[/math] that contains [math]\displaystyle{ m }[/math] gates and an input state [math]\displaystyle{ |0\rangle^n }[/math]. It then outputs a string of bits [math]\displaystyle{ x \in \{0, 1\} ^n }[/math] with probability [math]\displaystyle{ P(x_{m}) = |\langle x_{m}|U|0\rangle^n|^2 }[/math].
In Schrödinger's algorithm, [math]\displaystyle{ P(x_{m}) }[/math] is calculated straightforwardly via matrix multiplication. That is, [math]\displaystyle{ P(x_{m}) = |\langle x_{m}|U_{m} U_{m-1} U_{m-2} U_{m-3}, ..., U_{1}|0\rangle^n|^2 }[/math]. The quantum state of the system can be tracked throughout its evolution.[2]
In Feynman's path algorithm, [math]\displaystyle{ P(x_{m}) }[/math] is calculated by summing up the contributions of [math]\displaystyle{ (2^{n})^{m-1} }[/math] histories. That is, [math]\displaystyle{ P(x_{m}) = |\langle x_{m}|U|0\rangle^n|^2 = |\sum_{x_{1}, x_{2}, x_{3}, ... ,x_{m-1} \in \{0, 1\}^n} \prod_{j=1}^{m} \langle x_j|U_{j}|x_{j-1}\rangle|^2 }[/math]. [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 [math]\displaystyle{ \sim m 2^{n} }[/math] time and [math]\displaystyle{ \sim 2^{n} }[/math] space while Feynman's takes [math]\displaystyle{ \sim 4^{m} }[/math] time and [math]\displaystyle{ \sim m+n }[/math] space.[4]
Example
Consider the problem of creating a Bell state. What is the probability that the resulting measurement will be [math]\displaystyle{ 00 }[/math]?
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 [math]\displaystyle{ (H \otimes I) \times CNOT }[/math]. In that case, [math]\displaystyle{ P(00) = |\langle 00|(H \otimes I) \times CNOT|00\rangle|^2 = \frac{1}{2} }[/math] using Schrödinger's algorithm. So probability resulting measurement will be [math]\displaystyle{ 00 }[/math] is [math]\displaystyle{ \frac{1}{2} }[/math].
Using Feynman's algorithm, the Bell state circuit contains [math]\displaystyle{ (2^{2})^{2-1} = 4 }[/math] histories: [math]\displaystyle{ 00, 01, 10, 11 }[/math] . So [math]\displaystyle{ |\sum_{00, 01, 10, 11} \prod_{j=1}^{2} \langle x_j|U_{j}|x_{j-1}\rangle|^2 }[/math] = |[math]\displaystyle{ \langle 00| H \otimes I|00\rangle \times \langle 00| CNOT|00\rangle }[/math] + [math]\displaystyle{ \langle 01| H \otimes I|00\rangle \times \langle 00| CNOT|01\rangle }[/math] + [math]\displaystyle{ \langle 10| H \otimes I|00\rangle \times \langle 00| CNOT|10\rangle }[/math] + [math]\displaystyle{ \langle 11| H \otimes I|00\rangle \times \langle 00| CNOT|11\rangle|^2 = |\frac{1}{\sqrt{2}} + 0 + 0 + 0|^2 = \frac{1}{2} }[/math].
See also
- Hamiltonian simulation
- Quantum simulation
References
- ↑ Ethan Bernstein and Umesh Vazirani (1997). "Quantum Complexity Theory". SIAM Journal on Computing 26 (5): 1411–1473. doi:10.1137/S0097539796300921.
- ↑ 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. doi:10.1016/j.cpc.2006.08.007.
- ↑ Rudiak-Gould, Ben (2006). The sum-over-histories formulation of quantum computing. Bibcode: 2006quant.ph..7151R.
- ↑ 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. doi:10.4230/LIPIcs.CCC.2017.22. ISBN 9783959770408.
 |  |
