# Concatenating quantum error correcting codes with decoherence-free
subspaces, and vice versa

Nihar Ranjan Dash<EMAIL_ADDRESS>Indian Institute of Technology Jodhpur,
Rajasthan 342030, India  Sanjoy Dutta  Poornaprajna Institute of Scientific
Research (PPISR), Bidalur post, Devanahalli, Bengaluru 562164, India  R.
Srikanth<EMAIL_ADDRESS>Poornaprajna Institute of Scientific Research
(PPISR), Bidalur post, Devanahalli, Bengaluru 562164, India  Subhashish
Banerjee<EMAIL_ADDRESS>Indian Institute of Technology Jodhpur,
Rajasthan 342030, India

###### Abstract

Quantum error correcting codes (QECCs) and decoherence-free subspace (DFS)
codes provide active and passive means, respectively, to address certain
errors that arise during quantum computation. The latter technique is suitable
to correct correlated errors with certain symmetries, whilst the former to
correct independent errors. The concatenation of a QECC and DFS code results
in a degenerate code that splits into actively and passively correcting parts,
with the degeneracy impacting either part, leading to degenerate errors as
well as degenerate stabilizers. The concatenation of the two types of code can
aid universal fault-tolerant quantum computation when a mix of correlated and
independent errors is encountered. In particular, we show that for
sufficiently strongly correlated errors, the concatenation with the DFS as the
inner code provides better entanglement fidelity, whereas for sufficiently
independent errors, the concatenation with QECC as the inner code is
preferable. As illustrative examples, we examine in detail the concatenation
of a 2-qubit DFS code and a 3-qubit repetition code or 5-qubit Knill-Laflamme
code, under independent and correlated errors.

##  I Introduction

The loss of quantum coherence, aka the decoherence process, is the biggest
obstacle to realizing practical quantum computation and communication [1].
Errors also arise because of imperfections and faults in the quantum
communication system or computation circuit. These errors, due to decoherence
and device imperfections, reduce the fidelity and reliability of quantum
operations [2]. To overcome these obstacles, there is a variety of methods
employed, among them quantum error correcting codes (QECCs) [3, 4, 5, 6],
decoherence-free subspace (DFS) [7, 8, 9], dynamic decoupling (DD) [10], and
error mitigation [11, 12]. QECCs offer an active method of intervention to
protect quantum information from a wide variety of errors– including, most
generally, independent errors– by correcting them when they occur. These codes
can also be used to characterize quantum dynamics [13, 14]. DFS is a passive
scheme to combat correlated errors and preserves the coherence of the quantum
state by encoding information in subspaces that are immune to certain types of
noise by virtue of symmetries in the dynamics. An interesting example of DFS
arises in the study of quantum memory for photons, where a collective
reservoir interaction can happen for the cluster of atoms that make up the
memory. This motivates the construction of a two-dimensional decoherence-free
quantum memory protected from collective errors [15]. Note that this is an
extreme case, and in the other extreme, the atoms may be subjected to
independent errors.

The practice of concatenating block codes is extensively employed in the field
of quantum information science and serves as a crucial element in nearly all
fault-tolerant strategies [16, 17]. The basic concatenated code, even in the
classical context [18], comprises an outer and an inner code. More generally,
concatenation of codes is accomplished by iterative encoding of blocks of
qubits in different levels. Embedding an inner code in an outer code decreases
the effective error probability of the concatenated code, making its data
qubits more reliable [19]. The establishment of the accuracy threshold theorem
[20, 21, 22] relies substantially on these concatenated codes. There can be
multiple layers in the concatenated quantum code [23, 24, 25], where the
physical space of one code behaves as logical space for the next code. One can
construct an efficient and robust error correction scheme using this
hierarchical structure.

Whilst recursive concatenation of the same QECC or different QECCs has been
extensively studied [24, 26, 25, 27], recently a few authors have explored
hybrid concatenation schemes, such as DD and QECC [28, 29], DD and DFS [30,
31], as well as QECC and DFS [32]. The nature of errors in the given quantum
information processor, for example whether the noise is “bursty” or
independent, will determine the codes to concatenate as well the order in
which they may be concatenated [33]. Such a concatenated setup, together with
the availability of transversal gate operations [34, 35] enables universal
fault-tolerant quantum computation. In particular, the combination of QECC and
DFS can facilitate fault-tolerance [36] in the presence of correlated errors
[37, 38, 39]. The experimental implementation of the hybrid concatenation of
active and passive methods for fighting errors [36] paves the way for
practical quantum computation in the presence of coherent errors [40]. A
specific category of hybrid DFS-QECC codes has been developed to effectively
address spontaneous emission errors and collective dephasing specifically
intended to be compatible with the quantum optical and topological
implementation of quantum dots in cavities and trapped ions [41, 42]. The
efficiency of concatenated DFS-QECC codes is contingent upon the use of a
practical set of universal quantum gates that can maintain states exclusively
within the DFS. It also depends on the fault-tolerant execution of DFS state
preparation and decoding processes [9].

The present work focuses on the two-layered (and, in general, multi-layered)
protection based on the concatenation of QECC and DFS, in particular
comparatively studying the concatenation of DFS with QECC layer and vice
versa. The need for studying such a hybrid concatenation scheme naturally
arises when both correlated and independent errors occur simultaneously in the
setup of a quantum computer. A basic situation of this sort is depicted in
Figure 1. Here each row of qubits may represent for example ions in a linear
ion trap, which are subject to correlated errors, for which a DFS is suitable.
The full quantum information processor consists of an array of such rows, such
that the ions along the column are coupled with independent reservoirs and
hence subject to independent errors. In such a case as this, a QECC may be
suitable. For fault-tolerant computation, we would require a concatenation of
QECC and DFS. The question then hinges on the order of concatenating the two:
whether QECC with DFS or vice versa. It is the issue that this work studies,
to determine situations where one scheme or the other may be more advantageous
according to different criteria.

The remaining article is organized as follows. In Section II, we present
preliminaries on the decoherence-free subspaces (DFSs), quantum error
correcting codes (QECCs), and the construction of concatenated codes. In
Section III, we study in detail the concatenation of two or more codes, both
in the independent and correlated error models. Specifically, we discuss two
schemes of concatenating a QECC and DFS, one with the latter as the inner
layer and the former as the outer layer (QD code), and vice versa (DQ code).
Specific examples of concatenated codes, 6-qubit codes concatenating a
$[[3,1]]$ repetition QECC and $[[2,1]]$ DFS, and 10-qubit codes concatenating
a $[[5,1]]$ Knill-Laflamme QECC and $[[2,1]]$ DFS, are studied in Sections IV
and V, respectively. Passivity and degeneracy of the DFS are reflected
respectively as the passive part of the concatenated code and the degeneracy
in the passive and active parts of the concatenated code. In particular the
degeneracy has a two-fold manifestation: (a) as degenerate equivalence classes
of correctable errors (Sections IV and V, covering the $[[6,1]]$ and
$[[10,1]]$ codes); and (b) as the corresponding stabilizers (Section VI) of
the concatenated code. Finally, we conclude in Section VII.

Figure 1: Independent-correlated hybrid error model: Correlated and
independent noise in an array of qubits constituting a quantum computer such
as an optical lattice or trapped ions in a cavity QED setup: the qubits along
a row are subject to correlated noise, described a dependent error model;
qubits along a column are subject to an independent error model.

##  II Preliminaries

###  II.1 Decoherence Free Subspace (DFS)

DFSs are the subspaces that act as quiet corners in the total Hilbert space
shielded from errors by a certain symmetry in the system’s interaction with
the environment [43, 44, 45]. By encoding quantum information in these
subspaces, the coherence of the quantum system can be preserved for an
extended period. The concatenation of DFS and QECC gives an additional layer
of protection from hybrid errors, that have elements of symmetry and
independence.

The Liouville equation is given by

$\displaystyle\mathcal{L}[\rho]=\dot{\rho},$ (1)

where $\mathcal{L}$ is the Liouvillian. A DFS constitutes the degenerate
subspace obtained as a stationary solution to Eq. (1). States in this subspace
are called decoherence-free (DF) states.

For simplicity, we consider a two-qubit system affected by the collective bit-
flip error. The error group is {$II$, $XX$}. Since this group is Abelian, all
irreducible representations (irreps) belonging to it are one-dimensional [43].
It is result in group theory that the number of irreps within a group is
equivalent to the number of classes associated with that group [46].

As there are two classes in this group, $II$ and $XX$, the number of the
irreps of this group is equal to two, namely $\Gamma^{+}\equiv\\{1,1\\}$ and
$\Gamma^{-}\equiv\\{1,-1\\}$. The character is obtained by calculating the
trace of the irrep. Since the square of the two elements in the group is
identity, thus the character of the irreps can only take $\pm 1$. The DFS can
be constructed with the action of a projection operator belonging to one-
dimensional irrep on the initial states. Here there are two irreps, and
correspond to two DFSs, given by:

$\displaystyle\Gamma^{+}$
$\displaystyle\equiv\textrm{span}\\{\ket{00}+\ket{11},\ket{01}+\ket{10}\\},$
$\displaystyle\Gamma^{-}$
$\displaystyle\equiv\textrm{span}\\{\ket{00}-\ket{11},\ket{01}-\ket{10}\\}.$
(2)

The two corresponding operators which project to the given DFS are:

$\displaystyle P_{\pm}=\frac{1}{2}(II\pm XX).$ (3)

For example, we can define our logical DF code states for $\Gamma^{+}$ as
(apart from a normalization factor):

$\displaystyle\ket{0}_{D}$ $\displaystyle=\ket{00}+\ket{11},$
$\displaystyle\ket{1}_{D}$ $\displaystyle=\ket{01}+\ket{10}.$ (4)

The DFS spanned by these states is denoted $\mathcal{H}_{DFS}$, and is
orthogonal and complementary to the subspace $\mathcal{H}_{DFS}^{\perp}$,
spanned by the DFS states defined by $\Gamma^{-}$, namely:

$\displaystyle\ket{2}_{D}$ $\displaystyle=\ket{00}-\ket{11},$
$\displaystyle\ket{3}_{D}$ $\displaystyle=\ket{01}-\ket{10}.$ (5)

The two DFSs are

$\displaystyle\mathcal{H}_{DFS}\equiv\textrm{span}\\{\ket{0}_{D},\ket{1}_{D}\\},$
$\displaystyle\mathcal{H}_{DFS}^{\perp}\equiv\textrm{span}\\{\ket{2}_{D},\ket{3}_{D}\\}.$
(6)

Each of these subspaces in Eq. (6) serves as a bonafide DFS. The superposition
of DF states from the same irrep is also a DF state, that is

$\displaystyle\ket{\psi}_{D}$
$\displaystyle=\alpha\ket{0}_{D}+\beta\ket{1}_{D},$ (7)

with $|\alpha|^{2}+|\beta|^{2}=1$, is a DF state. But one can not take states
from different irrep to make DF state.

It may be noted that the projector of an irrep acts as an identity operator
for the DF states corresponding to that irrep, while those DF states are
annihilated by the projectors corresponding to a different irrep.

###  II.2 Quantum Error Correcting Codes

The QECCs constitute a major approach for combating errors [47]. In the
quantum error correction scheme, quantum information is encoded in a larger
Hilbert space by adding redundancy, such that errors only affect the
redundancy. The error correction process involves the encoding, detection, and
recovery process. Generally, a QECC is a set of orthogonal states or quantum
codewords represented by $[[n,k,d]]$ code, where $k$ logical qubits are
encoded into $n$ physical qubits with the code distance $d$.

Consider the codewords $\ket{\psi_{i}}$ for the code $\mathcal{C}$, the
necessary and sufficient conditions for the quantum error-correcting codes are
[5, 48]:

$\displaystyle\bra{\psi_{i}}E_{m}^{{\dagger}}E_{n}\ket{\psi_{j}}$
$\displaystyle=0,(i\neq j)$
$\displaystyle\bra{\psi_{i}}E_{m}^{{\dagger}}E_{n}\ket{\psi_{i}}$
$\displaystyle=\bra{\psi_{j}}E_{m}^{{\dagger}}E_{n}\ket{\psi_{j}},$ (8)

for $\bra{\psi_{i}}\ket{\psi_{j}}=0$. Here $E_{m}$ and $E_{n}$ are the error
operator elements from the correctable errors. Instead of the codewords, the
QECC can be represented by the minimal representation with the help of
stabilizer generators.

The set of stabilizer generators $S_{i}$ is a minimal set that can generate
all the elements in the stabilizer $\mathcal{S}$. The action of the stabilizer
generators $S_{i}$ on the codewords is written as,

$\displaystyle S_{i}\ket{\psi_{i}}=\ket{\psi_{i}}.$ (9)

The normalizer $\mathcal{N}$ is a subset of the set of Pauli operators
$\mathcal{P}$ such that the stabilizer is closed under conjugation by the
normalizer elements,

$\displaystyle NSN^{{\dagger}}\in\mathcal{S},$ (10)

with $N\in\mathcal{N}\subset\mathcal{P}$. The centralizer $\mathbb{C}$ is the
set of Pauli operators $\mathcal{P}$ that commute with stabilizer elements:

$\displaystyle CS$ $\displaystyle=SC,$ $\displaystyle\mathbb{C}$
$\displaystyle=\\{C\colon C\in\mathcal{P},\forall S,[S,C]=0\\}.$ (11)

###  II.3 Construction of Concatenated Codes

For a simple exposition of the concatenated quantum error correcting code
construction, we restrict at first to two levels of concatenation. Consider
two quantum codes– be they QECCs or DFSs or one of both– for overcoming
errors: $\mathcal{C}_{o}$, an outer $[[n_{o},k_{o}]]$ code, which encodes
$k_{o}$ logical qubits into $n_{o}$ physical qubits, and $\mathcal{C}_{i}$, an
inner $[[n_{i},k_{i}]]$ code which encodes $k_{i}$ logical qubits into $n_{i}$
physical qubits. There are two procedures for the construction of the
concatenated quantum codes [19], depending on whether $n_{o}$ is divisible by
$k_{i}$, or not.

The following procedure is suitable when $n_{o}$ is divisible by $k_{i}$.

  1. 1.

Encode of $k_{o}$ logical qubits into $n_{o}$ physical qubits.

  2. 2.

Since $n_{o}$ is divisible by $k_{i}$, $n_{o}$ qubits will be partitioned into
$\frac{n_{o}}{k_{i}}$ blocks with $n_{i}$ qubits in each block.

  3. 3.

This procedure results in a concatenated code (CC) given by:

$[[n_{CC},k_{CC}]]=[[\frac{n_{o}n_{i}}{k_{i}},k_{o}]].$ (12)

In the case that $n_{o}$ is not divisible by $k_{i}$ the following procedure
is employed:

  1. 1.

