# Sorting two numbers using quantum computing

To better understand how quantum computing works, I am trying to sort two numbers using unitary matrix. Based on this definition, I understand a quantum Turing machine to have the automorphism (unitary matrix) of a Hilbert state as its state transition function.

Now supposed the input is $$\begin{bmatrix}1 & 0 \end{bmatrix}$$, the following program $$\begin{bmatrix}0 & 1\\1 & 0 \end{bmatrix}$$sorts the input:

$$\begin{bmatrix}1 & 0 \end{bmatrix}\begin{bmatrix}0 & 1\\1 & 0 \end{bmatrix}=\begin{bmatrix}0 &1 \end{bmatrix} \tag{1}$$

However, if the input is $$\begin{bmatrix}0 & 1 \end{bmatrix}$$, then it is already sorted and the program should be the identity matrix

$$\begin{bmatrix}0 & 1 \end{bmatrix}\begin{bmatrix}1 & 0\\0 & 1 \end{bmatrix}=\begin{bmatrix}0 &1 \end{bmatrix} \tag{2}$$

How do I create a program that works with either inputs? That is, how do I implement a conditional branch such that if the input is $$\begin{bmatrix}1 & 0 \end{bmatrix}$$ then the unitary matrix of case (1) is executed. Whereas if the input is $$\begin{bmatrix}0 & 1 \end{bmatrix}$$ then the identity matrix is executed.

I do not see how I can implement a conditional branch that depends on the input using unitary matrices.

In a quantum circuit, a sorting step looks like this:

Or, in code:

let cmp = a > b
if cmp:
swap a, b


The main tricky thing here is that you can't discard the result of the comparison (cmp) if you want to maintain coherence.

Your question sort of implies that you want to sort the amplitudes of the state vector, as opposed to the superposed data within each case. So like you want state $$|0000\rangle$$ to end up with the biggest amplitude from the vector and state $$|0001\rangle$$ with the next biggest and so forth. That's not possible to do. It doesn't correspond to a unitary operation. That would be like being given a written down roll from biased die, and doing some scribbling and scrabbling with the written down answer, resulting in changing the bias of the original die. It's just not possible. It doesn't make sense.

• Can you explain the diagram. What are a and b in terms of unit vectors? Mar 2, 2023 at 21:40
• @Anon21 Those are just input labels, not states. Input any state you want. It's a reversible classical circuit, so you can understand it without any quantum mechanics at all. Mar 2, 2023 at 21:59

In Quantum Information notation, what you ask is an operation that maps both $$|0\rangle$$ and $$|1\rangle$$ to the same state $$|1\rangle$$. Thus, it is not unitary, because an unitary operation is inversible.

In fact, what you look for is a reset operation, that takes a qubit and set it to the $$|0\rangle$$ state. In order to do this, measure the qubit. If you obtain $$|0\rangle$$, great. Otherwise, apply an $$X$$ gate to flip it. In your case, you would do the same process, but with $$|1\rangle$$.

All in all, what you want to do is possible to realize on a quantum computer, but not as an unitary gate, you have to perform a measurement, which is not unitary.

• So are quantum computers not Turing complete then? (the require measurement + classical computer branching to achieve it?) Mar 2, 2023 at 20:53
• @Anon21 they definitely are, but they indeed require measurement, though not for the reason you invoke. For instance, Craig Gidney gave a way to perform this problem on a Quantum computer. More generally, a quantum computer is able to simulate a classical one, hence their Tiring completeness. However, measuring is the only way one has to get a classical information from a quantum computer, hence the need for measurement. Mar 3, 2023 at 7:36