I currently need to implement efficiently a quantum comparator, with one of the values that is known at generation-time.
In other words, I am searching for a quantum routine
compare(n, rhs) that will produce a circuit taking as input
- a quantum register $\vert a \rangle$ of size
nthat should be interpreted as a unsigned integer.
- a single qubit initialised to $\vert 0 \rangle$ that will store the result of $a < rhs$ at the end of the routine.
- at most one ancilla qubit, and preferably no ancilla qubit at all.
There are a lot of quantum comparators in the wild (for example ,  or ) but all of them are designed to compare values stored in two quantum registers, not one value from a quantum register and the other known at compile time.
Even if I have no rigorous proof, I think a similar argument applies to . My "intuition" comes from the fact that in , both $\vert a \rangle$ and $\vert b \rangle$ are used to store intermediate results, which is impossible if we remove one of them.
On the other hand,  is relatively easy to adapt. The only operation involving $\vert b \rangle$ is a controlled-Phase, so we can easily "remove" the control and just apply a Phase gate when the corresponding bit of $b$ (known at generation-time) is $1$.
Draper's adder () is nice on multiple points:
- No ancilla qubit needed.
- Only QFT and phase gates, which should be easy to implement on hardware.
- A depth in $O(n)$.
But an ideal implementation would also:
- have a number of gates that grows in $O(n)$. Draper's adder is $O(n^2)$ because of the QFT.
- have more room for optimisation with respect to the number of gates / depth (for example a very low cost when the constant is $\vert 00000\rangle$ or has a lot of $0$.
- be based on a logic/arithmetic approach like  or . One of the problem with Draper's adder is that it requires very precise rotations angle, and it is hard to compute the error introduced if one of the rotations is only approximated and not exact.
My question: do you know any paper that introduce an algorithm that may interest me, based on the lists above?