Feynman vs Schrödinger simulators

04 Oct 2020

$\newcommand{\ket}[1]{\left|{#1}\right\rangle}$ $\newcommand\bra[1]{\langle{#1}|}$ $\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$

The two basic simulation algorithms: Schrödinger's state-vector algorithm and Feynman's path algorithm have their pros and cons. While Schrödinger's takes less time to run compared to Feynman's, it takes more space. Feynman's tradeoff is the opposite of Schrödinger's: Feynman's takes more time and less space. More precicely, Schrödinger's takes $~ m^{2n}$ time and $∼2^{n}$ space while Feynman's takes $~4^{m}$ time and $∼m+n$ space; where $n$ in the number of qubits and $m$ is the number of gates.

An $n$ qubit quantum computer takes in a quantum circuit $U$ that contains $m$ gates and an input state $\ket{0}^n$. It then outputs a string of bits $x \in \{0, 1\} ^n$ with probability $P(x_{m}) = |\bra{x_{m}}U\ket{0}^n|^2 $. In Schrödinger's algorithm $P(x_{m}) = |\bra{x_{m}}U_{m} U_{m-1} U_{m-2} U_{m-3}, ..., U_{1}\ket{0}^n|^2$; the state is kept track of for the entire computation. Contrasted with Feynman's algorithm, $P(x_{m}) = |\bra{x_{m}}U\ket{0}^n|^2 = |\sum_{x_{1}, x_{2}, x_{3}, ... ,x_{m-1} \in \{0, 1\}^n} \prod_{j=1}^{m} \bra{x_j}U_{j}\ket{x_{j-1}}|^2$

Feynman's algorithm saves space because it calculates an amplitude instead of keeping track of the state vector. Not being able to inspect a state vector for debugging purposes is a disadvantage of Feynman's algorithm.

Here is an implementation of Feynman's simulation algorithm: feynman.py. It only works for one and two qubit gates for now. To run it, clone the repository and install the library.

    $ git clone https://github.com/vtomole/Kite.git
    $ cd Kite
    $ pip install e .
    import kite as kt

    def main():
        "To demonstrate the implementation and equivalence of results of the Schrodinger and Feynman simulators"
        prog = kt.Program(
            kt.QREG(2, probability_of_amplitude='00'),
            kt.H(0),
            kt.CNOT(0,1))
    
        amplitude_from_schrodinger = kt.schrodinger(prog)
        print("Amplitude from Schrodinger")
        print(amplitude_from_schrodinger )
    
        amplitude_from_feynman = kt.feynman(prog)
        print("Amplitude from Feynman")
        print(amplitude_from_feynman)
        
        assert amplitude_from_schrodinger == amplitude_from_feynman
    
    if __name__ == '__main__':
        main()
    

References