Edited to clarify what the Grassl--Beth--Pellizzari result is the earliest reference *for*, and to point to Felix Huber's answer
Source Link
Niel de Beaudrap
  • 10.6k
  • 1
  • 21
  • 59

A proof that you need at least 5 qubits (or qudits)

Here is a proof that any single-error correcting (i.e., distance 3) quantum error correcting code has at least 5 qubits. In fact, this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting one or more qudits of dimension $d$.

(As Felix Huber notes, the original proof that you require at least 5 qubits is due to the Knill--Laflamme article [arXiv:quant-ph/9604034] which set out the Knill--Laflamme conditions: the following is the proof technique which is more commonly used nowadays.)

Any quantum error correcting code which can correct $t$ unknown errors, can also correct up to $2t$ erasure errors (where we simply lose some qubit, or it becomes completely depolarised, or similar) if the locations of the erased qubits are known. [1, Sec. III A]*. Slightly more generally, a quantum error correcting code of distance $d$ can tolerate $d-1$ erasure errors. For example, while the $[\![4,2,2]\!]$ code can't correct any errors at all, in essence because it can tell an error has happened (and even which type of error) but not which qubit it has happened to, that same code can protect against a single erasure error (because by hypothesis we know precisely where the error occurs in this case).

It follows that any quantum error correcting code which can tolerate one Pauli error, can recover from the loss of two qubits. Now: suppose you have a quantum error correcting code on $n \geqslant 2$ qubits, encoding one qubit against single-qubit errors. Suppose that you give $n-2$ qubits to Alice, and $2$ qubits to Bob: then Alice should be able to recover the original encoded state. If $n<5$, then $2 \geqslant n-2$, so that Bob should also be able to recover the original encoded state — thereby obtaining a clone of Alice's state. As this is ruled out by the No Cloning Theorem, it follows that we must have $n \geqslant 5$ instead.

On correcting erasure errors

* The earliest reference I found for this is

[1] Grassl, Beth, and Pellizzari.
      Codes for the Quantum Erasure Channel.
      Phys. Rev. A 56 (pp. 33–38), 1997.
      [arXiv:quant-ph/9610042]

— which is not much long after the Knill–Laflamme conditions were described in [arXiv:quant-ph/9604034] and so plausibly the original proof of the connection between code distance and erasure errors. The outline is as follows, and applies to error correcting codes of distance $d$ (and applies equally well to qudits of any dimension in place of qubits, using generalised Pauli operators).

  • The loss of $d-1$ qubits can be modelled by those qubits being subject to the completely depolarising channel, which in turn can be modeled by those qubits being subject to uniformly random Pauli errors.

  • If the locations of those $d-1$ qubits were unknown, this would be fatal. However, as their locations are known, any pair Pauli errors on $d-1$ qubits can be distinguished from one another, by appeal to the Knill-Laflamme conditions.

  • Therefore, by substituting the erased qubits with qubits in the maximally mixed state and testing for Pauli errors on those $d-1$ qubits specificaly (requiring a different correction procedure than you would use for correcting arbitrary Pauli errors, mind you), you can recover the original state.

A proof that you need at least 5 qubits (or qudits)

Here is a proof that any single-error correcting (i.e., distance 3) quantum error correcting code has at least 5 qubits. In fact, this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting one or more qudits of dimension $d$.

Any quantum error correcting code which can correct $t$ unknown errors, can also correct up to $2t$ erasure errors (where we simply lose some qubit, or it becomes completely depolarised, or similar) if the locations of the erased qubits are known. [1, Sec. III A]*. Slightly more generally, a quantum error correcting code of distance $d$ can tolerate $d-1$ erasure errors. For example, while the $[\![4,2,2]\!]$ code can't correct any errors at all, in essence because it can tell an error has happened (and even which type of error) but not which qubit it has happened to, that same code can protect against a single erasure error (because by hypothesis we know precisely where the error occurs in this case).

It follows that any quantum error correcting code which can tolerate one Pauli error, can recover from the loss of two qubits. Now: suppose you have a quantum error correcting code on $n \geqslant 2$ qubits, encoding one qubit against single-qubit errors. Suppose that you give $n-2$ qubits to Alice, and $2$ qubits to Bob: then Alice should be able to recover the original encoded state. If $n<5$, then $2 \geqslant n-2$, so that Bob should also be able to recover the original encoded state — thereby obtaining a clone of Alice's state. As this is ruled out by the No Cloning Theorem, it follows that we must have $n \geqslant 5$ instead.

On correcting erasure errors

* The earliest reference I found for this is

[1] Grassl, Beth, and Pellizzari.
      Codes for the Quantum Erasure Channel.
      Phys. Rev. A 56 (pp. 33–38), 1997.
      [arXiv:quant-ph/9610042]

— which is not much long after the Knill–Laflamme conditions were described in [arXiv:quant-ph/9604034] and so plausibly the original proof. The outline is as follows, and applies to error correcting codes of distance $d$ (and applies equally well to qudits of any dimension in place of qubits, using generalised Pauli operators).

  • The loss of $d-1$ qubits can be modelled by those qubits being subject to the completely depolarising channel, which in turn can be modeled by those qubits being subject to uniformly random Pauli errors.

  • If the locations of those $d-1$ qubits were unknown, this would be fatal. However, as their locations are known, any pair Pauli errors on $d-1$ qubits can be distinguished from one another, by appeal to the Knill-Laflamme conditions.

  • Therefore, by substituting the erased qubits with qubits in the maximally mixed state and testing for Pauli errors on those $d-1$ qubits specificaly (requiring a different correction procedure than you would use for correcting arbitrary Pauli errors, mind you), you can recover the original state.

A proof that you need at least 5 qubits (or qudits)

Here is a proof that any single-error correcting (i.e., distance 3) quantum error correcting code has at least 5 qubits. In fact, this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting one or more qudits of dimension $d$.

(As Felix Huber notes, the original proof that you require at least 5 qubits is due to the Knill--Laflamme article [arXiv:quant-ph/9604034] which set out the Knill--Laflamme conditions: the following is the proof technique which is more commonly used nowadays.)

Any quantum error correcting code which can correct $t$ unknown errors, can also correct up to $2t$ erasure errors (where we simply lose some qubit, or it becomes completely depolarised, or similar) if the locations of the erased qubits are known. [1, Sec. III A]*. Slightly more generally, a quantum error correcting code of distance $d$ can tolerate $d-1$ erasure errors. For example, while the $[\![4,2,2]\!]$ code can't correct any errors at all, in essence because it can tell an error has happened (and even which type of error) but not which qubit it has happened to, that same code can protect against a single erasure error (because by hypothesis we know precisely where the error occurs in this case).

It follows that any quantum error correcting code which can tolerate one Pauli error, can recover from the loss of two qubits. Now: suppose you have a quantum error correcting code on $n \geqslant 2$ qubits, encoding one qubit against single-qubit errors. Suppose that you give $n-2$ qubits to Alice, and $2$ qubits to Bob: then Alice should be able to recover the original encoded state. If $n<5$, then $2 \geqslant n-2$, so that Bob should also be able to recover the original encoded state — thereby obtaining a clone of Alice's state. As this is ruled out by the No Cloning Theorem, it follows that we must have $n \geqslant 5$ instead.

On correcting erasure errors

* The earliest reference I found for this is

[1] Grassl, Beth, and Pellizzari.
      Codes for the Quantum Erasure Channel.
      Phys. Rev. A 56 (pp. 33–38), 1997.
      [arXiv:quant-ph/9610042]

— which is not much long after the Knill–Laflamme conditions were described in [arXiv:quant-ph/9604034] and so plausibly the original proof of the connection between code distance and erasure errors. The outline is as follows, and applies to error correcting codes of distance $d$ (and applies equally well to qudits of any dimension in place of qubits, using generalised Pauli operators).

  • The loss of $d-1$ qubits can be modelled by those qubits being subject to the completely depolarising channel, which in turn can be modeled by those qubits being subject to uniformly random Pauli errors.

  • If the locations of those $d-1$ qubits were unknown, this would be fatal. However, as their locations are known, any pair Pauli errors on $d-1$ qubits can be distinguished from one another, by appeal to the Knill-Laflamme conditions.

  • Therefore, by substituting the erased qubits with qubits in the maximally mixed state and testing for Pauli errors on those $d-1$ qubits specificaly (requiring a different correction procedure than you would use for correcting arbitrary Pauli errors, mind you), you can recover the original state.

Minor corrections, and elaboration to treat error detection codes and to make reference to code distance
Source Link
Niel de Beaudrap
  • 10.6k
  • 1
  • 21
  • 59

A proof that you need at least 5 qubits (or qudits)

Here is a proof that any single-error correcting (iei.e., distance 3 3) quantum error correcting code has at least 5 qubits — and in. In fact, this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting a quditone or more qudits of dimension $d$.

