Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Asymptotically Optimal Quantum Circuits for d-level Systems



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


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.
Physical Review Letters
No. 19


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


Bullock, S. , O'Leary, D. and Brennen, G. (2005), Asymptotically Optimal Quantum Circuits for d-level Systems, Physical Review Letters, [online], (Accessed March 5, 2024)
Created June 17, 2005, Updated February 17, 2017