Asymptotically Optimal Quantum Circuits for $d$-Level Systems

Scalability of a quantum computation requires that the information be processed on multiple subsystems. However, it is unclear how the complexity of a quantum algorithm, quantified by the number of entangling gates, depends on the subsystem size. We examine the quantum circuit complexity for exactly universal computation on many -level systems (qudits). Both a lower bound and a constructive upper bound on the number of two-qudit gates result, proving a sharp asymptotic of gates. This closes the complexity question for all -level systems ( finite). The optimal asymptotic applies to systems with locality constraints, e.g., nearest neighbor interactions.

Figure 1

Sequence of one-qudit Householders to reduce $|\psi ⟩$ to a multiple of $|0⟩$ for $d=3$, $n=3$. Each box represents a Householder $\underset{}{\overset{}{\bigwedge }}(C,V)$ and is labeled by a dit string. The control position is indicated by the boldface entry in the label and the target position is indicated by the free index $j$. The $\underset{}{\overset{}{\bigwedge }}(C,V)$ is constructed to use the state vector component in the top row of the box to zero the $d-1$ components below it.