2
$\begingroup$

I am currently studying the paper Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority and had a really hard time understanding the Quantum Authentication Scheme provided by the authors. As far as classical polynomial error correction codes go, I have had some experience with Reed-Solomon Code, but this does not seam to follow the same structure.

First of all, in Reed-Solomon the message $m = (m_0,..,m_d)$ takes the role of the coefficients of the polynomial $p_m$. However, in the above mentioned paper, the message seams to be just this $a \in F_p$ and the encoding to a polynomial $p_m$ has been replaced with the sum: $$|S_a^r⟩ = \frac{1}{\sqrt{p^r}}\sum_{f(0)=a,\\ deg(f) \leq r} |f(a_1),...,f(a_m)⟩$$ where $a_1,...,a_m \in F_p-{0}$ are known to everyone.

I am having a lot of trouble understanding this sum. My first (maybe really naive) thought that I cannot get rid of is the following: isn't this an infinite sum? In Reed-Solomon Codes the coefficients of all polynomials are determined by the demand that the polynomial passes through specific points. I see no such constrain here. Since the only constrain is the degree and the constant of the polynomial, what is stopping us from picking all integers (or even real numbers) as our coefficients?

My other question is: why does this sum even exist? Why do we need a sum of all the polynomials with such properties in the quantum world and not in the classical world?

I would really appreciate some help and I am sorry in advance if these questions are very naive, as I am new to the field. I have also found these lecture notes discussing the same Polynomial Quantum Error Correcting Code. I am providing them because the classical polynomial code structure that they present is "similarly different" from Reed-Solomon, in the sense that the encoded message is not the coefficient of the polynomial.

$\endgroup$
4
  • $\begingroup$ What is stopping us from picking all integers (or even real numbers) as our coefficients? Isn't it all over a finite field $\mathbb{Z}_p$? $\endgroup$
    – ChrisD
    Mar 12 at 4:50
  • $\begingroup$ Why do we need a sum of all the polynomials with such properties in the quantum world and not in the classical world? The short answer is that quantum states are afflicted by phase-flip errors as well as bit-flip errors. These notes are worth a read. $\endgroup$
    – ChrisD
    Mar 12 at 5:02
  • $\begingroup$ You are correct with your fist comment. As far as the second comment, the notes you provide it were really informing, although I am not quite sure I fully understood how that led to to the sum in my question. I am going to keep looking into this, thank you! $\endgroup$ Mar 14 at 15:41
  • $\begingroup$ In the set of lecture notes you linked to it mentions the Fourier transform "shifting bit-flip errors to phase errors" which is why we need this sum over polynomials, and I thought the notes I linked to provided a simpler example. Maybe an even simpler one is section 0.4 of these (the Hadamard gate is a DFT). $\endgroup$
    – ChrisD
    Mar 14 at 20:30

0

Your Answer

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

Browse other questions tagged or ask your own question.