2
$\begingroup$

So, currently I am going through the paper Concrete Quantum Cryptanalysis of Binary Elliptic Curves. The section on point addition mentions that for adding two points $P_1$ and $P_2$, they assume that $P_2$ is a fixed (non-quantum) point. Moreover, they assume a generic case where $P_1 \ne P_2 \ne O$, $P_1 \ne -P_2$. On studying another paper, I found that these are mostly valid assumptions to make.

Implementing Point Addition

My issue is with the const_ADD function they mention. I can see that the function basically adds a quantum and a fixed (non-quantum) polynomial, but there are no implementation details for it.

In addition, while performing the ctrl_const_ADD on line $(2)$, they multiply a qubit $q$ with a fixed polynomial $y_2$. There are no hints given as to how that can be implemented either.

If anyone has an idea of how to implement these in practice, please do guide me. Thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

This kind of thing would typically falls under the "we know we can do it, but we won't go into the actual implementation" practice. Adding a known, constant polynomial to another one is something that can be described classically. Once that's done, we convert this procedure into a quantum circuit and voilà.

Expliciting the implementation requires to describe the way our data is encoded, the algorithm we use, etc...

Fortunately here, if I'm not mistaken, const_ADD is quite a simple operation. A binary polynomial is represented as a bitstring, and an addition between two of these polynomials is simply an XOR between their respective bitstrings. Thus, implementing const_ADD(x, x_2) is simply done by applying $X$ gates on qubit number $i$ if the corresponding bit in $x_2$'s bitstring is set.

The multiplication would be a bit more involved, since there are (IIRC) more efficient algorithms to do so than the naive method. However, you could still do just like for the addition: translate this to an operation on the bitstrings and apply the corresponding gates.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks a lot, using this I was also able to implement multiplication of qubit with a fixed polynomial by using the LUP decomposition of fixed polynomial. $\endgroup$ Jan 13 at 9:21

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.