On the Quantum Circuit Complexity Equivalence

Abstract

Nielsen \cite{Nielsen05} recently asked the following question: "What is the minimal size quantum circuit required to exactly implement a specified -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.

QIP 2007

References in corpus (3)

• Quantum Computation as Geometry
• A geometric approach to quantum circuit lower bounds
• Cartan Decomposition of SU(2^n), Constructive Controllability of Spin systems and Universal Quantum Computing