Asymptotically Optimal Quantum Circuits for d-level Systems

Published

June 17, 2005

Author(s)

Stephen Bullock, Dianne M. O'Leary, G K. Brennen

Abstract

As a qubit is a two-level system whose state space is spanned by and , so a qudit is a -level system whose state space is spanned by , , . Quantum computation has stimulated much recent interest in algorithmsfactoring unitary evolutions of an -qubit state space into component two-particle unitary evolutions. In theabsence of symmetry, Shende, Markov, and Bullock use Sard s theorem to prove that at least two-qubit unitaryevolutions are required, while Vartiainen, Moettoenen, and Salomaa (VMS) use the matrix factorization andGray codes in an optimal order construction involving two-particle evolutions. In this work, we note that Sard s theorem demands two-qudit unitary evolutions to construct a generic (symmetry-less) -qudit evolution.However, the VMS result applied to virtual qubits only recovers optimal order in the case that is a power oftwo. We further construct a decomposition for multi-level quantum logics, proving a sharp asymptoticof two-qudit gates and thus closing the complexity question for all -level systems ( finite.) Gray codesare not required.

Citation

Physical Review Letters

Volume

94

Issue

No. 19

Pub Type

Journals

Download Paper

Local Download

Keywords

quantum computation, quantum gate, quantum multi-level logic, qudit

Citation

Bullock, S. , O'Leary, D. and Brennen, G. (2005), Asymptotically Optimal Quantum Circuits for d-level Systems, Physical Review Letters, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=150903 (Accessed May 2, 2026)

Additional citation formats