# How does the NOT gate generalize beyond binary?

If we are working with qudits instead of qubits, how do the NOT and CNOT gates work? If the control state for a qubit system is $$|1\rangle$$, what is it for a $$d$$-ary qudit system, and why?

For instance, in a qutrit system with three basis states $$|0\rangle,|1\rangle,|2\rangle$$: if one had a CNOT gate, which state would trigger the NOT gate?

There is no universally accepted CNOT (or even NOT) gate for qutrits or qudits with d>2, and the NOT operator conventionally turns 0 to 1 and 1 to 0 when the input is 1 binary bit or qubit.

Three-value logic is indeed a fairly well-studied topic, but there's many different conventions such as:

In Kleene logic, we have the following NOT gate (in qubit notation, even though Kleene logic was developed for classical computing):

• $$|T\rangle \rightarrow |F\rangle$$
• $$|U\rangle \rightarrow |U\rangle$$
• $$|F\rangle \rightarrow |T\rangle$$

So if the control qubit for a CNOT gate in Kleene logic is $$|T\rangle$$ then the target qubit will undergo the above transformation gate. Here, T = true, F = false, U = unknown, and you can replace these letters by 0,1,2 or -1,0,1 instead if you wish.

For qudits with d>3, as long as d is still finite there's even more options under the umbrella called "multi-valued logic":

• Belnap logic (for d=4)
• Gödel logics
• Product logic
• Rose logics
• Post logics (again)

For infinite-valued logic (d = infinity), for example if the qudits were representing a "continuous variable" like the position $$x$$ (where d is uncountably infinite), or if the qudits were representing a quantum harmonic oscillator where each energy level encodes some information (here d is countably infinite because while d is infinite it's still discrete), there's fuzzy logic and probabilistic logic.

• Thanks for that, that's really interesting! It's odd because I see qudit controls fairly often when reading about, like in this paper, but it's very unclear what exactly they're using as a control. – Sam Mar 8 at 21:57
• Do you mean the paper "Various Constructions of Qudit SWAP Gate"? What brought you to that paper? – user1271772 Mar 8 at 23:39
• I'm coming to the end of a project for university in which we explored a new topic (to us) and produced a report. I chose a topic which ended up involving conditional statements, and I needed a way to implement this on a quantum circuit. I realised as I went on this would be tricky, but I didn't realise how so. In the general formulation of the problem, qubits are in a superposition in separate registers, making them essentially qudits, and it was these that I needed to perform logic on. I stumbled across this paper looking for GXOR, but it wasn't much help. – Sam Mar 9 at 0:09
• @Sam I see. I would recommend to ignore this paper altogether okay? It's not published in a good journal and the author does not have a lot of experience publishing in quantum computing. If you have two qubits in separate registers, then you have two qubits, not a qudit. If you can complete your project using only qubits, that would be the best choice. As you can tell, there's not a lot of information available about qudits, because no quantum computers actually use them in practice. – user1271772 Mar 9 at 0:24
• Okay, thanks for that! – Sam Mar 9 at 9:39

As the previous answer mentions, how a controlled qudit gate is defined is up to a choice of convention. This paper contains a few examples of intuitively appealing definitions for controlled qudit operations. The first example for $$d$$-dimensional qudits is a block diagonal matrix where $$U$$ is applied to qudit 2 only if the state of qudit 1 is $$|d-1\rangle$$:

$$\tag{1} \text{Controlled-}U = \begin{pmatrix} \mathbb{I}_{d^2 - d} & 0 \\ 0 & U_d \end{pmatrix}$$

If we consider qutrits ($$d=3$$) this looks like: $$\begin{pmatrix} \begin{matrix} \tag{2} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{matrix} & \begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix} \\ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{matrix} & \begin{pmatrix} ~ & ~ & ~ \\ ~ & U & ~ \\ ~ & ~ & ~ \end{pmatrix} \end{pmatrix} \begin{matrix} \quad |00\rangle \\ \quad |01\rangle \\ \quad |02\rangle \\ \quad |10\rangle \\ \quad |11\rangle \\ \quad |12\rangle \\ \quad |20\rangle \\ \quad |21\rangle \\ \quad |22\rangle \\ \end{matrix}$$

