Geometric complexity of a unitary, as introduced for example here https://arxiv.org/abs/quant-ph/0502070, measures the length of a geodesic connecting the identity matrix and a given unitary in the metric where directions corresponding to multi-qubit gates are "stretched" (this is very informal, of course). Geometric complexity in an appropriate metric lower bounds the circuit complexity. I will assume that the circuit complexity is defined as the number of CNOTs needed for an exact compilation and that metric in geometric complexity is defined correspondingly.

My question is if the lower bound coming from the geometric complexity is anywhere near tight? Naively, the two complexity measures can be far apart. For example take a 2q unitary, a controlled $rx$ gate with a small angle:

enter image description here

It's exact compilation according to $KAK$ decomposition requires two CNOTs:

enter image description here

So this gives discrete complexity 2 even for small values of the rotation gate. I do not know the geometric complexity for this circuit, but since it must be continuous and given that the gate is sufficiently close to the identity I expect the geometric complexity to be small (also here https://arxiv.org/abs/2104.03332 it is proven that entangling power lower bounds the geometric complexity with the bound being tight for small values, and my gate definitely has very low entangling power).

I expect something similar to happen in the general case as well -- that generic small perturbation to the identity matrix would lead to small geometric complexity but exponential circuit complexity of an exact compilation. Is this intuition correct? If yes, how useful is the geometric complexity to lower bound the circuit complexity?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.