Feynman vs Schrödinger simulators

$\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 trade-off is the opposite of Schrödinger's: Feynman's takes more time and less space. More precisely, 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()

Feynman vs Schrödinger simulators

References