Efficient circuits for exact-universal computation with qudits

G. K. Brennen*, S. S. Bullock, D. P. O'Leary

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

32 Citations (Scopus)


This paper concerns the efficient implementation of quantum circuits for qudits. We show that controlled two-qudit gates can be implemented without ancillas and prove that the gate library containing arbitrary local unitaries and one two-qudit gate, CINC, is exact-universal. A recent paper [S.Bullock, D.O'Leary, and G.K. Brennen, Phys. Rev. Lett. 94, 230502 (2005)] describes quantum circuits for qudits which require O(d n) two-qudit gates for state synthesis and O(d 2n) two-qudit gates for unitary synthesis, matching the respective lower bound complexities. In this work, we present the state-synthesis circuit in much greater detail and prove that it is correct. Also, the [(n-2)/(d-2)] ancillas required in the original algorithm may be removed without changing the asymptotics. Further, we present a new algorithm for unitary synthesis, inspired by the QR matrix decomposition, which is also asymptotically optimal.

Original languageEnglish
Pages (from-to)436-454
Number of pages19
JournalQuantum Information and Computation
Issue number4-5
Publication statusPublished - Jul 2006
Externally publishedYes


Dive into the research topics of 'Efficient circuits for exact-universal computation with qudits'. Together they form a unique fingerprint.

Cite this