Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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<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.
