Physics – Quantum Physics
Scientific paper
2007-03-09
Physics
Quantum Physics
QIP 2007
Scientific paper
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.
Drezgich Milosh
Sastry Shankar S.
No associations
LandOfFree
On the Quantum Circuit Complexity Equivalence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Quantum Circuit Complexity Equivalence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Quantum Circuit Complexity Equivalence will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-290590