Computing max of 2, length n bit registries

Question

Define a quantum algorithm that computes the maximum of two n-qubit registers.

From Quantum Computing: A Gentle Introduction (Eleanor Rieffle & Wolfgang Polak), exercise 6.4.a (page 121).

I know how to do this classically using bit logic and a signed bit, but I don’t think there are signed bits in quantum computing. I think the answer should be pretty straight forward but I have no idea what to do.

Answer 1

I will not give you the exact answer but here are some hints:

• You already know how to perform the addition (mod $2^n$) of 2 $n$-qubit quantum registers (section 6.4.3).
• Let's say you want to compare $a$ and $b$ stored in binary in registers, if the most significant bit of $a$ is 0, then the most significant bit of $a-b (\text{mod} \ 2^n)$ is $1$ if and only if $a < b$ (the subtraction is done with unsigned integer, the result should be interpreted as a unsigned integer in the previous sentence).

• Exercise 6.4.b statement may help you understand. For those who do not have the book:

  Exercise 6.4.b: Explain why such an algorithm requires one additional qubit that cannot be reused; that is, the algorithm will have to have $2n+1$ input and output qubits.

Answer 2

A simple solution I can think of is use a comparator circuit. If $a<b$, this will output 1 in another qubit register. You can then put $b$ in another register using Toffolis with this qubit as control if you want the result in another register.