0
$\begingroup$

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?
$\endgroup$
0

2 Answers 2

0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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):

enter image description here

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:

enter image description here

$|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.

$\endgroup$
1
  • $\begingroup$ Correct me if I'm wrong but I believe your circuit checks for equality?! $\endgroup$
    – rhundt
    Feb 19, 2023 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.