# Computing max of 2, length n bit registries

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.

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.

A simple solution I can think of is use a comparator circuit. If $$a, 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.