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.

Efficient Circuits for Exact-Universal Computation With Qudits



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


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 give a formal proof that it is correct. We show that the [(n-2)/(d-2)] ancillas required in the original algorithm may be removed without changing the asymptotics. Further, we present an alternate algorithm for unitary synthesis, based on a QR decomposition of a unitary, which is also asymptotically optimal. Both unitary synthesis algorithms are well suited to solve the generalized state synthesis problem wherein one encodes a subspace of the many qudit state space to arbitrary superposition states.
Quantum Information & Computation


quantum computation, quantum information


Brennen, G. , Bullock, S. and O'Leary, D. (2006), Efficient Circuits for Exact-Universal Computation With Qudits, Quantum Information & Computation (Accessed June 17, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created June 30, 2006, Updated October 12, 2021