search

Renmusxd / RustQIP

Quantum computing using rust. Efficient and a borrow-checked no cloning theorem!
https://docs.rs/qip/
MIT License
229 stars 18 forks source link

Add Feynman path integral backend #20

Open Renmusxd opened 4 years ago

Renmusxd commented 4 years ago

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 commented 3 years ago

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 commented 2 years ago

Out of date as of rewrite.