QIS

QuDits and D-Valued Quantum Logic

A qudit is a generalization of a qubit in that it's a quantum state of finite dimension. Where a qubit's state can be described by a linear combination of two orthogonal states, a qudit can be described by a linear combination of \( d \)-many orthogonal states. Perhaps this is best stated in the form of an example, the extension of the well know plus state, \(\vert +\rangle = \frac{1}{\sqrt{2}}\left(\vert 0\rangle + \vert 1\rangle\right)\), to a qudit of dimension d can be stated explicity as:

$$ \vert +_d\rangle=\frac{1}{\sqrt{d}}\left(\vert 0 \rangle + \vert 1\rangle + \vert 2\rangle + ... + \vert d-1\rangle \right) $$

So why do we care about qudits when we have qubits? One good reason to consider these d-dimensional spaces is that they facilitate d-valued quantum logic, which may be more computationally efficient for some tasks. To accomplish a real implementation of this d-valued quantum logic we need to consider a certain set of common Generalized Gates. For a modern review article on the matter see here.

Relevant Qudit Gates

The most relevant gates for our considerations at the moment are the Quantum Fourier Transform (QFT), the generalized \(X\) gate, the generalized \(Z\) gate and the idea of a multi-qudit controlled gate [see Muthukrishnan and Stroud's Multivalued logic gates for quantum computation ]. These gates are generalizations of the Pauli \(X\) and Pauli \(Z\) operators of two-dimensional complex Hilbert spaces. For greater detail and other possible generalizations of the Pauli's in higher dimensions, see here. Otherwise, the general form of the gates are described individually below. Note that the generalized gates can be applied to arbitrary numbers of qudits, though the \(Z\) and \(X\) gates are generally applied to one qudit at a time as \(X_d\) and \(Z_d\).

\(X_{d^n}\) Generalized \(X\) Gate

The generalized X gate for \(n\) qudits, also known as the shift gate, can be thought of as a cyclic permutation on the basis states. The one qudit generalized \(X_{d}\) can be seen as an operator that adds one to the basis vector's index, and if it reaches \(d\) for a qu\(d\)it, it returns that digit of the index to \(0\).

$$ \begin{bmatrix} 0 & 0 & \cdots & 0& 1\\ 1 & 0 & \cdots& 0 & 0\\ 0 & 1 & \cdots& 0 & 0\\ \vdots & \vdots & \ddots & \vdots&\vdots\\ 0 & 0 & \cdots &1&0 \\ \end{bmatrix} $$

$$ X_{d^n}^{-1}= \begin{bmatrix} 0 & 1 &0& \cdots & 0\\ 0 & 0 & 1& \cdots& 0 \\ \vdots &\vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0&\cdots& 1 \\ 1 & 0 & 0 & \cdots &0 \\ \end{bmatrix} $$
$$ X_{3}= \begin{bmatrix} 0 & 0 &1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ \end{bmatrix},\quad X_{3}^{-1}= \begin{bmatrix} 0 & 1 &0\\ 0 & 0 & 1\\ 1 & 0 & 0\\ \end{bmatrix} $$

\(Z_{d^n}\) Generalized \(Z\) Gate

The generalized Z gate for \(n\) qudits of dimension \(d\), also known as the clock gate, assosciates to each basis vector \(\vert k\rangle\) a phase \(e^{2\pi i k/d^n}=\omega^{k}_{d^n}\). In the complex plane, it effectively rotates each basis vector \(\vert k\rangle\)'s amplitude by \(\frac{2\pi k}{d^n}.\)

$$ \begin{bmatrix} 1 & 0 & 0 &\cdots & 0\\ 0 & \omega_{d^n} & 0&\cdots& 0\\ 0 & 0 &\omega_{d^n}^2 & \cdots& 0\\ \vdots & \vdots &\vdots& \ddots & \vdots\\ 0 & 0 & 0 & \cdots &\omega_{d^n}^{d^n-1} \\ \end{bmatrix} $$
$$ Z_{d^n}^{-1}= \begin{bmatrix} 1 & 0 & 0 &\cdots & 0\\ 0 & \omega_{d^n}^{d^n-1} & 0&\cdots& 0\\ 0 & 0 &\omega_{d^n}^{d^n-2} & \cdots& 0\\ \vdots & \vdots &\vdots& \ddots & \vdots\\ 0 & 0 & 0 & \cdots &\omega_{d^n} \\ \end{bmatrix} $$
$$ Z_{3}= \begin{bmatrix} 1 & 0 &0\\ 0 & \omega_3 & 0\\ 0 & 0 & \omega_3^2\\ \end{bmatrix},\quad Z_{3}^{-1}= \begin{bmatrix} 1 & 0 &0\\ 0 & \omega_3^2 & 0\\ 0 & 0 & \omega_3\\ \end{bmatrix} $$

\(QFT_{d^n}\) \(n\)-Qu\(d\)it Quantum Fourier Transform

The Quantum Fourier Transform is succintly described element-wise as \(QFT_{d^n}^{i,j}=\omega_{d^n}^{i\cdot j}\). This gives the matrix form:

$$\frac{1}{\sqrt{d^n}} \begin{bmatrix} 1 & 1 & 1&1 &\cdots & 1\\ 1 & \omega_{d^n}^1 & \omega_{d^n}^{2}&\omega_{d^n}^{3} &\cdots& \omega_{d^n}^{d^n-1}\\ 1 & \omega_{d^n}^2 &\omega_{d^n}^{4} & \omega_{d^n}^{6} &\cdots& \omega_{d^n}^{2\cdot(d^n-1)}\\ 1 & \omega_{d^n}^3 &\omega_{d^n}^{6} &\omega_{d^n}^{9} & \cdots& \omega_{d^n}^{3\cdot(d^n-1)}\\ \vdots & \vdots &\vdots& \vdots&\ddots & \vdots\\ 1 & \omega_{d^n}^{d^n-1} & \omega_{d^n}^{(d^n-1)\cdot 2} & \omega_{d^n}^{(d^n-1)\cdot 3} &\cdots &\omega_{d^n}^{(d^n-1)(d^n-1)} \\ \end{bmatrix} $$
The inverse Quantum Fourier transform for \(n\)-qu\(d\)its can be described element-wise as \(QFT_{d^n}^{-1 \ (i,j)}=\omega_{d^n}^{-i\cdot j}\), giving the matrix form:
$$ QFT_{d^n}^{-1}= \begin{bmatrix} 1 & 1 & 1&1 &\cdots & 1\\ 1 & \omega_{d^n}^{(d^n-1)} & \omega_{d^n}^{(d^n-2)}&\omega_{d^n}^{(d^n-3)} &\cdots& \omega_{d^n}^{1}\\ 1 & \omega_{d^n}^{(d^n-2)} &\omega_{d^n}^{(d^n-4)} & \omega_{d^n}^{(d^n-6)} &\cdots& \omega_{d^n}^{2}\\ 1 & \omega_{d^n}^{(d^n-3)} &\omega_{d^n}^{(d^n-6)} &\omega_{d^n}^{(d^n-9)} & \cdots& \omega_{d^n}^{3}\\ \vdots & \vdots &\vdots& \vdots&\ddots & \vdots\\ 1 & \omega_{d^n}^{1} & \omega_{d^n}^{[d^n-2(d^n-1)]} & \omega_{d^n}^{[d^n-3(d^n-1)]} &\cdots &\omega_{d^n}^{(d^n-1)} \\ \end{bmatrix} $$
$$ QFT_{3}=\frac{1}{\sqrt{3}} \begin{bmatrix} 1 & 1 & 1\\ 1 & \omega_3 & \omega_3^2\\ 1 & \omega_3^2 & \omega_3\\ \end{bmatrix},\quad QFT_{3}^{-1}=\frac{1}{\sqrt{3}} \begin{bmatrix} 1 & 1 &1\\ 1 & \omega_3^2 & \omega_3\\ 1 & \omega_3 & \omega_3^2 \\ \end{bmatrix} $$

The \(QFT_d\) when applied to one qudit of dimension \(d\) is also known as a radix-\(d\) Chrestenson gate.

\(C^{n}G_{d^l}\) Qu\(d\)it Control \(G\)ates

The non-local controlled gates are also very important. They're definitively multi-qudit gates in that thay aren't separable into a tensor product of single-qudit gates. They're defined as gates that only apply a gate to the \(l\) target qudits when the \(n\) control qudit's hold a certain value. For a one qudit gate \(G_d\) (i.e. \(l=1\) ) and \(n\) control qudits where the gate is only applied when the control qudits hold the value \(k=1\), the controlled \(G_d\) gate takes the form of the following block diagonal matrix:

$$ \begin{bmatrix} \mathbb{I_d} & 0 & 0 &\cdots & 0\\ 0& G_d & 0 &\cdots & 0\\ 0& 0 & \mathbb{I_d} &\cdots & 0\\ \vdots&\vdots&\vdots& \ddots & \vdots\\ 0& 0 & 0 &\cdots & \mathbb{I_d}\\ \end{bmatrix} $$
where each element is really a \(d\times d \) matrix. Alternatively, we can define the control gate to apply different gates for different states of the control qudits, as opposed to just one specific state of the control qudits. This results in a \(d^{n+l}\) block diagonal matrix of \(n\) different \(d^l \times d^l \) matrices. Shown below,
$$ \begin{bmatrix} G_0 & 0 & 0 &\cdots & 0\\ 0& G_1 & 0 &\cdots & 0\\ 0& 0 & G_2 &\cdots & 0\\ \vdots&\vdots&\vdots& \ddots & \vdots\\ 0& 0 & 0 &\cdots & G_{n-1}\\ \end{bmatrix} $$
One example of this is the gate that applies the same gate raised to the \( k \)th power for the \( k \)th state of the target qudit (where \( k \) ranges from to \(0\) to\( (d^n-1) \)), shown explicitly below as $$ \begin{bmatrix} \mathbb{I} & 0 & 0 &\cdots & 0\\ 0& G^{} & 0 &\cdots & 0\\ 0& 0 & G^{2} &\cdots & 0\\ \vdots&\vdots&\vdots& \ddots & \vdots\\ 0& 0 & 0 &\cdots & G^{(d^n-1)} \end{bmatrix} $$ Which is known as a quantum multiplexer.

Basic \(d\)-ary Quantum Algorithms

Some basic quantum algorithms of the qubit paradigm have already been extended to \(d\)-ary qudit circuits. The quantum phase estimation algorithm has been extended to qudit circuits in several papers already, and has a pretty straight forward extension from the qubit case. The quantum search algorithm has several possible extensions beyond the binary qubit realm, one is to simply evaluate sparse binary functions over new dimensional spaces. The other extension is to the evaluation of specific outcomes of \(d\)-ary functions. Some progress in this direction has been made very recently.

Qudit Phase Estimation

Phase estimation has a clean extension into the realm of qudits, as done by Vamsi Parasa and Marek Perkowski in Quantum Phase Estimation Using Multivalued Logic (explained in the associated presentation). See also Ye Cao, et al.'s Quantum Fourier Transform and Phase Estimation in Qudit System and Hristo Tonchev and Nikolay V. Vitanov's Quantum phase estimation and quantum counting with qudits. A general circuit for the multi-valued phase estimation algorithm, utilizing qudits and quantum multiplexers, is shown below.

N-Qudit Multi-valued Phase Estimation circuit diagram

Notice the controlled \(\mathbf{U}\) gates here are multiplexers, signified by the circled \(\mathcal{M}\) on the control qudit.

Multiple-Valued Grover Search Algorithm

Grover's search algorithm can only be used to evaluate sparse binary functions, that is, multivariate functions where variables can take one of two values. A natural question to ask then, is whether we may encode multivariate finite functions of arbitrary input dimension. And, indeed we can in qudit spaces, but whether we can efficiently evaluate these encodings is yet undecided.

Finite-Function-Encoding States

Using qu\(d\)its and the \(d\)th roots of unity, we can actually encode multivariate functions over finite fields. The states we'll utilize are full superpositions of the basis vectors of multi-qudit states. In other words, if we extend the plus state of qubits \( \vert +\rangle\) to qudits \( \vert +_d\rangle\) and then vary the amplitudes by the \(d\)th roots of unity we can encode finite functions in the values of the amplitudes exponents.

$$ \vert f(x_n)\rangle := \frac{1}{\sqrt{d^n}}\sum_{k=0}^{d^n-1}\omega_d^{f(x_n)}\vert k \rangle $$

Let's consider a simple two qutrit example that encodes the polynomial \(f(x,y)=xy^2+x\) over the finite field \(\mathbb{F}_3\) (that is, the field of integers modulo three). In this context, it's implied the relative roots of unitary are those of order 3 as we are considering qutrits. Thus, below, our \(\omega\) is \(\omega_3=e^{\frac{2\pi i}{3}}\).
$$ \frac{1}{\sqrt{9}}\sum_{k=0}^{8}\omega^{xy^2+x}\vert k \rangle =\frac{1}{3}\left(\vert 00\rangle + \vert 01\rangle + \vert 02\rangle + \omega \vert 10\rangle + \omega^2 \vert 11\rangle + \omega^2 \vert 12\rangle + \omega^2 \vert 20\rangle + \omega \vert 21\rangle + \omega \vert 22\rangle \right) =\begin{array}{c c} \hspace{.4cm} x\ y & \begin{array}{c} \omega^{f(x,y)} \\ \end{array} \\ \begin{array}{c c c c c c c c c}\vert 00\rangle \\ \vert 01 \rangle\\ \vert 02 \rangle \\ \vert 10\rangle \\ \vert 11\rangle\\ \vert 12\rangle\\ \vert 20 \rangle \\ \vert 21 \rangle \\ \vert 22\rangle\end{array} \hspace{-.5cm}& \left[ \begin{array}{c} 1 \\ 1 \\ 1 \\ \omega \\ \omega^2 \\ \omega^2\\ \omega^2\\ \omega \\ \omega \\ \end{array} \right] \end{array} $$

This encoding can be physically realized by prescribed application of controlled generalized \(Z\) gates. For prime \(d\) we have that all finite-functions can be described by multivariate polynomials. For more detail, see Finite-Function-Encoding Quantum States.

Generalized Grover Diffusion Operator

The generalized Grover diffusion operator, \(\Delta_d(n)\), as defined by Samuel Hunt and Maximilien Gadouleau in Grover’s Algorithm and Many-Valued Quantum Logic is described in circuit form below.

N-Qudit Generalized Grover Diffusion Operator
Let's look at a three qutrit example and see what the operator \(\Delta_3(3)\) explicitly looks like. The circuit is the one below:
3-Qudit Generalized Grover Diffusion Operator
Note that we now omit the subscripts for the gates as the context assures us they're all 3 dimensional (given we're dealing with qutrits).

