© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2602.08780 · npj Quantum Information

The equivalence of quantum deletion and insertion errors on permutation-invariant codes

Lewis Bulled, Yingkai Ouyang

quant-phSubmitted Feb 9, 2026• Announced Feb 10, 2026• 0 citations• Revised Oct 5, 2026 (v2)

v1 · Feb 9, 2026 v2 · Oct 5, 2026

Abstract

Quantum synchronisation errors are a class of errors that change the number of qubits in a quantum system. The classical error correction of synchronisation errors has been well-studied, including an insertion-deletion equivalence more than a half-century ago, but little progress has been made towards the quantum counterpart since the birth of quantum error correction. We address the longstanding problem of a quantum insertion-deletion equivalence on permutation-invariant codes, detailing the conditions under which such codes are $t$-insertion error-correctable. We extend these conditions to quantum insertion-deletion errors, formulating a more restrictive set of conditions under which permutation-invariant codes are $(t,s)$-insdel error-correctable. For completeness, we extend our approach to qudit errors on qudit permutation-invariant codes. Our work resolves many of the outstanding questions regarding the quantum error correction of synchronisation errors.

DOI: 10.1038/s41534-026-01371-3
Comments: 11 pages, 1 figure

Related papers

Permutation-Invariant Quantum Codes for Deletion Errors

Taro Shibayama, Manabu Hagiwara

This paper presents conditions for constructing permutation-invariant quantum codes for deletion errors and provides a method for constructing them. Our codes include examples of quantum codes that can correct two or more deletion errors, which have not been studied before. We also give examples of quantum codes that can correct both multiple-qubit errors and multiple-deletion errors. We discuss a generalization of the construction of our codes at the end.

arXiv:2102.03015•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•16 citations

Permutation-invariant quantum coding for quantum deletion channels

Yingkai Ouyang

Quantum deletions, which are harder to correct than erasure errors, occur in many realistic settings. It is therefore pertinent to develop quantum coding schemes for quantum deletion channels. To date, not much is known about which explicit quantum error correction codes can combat quantum deletions. We note that any permutation-invariant quantum code that has a distance of$t+1$can correct$t$quantum deletions for any positive integer$t$in both the qubit and the qudit setting. Leveraging on coding properties of permutation-invariant quantum codes under erasure errors, we derive corresponding coding bounds for permutation-invariant quantum codes under quantum deletions. We focus our attention on a specific family of$N$-qubit permutation-invariant quantum codes, which we call shifted gnu codes. The main result of this work is that their encoding and decoding algorithms can be performed in$O(N)$and$O(N^{2})$.

arXiv:2102.02494•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•24 citations

Equivalence of Quantum Single Insertion and Single Deletion Error-Correctabilities, and Construction of Codes and Decoders

Taro Shibayama, Manabu Hagiwara

This article contributes to an unsolved quantum information problem: the equivalence between insertion error-correctability and deletion error-correctability. The solution in Shibayama and Ouyang’s sense is provided in the single-error under the assumption of the purity of quantum codeword states On the other hand, a class of codes that can correct both single deletion and single insertion is provided.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•8 citations

Quantum Insertion-Deletion Channels

Leahy, Janet, Dave Touchette, Penghui Yao

We introduce a model of quantum insertion-deletion (insdel) channels. Insdel channels are meant to represent, for example, synchronization errors arising in data transmission. In the classical setting, they represent a strict generalization of the better-understood corruption error channels, and until recently, had mostly resisted effort toward a similar understanding as their corruption counterparts. They have received considerable attention in recent years. Very recently, Haeupler and Shahrasbi developed a framework, using what they call synchronisation strings, that allows one to turn insdel-type errors into corruption-type errors. These can then be handled by the use of standard error-correcting codes. We show that their framework can be extended to the quantum setting, providing a way to turn quantum insdel errors into quantum corruption errors, which can be handled with standard quantum error-correcting codes.

arXiv:1901.00984•Jan 4, 2019•9 citations

Permutation-invariant codes: a numerical study and qudit constructions

Liam J. Bond, Jiří Minář, Māris Ozols +2 more

We investigate Permutation-Invariant (PI) quantum error-correcting codes encoding a logical qudit of dimension $\mathrm{d}_\mathrm{L}$ in PI states using physical qudits of dimension $\mathrm{d}_\mathrm{P}$. We extend the Knill--Laflamme (KL) conditions for $d-1$ deletion errors from qubits to qudits and investigate numerically both qubit ($\mathrm{d}_\mathrm{L} = \mathrm{d}_\mathrm{P} = 2$) and qudit ($\mathrm{d}_\mathrm{L} > 2$ or $\mathrm{d}_\mathrm{P} > 2$) PI codes. We analyze the scaling of the block length $n$ in terms of the code distance $d$, and compare to existing families of PI codes due to Ouyang, Aydin--Alekseyev--Barg (AAB) and Pollatsek--Ruskai (PR). Our three main findings are: (i) We conjecture that qubit PI codes correcting up to $d-1$ deletion errors have block length $n(d) \geq (3d^2 + 1) / 4$, which implies an upper bound $d \leq \sqrt{12n-3}/3$ on their code distance, and that PR codes can saturate this bound. (ii) For qudit PI codes encoding a single qudit we numerically observe that increasing $\mathrm{d}_\mathrm{P}$ results in $n$ monotonically decreasing and approaching the quantum Singleton bound $n(d) \geq 2d-1$. (iii) We propose a semi-analytic extension of the qubit AAB construction to qudits that finds explicit solutions by solving a linear program. Our results therefore provide key insights into lower bounds on the block length scaling of both qubit and qudit PI codes, and demonstrate the benefit of increased physical local dimension in the context of PI codes.

