The Quantum Singleton Bound states that for an error-correcting code with $n$ physical qubits and $k$ encoded qudits, and some subsystem $R$ of $m$ qudits that can 'access the entire quantum code', it is necessary that $m \ge \frac{n+k}{2}$.

As I understand (from section 4.3 of Harlow's TASI notes), one way to state the condition for 'accessing the entire code' is the Knill-Laflamme condition, which is the following.

Let $\bar{R}$ denote the complement of $R$, $\mathscr{H}_\bar{R}$ be the space of operators supported on $\bar{R}$, and $P$ denote the projection matrix onto the code subspace $\mathscr{H}_{code}$. Then for any operator $O_{\bar{R}} \in \mathscr{H}_\bar{R}$, $P O_{\bar{R}} P = \lambda P$, where $\lambda$ is some constant that depends on the operator $O_{\bar{R}}$

This means that operator supported on the complement region $\bar{R}$ has no effect on measurements on $\mathscr{H}_{code}$.

I'm confused because this does not seem compatible with the toric code. Because, it can be shown that in the toric code (where the number of encoded bits $k=2$), the Knill-Laflamme condition is satisfied for $\bar{R}$ being any contractible region of qubits, i.e. for $R$ containing the union of two distinct nontrivial cycles on the torus. In this case on a torus of length $L \times L$, we will have the number of physical qubits being $n = 2 L^2$ and the number of bits needed to access being $m = 4 L$. So, it seems that the singleton bound is explicitly violated.

Where does the logic I'm presenting fail, and why should the Toric Code be compatible with this?

EDIT: I think I found the issue. It turns out that Harlow was a bit unclear in what he meant in his statement that some subsystem of $m$ qudits being able to access the information. He didn't actually mean that, but meant a different statement, which I'll summarize in the following theorem.

Theorem: Suppose that in a qudit system S of size $n$, there are subsystems A,B both of size $m$ such that their complements $A^c$ and $B^c$ (both of size $n-m$) are disjoint and can be erased (not necessarily simultaneously) and the errors be recovered (in the Knill-Laflamme sense above, or in some other equivalent senses as in Theorem 4.1 of his TASI notes). Then, $m \ge \frac{n+k}{2}$.

Note that this condition does NOT mean the same thing as any subsystem being able to access the whole system. Rather, it means that if two disjoint regions of sizes $(n-m)$ (so that their total size is $2(n-m)$) can be erased and corrected (not necessarily simultaneously), then $m \ge \frac{n+k}{2}$.

This is equivalent to the statement that Preskill made in his notes (see Norbert's reply below), since $n-m = d-1$ relates $n-m$ to the distance $d$ of the code, which means that $n-k \ge 2(d-1)$, which is indeed the Singleton bound.

So long story short, the above bound $m \ge \frac{n+k}{2}$ does not hold for generally being able to access the logical operators from a subsystem of size $m$.

  • $\begingroup$ Cross-posted on QCSE. $\endgroup$
    – user199113
    Commented Apr 5, 2019 at 18:28

1 Answer 1


In Preskill's lecture notes (Ch. 7.8.3), the quantum Singleton bound for a [[n,k,d]] code reads $$ n-k \ge 2(d-1)\ . $$ This seems quite different from the bound you quote. For the toric code on an $N\times N$ lattice, $n=2N^2$, $k=2$, and $d=N$, so the inequality is clearly satisfied.

On the other hand, the bound you quote is derived in Harlow's paper. There, in the derivation, he states:

In general we cannot say much about how big k can be relative to n, but we can do much better if we assume that whether or not a collection of physical qudits is able to access the logical information is determined entirely by the number of qudits in that collection.

(Emphasis mine.) Indeed, this fact is used later in a kind of no-cloning argument.

Clearly, this property does not hold for the toric code. In particular, if you have a region which allows you to access the encoded information, its complement never allows you to access the information, as it topologically trivial. Still, the former can be two rings around the torus with total $2N$ qubits, while the latter will have $N^2-2N$ qubits, which is typically much larger than $N$ -- the ability to access the information is thus not only dependent on the number of qubits you act on. The argument thus does not hold.

  • $\begingroup$ Thanks. But although for this version of the bound it's clearly true, it doesn't address the version I stated above. $\endgroup$
    – Joe
    Commented Apr 8, 2019 at 21:28
  • 1
    $\begingroup$ @Joe Do you use it as derived in the paper of Harlow you reference? Just updated my answer, his argument does not hold for the TC. (Also, not sure why he calls this the quantum singleton bound) $\endgroup$ Commented Apr 8, 2019 at 21:48
  • $\begingroup$ Hello, thanks for your edit. I worked out the arguments that Harlow made, and it turns out that Harlow's statement is precisely the Singleton bound as Preskill stated, since the argument precisely matches that of Preskill's. Harlow doesn't actually use the statement that you quoted (that the access is determined entirely by the number of qudits), but uses a different statement that's equivalent to what Preskill says. I will make an edit above to clarify $\endgroup$
    – Joe
    Commented Apr 9, 2019 at 0:22
  • $\begingroup$ @Joe Then how come Harlow's bound is so different (and Preskill's proof involves entropies, while Harlow's proof involves cloning)? $\endgroup$ Commented Apr 9, 2019 at 9:58
  • $\begingroup$ It's actually the same exact proof. See the discussion starting at page 30 of his notes, starting at the paragraph before (4.21). Harlow invokes no-cloning to show that $m \ge \frac{n}{2}$, but to show $m \ge \frac{n+k}{2}$, we need the entropy argument which Harlow provides. (Preskill actually mentions the exact same cloning bound (7.102)) Actually, Harlow's presentation is more rigorous, because he justifies the tensor decompositions in (4.21). Whereas Preskill simply states his eqs (7.107)(7.108) as intuitive. My main post's edit shows the map between the variables they both use $\endgroup$
    – Joe
    Commented Apr 9, 2019 at 22:57

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.