A geometric approach to quantum circuit lower bounds

Nielsen, M. A. (2006) A geometric approach to quantum circuit lower bounds. Quantum Information & Computation, 6 3: 213-262.

Author Nielsen, M. A.
Title A geometric approach to quantum circuit lower bounds
Journal name Quantum Information & Computation
ISSN 1533-7146
Publication date 2006
Sub-type Article (original research)
Volume 6
Issue 3
Start page 213
End page 262
Total pages 50
Editor Dr Wei Chen
Place of publication United States
Publisher Rinton Press, Inc
Collection year 2006
Language eng
Subject C1
289999 Other Information, Computing and Communication Sciences
780102 Physical sciences
Abstract 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 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.
Keyword Computer Science, Theory & Methods
Physics, Mathematical
Physics, Particles & Fields
Quantum Circuits
Lower Bounds
Finsler Geometry
Q-Index Code C1

Document type: Journal Article
Sub-type: Article (original research)
Collections: 2007 Higher Education Research Data Collection
School of Physical Sciences Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 31 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Wed, 15 Aug 2007, 08:17:42 EST