What is the minimal size quantum circuit required to exactly implement a specified n-qubit unitary operation, U, without the use of ancilla qubits? We show that a lower bound on the minimal size is provided by the length of the minimal geodesic between U and the identity, I, where length is defined by a suitable Finsler metric on the manifold SU(2^n). The geodesic curves on these manifolds have the striking property that once an initial position and velocity are set, the remainder of the geodesic is completely determined by a second order differential equation known as the geodesic equation. This is in contrast with the usual case in circuit design, either classical or quantum, where being given part of an optimal circuit does not obviously assist in the design of the rest of the circuit. Geodesic analysis thus offers a potentially powerful approach to the problem of proving quantum circuit lower bounds. In this paper we construct several Finsler metrics whose minimal length geodesics provide lower bounds on quantum circuit size. For each Finsler metric we give a procedure to compute the corresponding geodesic equation. We also construct a large class of solutions to the geodesic equation, which we call \emph{Pauli geodesics}, since they arise from isometries generated by the Pauli group. For any unitary U diagonal in the computational basis, we show that: (a) provided the minimal length geodesic is unique, it must be a Pauli geodesic; (b) finding the length of the minimal Pauli geodesic passing from I to U is equivalent to solving an exponential size instance of the closest vector in a lattice problem (CVP); and (c) all but a doubly exponentially small fraction of such unitaries have minimal Pauli geodesics of exponential length.
Unitary synthesis underlies universal quantum computation by translating unitary transformations into circuits of elementary gates. We show that for any budget
m≥0 of ancilla, every
n-qubit unitary can be exactly implemented using a quantum circuit consisting of
O(4n) CNOT and single-qubit gates in
O(n+4n/(n+m)) layers attaining the asymptotically optimal depth--ancilla tradeoff while simultaneously achieving optimal circuit size. The key idea is to encode computational basis states as wavefunctions sharing a Gaussian envelope, converting unitary action on amplitudes into coordinate transformations that admit shallow circuit implementations. The continuous encoding is then discretized, with approximation errors removed by exact residual correction. The depth-ancilla tradeoff follows by recursively applying the quantum Shannon decomposition, synthesizing its smaller unitary factors, and reusing ancillary qubits.
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(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{% n^{4}}{p}d_{F_{p}}^{2}(I,U)L_{F_{p}}(I,\tilde{U})) $and the lowest upper bound of
Ω(n4dFp3(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 \cite{Nielsen06}. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.
This paper concerns the efficient implementation of quantum circuits for qudits. We show that controlled two-qudit gates can be implemented without ancillas and prove that the gate library containing arbitrary local unitaries and one two-qudit gate, $\CINC$, is exact-universal. A recent paper [S.Bullock, D.O'Leary, and G.K. Brennen, Phys. Rev. Lett. 94, 230502 (2005)] describes quantum circuits for qudits which require O(d^n) two-qudit gates for state synthesis and O(d^{2n}) two-qudit gates for unitary synthesis, matching the respective lower bound complexities. In this work, we present the state-synthesis circuit in much greater detail and prove that it is correct. Also, the (n-2)/(d-2) ancillas required in the original algorithm may be removed without changing the asymptotics. Further, we present a new algorithm for unitary synthesis, inspired by the QR matrix decomposition, which is also asymptotically optimal.
Abstract The modeling of computation using logic circuits occupies an important position in the fundamentals of complexity theory including quantum complexity theory. Consequently, research into methods for computing logic functions on quantum circuits as well as for minimizing and simplifying such circuits has become extremely important. In this paper we explicitly formulate the depth minimization problem for quantum logic circuits and show that this problem is closely related to a geometric approach to deriving a lower bound on the size of a quantum logic circuit. © 2007 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 90(10): 9–17, 2007; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/ecjc.20298