Command line program fails to terminate for some input

[jlapeyre]

Problem

@alexanderivrii reports that this

cargo run --release 0.785398163395 1e-10 --verbose

fails to terminate for at least a few minutes.

Expected behavior

It should terminate with a correct gate string.
Other implementations of this algorithm terminate in < 1s with a correct result

Note

0.785398163395 ≈ π/4. Up to a phase, the correct output is "T". But we have not implemented up-to-a-phase. So the correct output is a long string of gates.

Version

a335c5f

[jlapeyre]

We don't know if it will never terminate, or just takes a long time. Probably the latter:

Timing theta ≈ π / 4 to 1e-3

hyperfine "./target/debug/rsgridsynth 0.7853981633974483 1e-3"

gives 900ms. This is very slow. gridsynth does it in 12 ms

My latest suspicion is that the problem is: The value of k for which a solution is found has a very large number of candidates. It grows quickly.

For epsilon = 1e-5, the time to return an answer is 27s. And gridsynth still requires 12 ms. In the last case, there are about 50_000 candidates. We compute all candidates, instead of computing them lazily. #8 is intended to fix this.

[alexanderivrii]

Thanks @jlapeyre for looking into this: this is probably the most important thing to figure out for using rsgridsynth within Qiskit by default. Though if you think that $\pi/4$ and some of its multiples are the only problematic angles, then implementing #11 will solve the issue as well.

I really need to read the paper, but I have spent a little bit of time trying to understand what happens on the $\pi/4$ angle. Two small observations about the function solve_tdgp:

For $k\le 66$, it computes sol_x and sol_y with sol_x being a vector of a huge length (that furthermore grows with $k$) and sol_y being empty. Interchanging the computation for sol_x and sol_y immensely speeds up the computation for these values of $k$, but now it seems stuck (taking a very long time) for $k = 67$ (where sol_y has a single element). I also have a feeling that this trick does not solve the problem, and just possibly moves it to another angle.

It also seems that only the very first solution in sol_x is used in the rest of this function. If this makes sense, then indeed we should replace computing all solution for x to computing just a single solution (using the iterators). But it looks like we still need all solution for y.

[jlapeyre]

@alexanderivrii Thanks for looking at this.

My guess is: The slow down occurs for various parameters. It's most noticeble when the time to do a single decomposition is more than you want to wait for. A while ago, I did test for random angles (I think with the Python version) to see how many extra candidates (or pre-candidates) you are throwing way. I did this by making a copy of the iterators and collecting them and getting the length. I saw that for many angles there is not much difference. But for some it matters a bit and for others a lot (for some values of a bit and a lot).

If you are doing many decompositions around angles that take, say 200ms, then that could be intolerably slow.

We need to either just see what the problem is and fix it. And hopefully this means just lazy computation. Or else characterize the slowness. Eg. how does it vary as you go away from the bad angles (and what are the bad angles?) And then think about what else could be the problem.

I dont recall the details of sol_x and sol_y. I'd have to look at it. I could also compare to the Python which does not have the slow down. I mean, in what order does it compute these.

Do you think the implication is that making all list lazy will not solve the slowness problem?

I could do some debugging tests to try to test my idea. But I have been continuing with the edits for the moment.... I have done all of the modifications that do not involve generating these lists. If it looks like continuing will only create more work converting to iterators later, I'll stop and switch to that.