# How to compare 2 classical number using a quantum circuit

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?

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

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.

• Correct me if I'm wrong but I believe your circuit checks for equality?! Feb 19, 2023 at 14:39