A multi-valued grover search algorithm is also covered in section 3 of Yale Fan's Applications of Multi-Valued Quantum Algorithms. And, a three dimensional case of Grover's search algorithm seems to have been developed in Sudhindu Bikash Mandal, et al.'s Synthesis of Ternary Grover's Algorithm. The ternary case also seems to have had applications for graph coloring problems developed as is done in Yushi Wang and Marek Perkowski's Improved Complexity of Quantum Oracles for Ternary Grover Algorithm for Graph Coloring (with a presentation by the authors here).

Generalized Grover Search

The principle part of the search algorithm is just the repeated application of a function encoding gate and a generalized Grover diffusion operator, together termed a Grover iteration. After a prescribed number of applications of this Grover iteration (this number depends on the relative proportion of the different values), we measure in the computational basis and expect a high amplitude in the sparsest value. After a few more iterations we expect a high amplitude in the two sparsest values and so on, until we return to high amplitude exclusively in the sparsest value again.

Qudit search algorithms can still evaluate binary functions (that is, search through items of two types) as is done in papers like Saha, et. al.'s Asymptotically Improved Grover's Algorithm in Any Dimensional Quantum System with Novel Decomposed n-qudit Toffoli Gate. But Grover's search can naturally be extended to lists of items of \(d\) types, as is done in Wang, et. al.'s Qudits and High-Dimensional Quantum Computing.

Simulating Qudits

Google's quantum SDK, Cirq, natively supports qudits and qudit circuit simulations. A git repository of these qudit gates and relevant items is graciously under development by Andy Phillips and can be found here.