Quantum comparator with one fixed input

Question

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

1. a quantum register $\vert a \rangle$ of size n that should be interpreted as a unsigned integer.
2. a single qubit initialised to $\vert 0 \rangle$ that will store the result of $a < rhs$ at the end of the routine.
3. at most one ancilla qubit, and preferably no ancilla qubit at all.

There are a lot of quantum comparators in the wild (for example [1], [2] or [3]) 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.

I tried to modify [1] in order to be able to remove the need for the quantum register $\vert b \rangle$, but I ended up proving it was not possible (see my question).

Even if I have no rigorous proof, I think a similar argument applies to [2]. My "intuition" comes from the fact that in [2], 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, [3] 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 ([3]) is nice on multiple points:

1. No ancilla qubit needed.
2. Only QFT and phase gates, which should be easy to implement on hardware.
3. A depth in $O(n)$.

But an ideal implementation would also:

1. have a number of gates that grows in $O(n)$. Draper's adder is $O(n^2)$ because of the QFT.
2. 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$.
3. be based on a logic/arithmetic approach like [1] or [2]. 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?

Answer 1

You can do this with two ancillae and $O(n \lg n)$ operations by using the comparator from https://arxiv.org/abs/1706.07884.

The constant comparator uses two constant adders:

The constant adders are a recursive construction from https://arxiv.org/abs/1611.07995 which uses an incrementer and a carry signal propagator:

The incrementer uses a normal adder with same-sized input and target registers:

The same-sized input/target adder can be done with no ancillae:

And the carry propagation uses linear dirty ancillae:

If you're feeling really ambitious, you can remove at least one of the ancillae by using phasing operations in this way: