How to compare 2 classical number using a quantum circuit

Question

I'm given 2 numbers(could be positive/negative). I want to program a quantum circuit to compare them and return the greater one.

• How can I do that?
• Also, if the first step is encoding the numbers into qubits, would it be amplitude encoding or creating encoding qubits with the binary representation of the numbers using X gates?

Answer 1

The way this is done for example in Shor's algorithm is this. You encode the integers as binaries / qubits, let's call them $i_0$ and $i_1$. Then you subtract them and create the difference in place of, say, $i_0$. If the carry bit is not set, this means $i_0$ was the larger number and you perform a controlled addition of $i_1$ to $i_0$. If the carry qubit is set, $i_1$ was larger . In this case you could perform a controlled swap of $i_1$ into $i_0$. The difficulty is to avoid entanglement, you need to add proper uncomputation.

See, for example, this paper by Stephane Beauregard. I put a Python version here. Addition is done with the technique from Draper

Answer 2

Encoding:

This part is pretty intuitive. Let $x_0$ be the integer to encode, then for any $1$ digit in the binary representation of $x_0$ you should apply an $X$ gate to its corresponding qubit. E.g, let $x_0 = 11$ (decimal value), then its binary representation is $1011$, and it can be encoded into 4 qubits as follows (using little-endian convention):

Comparison:

That part is a little more complicated. What I would recommend is comparing qubit-by-qubit using a negated $XOR$ operation into auxiliary qubits, followed by an $MCX$ with all the auxiliary qubits as control qubits. The $XOR$ operation writes $|1\rangle$ to the auxiliary qubit when the 2 compared qubits are unequal, then by negating the auxiliary qubit we ensure that $|1\rangle$ is written to the auxiliary qubit when the 2 compared qubits are equal in value. The $XOR$ operation is implemented using a $CNOT$ gate from each compared qubit to the auxliairy qubit. E.g when comparing 2 integers of 2-bits length each, it looks like this:

$|1\rangle$ would be written into the result qubit if and only if $number\_1$ and $number\_2$ are equal.

---

In addition, I have published an open-source software lately that synthesizes cricuits for satisfiability problems - it is capable of easily handling comparison and arithmetic operations like these discussed here - it might help you. It is available as sat-circuits-engine on GitHub, and in the demos page you might find already executed demonstrations.

Let me know if you need anything more.