From the basis state annotations you can see that $$U$$ gets implemented on the second qutrit only if the first qutrit is in the state $$|2\rangle$$. If we return to arbitrary $$d$$ and think of $$U$$ as being generated by some $$d \times d$$ hermitian $$\theta H$$ then this matrix is equivalent to the operator $$\tag{3} \exp\left( i\theta |d-1 \rangle\langle d-1 | \otimes H \right)$$

which reduces to the expression for $$\text{CNOT}$$ on qubits (up to a local $$S^\dagger$$) for $$d=2$$, $$\theta H = \frac{\pi}{2} X$$. You could also use another block diagonal definition like

$$\tag{4} \text{Controlled-}\{U\} = \begin{pmatrix} U_0 & 0 & \cdots & 0\\ 0 & U_1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & U_{d-1} \end{pmatrix}$$

which will apply $$U_k$$ conditioned on the control qudit being in state $$|k \rangle$$ by the same reasoning above.

• +1. I've just added equation labels because even if you're not referring to equations in your answer, someone else might want to refer to them when citing your answer, and it's better if they can say "in Eq. 3" rather than "In the third equation". Also I'll mention that this answer gives yet another convention, not mentioned in my answer, and it seems that it's not compatible with the three-valued Kleene logic which is perhaps the most popular for 3-valued logic in classical computer science. Based on OP's comments, it seems they should not use qudits, but this is a useful answer for others! – user1271772 Mar 9 at 2:08
• +1. I think equation $(4)$ is the appropriate way to generalize controlled gates to qudits. I wrote another answer to give this a fuller justification. – Adam Zalcman Mar 12 at 18:36

Many classical programming languages are equipped with a construct known as the conditional statement

if (condition) {
u();
}


where condition is a boolean expression, i.e. an expression that evaluates to one of two values: true or false and where u() is an operation to be executed when condition evaluates to true. In quantum computing this construct corresponds to a controlled gate

$$CU = \begin{pmatrix} I & 0 \\ 0 & U \end{pmatrix}$$

which applies $$U$$ to target qubit(s) when the control qubit is in state $$|1\rangle$$.

Both, the conditional statement and the controlled gate use an input that has two values: true and false in the former case and $$|1\rangle$$ and $$|0\rangle$$ in the latter, to decide between two branches: execute u() or do nothing in the former case and apply $$U$$ or identity in the latter case.

One way to generalize a controlled gate to qudits is to mimic the way the conditional statement is generalized to expressions that evaluate to more than two values. In many programming languages this is achieved using the switch statement

switch (expression) {
case 1:
u_1();
break;
case 2:
u_2();
break;
...
case n:
u_n();
break;
}


which executes u_k() when expression evaluates to k.

Quantum counterpart of the switch statement is the quantum multiplexor (see e.g. section 3 in this paper and the answer to this question by @forky40)

$$U = \begin{pmatrix} U_1 & 0 & \dots & 0 \\ 0 & U_2 & \dots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \dots & U_n \end{pmatrix}$$

which applies unitary $$U_k$$ to the target subsystem if the control qudit is in state $$|k\rangle$$ where $$k=1,\dots, n$$.

Incidentally, this also suggests a quantum generalization of the conditional statement with the else branch:

if (condition) {
u();
} else {
v();
}


which is a two-part multiplexor

$$W = \begin{pmatrix} V & 0 \\ 0 & U \end{pmatrix}$$

that applies $$V$$ to the target when the control is in state $$|0\rangle$$ and applies $$U$$ when the control is in state $$|1\rangle$$.

I'm not sure if that's ever used for controlled gates, but a non-controlled $$X$$ can be generalized to qudits by a shift operator $$X: |i\rangle \mapsto |(i+1)\rangle$$.