Input a quantum string of length $k_{i}k_{o}$ qubits. Encode each block of
$k_{o}$ qubits into $n_{o}$ qubits using code $\mathcal{C}_{o}$. This results
in a string of length $n_{o}k_{i}$, i.e., $n_{o}$ blocks with $k_{i}$ qubits
in each block.

  2. 2.

Encode $k_{i}$ qubits in each block into $n_{i}$ qubits, resulting in
$n_{o}n_{i}$ qubits.

  3. 3.

This procedure results in a

$[[n_{CC},k_{CC}]]=[[n_{o}n_{i},k_{o}k_{i}]].$ (13)

In the present work with a hybrid scenario, the outer code can be a QECC and
the inner code a DFS, or vice versa.

##  III Two schemes for hybrid two-level concatenation

In this work, we consider two-level code concatenation, where one layer
employs a QECC and the other a DFS. The encoding that is first applied (or,
last to be decoded) is the outer layer, and the encoding that is applied last
(or, decoded first) is the inner layer. We consider two orderings of
concatenation: QECC being the outer code, and DFS the inner one (QD code), and
conversely, DFS being the outer code, and QECC the inner one (DQ code).

Throughout the paper, we will denote a $[[n,k]]$ code by $[[n,k]]_{Q}$ if it
embeds $k$ logical qubits in $n$ physical qubits of a QECC codeword, and by
$[[n,k]]_{D}$ if it embeds $k$ logical qubits in $n$ physical qubits of a DFS.

It is natural to consider correlated errors when DFS is used. We now consider
a restricted correlated noise model, a hybrid independent-correlated error
model, where correlation across qubits is allowed within the blocks of the
inmost layer of concatenation, but there are no cross-block correlations [24].
This is more general than the independent error model, but more restricted
than the most general correlated noise.

Let the probability of the single qubit without error and with errors be given
by:

$\displaystyle p_{0}$ $\displaystyle=1-p,$ $\displaystyle p_{1}$
$\displaystyle=p.$ (14)

Within each block, the conditional probabilities are expressed as

$\displaystyle p_{(i|j)}=(1-\mu)p_{i}+\mu\delta_{i,j},$ (15)

where $i,j={0,1}$, and $\mu$ is the strength of the correlation. Eq. (15)
implies that

$\displaystyle p_{(0|0)}$ $\displaystyle=(1-\mu)(1-p)+\mu,$ (16a)
$\displaystyle p_{(0|1)}$ $\displaystyle=(1-\mu)(1-p),$ (16b) $\displaystyle
p_{(1|0)}$ $\displaystyle=(1-\mu)p,$ (16c) $\displaystyle p_{(1|1)}$
$\displaystyle=(1-\mu)p+\mu.$ (16d)

The following result gives the recursion relation that determines the failure
probability $p_{F}^{\rm CC}$ of the concatenated code in this model.

######  Theorem 1.

Let $\mathcal{C}_{0},\mathcal{C}_{1},\mathcal{C}_{2},\cdots\mathcal{C}_{t}$
denote a sequence of $(t+1)$ codes that are concatenated, with 0 labelling the
outermost and $t$ the inmost. The errors are assumed to be subject to the
independent-correlated error model characterized by the parameters $p,\mu$.
Denoting the stand-alone failure probability of the code labelled
$\mathcal{C}_{j}$ by $p_{F}^{j}(\mu,p)$, the failure probability for the
concatenated code is

$p_{F}^{\rm
CC}(\mu,p)=p_{F}^{(0)}\left[0,p_{F}^{(1)}\left[0,\cdots[p_{F}^{(t-1)}[0,p_{F}^{(t)}(\mu,p)]]{\cdots}\right]\right].$
(17)

###### Proof.

For $1\leq j\leq t-1$, given the block failure probability $p_{F}^{j}$ of each
block at level $j$, this error is propagated to the next outer level $(j-1)$
as the block failure probability given by
$p_{F}^{(j-1)}[\mu_{j},p_{F}^{(j)}]\equiv p_{F}^{(j-1)}[0,p_{F}^{(j)}]$, the
equality following from the assumption of absence of cross-block correlation.
Proceeding thus recursively, we reach the $(t-1)$th layer for which the next
inner layer is the physical qubits: thus
$p_{F}^{(t-1)}=p_{F}^{(t-1)}[0,p_{F}^{(t)}]\equiv
p_{F}^{t-1}[0,p_{F}^{(t)}(\mu,p)]$. It follows that the error in the $t$-layer
concatenated code is given by $p_{F}^{CC}(p)$ in Eq. (17). ∎

As an illustration of Theorem 17, consider the case of concatenating two
codes, $\mathcal{C}_{o}$ and $\mathcal{C}_{i}$, denoting the outer and inner
codes, with failure probabilities $p_{F}^{(o)}(\mu,p)$ and
$p_{F}^{(i)}(\mu,p)$. Then the failure probability of the concatenated scheme
in the hybrid independent-correlated model is

$p_{F}^{\rm CC}(\mu,p)=p_{F}^{(o)}[0,p_{F}^{(i)}(\mu,p)].$ (18)

The follow Section discusses the two-level concatenation of a $[[2,1]]$ DFS
code (Eq. (4)) and a $[[3,1]]$ bit-flip QECC or a $[[5,1]]$ QECC.

If cross-block correlations are allowed, then the simplest scenario is one
where each level has an independent correlation parameter $\mu_{j}$ ($j\neq
t$) related to possible correlations that arise during decoding. If instead,
we generalize by simply removing the prohibition on cross-block correlations,
then the dependence of the correlation parameter at the $j$th level on the
basic parameters $\mu,p$ can in general be involved, and not lead to a simple
recursion formula in the manner of Eq. (17).

To see this, consider a [[6,1]] code obtained with a $[[3,1]]$ bit-flip code
QECC as outer layer and the above $[[2,1]]$ DFS as the inner layer. For this
QD configuration the blocks are $(1a,1b),(2a,2b),(3a,3b)$. We find the cross-
block correlation to be:

$\displaystyle p_{(\underline{0}_{1a1b}|\underline{0}_{2a2b})}$
$\displaystyle=p_{(II\vee XX|II\vee XX)}=\frac{p_{(II_{1a1b}\vee
XX_{1a1b}\wedge II_{2a2b}\vee XX_{2a2b})}}{p_{(II_{2a2b}\vee XX_{2a2b})}}$
$\displaystyle=\frac{1-(1-p)p(1-\mu)\bigg{[}4-4p(-1+\mu)^{2}+4p^{2}(-1+\mu)^{2}+(-1+\mu)\mu\bigg{]}}{[(1-\mu)(1-p)+\mu](1-p)+[(1-\mu)p+\mu]p},$
(19)

which clearly does not conform to a simple recursive formula along the lines
of Eq. (16a). For the remaining paper, we restrict to the hybrid model where
we assume vanishing cross-block correlations.

We quantify the performance of the concatenated code using entanglement
fidelity [49, 50], which in the present context can be expressed by the
formula [19, 51]

$F_{e}=1-p_{F}^{\rm CC}(\mu,p),$ (20)

where $p$ is the error probability on an individual qubit.

In the following two Sections, we study examples of concatenated codes, and
their performance under independent and independent-correlated noise.

We recollect that in a standalone code, errors $E_{a}$ and $E_{b}$ are
degenerate if $E_{a}E_{b}\in\mathcal{S}$, where $\mathcal{S}$ is the
stabilizer. Equivalently,
$\forall_{\ket{w}\in\mathcal{C}}E_{a}\ket{w}=E_{b}\ket{w}$. The DFS code has
degeneracy by definition, and this is inherited into the concatenation that it
forms a part of. In the concatenation we consider, the above degeneracy
condition must hold for the QECC, irrespective of whether it is the outer or
inner code.

##  IV The [[6,1]] QD and DQ codes

Consider the concatenation of the $[[3,1]]_{Q}$ bit flip code and the
$[[2,1]]_{D}$ DFS code (Eq. 4). In previous works, either the QD or DQ schemes
have been considered individually [37, 39, 38] but not comparatively, as we do
here.

(a) QD configuration

(b) DQ configuration

Figure 2: $[[6,1]]$ block structure: the dark orange balls represent the outer
code blocks, whilst the blue balls represent the inner code qubits.

First we consider the QD scheme, where the former is the outer and the latter
is the inner code (Fig. 2(a)). By Eq. (12), this results in the concatenated
$[[6,1]]_{QD}$ code, for which the logical codewords are

$\displaystyle\ket{0}$
$\displaystyle\longrightarrow\ket{0}_{D}\ket{0}_{D}\ket{0}_{D}=\frac{1}{2\sqrt{2}}(\ket{00}+\ket{11})^{\otimes
3},$ $\displaystyle\ket{1}$
$\displaystyle\longrightarrow\ket{1}_{D}\ket{1}_{D}\ket{1}_{D}=\frac{1}{2\sqrt{2}}(\ket{01}+\ket{10})^{\otimes
3}.$ (21)

The circuits for encoding in the [[6,1]] QD or DQ states (Fig. 2) are given in
Figs. 3 and 4, respectively.

$\ket{\reg_{\idx}}$$\mathcal{E}$$\mathcal{E}$$\mathcal{E}$$\mathcal{E}$$\mathcal{E}$$\mathcal{E}$
Figure 3: Circuit to implement the [[6,1]] QD code.

In the DQ scheme, we concatenate in the reverse order: the $[[3,1]]_{Q}$ bit
flip code as inner code with the $[[2,1]]_{D}$ DFS code as outer code (Fig.
2(b)). By Eq. (12), this results in the concatenated $[[6,1]]_{DQ}$ code, with
the logical codewords:

$\displaystyle\ket{0}$
$\displaystyle\longrightarrow\ket{00}_{Q}+\ket{11}_{Q}=\frac{1}{\sqrt{2}}\ket{000}^{\otimes
2}+\ket{111}^{\otimes 2},$ $\displaystyle\ket{1}$
$\displaystyle\longrightarrow\ket{01}_{Q}+\ket{10}_{Q}=\frac{1}{\sqrt{2}}\ket{000111}+\ket{111000}.$
(22)

$\ket{\reg_{\idx}}$$\mathcal{E}$$\mathcal{E}$$\mathcal{E}$$\mathcal{E}$$\mathcal{E}$$\mathcal{E}$
Figure 4: Circuit to implement the [[6,1]] DQ code.

###  IV.1 Equivalence classes of correctable Pauli errors

For the QD scheme, we note that the errors protected at the inner layer are:

$\displaystyle\\{II,XX\\}^{\otimes 3},$ (23)

and the errors protected at the outer layer are:

$\displaystyle\\{I_{D}I_{D}I_{D},X_{D}I_{D}I_{D},I_{D}X_{D}I_{D},I_{D}I_{D}X_{D}\\},$
(24)

where the subscript $D$ refers to error operations of the DFS. For the
$[[2,1]]_{D}$ code, logical bit flip is defined as
$X_{D}:\ket{0}_{D}\longleftrightarrow\ket{1}_{D}$. Letting $I_{D}$ represent
any of correctable errors, and $X_{D}$, $Y_{D}$, and $Z_{D}$ represent the
logical operators for the $[[2,1]]_{D}$ code, we have

$\displaystyle I_{D}$ $\displaystyle\rightarrow II,XX,$ $\displaystyle X_{D}$
$\displaystyle\rightarrow XI,IX,$ $\displaystyle Y_{D}$
$\displaystyle\rightarrow YZ,ZY,$ $\displaystyle Z_{D}$
$\displaystyle\rightarrow ZZ.$ (25)

Here we note that first three operations have multiplicity, which the last one
lacks.

Each block’s error in the outer code, namely $I_{D}$ or $X_{D}$, in Eq. (24),
is represented by a multiplicity (actually, 2) of realizations in the inner
code, given by Eq. (25). Thus, each of the four correctable errors in Eq. (24)
has $2^{3}=8$ degenerate realizations. Thus there are 32 errors that the
$[[6,1]]_{QD}$ code can correct, and these can be arranged in an equivalence
class of 4 sets such that all 8 elements within a given set are mutually
degenerate, given by:

$\displaystyle E_{equiv}^{[[6,1]]_{QD}}$
$\displaystyle\equiv\Bigg{\\{}\bigg{\\{}IIIIII,IIIIXX,IIXXII,IIXXXX,XXXXXX,$
$\displaystyle XXIIII,XXIIXX,XXXXII\bigg{\\}},\bigg{\\{}XIIIII,XIIIXX,$
$\displaystyle XIXXII,XIXXXX,IXIIII,IXIIXX,IXXXII,$ $\displaystyle
IXXXXX\bigg{\\}},\bigg{\\{}IIXIII,IIXIXX,IIIXII,IIIXXX,$ $\displaystyle
XXXIII,XXXIXX,XXIXII,XXIXXX\bigg{\\}},\bigg{\\{}IIIIXI,$ $\displaystyle
IIIIIX,IIXXXI,IIXXIX,XXIIXI,XXIIIX,$ $\displaystyle
XXXXXI,XXXXIX\bigg{\\}}\Bigg{\\}}.$ (26)

The four mutually degenerate sets in this error degeneracy equivalence class
correspond to four sets having eight degenerate elements each. The QD and DQ
codes inherently possess an element of passive error correction inherited from
the DFS. Here, this is reflected in the fact that elements in the first set of
the equivalence class are all passively correctable. Their provenance can be
attributed to the fact that all these errors correspond to the identity
operation ($I_{D}I_{D}I_{D}$) on the outer QECC layer. Structurally, we expect
that these error operators are identical to eight stabilizers of the
concatenated code, and thus commute with remaining stabilizers. We will find
that these eight stabilizers (or, their three generators) play a passive role
in that they don’t require to be measured, but formally arise as a result of
the concatenation.

By contrast, with regard to the DQ scheme (Fig. 2(b)), the errors protected by
the outer DFS layer:

$\displaystyle\\{I_{Q}I_{Q},X_{Q}X_{Q}\\},$ (27)

where the subscript $Q$ refers to the error operations of the QECC. There are
16 correctable errors that yield the first term in Eq. (27) when the inner
layer is decoded, namely

$\displaystyle\\{XII,IXI,IIX,III\\}^{\otimes 2},$ (28)

each of these has a counterpart corresponding to the second term in Eq. (27),
obtained by applying the logical NOT operation on both blocks, i.e., $XXXXXX$.
Thus for example, $XIIIXI\xrightarrow{XXXXXX}IXXXIX$.

Accordingly, we have 16 sets of 2 errors each, yielding 32 correctable errors
in all, which can be arranged in the following equivalence class:

