Asymptotically optimal quantum circuits for d-level systems

Stephen S. Bullock*, Dianne P. O'Leary, Gavin K. Brennen

*Corresponding author for this work

Research output: Contribution to journalArticle

83 Citations (Scopus)

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 Θ(d2n) 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.

Original languageEnglish
Article number230502
Pages (from-to)1-4
Number of pages4
JournalPhysical Review Letters
Volume94
Issue number23
DOIs
Publication statusPublished - 17 Jun 2005
Externally publishedYes

Fingerprint Dive into the research topics of 'Asymptotically optimal quantum circuits for d-level systems'. Together they form a unique fingerprint.

  • Cite this