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?


1 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:

enter image description here

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

enter image description here

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

enter image description here

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

enter image description here

And the carry propagation uses linear dirty ancillae:

enter image description here

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

enter image description here

  • $\begingroup$ Really interesting! At first glance, this seems like what I was searching for. I will take a look at the papers and implement the algorithms to test them. I come back to you once done. Thank you for your answer. $\endgroup$ Aug 23, 2019 at 8:11
  • $\begingroup$ @Nelimee There is code implementing the operations at github.com/Strilanc/PaperImpl-2017-DirtyPeriodFinding specifically github.com/Strilanc/PaperImpl-2017-DirtyPeriodFinding/blob/… $\endgroup$ Aug 24, 2019 at 1:38
  • $\begingroup$ Thank you for your answer, it helped me a lot. I only had to implement the carry propagation to compute the high-bit of $a - c = (a' + c)'$ where ' is the bitwise complementation. Once this done, the comparator is built as the high-bit of $a - c$ is $1$ only if $a < c$. I will implement the adder in the few next days (following your links and the papers) to compare its practical implementation to Draper's one (with QFT). $\endgroup$ Aug 29, 2019 at 8:10

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.