TASO termination criteria

[lmondada]

Termination would be a nice feature to have in TASO optimisation. The most practical benefit would be to detect early that we have reached a local optimum.

This termination criterion will have to be a heuristic: for cost functions such as CX gate count, the space of circuits of bounded CX gate count is infinite, as you can always insert more single-qubit gates. Even if we engineered better cost functions that exclude such cases, the space would still be too big to be explorable.

More broadly, this ties into the larger discussion of effective pruning strategies for circuit rewriting (using TASO or otherwise). Currently, the space is pruned by the following three mechanisms

• Rewrites are only considered if their cost is non-increasing (or similar). By default, we consider non-increasing CX cost, and prioritise circuits of equal cost by their total gate count
• Finite priority queue: the number of circuits that we keep track of is bounded during optimisation. Any circuits that ranks beyond the queue capacity is discarded.
• Timeout: in practice our sole termination criterion is a fixed timeout.

I'm hoping to gather alternative ideas here. Please post any thoughts and opinions you may have below.

[lmondada]

An obvious thing we could do would be to stop if no improvement is made after timeout/2 or so time. I have a sense this would not be a good criterion; we have many cases of improvements happening suddenly after large plateaus.

[lmondada]

Another observation: optimisation seems to work best in deep searches, where you prefer exploring the search tree in depth over width.

[aborgna-q]

Isn't that the default behaviour? (specially with the new tie-breaking cost function)

[lmondada]

Yes, it absolutely is. Just a property we might be able to use when thinking about this 🤷

[acl-cqc]

But what if you search deeply in the wrong direction?
If wins only come after searching deeply in the right direction...

• searching deeply in a random direction has some small chance of finding something
• searching shallowly in all directions has no chance of finding anything!

This might also be a property of the input circuit. Have these been optimised at all already? Maybe all the "easy wins" (nearby ones) have been found already?

[acl-cqc]

Ok, a few thoughts....

• This is a probabilistic process. (Which is to say - we can model our uncertainty over the future, as to whether a rewrite takes us in a good direction or not, explicitly; whether in the code or just in the design.)

  • It should be easier to estimate the distribution of unknown outcomes, than the unknown outcome itself. (Indeed - is the "goodness" of a rewrite decidable?)
  • No algorithm that doesn't have a basis in probability theory is going to truly good, nor have a claim to "correctness".
  • Monte-Carlo Tree Search is a good basis for this and is probably where we will end up, maybe even before too long

• If we are not exhaustively exploring the search place, then an algorithm that you run for as long as you want is probably better than one that always terminates according to some fix policy. Just recording "the best circuit seen so far" is enough to ensure that running for longer never degrades the outcome. Ideally, one explores options in order of decreasing probability of success (=> diminishing marginal returns from running longer), and then one can even say "stop exploring when the probability of finding anything better falls below X"

• Just because it's a probabilistic process doesn't mean it won't use heuristics! The ultimate heuristic is to train a neural network. To be honest I expect we will head down this route eventually, it is just a question of when (when do heuristics get complex enough that we can't write them easily ourselves?). But just adding more features (2-qubit gate count, total gate count, max depth, max 2-qubit depth, .....) may be beneficial - e.g. you could do a linear regression to compute optimal weights for each of those features, or feed them into a simple NN, before we ever try training a more general net (e.g. Graph Neural Network) that looks at the circuit "graph" itself.

• The connection with depth suggests there is some idea of "distance" between circuits - deep searches being more likely to find circuits that are distant from the starting point.

  • I wonder if it's possible to convert a circuit into an N-dimensional vector and then look for furthest points (in least-explored areas), or perhaps nearest ones for "pruning" purposes. (So hashing is a way of discarding circuits with distance==0, but we might also benefit from pruning circuits that have low distance from ones we've explored before.) Note this takes us away from the idea that the "goodness" of a circuit is inherent to that circuit; instead it becomes a property only of the universe of all circuits seen. This may make it harder to co-ordinate multiple searchers (threads/machines), but may be worthwhile anyway.
  • An easier version of the above is to note that typically one uses a priority queue to pick the best candidate. One can include a priority-boost for circuits discovered recently (to favour deep searches) or long ago (to favour broad shallow searches)