Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add Feynman path integral backend #20

Open
Renmusxd opened this issue Apr 19, 2020 · 2 comments
Open

Add Feynman path integral backend #20

Renmusxd opened this issue Apr 19, 2020 · 2 comments
Assignees
Labels
enhancement New feature or request

Comments

@Renmusxd
Copy link
Owner

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 Renmusxd added the enhancement New feature or request label Apr 19, 2020
@Renmusxd Renmusxd self-assigned this Apr 19, 2020
@Renmusxd
Copy link
Owner Author

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 24cd7f1 but it's not very smart.

@Renmusxd
Copy link
Owner Author

Renmusxd commented Jul 5, 2022

Out of date as of rewrite.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant