Nielsen \cite{ Nielsen05} recently asked the following question: "What is the minimal size quantum circuit required to exactly implement a specified $% \mathit{ n}$-qubit unitary operation $U$, without the use of ancilla qubits?" Nielsen was able to prove that a lower bound on the minimal size circuit is provided by the length of the geodesic between the identity $I$ and $U$, where the length is defined by a suitable Finsler metric on $SU(2^{ n})$. We prove that the minimum circuit size that simulates $U$ is in linear relation with the geodesic length and simulation parameters, for the given Finsler structure $F$. As a corollary we prove the highest lower bound of $O(\frac{ % n^{ 4}}{ p}d_{ F_{ p}}^{ 2}(I,U)L_{ F_{ p}}(I,\tilde{ U})) $and the lowest upper bound of $\Omega (n^{ 4}d_{ F_{ p}}^{ 3}(I,U))$, for the standard simulation technique. Therefore, our results show that by standard simulation one can not expect a better then $n^{ 2}$ times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty \cite{ Nielsen06}. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.
Categories: quant-ph