quant-pharXiv:2603.10981•Mar 12, 2026•0 citations

A theory of quantum error correction for permutation-invariant codes

Yingkai Ouyang, Gavin K. Brennen

We present for the first time a general theory of error correction for permutation invariant (PI) codes. Using representation theory of the symmetric group we construct efficient algorithms that can correct any correctible error on any PI code. These algorithms involve measurements of total angular momentum, quantum Schur transforms or logical state teleportations, and geometric phase gates. For erasure errors, or more generally deletion errors, on certain PI codes, we give a simpler quantum error correction algorithm.

quant-pharXiv:2602.13638•Feb 17, 2026•0 citations

Quantum synchronisation errors are a class of errors that change the number of qubits in a quantum system. The classical error correction of synchronisation errors has been well-studied, including an insertion-deletion equivalence more than a half-century ago, but little progress has been made towards the quantum counterpart since the birth of quantum error correction. We address the longstanding problem of a quantum insertion-deletion equivalence on permutation-invariant codes, detailing the conditions under which such codes are

t

-insertion error-correctable. We extend these conditions to quantum insertion-deletion errors, formulating a more restrictive set of conditions under which permutation-invariant codes are

(t,s)

-insdel error-correctable. For completeness, we extend our approach to qudit errors on qudit permutation-invariant codes. Our work resolves many of the outstanding questions regarding the quantum error correction of synchronisation errors.

Quantum deletions, which are harder to correct than erasure errors, occur in many realistic settings. It is therefore pertinent to develop quantum coding schemes for quantum deletion channels. To date, not much is known about which explicit quantum error correction codes can combat quantum deletions. We note that any permutation-invariant quantum code that has a distance of

t

can correct

t

quantum deletions for any positive integer

t

in both the qubit and the qudit setting. Leveraging on coding properties of permutation-invariant quantum codes under erasure errors, we derive corresponding coding bounds for permutation-invariant quantum codes under quantum deletions. We focus our attention on a specific family of

N

-qubit permutation-invariant quantum codes, which we call shifted gnu codes. The main result of this work is that their encoding and decoding algorithms can be performed in

O(N)

and

O(N^{2})

.

We introduce a model of quantum insertion-deletion (insdel) channels. Insdel channels are meant to represent, for example, synchronization errors arising in data transmission. In the classical setting, they represent a strict generalization of the better-understood corruption error channels, and until recently, had mostly resisted effort toward a similar understanding as their corruption counterparts. They have received considerable attention in recent years. Very recently, Haeupler and Shahrasbi developed a framework, using what they call synchronisation strings, that allows one to turn insdel-type errors into corruption-type errors. These can then be handled by the use of standard error-correcting codes. We show that their framework can be extended to the quantum setting, providing a way to turn quantum insdel errors into quantum corruption errors, which can be handled with standard quantum error-correcting codes.

We investigate Permutation-Invariant (PI) quantum error-correcting codes encoding a logical qudit of dimension

\mathrm{d}_\mathrm{L}

in PI states using physical qudits of dimension

\mathrm{d}_\mathrm{P}

. We extend the Knill--Laflamme (KL) conditions for

d-1

deletion errors from qubits to qudits and investigate numerically both qubit (

\mathrm{d}_\mathrm{L} = \mathrm{d}_\mathrm{P} = 2

) and qudit (

\mathrm{d}_\mathrm{L} > 2

or

\mathrm{d}_\mathrm{P} > 2

) PI codes. We analyze the scaling of the block length

d-1

in terms of the code distance

d

, and compare to existing families of PI codes due to Ouyang, Aydin--Alekseyev--Barg (AAB) and Pollatsek--Ruskai (PR). Our three main findings are: (i) We conjecture that qubit PI codes correcting up to

d-1

deletion errors have block length

n(d) \geq (3d^2 + 1) / 4

, which implies an upper bound

d \leq \sqrt{12n-3}/3

on their code distance, and that PR codes can saturate this bound. (ii) For qudit PI codes encoding a single qudit we numerically observe that increasing

\mathrm{d}_\mathrm{P}

results in

n

monotonically decreasing and approaching the quantum Singleton bound

n(d) \geq 2d-1

. (iii) We propose a semi-analytic extension of the qubit AAB construction to qudits that finds explicit solutions by solving a linear program. Our results therefore provide key insights into lower bounds on the block length scaling of both qubit and qudit PI codes, and demonstrate the benefit of increased physical local dimension in the context of PI codes.

We present for the first time a general theory of error correction for permutation invariant (PI) codes. Using representation theory of the symmetric group we construct efficient algorithms that can correct any correctible error on any PI code. These algorithms involve measurements of total angular momentum, quantum Schur transforms or logical state teleportations, and geometric phase gates. For erasure errors, or more generally deletion errors, on certain PI codes, we give a simpler quantum error correction algorithm.