4
$\begingroup$

I need to implement a quantum comparator that, given a quantum register $a$ and a real number $b$ known at generation time (i.e. when the quantum circuit is generated), set a qubit $r$ to the boolean value $(a < b)$.

I successfully implemented a comparator using 2 quantum registers as input by following A new quantum ripple-carry addition circuit (Steven A. Cuccaro and Thomas G. Draper and Samuel A. Kutin and David Petrie Moulton, 2004). This means that given two quantum registers $a$ and $b$, the circuit set a qubit $r$ to the boolean value $(a < b)$.

I could use an ancilla quantum register that will be initialised to the constant value $b$ I am interested in and then use the implementation I already have, but this sounds quite inefficient.

The only gate that use the quantum register $b$ (the one fixed at generation time) is the following:

MAJ gate as described by Cuccaro's paper

When this gate is used, the qubits of $b$ are given as the second input (i.e. the middle line in the circuit representation above) and the value of each of the qubit of $b$ is known at circuit generation.

My questions:

  1. Is there a way to remove completely the quantum register $b$ by encoding the constants values of each $b_i$ in the quantum circuit generated?
  2. Can the fact of knowing the value of the second entry of the gate at generation time be used to optimise the number of gates used (or their complexity)?

I already have a partial answer for question n°2: the Toffoli gate may be simplified to one CX gate when $b_i = 1$ and to the identity (i.e. no gate) when $b_i = 0$. There is still a problem with the first CX gate that prevent this optimisation, but this may be a track to follow?

$\endgroup$

2 Answers 2

3
$\begingroup$

Let's answer my own question: it is not possible.

After some research I ended up computing the "truth table" for the two possible cases:

  1. $b = 0$:
    • $\vert 00 \rangle\rightarrow\vert 00 \rangle$
    • $\vert 01 \rangle\rightarrow\vert 10 \rangle$
    • $\vert 10 \rangle\rightarrow\vert 10 \rangle$
    • $\vert 11 \rangle\rightarrow\vert 01 \rangle$
  2. $b = 1$:
    • $\vert 00 \rangle\rightarrow\vert 00 \rangle$
    • $\vert 01 \rangle\rightarrow\vert 11 \rangle$
    • $\vert 10 \rangle\rightarrow\vert 11 \rangle$
    • $\vert 11 \rangle\rightarrow\vert 01 \rangle$

It is clearly visible in the above truth tables that the operation I want to produce is not reversible (two different input give the same output) and so not unitary.

I will have to find another algorithm to do what I am searching for. I am still open to suggestions on interesting algorithms.

$\endgroup$
0
$\begingroup$

You can use Classiq's platform to create a comparator as explained here

Using

from classiq import Model, RegisterUserInput, synthesize, authenticate
from classiq.builtin_functions import Equal

authenticate()

params = GreaterEqual(left_arg=2.5, right_arg=RegisterUserInput(size=3))
model = Model()
model.Equal(params)
quantum_program = synthesize(model.get_model())
show(quantum_program)

You will see that it creates a circuit that uses a QFT adder, that does the addition in the Fourier transform using only the addition of phases.

The actual comparison is done with subtraction and sign-check (and auto uncomputation)

enter image description here

The subtraction is done with an adder of negative numbers (using two's complement)

enter image description here

The addition is done as explained before with phases and QFT

enter image description here

Notice that q4 does not need subtraction as it is representing the LSB ($2^{-1}=0.5$) that is compared to an integer and therefore does not affect the comparison

$\endgroup$
5
  • $\begingroup$ does this actually answer the OP? $\endgroup$
    – glS
    Jan 2 at 11:02
  • $\begingroup$ You show how to implement the comparator but the question is about optimizing already existing circuit. Yours one seems more complicated than that in the question. $\endgroup$ Jan 3 at 7:19
  • $\begingroup$ First, no allocation is needed for the constant addition whoch is done with phases inplace. Secondly there is no usage in the extra fraction places qubits, which saves 2-qubit gates $\endgroup$
    – Ron Cohen
    Jan 3 at 13:44
  • $\begingroup$ The QFT is a O(n²) gate algorithm that involves exponentially small rotations that will probably never be implementable efficiently in an error-corrected hardware. I ended up implementing the "high-bit compute" method presented in Figure 3 of arxiv.org/pdf/1611.07995.pdf (see gitlab.com/cerfacs/qaths/-/blob/master/src/qaths/routines/…) and used it in my comparator (see gitlab.com/cerfacs/qaths/-/blob/master/src/qaths/routines/…). It is a O(n) gate algorithm that only use X, CX and Toffoli gates. $\endgroup$ Jan 3 at 20:07
  • $\begingroup$ Correct, but. The question was about how to remove the need in another register fir the constant, and it can be done with QFT. The 2 features that Classiq offers are: 1. Automatically choosing between different comparator implementations according to the optimization preferences 2. Also in the non-qft (ccx) version the extra fractional qubits are not compared and this way the size of the circuit and numer of 2q gates shrinks $\endgroup$
    – Ron Cohen
    Jan 5 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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