Any quantum error correcting code which can correct $t$ unknown errors, can also correct up to $2t$ erasure errors (where we simply lose some qubit, or it becomes completely depolarised, or similar) if the locations of the erased qubits are known. [1, Sec. III A]*. SoSlightly more generally, a quantum error correcting code of distance $d$ can tolerate $d-1$ erasure errors. For example, while the $[\![4,2,2]\!]$ code can't correct any errors at all, in essence because it can tell an error has happened (and even which type of error) but not which qubit it has happened to, that same code can protect against a single erasure error (because by hypothesis we know precisely where the error occurs in this case).

It follows that any quantum error correcting code which can tolerate one Pauli error, can recover from the loss of two qubits.

Now Now: suppose you have a quantum error correcting code on $n \geqslant 2$ qubits, encoding one qubit against single-qubit errors. Suppose that you give $n-2$ qubits to Alice, and $2$ qubits to Bob: then Alice should be able to recover the original encoded state. If $n<5$, then $2 \geqslant n-2$, so that Bob should also be able to recover the original encoded state — thereby obtaining a clone of Alice's state. As this is ruled out by the No Cloning Theorem, it follows that we must have $n \geqslant 5$ instead.

On correcting erasure errors

* The earliest reference I found for this is

[1] Grassl, Beth, and Pellizzari.
      Codes for the Quantum Erasure Channel.
      Phys. Rev. A 56 (pp. 33–38), 1997.
      [arXiv:quant-ph/9610042]

— which is not much long after the Knill–Laflamme conditions were described in [arXiv:quant-ph/9604034] and so plausibly the original proof. The outline is as follows, and applies to error correcting codes of distance $d$ (and applies equally well to qudits of any dimension in place of qubits, using generalised Pauli operators).

  • The loss of $2t$$d-1$ qubits can be modelled by those qubits being subject to the completely depolarising channel, which in turn can be modeled by those qubits being subject to uniformly random Pauli errors.

  • If the locations of those $d-1$ qubits were unknown, this would be fatal;fatal. butHowever, as their locations are known, any pair of $2t$-qubitPauli errors on those $d-1$ qubits can be distinguished from one another, by appeal to the Knill-Laflamme conditions on (unknown) $t$-qubit Pauli errors.

  • Therefore, by substituting the erased qubits with qubits in the maximally mixed state and testing for Pauli errors on those two$d-1$ qubits specificaly (requiring a different correction procedure than you would use for correcting arbitrary Pauli errors, mind you), you can recover the original state.

A proof that you need at least 5 qubits (or qudits)

Here is a proof that any single-error correcting (ie., distance 3) quantum error correcting code has at least 5 qubits — and in fact this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting a qudit of dimension $d$.

Any quantum error correcting code which can correct $t$ unknown errors, can also correct up to $2t$ erasure errors (where we simply lose some qubit, or it becomes completely depolarised, or similar) if the locations of the erased qubits are known. [1, Sec. III A]*. So, any quantum error correcting code which can tolerate one Pauli error, can recover from the loss of two qubits.

Now: suppose you have a quantum error correcting code on $n \geqslant 2$ qubits, encoding one qubit against single-qubit errors. Suppose that you give $n-2$ qubits to Alice, and $2$ qubits to Bob: then Alice should be able to recover the original encoded state. If $n<5$, then $2 \geqslant n-2$, so that Bob should also be able to recover the original encoded state — thereby obtaining a clone of Alice's state. As this is ruled out by the No Cloning Theorem, it follows that we must have $n \geqslant 5$ instead.

On correcting erasure errors

* The earliest reference I found for this is

[1] Grassl, Beth, and Pellizzari.
      Codes for the Quantum Erasure Channel.
      Phys. Rev. A 56 (pp. 33–38), 1997.
      [arXiv:quant-ph/9610042]

— which is not much long after the Knill–Laflamme conditions were described in [arXiv:quant-ph/9604034] and so plausibly the original proof. The outline is as follows (and applies to qudits of any dimension in place of qubits, using generalised Pauli operators).

  • The loss of $2t$ qubits can be modelled by those qubits being subject to the completely depolarising channel, which in turn can be modeled by those qubits being subject to uniformly random Pauli errors.

  • If the locations of those qubits were unknown, this would be fatal; but as their locations are known, any pair of $2t$-qubit errors on those qubits can be distinguished from one another, by appeal to the Knill-Laflamme conditions on (unknown) $t$-qubit Pauli errors.

  • Therefore, by substituting the erased qubits with qubits in the maximally mixed state and testing for Pauli errors on those two qubits specificaly (requiring a different correction procedure than you would use for correcting arbitrary Pauli errors, mind you), you can recover the original state.

