Remove greedy recursion

Qiskit-Extensions / circuit-knitting-toolbox

Tools for knitting quantum circuits with Qiskit

https://qiskit-extensions.github.io/circuit-knitting-toolbox/

Apache License 2.0

70 stars 24 forks source link

Remove greedy recursion #537

Closed ibrahim-shehzad closed 2 months ago

ibrahim-shehzad commented 3 months ago

This PR aims to resolve #536, by getting rid of recursion inside the greedy_best_first_search algorithm that is used to warm start the search performed by the cut-finder. I have replaced recursion with a simple while loop and have verified that the issues reported to us for large QAOA circuits (which led to #536) are now avoided. Since these circuits have large widths, the algorithm takes a while to finish running and any direct tests on these circuits would significantly slow down the overall testing process. This is why I have not added any new tests at this stage.

coveralls commented 3 months ago

Pull Request Test Coverage Report for Build 8656075716

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

For more information on this, see Tracking coverage changes with pull request builds.
To avoid this issue with future PRs, see these Recommended CI Configurations.
For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

4 of 4 (100.0%) changed or added relevant lines in 1 file are covered.
No unchanged relevant lines lost coverage.
Overall coverage remained the same at 95.433%

Totals
Change from base Build 8560627750:	0.0%
Covered Lines:	3448
Relevant Lines:	3613

💛 - Coveralls

ibrahim-shehzad commented 3 months ago

With pieces of older git history showing up above, it looks like I may have (accidentally) created this branch locally from the deprecate-cutqc branch, instead of from main. Let me know if this is a problem and I should undo this and start over.

caleb-johnson commented 3 months ago

With pieces of older git history showing up above, it looks like I may have (accidentally) created this branch locally from the deprecate-cutqc branch, instead of from main. Let me know if this is a problem and I should undo this and start over.

@ibrahim-shehzad This can happen if you have commits from a feature branch and then those commits are squashed when that branch is merged. Git doesnt know what to do so it keeps things in the diff that are not actual changes. I think you can just checkout the main versions of these files and then commit and push those files and it'll update the diff

caleb-johnson commented 3 months ago

This looks nice, and it appears to implement the same logic. If you could just say something about what the conditions are when this loop should end, I'd like to consider if there are cases which could cause this to run forever.