TY - JOUR

T1 - Asymptotically optimal quantum circuits for d-level systems

AU - Bullock, Stephen S.

AU - O'Leary, Dianne P.

AU - Brennen, Gavin K.

PY - 2005/6/17

Y1 - 2005/6/17

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=27144464549&partnerID=8YFLogxK

U2 - 10.1103/PhysRevLett.94.230502

DO - 10.1103/PhysRevLett.94.230502

M3 - Article

C2 - 16090450

AN - SCOPUS:27144464549

VL - 94

SP - 1

EP - 4

JO - Physical Review Letters

JF - Physical Review Letters

SN - 0031-9007

IS - 23

M1 - 230502

ER -