Max recursion limit exceeded when running cut-finder on deep circuits

[ibrahim-shehzad]

For circuits with ~5000 non-local gates, such as those that appear in use cases of the QAOA, the default max recursion limit in python (3000) is exceeded. This is understandable because 5000 non-local gates involve around ~5000 recursive calls to the greedy BFS algorithm.

Replace recursive calls to greedy_best_first_search() with a different data structure, possibly a heapq.

[garrison]

One option would be to rewrite greedy_best_first_search to use a list as a stack. One existing example of this style is the following three lists that are (mostly) used as stacks introduced before a loop that could instead conceptually be a recursive function:

https://github.com/Qiskit-Extensions/circuit-knitting-toolbox/blob/6db5cbd527adcd9c0973f8269c8b33925d5efa58/circuit_knitting/cutting/qpd/weights.py#L109-L112

However, there is a bit more flexibility because the recursion in this function is actually a tail call. Python itself does not optimize tail-recursion, but it would be possible to use something like https://github.com/baruchel/tco. (I first found this from the answer at https://stackoverflow.com/a/18506625/1558890.) I can't rule out that it might ding performance a bit, though, which I believe would be quite unfortunate here.

[garrison]

I got excited about using tco for a moment, but I actually think rewriting this as a loop is going to be pretty straightforward, and allows us to refrain from adding a package to our dependency chain.