3
$\begingroup$

I am working from chapter 7 from notes for ph229 by J. Preskill.

The notes define the distance of a quantum code as:

The distance $d$ is the the minimum weight of a Pauli operator $E$ such that: $$\langle i|E_{a}|j \rangle \neq C_{a}\delta_{ij}.$$

The notes also state that

A (Quantum Error Correcting Code) can correct $t$ errors if the set $\varepsilon$ of $E_{a}$'s that allow recovery includes all Pauli operators of weight $t$ or less. Our definition of distance implies that the criterion for error correction $$\langle i | E_{a}^{ > †} E_{b} | j \rangle = C_{ab}\delta_{ij}$$ will be satisfied by all Pauli operators of weight $t$ or less provided that $d \geq 2t + 1$. Therefore, a (Quantum Error Correcting Code) with distance $d=2t + 1$ can correct $t$ errors.


I am struggling with understanding how we come to the conclusion that$d \geq 2t+1$ in order for the criterion for error correction to be satisfied by all Pauli operators of weight $t$ or less.

My understanding works as follows: $d = \text{min}(wt(E_{a}))$ such that $\langle i|E_{a}|j \rangle \neq C_{a}\delta_{ij}$. But if we want our code to correct $t$ errors, then the set of $E_{a}$'s must consist of all the Pauli operators of weight $\leq t$. So the distance of this code must be $d \geq t$. I would have thought that for: $$\langle i | E_{a}^{ †} E_{b} | j \rangle = C_{ab}\delta_{ij}\,,$$ we would also simply require that $d \geq t$?

$\endgroup$

2 Answers 2

3
$\begingroup$

Imagine you have two errors $E_a$ and $E_b$. When can you correct for both errors? If they have different syndromes, you can certainly correct them. The problem is what happens if they have the same syndrome. In that case, assume you found that syndrome and corrected for $E_a$.

If your error was originally $E_a$, great, you're done! If your error was $E_b$, you've now performed the net operation $E_aE_b$ on your code. If the weight of $E_aE_b$ is less than $d$, you are guaranteed that $E_aE_b$ is not a logical operator. So it must be in the stabilizer, and you have successfully corrected. Phew! So, now we just need to say $|E_aE_b|<|E_a|+|E_b|<d$. This is always satisfied if we only consider error operators of weight less than $d/2$. Of course, there may be combinations at higher weight that still work, but as soon as you pass that threshold, you can construct errors that will do bad things (e.g. split a logical operator in half).

$\endgroup$
3
  • 1
    $\begingroup$ Ah I think I understand now! So if we only consider operators of weight less than $d$, then say $|E_{a}| < \frac{d}{2}$, $|E_{b}| < \frac{d}{2}$, then $|E_{a}E_{b}| < d$. But we also must include all operators of weight $\leq t$, so we require that $d \geq t$. So $\frac{d}{2} \geq t \Rightarrow d \geq 2t$. However, I am not sure how to get to $d \geq 2t+1$, perhaps because we must have $|E_{a}| + |E_{b}| <d$, we should actually only consider operators of weight $\leq \frac{d-1}{2}$. $\endgroup$
    – am567
    Commented Feb 12 at 12:48
  • 2
    $\begingroup$ Yes, so all you're saying is that for $|E_a|,|E_b|\leq t$ then $|E_aE_B|\leq 2t<d$. Given everything's an integer, $2t+1\leq d$. $\endgroup$
    – DaftWullie
    Commented Feb 12 at 14:04
  • 2
    $\begingroup$ It's probably worth pointing out that this is a result that also holds for classical codes. $\endgroup$ Commented Feb 12 at 19:58
0
$\begingroup$

Because when you retrieve a faulty code word $\tilde{c}\in\mathbb{F}_q^n$, you decode by looking at what codeword $c\in C\subseteq\mathbb{F}_q^n$ minimises the Hamming distance $|c-\tilde{c}|_H$. The minimum distance $d$ of a code is defined as the minimum Hamming weight of a codeword in that code. So every codeword can have a Hamming ball of maximal radius $t = [\frac{d-1}{2}]$, such that every ball is disjoint. Then, the only way to correctly decode a faulty codeword is if and only if $\tilde{c}$ is in the Hamming ball of $c$, which can only happen if $d\geq 2t+1$.

$\endgroup$

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.