A proof that you need at least 5 qubits (or qudits)

Here is a proof that any single-error correcting (i.e., distance 3) quantum error correcting code has at least 5 qubits. In fact, this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting one or more qudits of dimension $d$.

Any quantum error correcting code which can correct $t$ unknown errors, can also correct up to $2t$ erasure errors (where we simply lose some qubit, or it becomes completely depolarised, or similar) if the locations of the erased qubits are known. [1, Sec. III A]*. Slightly more generally, a quantum error correcting code of distance $d$ can tolerate $d-1$ erasure errors. For example, while the $[\![4,2,2]\!]$ code can't correct any errors at all, in essence because it can tell an error has happened (and even which type of error) but not which qubit it has happened to, that same code can protect against a single erasure error (because by hypothesis we know precisely where the error occurs in this case).

It follows that any quantum error correcting code which can tolerate one Pauli error, can recover from the loss of two qubits. Now: suppose you have a quantum error correcting code on $n \geqslant 2$ qubits, encoding one qubit against single-qubit errors. Suppose that you give $n-2$ qubits to Alice, and $2$ qubits to Bob: then Alice should be able to recover the original encoded state. If $n<5$, then $2 \geqslant n-2$, so that Bob should also be able to recover the original encoded state — thereby obtaining a clone of Alice's state. As this is ruled out by the No Cloning Theorem, it follows that we must have $n \geqslant 5$ instead.

On correcting erasure errors

* The earliest reference I found for this is

[1] Grassl, Beth, and Pellizzari.
      Codes for the Quantum Erasure Channel.
      Phys. Rev. A 56 (pp. 33–38), 1997.
      [arXiv:quant-ph/9610042]

— which is not much long after the Knill–Laflamme conditions were described in [arXiv:quant-ph/9604034] and so plausibly the original proof. The outline is as follows, and applies to error correcting codes of distance $d$ (and applies equally well to qudits of any dimension in place of qubits, using generalised Pauli operators).

  • The loss of $d-1$ qubits can be modelled by those qubits being subject to the completely depolarising channel, which in turn can be modeled by those qubits being subject to uniformly random Pauli errors.

  • If the locations of those $d-1$ qubits were unknown, this would be fatal. However, as their locations are known, any pair Pauli errors on $d-1$ qubits can be distinguished from one another, by appeal to the Knill-Laflamme conditions.

  • Therefore, by substituting the erased qubits with qubits in the maximally mixed state and testing for Pauli errors on those $d-1$ qubits specificaly (requiring a different correction procedure than you would use for correcting arbitrary Pauli errors, mind you), you can recover the original state.

Added proof outline
Source Link
Niel de Beaudrap
  • 10.6k
  • 1
  • 21
  • 59

A proof that you need at least 5 qubits (or qudits)

Here is a proof that any single-error correcting (ie., distance 3) quantum error correcting code has at least 5 qubits — and in fact this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting a qudit of dimension $d$.

Any quantum error correcting code which can correct $t$ unknown errors, can also correct up to $2t$ erasure errors (where we simply lose some qubit, or it becomes completely depolarised, or similar) if the locations of the erased qubits are known. [1, Sec. III A]*. So, any quantum error correcting code which can tolerate one Pauli error, can recover from the loss of two qubits.

Now: suppose you have a quantum error correcting code on $n \geqslant 2$ qubits, encoding one qubit against single-qubit errors. Suppose that you give $n-2$ qubits to Alice, and $2$ qubits to Bob: then Alice should be able to recover the original encoded state. If $n<5$, then $2 \geqslant n-2$, so that Bob should also be able to recover the original encoded state — thereby obtaining a clone of Alice's state. As this is ruled out by the No Cloning Theorem, it follows that we must have $n \geqslant 5$ instead.

On correcting erasure errors

* The earliest reference I found for this so far is:

[1] Grassl, Beth, and Pellizzari.
      Codes for the Quantum Erasure Channel.
      Phys. Rev. A 56 (pp. 33–38), 1997.
      [arXiv:quant-ph/9610042]

