Comment by d--b
Oof, it's brutally hard!
Oof, it's brutally hard!
Yeah, the problem is in a sense solved asymptotically by the optimal construction in https://arxiv.org/abs/quant-ph/0302002, but that one tends to lead to long solutions in practice, so there's plenty of room to try to come up with solutions that give shorter solutions for concrete instances.
On the other hand, if you find a way to make it easier (I believe the general case is O(n²) in gates), then you've improved a very hard computer science problem!