0
$\begingroup$

I was thinking to ask this on Math Stackexchange, but maybe here would be better since I also hope the answers also explain from quantum computation context.

Problem

So I was reading the paper "Concrete quantum-cryptanalysis of binary elliptic curves", and I got stuck in understanding how to construct a multiplication by constant circuit for binary field. In their CHES presentation and their other paper, the authors describe that it is easy to construct the circuit from a matrix since multiplication by constant is just a linear mapping.

On their other paper, they present this matrix as a representation of multiplication by $1 + x^2$ modulo $1 + x + x^4$:

$\Gamma = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \end{bmatrix} $

which by LUP decomposition, corresponds to this circuit:

enter image description here

Questions

The questions are interrelated. They are:

1. How to construct matrix $\Gamma$?

2. Why the multiplication matrix is a 4x4 matrix for a 4-qubit circuit? I thought it would be 16x16 $(2^n = 16)$?

3. Is that particular matrix ($\Gamma$) really correct for all values?

My Attempts So Far

For Question 1

My guess is by creating two matrices, e.g., $INPUT$ and $OUTPUT$, which includes all possible inputs and the corresponding output after the constant multiplication. Then, the matrix $\Gamma$ can be obtained from $OUTPUT * INPUT^{-1}$.

I have tried from scratch: calculated all the possible 16 input and the corresponding output pairs (derived from SageMath) and make the mapping (i.e., $\left| x0,x,x^2,x^3 \right> = \left| 0010 \right> \rightarrow \left| 1110 \right>, \left| 0100 \right> \rightarrow \left| 0101 \right>$, and so on...

However, then I realized that the resulting matrix is a rectangular 16x4 matrix rather than a square matrix for each $INPUT$ and $OUTPUT$, so the inversion can not be done when I tried that on Matlab.

For Question 3

For each possible input, I applied $\Gamma$ to verify the output result. While 6 of them are correct, the other 10 are wrong. For example, $\left| 1011 \right> \rightarrow \left| 2231 \right>$ rather than $\left| 0011 \right> $.

I am not sure that kind of paper would contain such errors. So my bet is my approach was all wrong.

I would be very grateful if anyone could guide me on this. Any help is appreciated. Thanks!

$\endgroup$
3
  • $\begingroup$ The matrix looks correct (assuming they used the polynomial basis). Are you familiar with Galois fields? Then I could try to formulate an answer. $\endgroup$ Oct 26 at 15:42
  • $\begingroup$ Yes, I am quite familiar. Also, I am quite confident with my mapping since I calculated some by hand then verify them on SageMath. If it helps/make it more convenient to you, I could post the whole matrix of $INPUT$ and $OUTPUT$ (for Question 1), and the actual result of the multiplication to matrix $\Gamma$ which I found wrong (for Question 3) $\endgroup$
    – prairie99
    Oct 27 at 0:33
  • 1
    $\begingroup$ You don't need to. Your logic seems to be correct, but you're overcomplicating things. I'll post an answer within the next hours. $\endgroup$ Oct 27 at 6:14
3
$\begingroup$

Let me start with some background information on this problem as not all people might be familiar with it.

It is well known that finite fields for prime order $p$ can be constructed by taking integers modulo $p$, this is $\mathbb F_p \simeq \mathbb Z / p\mathbb Z$. From this, we can construct certain field extensions, namely Galois extensions, as follows. Consider the univariate polynomial ring $\mathbb F_p[\theta]$ (I don't use $x$ as variable symbol to keep notation clean.) Let $f\in\mathbb F_p[\theta]$ be an irreducible polynomial of degree $m$, this is $f$ cannot be written as a product of two non-constant polynomials. Then, the quotient w.r.t. to the ideal generated by $f$, $\mathbb F_{p^m}:=\mathbb F_p[\theta]/(f)$ is a finite field with $q=p^m$ elements. Its elements can be seen as polynomials in $\theta$ modulo $f$.

Question 1 The first problem you're considering is to find a matrix representation of the multiplication with an element $a = 1+\theta^2$ from the finite field $\mathbb F_{2^4}=\mathbb F_{16}$ (as $1+\theta+\theta^4$ is irreducible). More generally, the additive group of $\mathbb F_{p^m}$ has the structure of a vector space over $\mathbb F_p$, $\mathbb F_{p^m}^+ \simeq \mathbb F_p^m$. Choosing a polynomial basis, i.e. writing any element $b\in\mathbb F_{p^m}$ uniquely as $$ b = b_0 \theta^0 + b_1 \theta^1 + \dots + b_{m-1} \theta^{m-1}, \quad b_i \in \mathbb F_p, $$ induces such an isomorphism by $b \mapsto (b_0,\dots,b_{m-1})\in\mathbb F_p^m$.

Since the multiplication $M_a: b \mapsto ab$ is $\mathbb F_p$-linear, $M_a$ induces a linear map on $\mathbb F_p^m$ which can be written in a basis as a $m\times m$ matrix with coefficients in $\mathbb F_p$.

Now back to your example. To find the matrix representing $M_{1+\theta^2}$ in the standard polynomial basis, we have to act with $1+\theta^2$ on all four basis elements, i.e. on $\theta^0,\dots,\theta^3$. This yields: $$ 1 \mapsto 1+\theta^2, \quad \theta \mapsto \theta + \theta^3, \\ \theta^2 \mapsto \theta^2 + \theta^4 = 1 + \theta + \theta^2, \quad \theta^3 \mapsto \theta(\theta^2+\theta^4) = \theta+\theta^2+\theta^3. $$ We can now extract the expansion coefficients from the images and write them as columns of the matrix representation $$ M_{1+\theta^2} \simeq \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix} =\Gamma. $$ This should answer Question 3 (btw in your example, you have to take the result modulo 2, since we're in $\mathbb F_2$!).

Question 2 That $M_a$ is a $4\times 4$ matrix should be clear by now. How is this now related to quantum circuits? We can label the computational basis of a $n$-qubit system by vectors $x\in\mathbb F_2^n$, namely we set $$ | x \rangle := | x_1 \rangle \otimes \dots \otimes |x_n\rangle. $$ Matrices $M\in\mathrm{GL}_n(\mathbb F_2)$ act naturally on this basis by $| x \rangle \mapsto | Mx\rangle$, i.e. they only permute the computational basis. As such, they clearly define a unitary $U_M$. Note that the unitary has dimension $2^n \times 2^n$ and complex (here: real) entries but $M$ is a $n\times n$ matrix with binary entries.

Remark: It is a well-known fact that $\mathrm{GL}_n(\mathbb F_2)$, i.e. the reversible linear Boolean circuits, is generated by $CNOT$ gates with representation $$ CNOT_{12} \simeq \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, \quad CNOT_{21} \simeq \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}. $$ This basically follows from the PLU decomposition together with rewritting permutations as CNOT circuits.

$\endgroup$
5
  • $\begingroup$ It did not come to my mind at all to modulo the result! And thanks for stressing about the basis, that clears up much of my confusion. One question, is the term LUP and PLU decomposition interchangeable? $\endgroup$
    – prairie99
    Oct 27 at 10:13
  • 1
    $\begingroup$ @prairie99 If I'm not mistaken, LUP and PLU are basically interchangeable: LUP states that $PA = LU$ and PLU that $A = P' LU$. Although the permutations might not be unique, we can take $P' = P^{-1}$ such that one decomposition follows from the other. $\endgroup$ Oct 27 at 11:54
  • $\begingroup$ Hi, do you know how to construct the swap gates given the corresponding $n$ x $n$ permutation gate? If yes, I will make a new question for this. (Note: I already understand how to make the corresponding CNOT from the L and U matrix, but my swap implementation has not given completely correct result). $\endgroup$
    – prairie99
    Nov 8 at 10:06
  • $\begingroup$ @prairie99 the task you want to solve is to write a permutation $\pi$ as a product of transpositions (since this is what SWAP gates are!). This is always possible, but non-unique. I remember some paper which proposes an algorithm for this in the context of circuit synthesis, but I cannot find it right now ... Perhaps, you should open a new question for this, I'll try to find it :) $\endgroup$ Nov 9 at 12:11
  • $\begingroup$ here is my question, I'd be happy to have more answers :) thank you! $\endgroup$
    – prairie99
    Nov 9 at 13:06

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.