$\displaystyle E_{equiv}^{[[6,1]]_{DQ}}$
$\displaystyle\equiv\Bigg{\\{}\bigg{\\{}XIIXII,IXXIXX\bigg{\\}},\bigg{\\{}XIIIXI,IXXXIX\bigg{\\}},$
$\displaystyle\bigg{\\{}XIIIIX,IXXXXI\bigg{\\}},\bigg{\\{}XIIIII,IXXXXX\bigg{\\}},$
$\displaystyle\bigg{\\{}IIXXII,XXIIXX\bigg{\\}},\bigg{\\{}IIXIXI,XXIXIX\bigg{\\}},$
$\displaystyle\bigg{\\{}IIXIIX,XXIXXI\bigg{\\}},\bigg{\\{}IIXIII,XXIXXX\bigg{\\}},$
$\displaystyle\bigg{\\{}IXIXII,XIXIXX\bigg{\\}},\bigg{\\{}IXIIXI,XIXXIX\bigg{\\}},$
$\displaystyle\bigg{\\{}IXIIIX,XIXXXI\bigg{\\}},\bigg{\\{}IXIIII,XIXXXX\bigg{\\}},$
$\displaystyle\bigg{\\{}IIIXII,XXXIXX\bigg{\\}},\bigg{\\{}IIIIXI,XXXXIX\bigg{\\}},$
$\displaystyle\bigg{\\{}IIIIIX,XXXXXI\bigg{\\}},\bigg{\\{}IIIIII,XXXXXX\bigg{\\}}\Bigg{\\}}.$
(29)

The $16$ mutually degenerate sets in the equivalence class correspond to $16$
sets having 2 degenerate elements. As in the QD case, passively correctable
errors arise here too. In this example, they correspond to the last set in Eq.
(29). Their provenance can be attributed to the fact that they lead without
syndrome generation to the DFS correctable errors $I_{Q}I_{Q},X_{Q}X_{Q}$ in
the outer layer. Here again, the passively correctable errors can be shown to
coincide with passive stabilizers.

