2007/03/09 by M. Drezgic, Milosh Drezgich, S. Shankar Sastry +3
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0703082
QIP 2007
arxiv created 2007/03/09 · openalex publication_date 2007/03/09 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Nielsen \citeNielsen05 recently asked the following question: "What is the minimal size quantum circuit required to exactly implement a specified % 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(2n). 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% n4pd_Fp2(I,U)L_Fp(I,U)) and the lowest upper bound of Ω(n4d_Fp3(I,U)), for the standard simulation technique. Therefore, our results show that by standard simulation one can not expect a better then n2 times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty \citeNielsen06. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.