4
$\begingroup$

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 routinecompare(n, rhs) that will produce a circuit taking as input

  1. a quantum register$\vert a \rangle$ of sizen 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 (seemy 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?

askedJul 18, 2019 at 8:13
Adrien Suau's user avatar
$\endgroup$

1 Answer1

1
+50
$\begingroup$

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

The constant comparator uses two constant adders:

enter image description here

The constant adders are a recursive construction fromhttps://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

answeredAug 22, 2019 at 20:21
Craig Gidney's user avatar
$\endgroup$
6
  • $\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$CommentedAug 23, 2019 at 8:11
  • $\begingroup$@Nelimee There is code implementing the operations atgithub.com/Strilanc/PaperImpl-2017-DirtyPeriodFinding specificallygithub.com/Strilanc/PaperImpl-2017-DirtyPeriodFinding/blob/…$\endgroup$CommentedAug 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$CommentedAug 29, 2019 at 8:10
  • $\begingroup$@AdrienSuau Did you finish the comparison with Draper-based adder? I am interested in a similar application.$\endgroup$CommentedMay 19 at 21:17
  • $\begingroup$@CraigGidney Are the constant adders you mentioned still optimal compared to the conditionally clean ancillae approach in your new paper? Also, any thoughts onquantumcomputing.stackexchange.com/q/41829/36359 ?$\endgroup$CommentedMay 19 at 21:19

Your Answer

Sign up orlog in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

By clicking “Post Your Answer”, you agree to ourterms of service and acknowledge you have read ourprivacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.