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!

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.