RustQIP icon indicating copy to clipboard operation
RustQIP copied to clipboard

Add Feynman path integral backend

Open Renmusxd opened this issue 4 years ago • 2 comments

The existing backend is "Schrodinger"-style, which means it stores the entire wavefunction, runtime is O(2^N M) and space is O(2^N) where N is the number of qubits and M the number of gates. A Feynman path integral backend would sum up all the possible paths from the input to the output through the circuit, making the runtime exponential in the circuit depth, but the memory footprint constant. This may be difficult to implement because of measurements taken midway through the circuit, but would be very helpful for certain circuit types. Furthermore there are likely mixed S-F algorithms which can optimize space/runtime tradeoffs.

Renmusxd avatar Apr 19 '20 21:04 Renmusxd

Some work done on this, a basic version with no memory has been implemented but that's very computationally expensive for most graphs. Memoization helps this significantly and a simple version was added in 24cd7f1e46fec9faf15700e1d9f645c28a8ed013 but it's not very smart.

Renmusxd avatar Nov 12 '20 06:11 Renmusxd

Out of date as of rewrite.

Renmusxd avatar Jul 05 '22 22:07 Renmusxd