Efficient quantum circuits for qudits

We describe quantum circuits for exactly universal quantum computation on multiple d-level quantum systems (qudits). In a single qudit we identify a coupling graph associated with the logical basis states as nodes and couplings as links and show that any unitary can be constructed efficiently provided the graph is connected. We prove a lower bound on the number of two qudit gates necessary to built an arbitrary (structureless) n-qudit unitary and provide a constructive algorithm that asymptotically matches this bound. The algorithm is a variant of the QR matrix decomposition and scales well in the presence of architectural constraints to qudit interactions