The Hamming bound [52] on a nondegenerate QECC requires that
$n-k\geq\log_{2}(\\#{\rm~{}correctable~{}errors})$. Thus we can define the
metric of Hamming efficiency as a rough guide on how efficiently the
correction works:

$\varphi=\frac{\log_{2}\left(\\#{\rm~{}correctable~{}errors}\right)}{n-k}.$
(30)

From Eq. (26) and (29), we have $\|E_{equiv}^{[[6,1]]_{QD}}\|=4\times 8=32$,
and $\|E_{equiv}^{[[6,1]]_{DQ}}\|=16\times 2=32$ as the number of elements in
the equivalence class for respective QD and DQ code. Here, we adopt the
notational convention wherein the symbol $|E_{equiv}^{CC}|$ denotes the
cardinality of the equivalence class $E_{equiv}^{CC}$ (i.e., the number of
sets in the class), whereas $\|E_{equiv}^{CC}\|$ denotes the total number of
elements in the equivalence class. Thus, for both the above $[[6,1]]$
concatenated codes, $\varphi=\frac{\log_{2}(32)}{5}=1$, appropriate for a
perfect code. However, as the present codes are degenerate, we suggest that in
this case, it seems more appropriate to generalize Eq. (30) to the modified
Hamming efficiency

$\varphi^{\prime}=\frac{\log_{2}\left(|{\rm~{}error~{}equivalence~{}class}|\right)}{n-k}.$
(31)

This quantifies the number of distinguishable correctable errors as a fraction
of non-coding bits. From Eqs. (26) and (29), $|E_{equiv}^{[[6,1]]_{QD}}|=4$ ,
and $|E_{equiv}^{[[6,1]]_{DQ}}|=16$ respectively. Thus the values
$\varphi^{\prime}=\frac{2}{5}$ and $\varphi^{\prime}=\frac{4}{5}$ for
$[[6,1]]_{QD}$ and $[[6,1]]_{DQ}$ code respectively.

The above examples illustrate the following result, which is generally true
for QD and DQ concatenations.

######  Theorem 2.

All passively correctable errors of a given QD or DQ code are mutually
degenerate (i.e., they constitute a single set in the error degeneracy
equivalence class).

###### Proof.

In the QD case, the passively correctable errors of the concatenated code
decode to the identity error in the outer QECC layer. In the DQ case, these
passively correctable errors decode syndromelessly to the correctable errors
in the outer DFS layer. In the QD and DQ cases, therefore the passive
correctability criterion fulfills the requirement to constitute an element of
the error degeneracy equivalence class. ∎

As an illustration of Theorem 2, in a given equivalence class of correctable
errors for a concatenation involving DFS as one layer of protection, all
elements in a set or none will possess a DFS-like structure.

###  IV.2 Performance of the $[[6,1]]$ QD and DQ codes under correlated noise

We now discuss the performance of the $[[6,1]]$ QD and DQ codes in terms of
the failure probability for the hybrid independent-correlated noise model. In
a correlated error model, the stand-alone failure probability for a
$[[3,1]]_{Q}$ and $[[2,1]]_{D}$ are given by:

$\displaystyle p_{F}^{[[3,1]]_{Q}}(\mu,p)$
$\displaystyle=p_{(0|0)}p_{(0|0)}p_{0}+p_{(1|0)}p_{(0|0)}p_{0}$
$\displaystyle+p_{(0|1)}p_{(1|0)}p_{0}+p_{(0|0)}p_{(0|1)}p_{1}$
$\displaystyle=(3p^{2}-2p^{3})(\mu-1)^{2}-p(\mu-2)p,$ (32a) $\displaystyle
p_{F}^{[[2,1]]_{D}}(\mu,p)$ $\displaystyle=p_{(1|0)}p_{0}+p_{(0|1)}p_{1}$
$\displaystyle=2(1-p)p(1-\mu).$ (32b)

By Eqs. (18) and (32), the failure probability of the $[[6,1]]_{QD}$ code is

$\displaystyle p_{F}^{[[6,1]]_{QD}}$
$\displaystyle=p_{F}^{[[3,1]]_{Q}}\left[0,p_{F}^{[[2,1]]_{D}}(\mu,p)\right]$
$\displaystyle=3\left(p_{F}^{[[2,1]]_{D}}(\mu,p)\right)^{2}\left(1-p_{F}^{[[2,1]]_{D}}(\mu,p)\right)$
$\displaystyle+\left(p_{F}^{[[2,1]]_{D}}(\mu,p)\right)^{3},$ (33)

whereas the failure probability of the $[[6,1]]_{DQ}$ code is

$\displaystyle p_{F}^{[[6,1]]_{DQ}}$
$\displaystyle=p_{F}^{[[2,1]]_{D}}\left[0,p_{F}^{[[3,1]]_{Q}}(\mu,p)\right]$
$\displaystyle=2p_{F}^{[[3,1]]_{Q}}(\mu,p)\left(1-p_{F}^{[[3,1]]_{Q}}(\mu,p)\right).$
(34)

The above two lead to roughly similar behavior, with the failure probability
for the concatenated code attaining the maximum for $p=\frac{1}{2}$, as should
be the case. The entanglement fidelities (according to Eq. (20)) for the two
concatenated codes (namely, $F_{e}^{[[6,1]]_{QD}}$ and $F_{e}^{[[6,1]]_{DQ}}$)
are plotted in Fig. 5 both for the regime of independent errors ($\mu=0$) and
errors with high correlation ($\mu=0.75$). In the former case, the DQ code
outperforms the QD code, because the inner layer of the QD code fails to
correct many errors that are independent. In the latter case, the QD code
outperforms the DQ code, because the inner layer of the DQ code fails to
correct many errors that are correlated.

Figure 5: (Color online) EF of the codes $[[6,1]]_{QD}$, $[[6,1]]_{DQ}$ for
the independent error model ($\mu=0$) and for the restricted correlated error
model ($\mu=0.75$, sans cross-block correlation), respectively, is depicted as
the solid (blue), dashed (red), dashdot (blue), dotted (red) plots. The plots
illustrate the idea that QD codes outperform DQ ones for sufficiently strong
correlation of the noise.

##  V The [[10,1]] QD and DQ codes

Here the $[[5,1]]$ Knill-Laflamme QECC code [53] is concatenated with the
$[[2,1]]_{D}$ code. Such a concatenation may be useful in situations where
independent and correlated errors coexist [36]. When the latter errors are
relatively stronger than the independent errors, then the QD scheme is
preferable, whereas the DQ scheme is preferable when independent errors are
relatively stronger than correlated errors.

The $[[10,1]]_{QD}$ code is depicted in Fig. 6(a). The logical codewords for
this code are

$\displaystyle\ket{0}$
$\displaystyle\longrightarrow\frac{1}{4}\bigg{[}\ket{00000}_{D}+\ket{10010}_{D}+\ket{01001}_{D}+\ket{10100}_{D}$
$\displaystyle+\ket{01010}_{D}-\ket{11011}_{D}-\ket{00110}_{D}-\ket{11000}_{D}$
$\displaystyle-\ket{11101}_{D}-\ket{00011}_{D}-\ket{11110}_{D}-\ket{01111}_{D}$
$\displaystyle-\ket{10001}_{D}-\ket{01100}_{D}-\ket{10111}_{D}+\ket{00101}_{D}\bigg{]},$
$\displaystyle\ket{1}$
$\displaystyle\longrightarrow\frac{1}{4}\bigg{[}\ket{11111}_{D}+\ket{01101}_{D}+\ket{10110}_{D}+\ket{01011}_{D}$
$\displaystyle+\ket{10101}_{D}-\ket{00100}_{D}-\ket{11001}_{D}-\ket{00111}_{D}$
$\displaystyle-\ket{00010}_{D}-\ket{11100}_{D}-\ket{00001}_{D}-\ket{10000}_{D}$
$\displaystyle-\ket{01110}_{D}-\ket{10011}_{D}-\ket{01000}_{D}-\ket{11010}_{D}\bigg{]},$
(35)

where the subscript $D$ indicates that there is an inner layer of encoding
where each qubit is replaced by the corresponding encoded qubit of the DFS.
Thus for example:

$\displaystyle\ket{00000}_{D}$
$\displaystyle=\ket{0}_{D}\ket{0}_{D}\ket{0}_{D}\ket{0}_{D}\ket{0}_{D}$
$\displaystyle=(\ket{00}+\ket{11})^{\otimes 5},$

and so forth.

(a) QD configuration

(b) DQ configuration

Figure 6: $[[10,1]]$ block structure: the dark orange balls represent the
outer code blocks, whilst the blue balls represent the inner code qubits.

The DQ scheme of the $[[10,1]]$ code is depicted in Fig. 6(b), for which the
logical codewords for this ten-qubit DQ code are

$\displaystyle\ket{0}$
$\displaystyle\longrightarrow|00\rangle_{Q}+|11\rangle_{Q},$
$\displaystyle\ket{1}$
$\displaystyle\longrightarrow\ket{01}_{Q}+\ket{10}_{Q}.$ (36)

where $\ket{0}_{Q}$ and $\ket{1}_{Q}$ are the logical codewords for the five-
qubit QECC.

Figure 7: (Color online) EF of the concatenated codes $[[10,1]]_{QD}$,
$[[10,1]]_{DQ}$ under the independent-error model ($\mu=0$) and the same codes
under the restricted-correlated error model ($\mu=0.75$), respectively, are
depicted as the solid (green), dashed (magenta), dashdot (green), dotted
(magenta) plots. As in the 6-qubit case, here too that for sufficiently
correlated error, QD outperforms DQ, and the reverse when the independent-
error model is used.

###  V.1 Equivalence classes of correctable Pauli errors

The correctable errors here can be arranged in an equivalence superclass,
consisting of two separate equivalence classes. The separation arises because
of the difference in the multiplicity of $Z_{D}$ vis-a-vis $I_{D},X_{D},Y_{D}$
(viz. Eq. (25). One of the two equivalence classes is the collection of 11
sets given by

$\displaystyle E_{equiv}^{[[10,1]]_{QD};XY}\equiv$
$\displaystyle~{}~{}\\{[XIIII]_{D},[IXIII]_{D},[IIXII]_{D},[IIIXI]_{D},$
$\displaystyle~{}~{}[IIIIX]_{D},[IIIII]_{D},[YIIII]_{D},[IYIII]_{D},$
$\displaystyle~{}~{}[IIYII]_{D},[IIIYI]_{D},[IIIIY]_{D}\\},$ (37)

which correspond to 11 of the 16 errors correctable by the outer code. Here
$[\cdots]_{D}$ denotes the expansion of the 5-qubit operator string by
insertion of corresponding logical operation in the inner code, e.g.,
$[IIIII]_{D}\equiv\\{II,XX\\}^{\otimes 5}$, yielding 32 operators of length 10
qubit operators. Thus Eq. (37) represents an equivalence class of 11 sets
having 32 degenerate elements, which yields
$\|E_{equiv}^{[[10,1]]_{QD};XY}\|=352$ elements in all. Here all elements in
the set $[IIIII]_{D}$ are passively correctable, in the manner of those in the
set $[III]_{D}$ of $E_{equiv}^{[[6,1]]_{QD}}$, Eq. (26). In Section VI.2, we
will show that these errors are generated by five passive stabilizer
generators.

The other equivalence class is a collection of 5 sets given by

$\displaystyle E_{equiv}^{[[10,1]]_{QD};Z}\equiv$
$\displaystyle~{}~{}\\{[ZIIII]_{D},[IZIII]_{D},[IIZII]_{D},[IIIZI]_{D},$
$\displaystyle~{}~{}[IIIIZ]_{D}\\},$ (38)

corresponding to the five errors correctable by the outer code and which
contain the Pauli $Z$. Note that in contrast to $X_{D},Y_{D}$, logical
operator $Z_{D}$ has only a single realization, in light of Eq. (25). Thus Eq.
(38) represents an equivalence class of 5 sets having 16 degenerate elements,
which yields $\|E_{equiv}^{[[10,1]]_{QD};Z}\|=80$ elements in all. We find
$\|E_{equiv}^{[[10,1]]_{QD};XY}\|+\|E_{equiv}^{[[10,1]]_{QD};Z}\|=432$, as
expected. Further,
$|E_{equiv}^{[[10,1]]_{QD};XY}|+|E_{equiv}^{[[10,1]]_{QD};Z}|=16$.

Therefore, for the $[[10,1]]_{QD}$ concatenated code, the Hamming efficiency
$\varphi=\frac{\log_{2}(432)}{9}\approx 0.972$ and the modified Hamming
efficiency $\varphi^{\prime}=\frac{\log_{2}(16)}{9}\approx\frac{4}{9}$.

For the $[[10,1]]_{DQ}$ code, as with the $[[6,1]]_{DQ}$, there is a single
equivalence class consisting of a pair of elements, demonstrating an
insensitivity with respect to the differing multiplicities, Eq. (25). There
are 16 Pauli errors that are correctable and thus yield $I_{Q}$ after the
inner layer has been decoded. Correspondingly, there are 16 Pauli errors that
result in $X_{Q}$ after the inner layer has been decoded. These are just the
correctable errors to which the logical NOT operator $XXXXX$ has been applied,
e.g., $IIYII\rightarrow XXZXX$. Thus there are $16^{2}$ sets consisting of a
pair of Pauli errors in the set $E_{equiv}^{[[10,1]]_{DQ}}$. We thus have
$|E_{equiv}^{[[10,1]]_{DQ}}|=16^{2}=256$ as the number of sets in the class,
and $\|E_{equiv}^{[[10,1]]_{DQ}}\|=16^{2}\times 2=512$ as the total number of
elements in the equivalence class. Accordingly, the Hamming efficiency is
$\varphi=\frac{\log_{2}(512)}{9}=1$ and the modified Hamming efficiency is
$\varphi^{\prime}=\frac{\log_{2}(256)}{9}=\frac{8}{9}$. In the manner of the
$[[6,1]]_{DQ}$ case (Eq. (29)), here too, there are only two passively
correctable errors, ($I^{\otimes 10}$ and $X^{\otimes 10}$), generated by a
passive stabilizer generator (Section VI.2).

###  V.2 Performance of the $[[10,1]]$ QD and DQ codes under correlated noise

In a correlated error model, the stand-alone failure probability for the
$[[5,1]]_{Q}$ and $[[2,1]]_{D}$ code is calculated as:

$\displaystyle p_{F}^{[[5,1]]_{Q}}(\mu,p)$
$\displaystyle=1-p_{C}^{[[5,1]]_{Q}}(\mu,p)$
$\displaystyle=1-3(1-p)^{2}p(1-\mu)^{2}\left((1-p)(1-\mu)+\mu\right)^{2}$
$\displaystyle-2(1-p)p(1-\mu)\left((1-p)(1-\mu)+\mu\right)^{3}$
$\displaystyle-(1-p)\left((1-p)(1-\mu)+\mu\right)^{4},$ (39a) $\displaystyle
p_{F}^{[[2,1]]_{D}}(\mu,p)$ $\displaystyle=1-p_{C}^{[[2,1]]_{D}}(\mu,p)$
$\displaystyle=1-(1-p)\left((1-p)(1-\mu)+\mu\right)$
$\displaystyle-\frac{p}{3}(\frac{p}{3}(1-\mu)+\mu),$ (39b)

where $p_{C}^{[[5,1]]_{Q}}$ and $p_{C}^{[[2,1]]_{D}}$ are the probability of
the correctable errors for the $[[5,1]]_{Q}$ and $[[2,1]]_{D}$ code
respectively. Here, $p_{0}=1-p$, $p_{1}=p_{2}=p_{3}=\frac{p}{3}$. The DFS
failure probability Eq. (39b), which includes $Y,Z$ errors, may be contrasted
with Eq. (32b), which includes only $X$ errors. By Eqs. (18) and (39), the
failure probability of the $[[10,1]]_{QD}$ code is

$\displaystyle p_{F}^{[[10,1]]_{QD}}(\mu,p)$
$\displaystyle=p_{F}^{[[5,1]]_{Q}}\left[0,p_{F}^{[[2,1]]_{D}}(\mu,p)\right]$
$\displaystyle=1-\left(1-p_{F}^{[[2,1]]_{D}}(\mu,p)\right)^{5}$
$\displaystyle-5\left(1-p_{F}^{[[2,1]]_{D}}(\mu,p)\right)^{4}p_{F}^{[[2,1]]_{D}}(\mu,p),$
(40)

whereas the failure probability of the $[[10,1]]_{DQ}$ code is

$\displaystyle p_{F}^{[[10,1]]_{DQ}}(\mu,p)$
$\displaystyle=p_{F}^{[[2,1]]_{D}}\left[0,p_{F}^{[[5,1]]_{Q}}(\mu,p)\right]$
$\displaystyle=\frac{2}{3}\left(p_{F}^{[[5,1]]_{Q}}(\mu,p)\right)\left(1-p_{F}^{[[5,1]]_{Q}}(\mu,p)\right).$
(41)

Employing Eq. (20), we obtain the entanglement fidelities
$F_{e}^{[[10,1]]_{QD}}$ and $F_{e}^{[[10,1]]_{DQ}}$ for the 10-qubit QD and
DQ, respectively. These fidelities as a function of single-qubit error
probability $p$ are plotted in Fig. 7. We find that for sufficiently low
correlation of the noise, the DQ code outperforms the QD code, and vice versa
when the correlation is sufficiently large, as discussed earlier in the
context of the $[[6,1]]$ code.

##  VI Generator structure of the concatenated code

The stabilizer of the concatenated code is a concatenation of the stabilizers
of the constituent codes. A well known example is the Shor code, whose
stabilizer generator can be constructed by concatenating the three-qubit
phase-flip and bit-flip codes [19]. A DFS code is a kind of stabilizer code
[32, 44] in that the code space is stabilized by commuting operators and the
errors fulfill the error correcting condition Eq. (8). However, unlike with a
conventional stabilizer code [54], the stabilizer generators commute with all
error operators, being identical with the error operators. This is reflective
of the fact that DFS is a passive rather than active error correction scheme.
Therefore, in a broader sense, we expect that the QD and DQ concatenations
also to possess a stabilizer structure.

On the other hand, the DFS introduces novel elements into the stabilizer
structure, resulting in the degeneracy of the correctable errors and also,
interestingly, degeneracy of the stabilizers. Importantly, the stabilizer
structure divides into an active and passive part, with corresponding errors
and stabilizers. In the following, we illustrate the stabilizer structure of
QD and DQ codes by means of the [[6,1]] and [[10,1]] codes considered above.

###  VI.1 The $[[6,1]]$ codes

This concatenates the $[[3,1]]_{Q}$ and $[[2,1]]_{D}$ codes, with stabilizer
generators given, respectively, by,

$\displaystyle\mathcal{S}^{[[3,1]]_{Q}}=\langle Z^{1}Z^{2},Z^{1}Z^{3}\rangle,$
(42)

and

$\displaystyle\mathcal{S}^{[[2,1]]_{D}}=\langle X^{1}X^{2}\rangle.$ (43)

In both cases QD and DQ, there will be $n-k=5$ stabilizer generators.

In the QD case, we label the qubits blockwise as $(1a,1b),(2a,2b),(3a,3b)$. To
each block, we assign a copy of stabilizer generator of the DFS (Eq. (43)),
yielding three of the generators:

$\displaystyle S_{1}=X^{1a}X^{1b},$ $\displaystyle S_{2}=X^{2a}X^{2b},$
$\displaystyle S_{3}=X^{3a}X^{3b}.$ (44)

Note that the elements of the first set in Eq. (26) for
$E_{equiv}^{[[6,1]]_{QD}}$ are generated by the operators in Eq. (44), in
keeping with the fact that these errors are passively correctable.

Interestingly, these stabilizers are themselves degenerate, which can be
understood as a consequence of the fact that all of them are passive. Their
passivity by design arises from the fact that they are stabilizers of
correctable errors of the inner code, and the remaining errors correspond to
logical operations at the inner layer that decode to errors corrected at the
outer layer. As such the operators $S_{1},S_{2},S_{3}$ do not require to be
measured. By virtue of the fact that the passively correctable errors are
stabilizers, it follows that they commute with other stabilizer generators,
$S_{4},S_{5}$, given below.

The remaining two generators can be obtained by encoding the qubits that make
up the outer code’s stabilizer in terms of logical operations of the inner
code. Accordingly, from Eqs. (42) and (25), we find

$\displaystyle S_{4}=(Z^{1a}Z^{1b})(Z^{2a}Z^{2b}),$ $\displaystyle
S_{5}=(Z^{1a}Z^{1b})(Z^{3a}Z^{3b}).$ (45)

Thus, the set of 5 stabilizer generators for the $[[6,1]]_{QD}$ are given by
Eqs. (44) and (45).

In the DQ case, we label the qubits blockwise as $(1a,1b,1c),(2a,2b,2c)$. To
each block, we assign a copy of stabilizer generators of the QECC (Eq. (42)),
yielding four of the five generators:

$\displaystyle S_{1}=Z^{1a}Z^{1b},$ $\displaystyle S_{2}=Z^{1a}Z^{1c},$
$\displaystyle S_{3}=Z^{2a}Z^{2b},$ $\displaystyle S_{4}=Z^{2a}Z^{2c}.$ (46)

The remaining single generator can be obtained by encoding the qubits that
make up the outer code’s stabilizer in terms of logical operations of the
inner code. Accordingly, from Eq. (42) and the fact that $X_{L}=XXX$ for the
$[[3,1]]_{Q}$ QECC, we find

$\displaystyle S_{5}=(X^{1a}X^{1b}X^{1c})(X^{2a}X^{2b}X^{2c}).$ (47)

Note that this generator is passive and generates the two passively
correctable errors $I^{\otimes 6}$ and $X^{\otimes 6}$. Summarizing, the set
of five stabilizer generators for the $[[6,1]]_{QD}$ are given by Eqs. (46)
and (47).

###  VI.2 The $[[10,1]]$ codes

The $[[5,1]]_{Q}$ and $[[2,1]]_{D}$ codes are concatenated here, and the
stabilizer generators are provided, respectively, by,

$\displaystyle\mathcal{S}^{[[5,1]]_{Q}}=\langle
X^{1}Z^{2}Z^{3}X^{4},X^{2}Z^{3}Z^{4}X^{5},X^{1}X^{3}Z^{4}Z^{5},Z^{1}X^{2}X^{4}Z^{5}\rangle,$
(48)

and Eq. (43). Here there will be $n-k=9$ stabilizer generators for both QD and
DQ codes. In the QD case, the qubits are designated via blockwise labeling as
$(1a,1b),(2a,2b),(3a,3b),(4a,4b),(5a,5b)$. The assignment of a copy of the
stabilizer generators of the DFS (Eq.(43)) to each block will give five
stabilizer generators:

$\displaystyle S_{1}=X^{1a}X^{1b},$ $\displaystyle S_{2}=X^{2a}X^{2b},$
$\displaystyle S_{3}=X^{3a}X^{3b},$ $\displaystyle S_{4}=X^{4a}X^{4b},$
$\displaystyle S_{5}=X^{5a}X^{5b}.$ (49)

Note that the thirty-two elements of the error set $[IIIII]_{D}$ in Eq. (37)
are generated by the operators $S_{j}$ in Eq. (49), consistent with the fact
that those errors are passively correctable. As in the case of the
$[[6,1]]_{QD}$ code, these operators are themselves passive, and thus
degenerate.

The remaining four stabilizer generators are the encoded version of stabilizer
generators of the five-qubit code (Eq.(48)) in block labels. These four
generators, though actively error correcting, also involve stabilizer
degeneracy, in this arising because of the multiplicity Eq. (25).

$\displaystyle S_{6}=[X^{1}][X^{3}](Z^{4a}Z^{4b})(Z^{5a}Z^{5b}),$
$\displaystyle S_{7}=(Z^{1a}Z^{1b})[X^{2}][X^{4}](Z^{5a}Z^{5b}),$
$\displaystyle S_{8}=[X^{1}](Z^{2a}Z^{2b})(Z^{3a}Z^{3b})[X^{4}],$
$\displaystyle S_{9}=[X^{2}](Z^{3a}Z^{3b})(Z^{4a}Z^{4b})[X^{5}],$ (50)

where the terms in the square brackets can each be encoded in two ways. Thus,
each of the stabilizers in Eq. (50) represents an equivalence class of 4
generators that produce the same syndrome for each correctable error. This
degeneracy of the stabilizers should be distinguished from that of the
stabilizers in Eq. (49), which has its origin in the passivity of their error
correction. On the other, the degeneracy of the stabilizers in Eq. (50) has
the same origin as the degeneracy of errors in Eq. (37), namely the
multiplicity Eq. (25) of the DFS.

Thus the set of 9 stabilizer generators for the $[[10,1]]_{QD}$ code is given
by Eq. (49), and selecting any one element from each generator in the
equivalence classes of Eq. (50).

In the DQ case, the resultant concatenated code has two blocks:
$(1a,1b,1c,1d,1e),(2a,2b,2c,2d,2e)$. We assign a copy of stabilizer generators
of the inner QECC (Eq. (48)) to each block, yielding the eight of nine
stabilizer generators are expressed as,

$\displaystyle S_{1}=X^{1a}Z^{1b}Z^{1c}X^{1d},$ $\displaystyle
S_{2}=X^{1b}Z^{1c}Z^{1d}X^{1e},$ $\displaystyle
S_{3}=X^{1a}X^{1c}Z^{1d}Z^{1e},$ $\displaystyle
S_{4}=Z^{1a}X^{1b}X^{1d}Z^{1e},$ $\displaystyle
S_{5}=X^{2a}Z^{2b}Z^{2c}X^{2d},$ $\displaystyle
S_{6}=X^{2b}Z^{2c}Z^{2d}X^{2e},$ $\displaystyle
S_{7}=X^{2a}X^{2c}Z^{2d}Z^{2e},$ $\displaystyle
S_{8}=Z^{2a}X^{2b}X^{2d}Z^{2e}.$ (51)

The block label encoding of the generators of outer DFS (Eq. (43)) will give
the remaining one generator:

$\displaystyle
S_{9}=(X^{1a}X^{1b}X^{1c}X^{1d}X^{1e})(X^{2a}X^{2b}X^{2c}X^{2d}X^{2e}).$ (52)

Thus the set of stabilizer generators for the $[[10,1]]_{DQ}$ code is given by
Eqs. (51) and (52). We note that the generator in Eq. (52) is passive and
generates the two passively correctable errors $I^{\otimes 10}$ and
$X^{\otimes 10}$, in a manner similar to the case of the $[[6,1]]_{DQ}$ code,
Eq. (47).

##  VII Conclusions and discussions

This work studied the codes obtained by concatenating quantum error correcting
codes (QECCs) and decoherence-free subspaces (DFSs). This concatenation is
suitable when both independent and correlated errors occur simultaneously.
When the errors are sufficiently strongly correlated, the concatenation with
the DFS as the inner code provides better entanglement fidelity, whereas for
errors that are sufficiently independent, the concatenation with QECC as the
inner code is preferable. The concatenation of QECC and DFS results in a kind
of stabilizer structure that splits naturally into passive and active parts.
Whereas the passive part functions like a DFS, the active one like a QECC.

As examples, we studied in specific the concatenation of a 2-qubit DFS code
with a 3-qubit repetition code and 5-qubit Knill-Laflamme code, under
independent and correlated error models.

Whereas increasing the number of concatenated layers improves resistance to
noise (with the asymptotic performance for the fault-tolerant systems obtained
when the number of layers approaches infinity [24]), the practical
implementation also gets harder. Moreover, the pseudothreshold (defined as the
maximum physical error rate $p$ below which $p_{F}(p)<p$) is insensitive to
concatenation. In Fig. 8, the probability of failure ($p_{F}$) is plotted as a
function of the probability of the individual qubit error ($p$) with
concatenation depth ${L=1,2,3,4}$ for the $[[6,1]]_{DQ}$.

Figure 8: (Color online) Failure probability of the concatenated code
$[[6,1]]_{DQ}$ with pseudothreshold probability($p_{thres})\approx 0.225$ for
$L=1$, $L=2$, $L=3$, and $L=4$ concatenations respectively, are depicted as
the dotted (red), dashdot (orange), dashed (green), solid (blue) plots.

The pseudothreshold remains invariant, because when the inmost code fails, it
precipitates the failure of all outer layers. The pattern is same for the
$[[6,1]]_{QD}$, and the $[[10,1]]_{QD/DQ}$ codes, except that the
pseudothreshold is slightly different. For independent errors, typically, the
inner code with the higher pseudothreshold provides better logical noise
suppression [35]. The performance parameters for the four codes discussed in
this work, along with their pseudothresholds, are summarized in Table 1. In
conclusion, the preferred order of concatenation will depend both on the level
of correlation in the noise and the desired pseudothreshold. Here, the concept
of pseudothreshold is the same as that of threshold mentioned in Ref. [24].
Note that the pseudothreshold should be distinguished from the asymptotic
threshold relevant to realistic simulations of fault tolerant computing [55].
Here different components of the circuit are allowed to fail at differing
rates, so that the thresholds at different levels of concatenation no longer
match, and an asymptotic analysis would be needed to determine the tolerable
error rate $p$.

Code | $[[6,1]]_{QD}$ | $[[6,1]]_{DQ}$ | $[[10,1]]_{QD}$ | $[[10,1]]_{DQ}$
---|---|---|---|---
$E_{type}$ | $X,XX$ | $X,XX$ | $X,Y,Z,XX$ | $X,Y,Z,XX$
$\varphi$ | $1$ | $1$ | $0.972$ | $1$
$\varphi^{\prime}$ | $0.4$ | $0.8$ | $0.444$ | $0.888$
$p_{thres}$ | $0.1293$ | $0.2252$ | $0.02988$ | $0.0579$
Table 1: Error type, Hamming efficiency, modified Hamming efficiency, and
pseudothreshold probability of the concatenated codes.

Given the presence of correlated noise, here the main task involves
identifying the DFS and the selection of the compatible QECC in a way that
facilitates implementing fault-tolerant quantum computation with the
concatenated code in a given quantum processor. For example, in a two-
dimensional decoherence-free photonic memory subspace protected from
collective errors, if the independent errors also occur with nonvanishing
probability, then a QECC can be encoded in it to improve protection. Our work
motivates the study of other types of compatible QECC and DFS code
concatenation.

The DQ and QD codes can be considered as generalizing stabilizer codes to a
new class of hybrid codes, which correct errors both actively and passively.
QECCs and DFSs form special cases of such a hybrid code.

###### Acknowledgements.

NRD and SD acknowledge financial support by the Department of Science and
Technology (DST) India through the INSPIRE fellowship, and the University
Grants Commision (UGC) India through the NET fellowship, respectively. NRD
also thanks to Vinod Rao for insightful discussions during early stages of
this project. RS acknowledges partial support by the Indian Science &
Engineering Research Board (SERB) grant CRG/2022/008345. NRD is sincerely
grateful to the Poornaprajna Institute of Scientific Research (PPISR) for its
hospitality and conductive environment during his academic visit.

## References

  * Banerjee [2018] S. Banerjee,  _Open Quantum Systems: Dynamics of Nonclassical Evolution_, Texts and Readings in Physical Sciences (Springer Nature Singapore, 2018).
  * Shor [1995] P. W. Shor, Phys. Rev. A 52, R2493 (1995).
  * Steane [1996] A. M. Steane, Phys. Rev. Lett. 77, 793 (1996).
  * Calderbank and Shor [1996] A. R. Calderbank and P. W. Shor, Phys. Rev. A 54, 1098 (1996).
  * Knill and Laflamme [1997] E. Knill and R. Laflamme, Phys. Rev. A 55, 900 (1997).
  * Knill  _et al._ [2000] E. Knill, R. Laflamme, and L. Viola, Phys. Rev. Lett. 84, 2525 (2000).
  * Zanardi and Rasetti [1997] P. Zanardi and M. Rasetti, Phys. Rev. Lett. 79, 3306 (1997).
  * Lidar  _et al._ [1998] D. A. Lidar, I. L. Chuang, and K. B. Whaley, Phys. Rev. Lett. 81, 2594 (1998).
  * Bacon  _et al._ [2000] D. Bacon, J. Kempe, D. A. Lidar, and K. B. Whaley, Phys. Rev. Lett. 85, 1758 (2000).
  * Viola  _et al._ [1999] L. Viola, E. Knill, and S. Lloyd, Physical Review Letters 82, 2417 (1999).
  * Temme  _et al._ [2017] K. Temme, S. Bravyi, and J. M. Gambetta, Phys. Rev. Lett. 119, 180509 (2017).
  * Li and Benjamin [2017] Y. Li and S. C. Benjamin, Phys. Rev. X 7, 021050 (2017).
  * Omkar  _et al._ [2015a] S. Omkar, R. Srikanth, and S. Banerjee, Phys. Rev. A 91, 012324 (2015a).
  * Omkar  _et al._ [2015b] S. Omkar, R. Srikanth, and S. Banerjee, Phys. Rev. A 91, 052309 (2015b).
  * Cerf  _et al._ [2007] N. Cerf, G. Leuchs, and E. Polzik,  _Quantum Information With Continuous Variables Of Atoms And Light_ (World Scientific Publishing Company, 2007).
  * Gottesman [2009] D. Gottesman, “An introduction to quantum error correction and fault-tolerant quantum computation,” (2009), arXiv:0904.2557 [quant-ph] .
  * Poulin [2006] D. Poulin, Phys. Rev. A 74, 052333 (2006).
  * G. D. Forney [1966] J. G. D. Forney, MIT Press,Cambridge, MA (1966).
  * Gaitan [2008] F. Gaitan,  _Quantum Error Correction and Fault Tolerant Quantum Computing_ (Taylor & Francis, 2008).
  * Aharonov and Ben-Or [1999] D. Aharonov and M. Ben-Or, “Fault-tolerant quantum computation with constant error rate,” (1999), arXiv:quant-ph/9906129 [quant-ph] .
  * Knill  _et al._ [1998] E. Knill, R. Laflamme, and W. H. Zurek, Science 279, 342 (1998).
  * Kitaev [1997] A. Y. Kitaev, Russian Mathematical Surveys 52, 1191 (1997).
  * Knill and Laflamme [1996] E. Knill and R. Laflamme, “Concatenated quantum codes,” (1996), arXiv:quant-ph/9608012 [quant-ph] .
  * Rahn  _et al._ [2002] B. Rahn, A. C. Doherty, and H. Mabuchi, Phys. Rev. A 66, 032304 (2002).
  * Grassl  _et al._ [2009] M. Grassl, P. Shor, G. Smith, J. Smolin, and B. Zeng, Phys. Rev. A 79, 050306 (2009).
  * Fern [2008] J. Fern, Phys. Rev. A 77, 010301 (2008).
  * Huang  _et al._ [2015] L. Huang, B. You, X. Wu, and T. Zhou, Phys. Rev. A 92, 052320 (2015).
  * Khodjasteh and Lidar [2003] K. Khodjasteh and D. A. Lidar, Phys. Rev. A 68, 022322 (2003).
  * Paz-Silva and Lidar [2013] G. A. Paz-Silva and D. A. Lidar, Scientific Reports 3 (2013), 10.1038/srep01530.
  * Zhang  _et al._ [2004] Y. Zhang, Z.-W. Zhou, B. Yu, and G.-C. Guo, Phys. Rev. A 69, 042315 (2004).
  * West and Fong [2012] J. R. West and B. H. Fong, New Journal of Physics 14, 083002 (2012).
  * Lidar  _et al._ [1999] D. A. Lidar, D. Bacon, and K. B. Whaley, Phys. Rev. Lett. 82, 4556 (1999).
  * Chamberland and Jochym-O’Connor [2017] C. Chamberland and T. Jochym-O’Connor, Quantum Science and Technology 2, 035008 (2017).
  * Jochym-O’Connor and Laflamme [2014] T. Jochym-O’Connor and R. Laflamme, Phys. Rev. Lett. 112, 010505 (2014).
  * Chamberland  _et al._ [2016] C. Chamberland, T. Jochym-O’Connor, and R. Laflamme, Phys. Rev. Lett. 117, 010501 (2016).
  * Boulant  _et al._ [2005] N. Boulant, L. Viola, E. M. Fortunato, and D. G. Cory, Phys. Rev. Lett. 94, 130501 (2005).
  * Clemens  _et al._ [2004] J. P. Clemens, S. Siddiqui, and J. Gea-Banacloche, Phys. Rev. A 69, 062313 (2004).
  * Cafaro and Mancini [2011] C. Cafaro and S. Mancini, International Journal of Quantum Information 09, 309 (2011).
  * Cafaro  _et al._ [2011] C. Cafaro, S. L’Innocente, C. Lupo, and S. Mancini, Open Systems & Information Dynamics 18, 1 (2011).
  * Ouyang [2021] Y. Ouyang, npj Quantum Information 7 (2021), 10.1038/s41534-021-00429-8.
  * Alber  _et al._ [2001] G. Alber, T. Beth, C. Charnes, A. Delgado, M. Grassl, and M. Mussinger, Phys. Rev. Lett. 86, 4402 (2001).
  * Khodjasteh and Lidar [2002] K. Khodjasteh and D. A. Lidar, Phys. Rev. Lett. 89, 197904 (2002).
  * Lidar  _et al._ [2001a] D. A. Lidar, D. Bacon, J. Kempe, and K. B. Whaley, Phys. Rev. A 63, 022306 (2001a).
  * Lidar  _et al._ [2001b] D. A. Lidar, D. Bacon, J. Kempe, and K. B. Whaley, Phys. Rev. A 63, 022307 (2001b).
  * Pathak [2013] A. Pathak,  _Elements of Quantum Computation and Quantum Communication_ (CRC Press, 2013).
  * Cornwell [1997] J. Cornwell,  _Group Theory in Physics: An Introduction_, Techniques of Physics Series (Academic Press, 1997).
  * Lidar and Brun [2013] D. A. Lidar and T. A. Brun,  _Quantum Error Correction_ (Cambridge University Press, 2013).
  * Bennett  _et al._ [1996] C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters, Phys. Rev. A 54, 3824 (1996).
  * Schumacher [1996] B. Schumacher, Phys. Rev. A 54, 2614 (1996).
  * Nielsen [1996] M. A. Nielsen, “The entanglement fidelity and quantum error correction,” (1996), arXiv:quant-ph/9606012 [quant-ph] .
  * Cafaro and Mancini [2010] C. Cafaro and S. Mancini, Phys. Rev. A 82, 012306 (2010).
  * Ekert and Macchiavello [1996] A. Ekert and C. Macchiavello, Phys. Rev. Lett. 77, 2585 (1996).
  * Knill  _et al._ [2001] E. Knill, R. Laflamme, R. Martinez, and C. Negrevergne, Phys. Rev. Lett. 86, 5811 (2001).
  * Gottesman [1997] D. Gottesman, “Stabilizer codes and quantum error correction,” (1997), arXiv:quant-ph/9705052 [quant-ph] .
  * Svore  _et al._ [2005] K. M. Svore, A. W. Cross, I. L. Chuang, and A. V. Aho, arXiv preprint quant-ph/0508176 (2005).


# A Normal Test for Independence via Generalized Mutual Information

Jialin Zhang
and
Zhiyi Zhang Department of Mathematics and Statistics, Mississippi State
UniversityDepartment of Mathematics and Statistics, University of North
Carolina at Charlotte

###### Abstract

Testing hypothesis of independence between two random elements on a joint
alphabet is a fundamental exercise in statistics. Pearson’s chi-squared test
is an effective test for such a situation when the contingency table is
relatively small. General statistical tools are lacking when the contingency
data tables are large or sparse. A test based on generalized mutual
information is derived and proposed in this article. The new test has two
desired theoretical properties. First, the test statistic is asymptotically
normal under the hypothesis of independence; consequently it does not require
the knowledge of the row and column sizes of the contingency table. Second,
the test is consistent and therefore it would detect any form of dependence
structure in the general alternative space given a sufficiently large sample.
In addition, simulation studies show that the proposed test converges faster
than Pearson’s chi-squared test when the contingency table is large or sparse.

Keywords: Test for independence, countable joint alphabets, mutual
information, sparse contingency tables.

##  1 Introduction and Summary

Let $(X,Y)$ be a pair of random elements on a joint alphabet,
$\mathscr{X}\times\mathscr{Y}=\\{(l_{i},m_{j});1\leq i\leq I,1\leq j\leq
J\\}$, with a joint probability distribution,
$\mathbf{p}_{\scalebox{0.7}{X,Y}}=\\{p_{i,j};1\leq i\leq I,1\leq j\leq J\\}$,
and the two marginal distributions,
$\mathbf{p}_{\scalebox{0.7}{X}}=\\{p_{i,\cdot}=\sum_{j\geq 1}p_{i,j};i\geq
1\\}$ and $\mathbf{p}_{\scalebox{0.7}{Y}}=\\{p_{\cdot,j}=\sum_{i\geq
1}p_{i,j};j\geq 1\\}$, for $X$ and $Y$ respectively. Consider one the most
fundamental problems of statistics: testing the hypothesis of independence
between $X$ and $Y$, denoted $H_{0}:X\perp Y$ versus $H_{a}:X\not\perp Y$. Let
an identically and independently distributed (iid) sample of size $n$ be
represented by the empirical distribution, that is,
$\hat{\mathbf{p}}_{\scalebox{0.7}{X,Y}}=\\{\hat{p}_{i,j}=f_{i,j}/n\\}$ where
$f_{i,j}$ is the observed frequency of letter $(l_{i},m_{j})$. Let
$\hat{\mathbf{p}}_{\scalebox{0.7}{X}}=\\{\hat{p}_{i,\cdot}=\sum_{j\geq
1}f_{i,j}/n;i\geq 1\\}$ and
$\hat{\mathbf{p}}_{\scalebox{0.7}{Y}}=\\{\hat{p}_{\cdot,j}=\sum_{i\geq
1}f_{i,j}/n;j\geq 1\\}$ be the two observed marginal relative frequencies of
$X$ and $Y$.

In statistical practice, the standard procedure for such a setting is the
well-studied Pearson’s chi-squared test, which is based on the fact that, as
$n\rightarrow\infty$,

$T=n\sum_{i,j}\hat{p}_{i,\cdot}\hat{p}_{\cdot,j}\left(\frac{\hat{p}_{i,j}-\hat{p}_{i,\cdot}\hat{p}_{\cdot,j}}{\hat{p}_{i,\cdot}\hat{p}_{\cdot,j}}\right)^{2}\stackrel{{\scriptstyle
p}}{{\longrightarrow}}\chi^{2}_{(I-1)(J-1)}$ (1)

where $\chi^{2}_{(I-1)(J-1)}$ is a chi-squared random variable with degrees of
freedom $\nu=(I-1)(J-1)$. The Pearson’s chi-squared test is an effective tool
for relatively small 2-way contingency tables. However it is not without
discomforting issues in practice, particularly when it is applied to a large
or sparse contingency table.

One of the issues in practice is when $I$ and $J$ are unknown. In such a case,
it is difficult to fix the reference distribution in (1). A popular adjustment
in practice is to replace $I$ and $J$ with observed numbers of rows and
columns, $\hat{I}$ and $\hat{J}$. However, such an adjustment lacks
theoretical support and the reference distribution used may be quite far away
from the asymptotic chi-squared distribution. Another commonly encountered
issue in a large contingency table is the occurrence of low-frequency cells.
Given the fact that the essence of the asymptotic behavior of Pearson’s chi-
squared statistic is the asymptotic normality of
$\sqrt{n}\left[(\hat{p}_{i,j}-\hat{p}_{i,\cdot}\hat{p}_{\cdot,j})/(\hat{p}_{i,\cdot}\hat{p}_{\cdot,j})\right]$
in each cell, many low or zero frequency cells in a large contingency table
could negatively impact the performance of the test, mostly in the form of a
much inflated Type I error probability. This is a long-standing issue
considered by many in the existing literature.

A popular adjustment to offset the low or zero frequency cells, when applying
a Pearson-type chi-squared test, is to combine cells to increase the cell
frequency. A well-known rule of thumb, often thought to be suggested by R.A.
Fisher, is to combine cells into new cells such that the combined frequencies
are at least five. However, in applying Pearson’s chi-squared test for
independence, it is not clear how this adjustment may be done. To assure
independence under $H_{0}$, the adjustment must be made by combining low-
frequency rows and low-frequency columns, respectively, due to the invariance
of independence under any row permutation and/or column permutation. However,
by doing so, it is not guaranteed that all new cells would see enough
frequencies. Only by combining the rows and columns further, can the new cells
then see meaningfully higher frequencies. When this is the case, the re-
aggregation becomes somewhat arbitrary. Even if this could be done, the
following two points of concern remain.

  1. 1.

Aggressive re-aggregation of cells could greatly reduce the number of
(observed) degrees of freedom and consequently could shift the reference
distribution to one that is far away from $\chi^{2}_{(I-1)(J-1)}$.

  2. 2.

Aggressive re-aggregation of cells could cause local dependence between $X$
and $Y$, manifested in fine structures of the joint distribution, to be
inadvertently buried, and hence could deprive Pearson’s chi-squared test a
chance to detect such a dependence.

Consider a simple but amplified illustrative example of concept as follows.
Let

$\displaystyle\mathbf{p}_{\scalebox{0.7}{X}}$
$\displaystyle=\\{p_{i,\cdot};i=1,\cdots,11\\}=\\{0.9,0.01,\cdots,0.01\\},$
$\displaystyle\mathbf{p}_{\scalebox{0.7}{Y}}$
$\displaystyle=\\{p_{\cdot,j};j=1,\cdots,11\\}=\\{0.9,0.01,\cdots,0.01\\}.$

Under independence, the joint distribution of $(X,Y)$ is given in
$\mathbf{p}_{0}$ below.

$\mathbf{p}_{0}=\left(\begin{array}[]{c|ccc}0.8100&0.0090&\cdots&0.0090\\\
\hline\cr 0.0090&0.0001&\cdots&0.0001\\\ 0.0090&0.0001&\cdots&0.0001\\\
\vdots&\vdots&\vdots\hskip 2.0pt\vdots\hskip 2.0pt\vdots&\vdots\\\
0.0090&0.0001&\cdots&0.0001\end{array}\right)=\left(\begin{array}[]{cc}P_{1,1}&P_{1,2}\\\
P_{2,1}&P_{2,2}\end{array}\right)$

Summing up all probabilities in $P_{2,2}$,
$\sum_{i=2}^{11}\sum_{j=2}^{11}p_{i,j}=0.1$. Let the total mass of $0.1$ be
redistributed uniformly only on the diagonal of $P_{2,2}$, augmenting
$P_{2,2}$ into

$P_{2,2}^{*}=\left(\begin{array}[]{cccc}0.001&&&\\\ &0.001&&\\\ &&\ddots&\\\
&&&0.001\end{array}\right)$

with all off-diagonal elements being zeros. Let

$\mathbf{p}_{a}=\left(\begin{array}[]{cc}P_{1,1}&P_{1,2}\\\
P_{2,1}&P_{2,2}^{*}\end{array}\right)$

and let it be assumed that $(X,Y)$ follows the joint distribution
$\mathbf{p}_{a}$. Clearly, $X$ and $Y$ are not independent. Suppose there is a
sample with a sufficiently large $n$, such that, all cells with a positive
probability see $f_{i,j}\geq 5$. That however does not change the fact that
the observed frequencies for cells corresponding to the zero-probability
locations in $P_{2,2}^{*}$ are zeros. In applying the usual re-aggregation of
the contingency table, by means of combining rows and columns, one would not
be able to end up with all cell frequencies greater than or equal to five,
unless all rows of $i=2,\cdots,11$ are lumped together and all columns of
$j=2,\cdots,11$ are lumped together. However by doing this, the underlying
joint distribution becomes

$\mathbf{p}_{a}^{*}=\left(\begin{array}[]{cc}0.81&0.09\\\
0.09&0.01\end{array}\right)$

under which $X$ and $Y$ are independent. In this example, it is evident that
the aggregated data would imply $\hat{I}=\hat{J}=2$, far away from the
$I=J=11$. It is also evident that the data aggregation would completely erase
the fine dependence structure in $P_{2,2}^{*}$ and would leave no chance for
the dependence to be detected.

As the need to extend Pearson’s chi-squared test to accommodate data in a
large or a sparse contingency table increases, many studies have been reported
and less stringent rules of thumb have been proposed. The main guideline for
the chi-squared test focuses on the (estimated) expected cell counts in the
contingency table, following from Cochran (1952), Cochran (1954), Agresti
(2003), and Yates et al. (1999). The widely accepted general rule of thumb
(referred to below as the Rule) is: (a) at least 80$\%$ the expected counts
are five or greater, and (b) all individual expected counts are one or
greater. This however is still very stringent. In the example given above,
Part (b) alone requires on average $n\times 0.0001\geq 1$, or $n\approx
10000$, or much greater if $f_{i,j}\geq 1$ is required. In fact, in the
example above, $f_{i,j}\geq 1$ cannot be satisfied for each and every $(i,j)$.

To alleviate the above-mentioned difficulties, a new test of independence in a
contingency table is proposed in this article. The proposed test has at least
two desirable properties. First, the asymptotic distribution of the test
statistic is normal under the independence assumption, and consequently
neither the test statistic nor its asymptotic distribution requires the
knowledge of $I$ and $J$. Second, the test is consistent and therefore it
would detect any form of dependence structure in the general alternative space
given a sufficiently large sample. In addition, empirical evidence shows that
the proposed test converges faster than Pearson’s chi-squared test when the
contingency table is large or sparse.

There are five sections in this article. The main results leading to the
proposed test are discussed in Section 2. In Section 3, several simulation
studies are presented. A few concluding remarks are given in Section 4. The
article ends with Appendix where a few proofs are found.

##  2 Toward a Normal Test for Independence

Consider Shannon’s entropy, introduced in Shannon (1948), for an random
element $Z$ assuming a label in a countable alphabet
$\mathscr{Z}=\\{\ell_{k};k\geq 1\\}$ with probability distribution
$\mathbf{p}=\\{p_{k};k\geq 1\\}$, $H(Z)=-\sum_{k\geq 1}p_{k}\ln p_{k}$, and
Shannon’s mutual information of $X$ and $Y$, $MI(X,Y)=H(X)+H(Y)-H(X,Y)$. One
of the most important utilities of Shannon’s mutual information is based on
the fact that $MI(X,Y)=0$ if and only if $X$ and $Y$ are independent. The
plug-in estimator of $MI(X,Y)$,
$\widehat{MI}=\hat{H}(X)+\hat{H}(Y)-\hat{H}(X,Y)$, where
$\hat{H}(X)=-\sum_{i\geq 1,}\hat{p}_{i,\cdot}\ln\hat{p}_{i,\cdot}$,
$\hat{H}(Y)=-\sum_{j\geq 1}\hat{p}_{\cdot,j}\ln\hat{p}_{\cdot,j}$, and
$\hat{H}(X,Y)=-\sum_{i\geq 1,j\geq 1}\hat{p}_{i,j}\ln\hat{p}_{i,j}$, is well-
studied, and it is known, under mild conditions, that
$\sqrt{n}(\widehat{MI}-MI)\stackrel{{\scriptstyle
p}}{{\rightarrow}}N(0,\sigma^{2}_{m})$ where $\sigma^{2}_{m}$ may be estimated
by a consistent estimator. Many details of the said fact may be found in Zhang
(2016). However the mild conditions include $MI>0$. When $MI=0$,
$\sqrt{n}(\widehat{MI}-MI)=\sqrt{n}\widehat{MI}$ degenerates, but on the other
hand, $2n\widehat{MI}\stackrel{{\scriptstyle
p}}{{\rightarrow}}\chi^{2}_{(I-1)(J-1)}$, and the derivation of this fact may
be found in Wilks (1938).

Toward proposing the normal test, let the notion of escort distributions be
introduced. In the context of thermodynamics, Beck & Schögl (1995) defines an
escort distribution as an induced distribution based on an original
distribution, $\mathbf{p}=\\{p_{k};k\geq 1\\}$, by means of a positive
function $g(p)>0$ on $(0,1)$. Let $p_{k}^{*}=g(p_{k})/\sum_{i\geq 1}g(p_{i})$
for each $k\geq 1$. $\mathbf{p}^{*}=\\{p^{*}_{k};k\geq 1\\}$ is referred to as
an escort distribution. The notion of escort distributions is increasingly
adopted in recent years as a means of describing random behaviors of different
components in a complex system, each of which scans an underlying distribution
$\mathbf{p}=\\{p_{k};k\geq 1\\}$ via a possibly different function $g(p)$. For
a specific function form, $g(p)=p^{\lambda}$ where $\lambda>0$ is a parameter,
the resulting escort distribution,
$\mathbf{p}^{*}=\\{p_{k}^{*}=p_{k}^{\lambda}/\sum_{i\geq
1}p^{\lambda}_{i};k\geq 1\\}$, is known as a power escort distribution.

Applying the power escort transformation to the joint distribution
$\mathbf{p}_{\scalebox{0.7}{X,Y}}$, the resulting distribution is

$\mathbf{p}^{*}_{\scalebox{0.7}{X,Y}}=\left\\{p_{i,j}^{*}=\frac{p_{i,j}^{\lambda}}{\sum_{s\geq
1,t\geq 1}p^{\lambda}_{s,t}};i\geq 1,j\geq 1\right\\}.$ (2)

Let $X^{*}$ and $Y^{*}$ be a pair of random elements on the same joint
alphabet $\mathscr{X}\times\mathscr{Y}$ according to the joint distribution
$\mathbf{p}^{*}_{\scalebox{0.7}{X,Y}}$ of (2). The following lemma is due to
Zhang (2020).

######  Lemma 1.

Given $\lambda>0$,

  1. 1.

$\mathbf{p}_{\scalebox{0.7}{X,Y}}$ and $\mathbf{p}^{*}_{\scalebox{0.7}{X,Y}}$
uniquely determine each other, that is,
$\mathbf{p}_{\scalebox{0.7}{X,Y}}\Leftrightarrow\mathbf{p}^{*}_{\scalebox{0.7}{X,Y}}$;
and

  2. 2.

$X$ and $Y$ are independent if and only if $X^{*}$ and $Y^{*}$ are
independent, that is, $X\perp Y\Leftrightarrow X^{*}\perp Y^{*}$.

By Part 2 of Lemma 1, the null hypothesis, $H_{0}:X\perp Y$ may then be stated
equivalently as $H_{0}:X^{*}\perp Y^{*}$, that is, $MI(X^{*},Y^{*})=0$, or
letting $c_{\lambda,\mathbf{p}}=\sum_{s,t}p_{s,t}^{\lambda}$,

$\sum_{i,j}\left(\frac{p^{\lambda}_{i,j}}{c_{\lambda,\mathbf{p}}}\right)\ln\left(\frac{p^{\lambda}_{i,j}}{c_{\lambda,\mathbf{p}}}\right)-\sum_{i}\left[\left(\frac{\sum_{t}p^{\lambda}_{i,t}}{c_{\lambda,\mathbf{p}}}\right)\ln\left(\frac{\sum_{t}p^{\lambda}_{i,t}}{c_{\lambda,\mathbf{p}}}\right)\right]-\sum_{j}\left[\left(\frac{\sum_{s}p^{\lambda}_{s,j}}{c_{\lambda,\mathbf{p}}}\right)\ln\left(\frac{\sum_{s}p^{\lambda}_{s,j}}{c_{\lambda,\mathbf{p}}}\right)\right]=0.$
(3)

On the other hand, let it be observed that under $H_{0}$,

$\displaystyle c_{\lambda,\mathbf{p}}$
$\displaystyle=\sum_{s,t}p_{s,t}^{\lambda}=\left(\sum_{s}p_{s,\cdot}^{\lambda}\right)\left(\sum_{t}p_{\cdot,t}^{\lambda}\right),$
(4)
$\displaystyle\sum_{i}\left[\left(\frac{\sum_{t}p^{\lambda}_{i,t}}{c_{\lambda,\mathbf{p}}}\right)\ln\left(\frac{\sum_{t}p^{\lambda}_{i,t}}{c_{\lambda,\mathbf{p}}}\right)\right]$
$\displaystyle=\sum_{i}\left[\left(\frac{p^{\lambda}_{i,\cdot}}{\sum_{s}p_{s,\cdot}^{\lambda}}\right)\ln\left(\frac{p^{\lambda}_{i,\cdot}}{\sum_{s}p_{s,\cdot}^{\lambda}}\right)\right],$
(5)
$\displaystyle\sum_{j}\left[\left(\frac{\sum_{s}p^{\lambda}_{s,j}}{c_{\lambda,\mathbf{p}}}\right)\ln\left(\frac{\sum_{s}p^{\lambda}_{s,j}}{c_{\lambda,\mathbf{p}}}\right)\right]$
$\displaystyle=\sum_{j}\left[\left(\frac{p^{\lambda}_{\cdot,j}}{\sum_{t}p_{\cdot,t}^{\lambda}}\right)\ln\left(\frac{p^{\lambda}_{\cdot,j}}{\sum_{t}p_{\cdot,t}^{\lambda}}\right)\right].$
(6)

Let it also be noted that

  1. 1.

(3) is a necessary and sufficient condition, that is, the equality of (3)
holds if and only if $X\perp Y$,

  2. 2.

the equalities in (4), (5) and (6) do not necessarily hold in general but
under the assumption of $H_{0}$.

Adding and subtracting the left-hand sides of (5) and (6) to and from (3),
another restatement of $H_{0}$ is obtained below.

$\displaystyle\left\\{\sum_{i,j}\left(\frac{p^{\lambda}_{i,j}}{c_{\lambda,\mathbf{p}}}\right)\ln\left(\frac{p^{\lambda}_{i,j}}{c_{\lambda,\mathbf{p}}}\right)-\sum_{i}\left[\left(\frac{p^{\lambda}_{i,\cdot}}{\sum_{s}p_{s,\cdot}^{\lambda}}\right)\ln\left(\frac{p^{\lambda}_{i,\cdot}}{\sum_{s}p_{s,\cdot}^{\lambda}}\right)\right]-\sum_{j}\left[\left(\frac{p^{\lambda}_{\cdot,j}}{\sum_{t}p_{\cdot,t}^{\lambda}}\right)\ln\left(\frac{p^{\lambda}_{\cdot,j}}{\sum_{t}p_{\cdot,t}^{\lambda}}\right)\right]\right\\}$
$\displaystyle+\left\\{\sum_{i}\left[\left(\frac{p^{\lambda}_{i,\cdot}}{\sum_{s}p_{s,\cdot}^{\lambda}}\right)\ln\left(\frac{p^{\lambda}_{i,\cdot}}{\sum_{s}p_{s,\cdot}^{\lambda}}\right)\right]+\sum_{j}\left[\left(\frac{p^{\lambda}_{\cdot,j}}{\sum_{t}p_{\cdot,t}^{\lambda}}\right)\ln\left(\frac{p^{\lambda}_{\cdot,j}}{\sum_{t}p_{\cdot,t}^{\lambda}}\right)\right]\right.$
$\displaystyle\hskip
20.00003pt\left.-\sum_{i}\left[\left(\frac{\sum_{t}p^{\lambda}_{i,t}}{c_{\lambda,\mathbf{p}}}\right)\ln\left(\frac{\sum_{t}p^{\lambda}_{i,t}}{c_{\lambda,\mathbf{p}}}\right)\right]-\sum_{j}\left[\left(\frac{\sum_{s}p^{\lambda}_{s,j}}{c_{\lambda,\mathbf{p}}}\right)\ln\left(\frac{\sum_{s}p^{\lambda}_{s,j}}{c_{\lambda,\mathbf{p}}}\right)\right]\right\\}$
$\displaystyle=0.$ (7)

Writing the terms within the curly brackets in (2) as $T_{A}$ and $T_{B}$, (2)
becomes

$T_{A}+T_{B}=0.$ (8)

A natural test for independence would be to statistically check the value of
the left-hand-side in (3), or that in (2), or that in (8), and assess the
statistical evidence against that value being zero. Consider the plug-in
estimator of the the left-hand-side of (8), by replacing $p_{i,j}$ with
$\hat{p}_{i,j}=f_{i,j}/n$ for every pair $(i,j)$, $p_{i,\cdot}$ with
$\hat{p}_{i,\cdot}=\sum_{j}f_{i,j}/n$ for every $i$, and $p_{\cdot,j}$ with
$\hat{p}_{\cdot,j}=\sum_{i}f_{i,j}/n$ for every $j$, resulting in plug-in
estimators of $T_{A}$ and $T_{B}$, denoted by $\hat{T}_{A}$ and $\hat{T}_{B}$.

By Wilks (1938), $2n(\hat{T}_{A}+\hat{T}_{B})\stackrel{{\scriptstyle
p}}{{\rightarrow}}\chi^{2}_{(I-1)(J-1)}$ under $H_{0}$, which implies that

$\sqrt{n}(\hat{T}_{A}+\hat{T}_{B})=\frac{1}{2\sqrt{n}}[2n(\hat{T}_{A}+\hat{T}_{B})]\stackrel{{\scriptstyle
p}}{{\longrightarrow}}0.$ (9)

The following proposition is the keystone of the test to be proposed.

######  Proposition 1.

Suppose neither of the two underlying marginal distributions,
$\mathbf{p}_{\scalebox{0.7}{X}}$ and $\mathbf{p}_{\scalebox{0.7}{Y}}$, is
uniform, and $H_{0}:X\perp Y$ holds.
$\sqrt{n}\hat{T}_{A}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N(0,\sigma^{2})$ as $n\rightarrow\infty$, where
$\sigma^{2}>0$ is a positive constant depending on the parameter
$\lambda\in(0,1)\cup(1,\infty)$.

A proof of Proposition 1 is given in Appendix.

Let $N=\lim_{n\rightarrow\infty}\sqrt{n}\hat{T}_{A}$ denote the normal random
variable under the conditions of Proposition 1. By (9) and Lemma 1,
$-N=\lim_{n\rightarrow\infty}\sqrt{n}\hat{T}_{B}$, where $N$ is the same
random variable as in $N=\lim_{n\rightarrow\infty}\sqrt{n}\hat{T}_{A}$.

######  Proposition 2.

Under the conditions of Proposition 1,

  1. 1.

$Z_{A}=\sqrt{n}\hat{T}_{A}/\hat{\sigma}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N(0,1)$,

  2. 2.

$Z_{B}=\sqrt{n}\hat{T}_{B}/\hat{\sigma}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N(0,1)$, and

  3. 3.

$Z_{AB}=1_{[|Z_{A}|\geq|Z_{B}|]}Z_{A}+1_{[|Z_{A}|<|Z_{B}|]}Z_{B}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N(0,1)$,

where $\hat{\sigma}^{2}$ is the variance given in (12) with all $p_{i,j}$
replaced by $\hat{p}_{i,j}$ for $i\geq 1$ and $j\geq 1$.

At least three tests for $H_{0}:X\perp Y$ are feasible according to
Proposition 2.

  1. 1.

Test 1: $H_{0}$ is rejected if $Z_{A}<-z_{\alpha/2}$ or $Z_{A}>z_{\alpha/2}$;

  2. 2.

Test 2: $H_{0}$ is rejected if $Z_{B}<-z_{\alpha/2}$ or $Z_{B}>z_{\alpha/2}$;
and

  3. 3.

Test 3: $H_{0}$ is rejected if $Z_{AB}<-z_{\alpha/2}$ or $Z_{AB}>z_{\alpha/2}$

where $\alpha\in(0,1)$ is a prefixed constant, $z_{\alpha/2}$ is the
$100\times(1-\alpha/2)$ th percentile of the standard normal distribution. The
test based on $Z_{AB}$ is the proposed test, and it is a consistent test as
described in Proposition 3 below.

######  Proposition 3.

Suppose neither of the two underlying marginal distributions,
$\mathbf{p}_{\scalebox{0.7}{X}}$ and $\mathbf{p}_{\scalebox{0.7}{Y}}$, is
uniform. Then

$\lim_{n\rightarrow\infty}\operatorname{P}(Z_{AB}\in(-\infty,-z_{\alpha/2})\cup(z_{\alpha/2},\infty)|H_{a})=1.$

A proof of Proposition 3 is given in Appendix.

##  3 Simulations

The performance of the proposed test is assessed by simulations. Numerous
simulation studies are carried out for cases with various forms of underlying
distributions. In each case, the proposed test is compared against Pearson’s
chi-squared test, with degrees of freedom $(I-1)(J-1)$ and
$(\hat{I}-1)(\hat{J}-1)$ respectively, with six levels of sample size,
$n=30,100,500,1000,1500$, and $2000$. The results summarized in Table 1 are
representative of the general trends observed and therefore are presented
below.

The sequence of five pairs of $H_{0}$ and $H_{a}$ is specifically constructed
as follows. The example of the $11\times 11$ contingency table in Section 1 is
one of such cases. In that example, the contingency table has $I=11=1+10$ rows
and $J=11=1+10$ columns. A more general distribution may be described as
follows. For a given value $p\in(0,1)$, let both of the row and the column
marginal be $\\{1-p,p/(I-1),p/(I-1),\cdots,p/(I-1)\\}$. A pair of $H_{0}$ and
$H_{a}$ may be constructed as follows.

Under $H_{0}$, a joint distribution is constructed as follows.

$\mathbf{p}_{0}=\left(\begin{array}[]{cccc}(1-p)^{2}&p(1-p)/(I-1)&\cdots&p(1-p)/(I-1)\\\
p(1-p)/(I-1)&p^{2}/(I-1)^{2}&\cdots&p^{2}/(I-1)^{2}\\\
p(1-p)/(I-1)&p^{2}/(I-1)^{2}&\cdots&p^{2}/(I-1)^{2}\\\
\vdots&\vdots&\vdots\hskip 2.0pt\vdots\hskip 2.0pt\vdots&\vdots\\\
p(1-p)/(I-1)&p^{2}/(I-1)^{2}&\cdots&p^{2}/(I-1)^{2}\\\ \end{array}\right).$
(10)

The joint distribution of (10) is reconstructed, first by summing all entries
in the lower-right $(I-1)(J-1)$ sub-matrix and then redistributing the sum on
the diagonal of the sub-matrix uniformly, resulting in

$\mathbf{p}_{a}=\left(\begin{array}[]{cccc}(1-p)^{2}&p(1-p)/(I-1)&\cdots&p(1-p)/(I-1)\\\
p(1-p)/(I-1)&p^{2}/(I-1)&\cdots&0\\\ p(1-p)/(I-1)&0&\ddots&0\\\
\vdots&\vdots&\vdots\hskip 2.0pt\vdots\hskip 2.0pt\vdots&0\\\
p(1-p)/(I-1)&0&\cdots&p^{2}/(I-1)\\\ \end{array}\right).$

Thus, $H_{0}:\mathbf{p}_{0}$ versus $H_{a}:\mathbf{p}_{a}$ becomes a pair.
Letting the parameter $p$ take on values, 0.5, 0.6, 0.7, 0.8, and 0.9,
respectively, the dependence structure in $H_{a}$ becomes weaker and weaker.

The results of the simulation studies are reported in Table 1, each based on
one hundred thousand replicates of iid sample of indicated size $n$, and
$\lambda=2$.

Referring to Table 1, the distribution with $1-p=0.5$ on the top corresponds
to the strongest contrast between $H_{0}$ and $H_{a}$ among all five cases in
the table. For $n=30$ and $n=100$, none of the three test statistics converges
satisfactorily under $H_{0}$ at $\alpha=0.01$. For $n\geq 500$, both the
proposed test and the Pearson’s chi-squared test with observed degrees of
freedom converge satisfactorily under $H_{0}$, and provide very good power at
$H_{a}$. However, the Pearson’s chi-squared test with theoretical degrees of
freedom does not converge under $H_{0}$.

The distribution with $1-p=0.6$ provides a less strong contrast between
$H_{0}$ and $H_{a}$. For $n\geq 500$, both the proposed test and the Pearson’s
chi-squared test with observed degrees of freedom converge satisfactorily
under $H_{0}$, and provide very good power at $H_{a}$. However, the Pearson’s
chi-squared test with theoretical degrees of freedom has a very inflated Type
I error probability. One may also notice that the Pearson’s chi-squared test
with observed degrees of freedom perhaps converges a little slower than the
proposed test under $H_{0}$.

The distribution with $1-p=0.7$ provides an even less strong contrast between
$H_{0}$ and $H_{a}$. For $n\geq 500$, only the proposed test converges
satisfactorily under $H_{0}$, and provide meaningful power at $H_{a}$.
However, both of the Pearson’s chi-squared tests have inflated Type I error
probability.

The distribution with $1-p=0.8$ provides a weak contrast between $H_{0}$ and
$H_{a}$. For $n\geq 500$, the proposed test converges satisfactorily under
$H_{0}$, and provide little power at $H_{a}$. On the other hand, both of the
Pearson’s chi-squared tests have very inflated Type I error probability. One
may also notice that the Pearson’s chi-squared test with observed degrees of
freedom perhaps converges a little slower than the proposed test under
$H_{0}$.

The distribution with $1-p=0.9$ provides a very weak contrast between $H_{0}$
and $H_{a}$. So much so that even for $n\geq 500$, the proposed test converges
very slowly under $H_{0}$, and provides essentially no power at $H_{a}$. On
the other hand, both of the Pearson’s chi-squared tests have a total breakdown
under $H_{0}$.

The following three major points are observed in Table 1, as well as in other
simulation studies investigated but not presented herewithin.

  1. 1.

In small or dense contingency tables, both Pearson’s chi-squared tests
converge quickly under $H_{0}$ and are generally more powerful than the
proposed test.

  2. 2.

In larger and sparse contingency tables, both Pearson’s chi-squared tests
converge much slower under $H_{0}$ and tend to have a much higher probability
of Type I error than what is intended.

All things considered, in practice, if the Rule is satisfied, then Pearson’s
chi-squared test is recommended, otherwise the proposed test of this article
is recommended, provided that $nIJ\geq 5$ or more practically
$n\hat{I}\hat{J}\geq 5$. In that regard, the proposed test is not meant to
replace Pearson’s test in all circumstances, but only when Pearson’s test is
judged not appropriate by the current rule-of-thumb criteria.

##  4 Remarks

The idea of the article may be explained simply by the convergence rate of
$\widehat{MI}(X^{*},Y^{*})$ under $H_{0}$. $\widehat{MI}(X^{*},Y^{*})$ is
$n$-convergent, that is,

$\displaystyle n\widehat{MI}(X^{*},Y^{*})$
$\displaystyle=n[(H(X^{*})+H(Y^{*}))+(-H(X^{*},Y^{*}))]\rightarrow\chi^{2}_{(I-1)(J-1)}/2,\mbox{
and}$ $\displaystyle\sqrt{n}\widehat{MI}(X^{*},Y^{*})$
$\displaystyle=\sqrt{n}[(H(X^{*})+H(Y^{*}))+(-H(X^{*},Y^{*}))]\rightarrow 0.$

In other words, under $H_{0}$, the difference between the two additive parts
of $\widehat{MI}(X^{*},Y^{*})$ approaches zero very fast. However by inserting
a zero in the form of four terms, as in (2), $\widehat{MI}(X^{*},Y^{*})$ is
wedged into two terms, $\hat{T}_{A}$ and $\hat{T}_{B}$, both of which approach
zero under $H_{0}$, but are at a much slower rate, that is,
$\sqrt{n}$-convergent. This insertion is almost literally a keystone,
splitting $\sqrt{n}\widehat{MI}(X^{*},Y^{*})$ into two random variables and
eking out asymptotic normality of $Z_{A}$, of $Z_{B}$, and hence of $Z_{AB}$
under $H_{0}$. The immediate advantages of the normality of $Z_{AB}$ are that
the knowledge of $I$ and $J$ is not required when testing $H_{0}$, and that
the test statistic seems to converge faster than Pearson’s chi-squared test
under $H_{0}$. On the other hand, the statistical assessment of $H_{0}$ is
done by two separate random pieces instead of one, as in $n\widehat{MI}$, and
some efficiency may be lost as evidenced by the simulation studies. The
observed loss of power may be considered a cost for more generality, that is,
the knowledge of $I$ and $J$ is not required.

It is to be noted that the concept of escort distributions is essential in the
arguments leading to the proposed test. Only when $\lambda\neq 1$, the
inserts, the left-hand-sides of (5) and (6), would enable an positive variance
in (12), and hence the asymptotic normality of $Z_{AB}$.

It is also to be highlighted that the proposed test based on $Z_{AB}$ is a
consistent test as stated in Proposition 3. This fact lends the utility of the
proposed test in the general alternative space. That is to say, provided a
sufficiently large sample, any form of dependent structure between $X$ and $Y$
will be detected. The test is proposed herewithin in the form of a two-sided
test due to its generality. For specific forms of dependence structures
between $X$ and $Y$, some of the tests based on $Z_{A}$, $Z_{B}$ or $Z_{AB}$,
one-sided or two-sided, may have better performance in terms of faster
convergence under $H_{0}$ and higher power under $H_{a}$ than others. This
provides a potentially fruitful direction for further investigation.

##  5 Appendix

###### Proof of Proposition 1.

It may be verified that for each pair $(i,j)$, $i=1,\cdots,I-1$, and
$j=1,\cdots,J-1$,

$\displaystyle\frac{\partial T_{A}}{\partial p_{i,j}}=$
$\displaystyle\quad(\ln p^{*}_{I,.}+1)\frac{\lambda p^{*}_{I,.}}{p_{I,.}}-(\ln
p^{*}_{i,.}+1)\frac{\lambda
p^{*}_{i,.}}{p_{i,.}}+\lambda\left[\frac{p^{*}_{I,.}}{p_{I,.}}p^{\lambda-1}_{.,J}-\frac{p^{*}_{i,.}}{p_{i,.}}\right](H(X^{*})-1)$
$\displaystyle+(\ln p^{*}_{.,J}+1)\frac{\lambda p^{*}_{.,J}}{p_{.,J}}-(\ln
p^{*}_{.,j}+1)\frac{\lambda
p^{*}_{.,j}}{p_{.,j}}+\lambda\left[\frac{p^{*}_{.,J}}{p_{.,J}}p^{\lambda-1}_{I,.}-\frac{p^{*}_{.,j}}{p_{.,j}}\right](H(Y^{*})-1)$
$\displaystyle+(\ln p^{*}_{i,j})\frac{\lambda
p^{*}_{i,j}}{p_{i,j}}+\lambda\left(\frac{p^{*}_{i,j}}{p_{i,j}}-\frac{p^{*}_{I,J}}{p_{I,J}}\right)H(X^{*},Y^{*})-\lambda(\ln
p^{*}_{I,J})\frac{p^{*}_{I,J}}{p_{I,J}}$

where $p^{*}_{i,j}$ is defined in (2), $p^{*}_{\cdot,j}=\sum_{i}p^{*}_{i,j}$,
and $p^{*}_{\cdot,j}=\sum_{j}p^{*}_{i,j}$;

for $i=I$, and $j=1,\dots,J-1$,

$\displaystyle\frac{\partial T_{A}}{\partial p_{i=I,j}}=$
$\displaystyle\quad\lambda\frac{p^{*}_{I,.}}{p_{I,.}}\left(p^{\lambda-1}_{.,J}-p^{\lambda-1}_{.,j}\right)(H(X^{*})-1)$
$\displaystyle+(\ln p^{*}_{.,J}+1)\frac{\lambda p^{*}_{.,J}}{p_{.,J}}-(\ln
p^{*}_{.,j}+1)\frac{\lambda
p^{*}_{.,j}}{p_{.,j}}+\lambda\left(\frac{p^{*}_{.,J}}{p_{.,J}}p^{\lambda-1}_{I,.}-\frac{p^{*}_{.,j}}{p_{.,j}}\right)(H(Y^{*})-1)$
$\displaystyle+(\ln p^{*}_{I,j})\frac{\lambda
p^{*}_{I,j}}{p_{I,j}}+\lambda\left(\frac{p^{*}_{I,j}}{p_{I,j}}-\frac{p^{*}_{I,J}}{p_{I,J}}\right)H(X^{*},Y^{*})-\lambda(\ln
p^{*}_{I,J})\frac{p^{*}_{I,J}}{p_{I,J}}$

and for $i=1,\dots,I-1$, and $j=J$,

$\displaystyle\frac{\partial T_{A}}{\partial p_{i,J}}=$
$\displaystyle\quad(\ln p^{*}_{I,.}+1)\frac{\lambda p^{*}_{I,.}}{p_{I,.}}-(\ln
p^{*}_{i,.}+1)\frac{\lambda
p^{*}_{i,.}}{p_{i,.}}+\lambda\left(\frac{p^{*}_{I,.}}{p_{I,.}}p^{\lambda-1}_{.,J}-\frac{p^{*}_{i,.}}{p_{i,.}}\right)(H(X^{*})-1)$
$\displaystyle+\lambda\frac{p^{*}_{.,J}}{p_{.,J}}\left(p^{\lambda-1}_{I,.}-p^{\lambda-1}_{i,.}\right)(H(Y^{*})-1)$
$\displaystyle+(\ln p^{*}_{i,J})\frac{\lambda
p^{*}_{i,J}}{p_{i,J}}+\lambda\left(\frac{p^{*}_{i,J}}{p_{i,J}}-\frac{p^{*}_{I,J}}{p_{I,J}}\right)H(X^{*},Y^{*})-\lambda(\ln
p^{*}_{I,J})\frac{p^{*}_{I,J}}{p_{I,J}}$

Let

$\displaystyle\mathbf{v}=(v_{1},\cdots,v_{IJ-1})^{\tau}=\left(p_{1,1},p_{1,2}.\cdots,p_{1,J},p_{2,1},p_{2,2},\cdots,p_{2,J},\cdots,p_{I,1},p_{I,2},\cdots,p_{I,J-1}\right)^{\tau},$
$\displaystyle\hat{\mathbf{v}}=(\hat{v}_{1},\cdots,\hat{v}_{IJ-1})^{\tau}=\left(\hat{p}_{1,1},\hat{p}_{1,2}.\cdots,\hat{p}_{1,J},\hat{p}_{2,1},\hat{p}_{2,2},\cdots,\hat{p}_{2,J},\cdots,\hat{p}_{I,1},\hat{p}_{I,2},\cdots,\hat{p}_{I,J-1}\right)^{\tau},$

noting specifically the implied enumeration of the indexes of $\mathbf{v}$
corresponds to the arrangement of $(i,j)$ as in $p_{i,j}$, that is,

$\\{1,2,\cdots,IJ-1\\}=\\{(1,1),\cdots,(1,J),(2,1),\cdots,(2,J),\cdots,(I-1,J),(I,1),\cdots,(I,J-1)\\}.$
(11)

Let the gradient of $T_{A}$ with respect to $p_{i,j}$ for all $(i,j)$ be
denoted by $\nabla=\\{\partial T_{A}/\partial p_{i,j}\\}$ with the index
arrangement given in (11).

It follows that $\sqrt{n}(\hat{\mathbf{v}}-\mathbf{v})\stackrel{{\scriptstyle
d}}{{\rightarrow}}MVN(\mathbf{0},\Sigma(\mathbf{v}))$, where
$\Sigma(\mathbf{v})$ is the $(IJ-1)\times(IJ-1)$ covariance matrix given by

$\displaystyle\Sigma=\Sigma(\mathbf{v})=\left(\begin{array}[]{cccc}v_{1}\left(1-v_{1}\right)&-v_{1}v_{2}&\cdots&-v_{1}v_{IJ-1}\\\
-v_{2}v_{1}&v_{2}\left(1-v_{2}\right)&\cdots&-v_{2}v_{IJ-1}\\\
\vdots&\vdots&\vdots\hskip 2.0pt\vdots\hskip 2.0pt\vdots&\vdots\\\
-v_{IJ-1}v_{1}&-v_{IJ-1}v_{2}&\cdots&v_{IJ-1}\left(1-v_{IJ-1}\right)\end{array}\right)$

According to the first-order delta method,
$\sqrt{n}\hat{T}_{A}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N(0,\sigma^{2})$, as $n\rightarrow\infty$, where

$\sigma^{2}=\nabla^{\tau}\Sigma\nabla.$ (12)

∎

###### Proof of Proposition 3.

Under $H_{a}:X\not\perp Y$, by Lemma 1, $T_{A}+T_{B}=\mu_{\mathbf{p}}>0$ where
$T_{A}$ and $T_{B}$ are as in (8). By the respective consistencies of plug-in
estimators of $T_{A}$, $T_{B}$ and $\sigma^{2}$,
$\hat{T}_{A}+\hat{T}_{B}\stackrel{{\scriptstyle
p}}{{\rightarrow}}\mu_{\mathbf{p}}>0$, and hence
$\sqrt{n}\hat{T}_{A}/\hat{\sigma}+\sqrt{n}\hat{T}_{A}/\hat{\sigma}=Z_{A}+Z_{B}\stackrel{{\scriptstyle
p}}{{\rightarrow}}\infty$, which in turn implies that at least one of $Z_{A}$
and $Z_{B}$ is carried above all bounds in probability, which finally implies
that $Z_{AB}\stackrel{{\scriptstyle p}}{{\rightarrow}}\infty$, as
$n\rightarrow\infty$. ∎

Distribution | Sample Size | $Z_{AB}:H_{0},H_{a}$ | $\chi^{2}_{(\hat{I}-1)(\hat{J}-1)}:H_{0},H_{a}$ | $\chi^{2}_{(I-1)(J-1)}:H_{0},H_{a}$
---|---|---|---|---
$1-p=0.50$ |  $n$ = 30 | 0.2002 | 0.3235 | 0.0632 | 0.4377 | 0.0831 | 0.0694
$n$ = 100 | 0.0561 | 0.7739 | 0.0373 | 0.9951 | 0.0439 | 0.9940
$n$ = 500 | 0.0145 | 1.0000 | 0.0124 | 1.0000 | 0.2058 | 1.0000
$n$ = 1000 | 0.0122 | 1.0000 | 0.0113 | 1.0000 | 0.1437 | 1.0000
$n$ = 1500 | 0.0122 | 1.0000 | 0.0109 | 1.0000 | 0.10841 | 1.0000
$n$ = 2000 | 0.0113 | 1.0000 | 0.0098 | 1.0000 | 0.0858 | 1.0000
$1-p=0.60$ |  $n$ = 30 | 0.0540 | 0.0862 | 0.0968 | 0.2811 | 0.0021 | 0.0133
$n$ = 100 | 0.0071 | 0.0965 | 0.0764 | 0.8760 | 0.0997 | 0.8515
$n$ = 500 | 0.0087 | 0.9267 | 0.0183 | 1.0000 | 0.0767 | 1.0000
$n$ = 1000 | 0.0105 | 0.9997 | 0.0143 | 1.0000 | 0.0412 | 1.0000
$n$ = 1500 | 0.0103 | 1.0000 | 0.0123 | 1.0000 | 0.0316 | 1.0000
$n$ = 2000 | 0.0102 | 1.0000 | 0.0120 | 1.0000 | 0.0263 | 1.0000
$1-p=0.70$ |  $n$ = 30 | 0.0040 | 0.0054 | 0.1352 | 0.2118 | 0.0002 | 0.0020
$n$ = 100 | 0.0003 | 0.0011 | 0.1400 | 0.5563 | 0.0966 | 0.4720
$n$ = 500 | 0.0081 | 0.1324 | 0.0320 | 1.0000 | 0.0320 | 1.0000
$n$ = 1000 | 0.0096 | 0.4032 | 0.0200 | 1.0000 | 0.0200 | 1.0000
$n$ = 1500 | 0.0102 | 0.6541 | 0.0168 | 1.0000 | 0.0168 | 1.0000
$n$ = 2000 | 0.0104 | 0.8196 | 0.0151 | 1.0000 | 0.0151 | 1.0000
$1-p=0.80$ |  $n$ = 30 | 0.0021 | 0.0027 | 0.1697 | 0.1941 | 0.00213 | 0.0027
$n$ = 100 | 0.0000 | 0.0000 | 0.2082 | 0.3369 | 0.0997 | 0.1977
$n$ = 500 | 0.0086 | 0.0189 | 0.0768 | 0.9426 | 0.0767 | 0.9426
$n$ = 1000 | 0.0104 | 0.0389 | 0.0412 | 0.9999 | 0.0412 | 0.9999
$n$ = 1500 | 0.0108 | 0.0586 | 0.0316 | 1.0000 | 0.0316 | 1.0000
$n$ = 2000 | 0.0109 | 0.0813 | 0.0263 | 1.0000 | 0.0263 | 1.0000
$1-p=0.90$ |  $n$ = 30 | 0.0831 | 0.0822 | 0.2326 | 0.2337 | 0.0832 | 0.0822
$n$ = 100 | 0.0000 | 0.0000 | 0.2386 | 0.2519 | 0.0439 | 0.0532
$n$ = 500 | 0.0213 | 0.0222 | 0.2120 | 0.4037 | 0.2058 | 0.3966
$n$ = 1000 | 0.0202 | 0.0227 | 0.1437 | 0.6408 | 0.1437 | 0.6407
$n$ = 1500 | 0.0162 | 0.0212 | 0.1084 | 0.8330 | 0.1084 | 0.8330
$n$ = 2000 | 0.0158 | 0.0206 | 0.0854 | 0.9385 | 0.0854 | 0.9385

Table 1: Simulated Convergence and Power Comparison, $I=J=11$, $\alpha=0.01$

## References

  * (1)
  * Agresti (2003) Agresti, A. (2003), Categorical data analysis, John Wiley & Sons.
  * Beck & Schögl (1995) Beck, C. & Schögl, F. (1995), Thermodynamics of chaotic systems.
  * Cochran (1952) Cochran, W. G. (1952), ‘The $\chi$2 test of goodness of fit’, The Annals of mathematical statistics pp. 315–345.
  * Cochran (1954) Cochran, W. G. (1954), ‘Some methods for strengthening the common $\chi$ 2 tests’, Biometrics 10(4), 417–451.
  * Shannon (1948) Shannon, C. E. (1948), ‘A mathematical theory of communication’, The Bell system technical journal 27(3), 379–423.
  * Wilks (1938) Wilks, S. S. (1938), ‘The large-sample distribution of the likelihood ratio for testing composite hypotheses’, The annals of mathematical statistics 9(1), 60–62.
  * Yates et al. (1999) Yates, D., Moore, D. & McCabe, G. (1999), ‘The practice of statistics. new york, ny: H’.
  * Zhang (2016) Zhang, Z. (2016), Statistical Implications of Turing’s Formula, John Wiley & Sons.
  * Zhang (2020) Zhang, Z. (2020), ‘Generalized mutual information’, Stats 3(2), 158–165.