2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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