title: Asymptotically optimal quantum circuits for d-level systems.
abstract: Scalability of a quantum computation requires that the information be processed on multiple subsystems. However, it is unclear how the complexity of a quantum algorithm, quantified by the number of entangling gates, depends on the subsystem size. We examine the quantum circuit complexity for exactly universal computation on many d-level systems (qudits). Both a lower bound and a constructive upper bound on the number of two-qudit gates result, proving a sharp asymptotic of theta(d(2n)) gates. This closes the complexity question for all d-level systems (d finite). The optimal asymptotic applies to systems with locality constraints, e.g., nearest neighbor interactions.
authors.affiliation: Mathematical and Computational Sciences Division, National Institute of Standards and Technology, Gaithersburg, Maryland 20899-8910, USA.
authors.forename: Stephen S
authors.initials: SS
authors.lastname: Bullock
authors.forename: Dianne P
authors.initials: DP
authors.lastname: O'Leary
authors.forename: Gavin K
authors.initials: GK
authors.lastname: Brennen