which is not much long after the Knill–Laflamme conditions were described in [arXiv:quant-ph/9604034] and so plausibly the original proof. The outline is simple:as follows (and applies to qudits of any dimension in place of qubits, using generalised Pauli operators).

  • The loss of $2t$ qubits can be modelled by those qubits being subject to the completely depolarising channel, which in turn can be modeled by those qubits being subject to uniformly random Pauli errors.

  • If the locations of those qubits were unknown, this would be fatal; but as their locations are known, any pair of $2t$-qubit errors on those qubits can be distinguished from one another, by appeal to the Knill-Laflamme conditions on (unknown) $t$-qubit Pauli errors.

  • Therefore, by substituting the erased qubits with qubits in the maximally mixed state and testing for Pauli errors on those two qubits specificaly (requiring a different correction procedure than you would use for correcting arbitrary Pauli errors, mind you), you can recover the original state.

Here is a proof that any single-error correcting (ie., distance 3) quantum error correcting code has at least 5 qubits — and in fact this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting a qudit of dimension $d$.

Any quantum error correcting code which can correct $t$ unknown errors, can also correct up to $2t$ erasure errors (where we simply lose some qubit, or it becomes completely depolarised, or similar) if the locations of the erased qubits are known. [1, Sec. III A]*. So, any quantum error correcting code which can tolerate one Pauli error, can recover from the loss of two qubits.

Now: suppose you have a quantum error correcting code on $n \geqslant 2$ qubits, encoding one qubit against single-qubit errors. Suppose that you give $n-2$ qubits to Alice, and $2$ qubits to Bob: then Alice should be able to recover the original encoded state. If $n<5$, then $2 \geqslant n-2$, so that Bob should also be able to recover the original encoded state — thereby obtaining a clone of Alice's state. As this is ruled out by the No Cloning Theorem, it follows that we must have $n \geqslant 5$ instead.

* The earliest reference I found for this so far is:

[1] Grassl, Beth, and Pellizzari.
      Codes for the Quantum Erasure Channel.
      Phys. Rev. A 56 (pp. 33–38), 1997.
      [arXiv:quant-ph/9610042]

which is not much long after the Knill–Laflamme conditions were described in arXiv:quant-ph/9604034 and so plausibly the original proof. The outline is simple:

A proof that you need at least 5 qubits (or qudits)

Here is a proof that any single-error correcting (ie., distance 3) quantum error correcting code has at least 5 qubits — and in fact this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting a qudit of dimension $d$.

Any quantum error correcting code which can correct $t$ unknown errors, can also correct up to $2t$ erasure errors (where we simply lose some qubit, or it becomes completely depolarised, or similar) if the locations of the erased qubits are known. [1, Sec. III A]*. So, any quantum error correcting code which can tolerate one Pauli error, can recover from the loss of two qubits.

Now: suppose you have a quantum error correcting code on $n \geqslant 2$ qubits, encoding one qubit against single-qubit errors. Suppose that you give $n-2$ qubits to Alice, and $2$ qubits to Bob: then Alice should be able to recover the original encoded state. If $n<5$, then $2 \geqslant n-2$, so that Bob should also be able to recover the original encoded state — thereby obtaining a clone of Alice's state. As this is ruled out by the No Cloning Theorem, it follows that we must have $n \geqslant 5$ instead.

On correcting erasure errors

* The earliest reference I found for this is

[1] Grassl, Beth, and Pellizzari.
      Codes for the Quantum Erasure Channel.
      Phys. Rev. A 56 (pp. 33–38), 1997.
      [arXiv:quant-ph/9610042]

which is not much long after the Knill–Laflamme conditions were described in [arXiv:quant-ph/9604034] and so plausibly the original proof. The outline is as follows (and applies to qudits of any dimension in place of qubits, using generalised Pauli operators).

  • The loss of $2t$ qubits can be modelled by those qubits being subject to the completely depolarising channel, which in turn can be modeled by those qubits being subject to uniformly random Pauli errors.

  • If the locations of those qubits were unknown, this would be fatal; but as their locations are known, any pair of $2t$-qubit errors on those qubits can be distinguished from one another, by appeal to the Knill-Laflamme conditions on (unknown) $t$-qubit Pauli errors.

  • Therefore, by substituting the erased qubits with qubits in the maximally mixed state and testing for Pauli errors on those two qubits specificaly (requiring a different correction procedure than you would use for correcting arbitrary Pauli errors, mind you), you can recover the original state.

Revised for concision and to add references
Source Link
Niel de Beaudrap
  • 10.6k
  • 1
  • 21
  • 59
Loading
Source Link
Niel de Beaudrap
  • 10.6k
  • 1
  • 21
  • 59
Loading