# Evaluating Pauli errors on cluster states by weighted distances

Choong Pak Shen  UCSI College, Lot 39890, Jalan Cerdas Taman Connaught Cheras,
56000 Kuala Lumpur, Malaysia  Institute for Mathematical Research, Universiti
Putra Malaysia, 43400 Serdang, Selangor, Malaysia  Davide Girolami
Politecnico di Torino, Corso Duca Degli Abruzzi, 24, 10129 Torino, Italy

###### Abstract

We address the problem of evaluating the difference between quantum states
before and after being affected by errors encoded in unitary transformations.
Standard distance functions, e.g., the Bures length, are not fully adequate
for such a task. Weighted distances are instead appropriate information
measures to quantify distinguishability of multipartite states. Here, we
employ the previously introduced weighted Bures length and the newly defined
weighted Hilbert-Schmidt distance to quantify how much single-qubit Pauli
errors alter cluster states. We find that different errors of the same
dimension change cluster states in a different way, i.e., their detectability
is in general different. Indeed, they transform an ideal cluster state into a
state whose weighted distance from the input depends on the specific chosen
Pauli rotation, as well as the position of the affected qubit in the graph
related to the state. As these features are undetected by using standard
distances, the study proves the usefulness of weighted distances to monitor
key but elusive properties of many-body quantum systems.

## Introduction

Quantifying the difference between quantum states is a critical task in both
theoretical and experimental quantum information processing. Indeed, several
quantifiers of state difference have been invented [1]. An important class of
them is represented by geometric distance functions, which are built to
compare the physical properties of different configurations in terms of their
distance in the abstract space of all possible quantum states of a system [2,
3].

Despite their wide applicability and obvious importance, such “standard”
distances are not fully adequate to investigate quantum states of many
particles, as they do not take into account their dimension. For such a
reason, the concept of weighted distances has been introduced [4]. These
quantities satisfy a set of desirable mathematical properties, just as
standard distances, while factoring in the dimension of the system under
scrutiny and, at the same time, the size of the apparatuses that implement
appropriate discriminating measurements.

In particular, the weighted Bures length has a compelling operational
interpretation: It quantifies the difficulty in distinguishing two quantum
states by the most informative measurements. Subsequent studies have found
that the weighted Bures length between the input and output states of a
computation quantifies the complexity of the process [5], and signals chaotic
behaviour in quantum dynamics [6, 7].

In this paper, we expand the use of weighted distances, by applying them to
evaluate the difficulty of detecting errors, i.e., uncontrollable, unwanted
changes of a state. Specifically, we calculate the weighted Bures length, and
a newly introduced weighted Hilbert-Schmidt distance, between cluster states
of three, four, and five qubits, and the same states after they have undergone
unplanned single-qubit unitary rotations (“Pauli errors”). Cluster states are
an important class of states that are entangled even when information about
some system components is lost. That is, they are “robust”, as they display
genuine multipartite entanglement [8, 9, 10]. Also, they are the resource to
perform one-way quantum computations [11, 12, 13].

Our results show that there exists a hierarchy between unitary errors in terms
of their effects on an initial, ideal cluster state. Specifically, input
cluster states are sent by single-qubit Pauli errors into output states whose
weighted distance from the input depends on the chosen Pauli error. That is,
our ability to detect when a cluster state has been corrupted depends on the
specific error.
Moreover, we observe another surprising feature. As the number of qubits
increases, phase flips (Pauli-$Z$ errors) that affect “central” qubits of one-
dimensional cluster states send the system into a state that is closer to the
input state in comparison with phase flips affecting “peripheral” qubits.
Centrally located errors are therefore more difficult to detect, somehow
hidden in the structure of the system.
Remarkably, both results are independent of the employed weighted distance, as
they describe how errors change subsystems of different size within systems
prepared in cluster states. Also, neither phenomena can be observed by using
any standard distances.

It is important to note that state transformation and state discrimination are
“quite different tasks” [14]. Indeed, every single unitary error can be
corrected by reapplying the very same unitary. More generally, quantifiers of
the complexity of an input/output transformation (how difficult it is to
transform quantum states) and input/output distinguishability (how difficult
it is to distinguish quantum states) are in general different kinds of
information measures. Yet, the weighted Bures length, which reliably evaluates
our ability to discriminate between two states via measurements, is also a
lower bound to the experimental cost, in terms of physical resources, to
transform the states into each other [4].

The paper is organized as follows. In Section I, we review the notion of
weighted distances and their advantages with respect to standard geometric
quantifiers of state difference. First, we recall the definition of Bures
length introduced in [4]. Then, we introduce the computationally friendly
weighted Hilbert-Schmidt distance and prove some properties that inherits from
the related standard distance. In Section II, we present a case study: We
evaluate the difference between cluster states plagued by unitary errors and
their textbook form in terms of their weighted distances. In the Conclusion,
we draw our final comments and suggest further lines of research.

##  I From standard distances to weighted distances

The difference between quantum states, e.g., between a target configuration
and what one actually implements in an experiment, is customarily quantified
by means of state fidelity. The fidelity between two pure states is indeed
equivalent to the state overlap:

$\displaystyle
F(\left|\psi\right\rangle,\,\left|\phi\right\rangle)=\left|\langle\psi|\phi\rangle\right|^{2}.$
(1)

Remarkably, the overlap has a geometric interpretation, being related to the
Fubini-Study distance
$\cos^{-1}\sqrt{F(\left|\psi\right\rangle,\,\left|\phi\right\rangle)}$ [1, 15,
16, 17]. Generalizing the fidelity to mixed states [18, 20, 19, 21], one has

$\displaystyle
F(\rho,\,\sigma)=\left(\text{Tr}\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\right)^{2}.$
(2)

Among many distance functions for mixed states, the Bures length between two
density matrices $\rho,\sigma$ is the natural generalization of the Fubini-
Study distance:

$\displaystyle B(\rho,\,\sigma)=\text{cos}^{-1}\sqrt{F(\rho,\,\sigma)}.$ (3)

State fidelity and Bures length are ubiquitous in quantum information theory.
They are well motivated quantities, as they provably quantify the difficulty
in discriminating quantum states by means of a single measurement on the
global system. Further, they are the most popular quantifiers of how close an
engineered quantum state, say $\rho_{N}$, is to the desired target
$\sigma_{N}$.

Yet, they are not fully satisfactory metrics when one wants to compare states
of multipartite quantum systems. Consider for example the following quantum
states:

$\displaystyle\left|0\right\rangle^{\otimes N},\left|0\right\rangle^{\otimes
N-k}\left|1\right\rangle^{\otimes k}.$

If we evaluate their difference by means of their Bures length, they are
maximally far for any value of $k$. Yet, the larger is $k$, the easier it is
to experimentally distinguish them, as there are more (local) measurements
that enable to discriminate between these two states. In general, overlap-
based distances reach maximal value when two global states are orthogonal, no
matter how close the marginal density matrices may be. Another relevant
example is the comparison between a state of $N$ qubits that displays maximal
entanglement, say a GHZ state, with a classically correlated mixed state:

$\displaystyle\left(|0\rangle^{\otimes N}+|1\rangle^{\otimes
N}\right)/\sqrt{2},\,\,\frac{1}{2}\left(|0\rangle\langle 0|^{\otimes
N}+|1\rangle\langle 1|^{\otimes N}\right).$

The difficulty of experimentally discriminating these two states increases
with $N$, as only global measurements over all qubits would output different
data, while the Bures length between them is independent of the system size.

In order to overcome these issues, while retaining the explanatory power of
distance functions, the concept of weighted distances was introduced [4]. They
are generalizations of standard distances that take into account the size of
both the system and the possible measurements one can perform on it.

We review the construction of the weighted Bures length between two
preparations $\rho_{N},\sigma_{N}$ of an $N$-particle system (see [4] for full
details), while the argument applies to any distance function. Suppose
cooperating agents independently measure on different subsystems
$k_{\alpha}\leq N$ of two copies of the system, which are prepared in the
states $\rho_{N},\sigma_{N}$, respectively. Each agent evaluates the
difference between two states of the assigned subsystem by the Bures length
$B(\rho_{k_{\alpha}},\,\sigma_{k_{\alpha}})$. In particular, they perform the
optimal measurement ${\cal
M}^{k_{\alpha}}=\rho_{k_{\alpha}}^{-1/2}\sqrt{\rho_{k_{\alpha}}^{1/2}\sigma_{k_{\alpha}}\rho_{k_{\alpha}}^{1/2}}\rho_{k_{\alpha}}^{-1/2}$
to discriminate the marginal states of $k_{\alpha}$ particles. The setup
defines a measurement partition $P_{k_{\alpha}}:=\left\\{{\cal
M}^{k_{\alpha}},\,\sum_{a}\,k_{\alpha}=N\right\\}$.

Then, one builds a weighted sum of each agent contribution
$B(\rho_{k_{\alpha}},\,\sigma_{k_{\alpha}})$, assigning a weight
$1/k_{\alpha}$ to each of them, i.e., evaluating their importance as inversely
proportional to the size of the related subsystem. The reason is the
following: One can quantify the difficulty in realizing a measurement with the
size of the measured subsystem $k_{\alpha}$. As a distance must quantify how
easy it is to distinguish the two states, i.e., how easy it is to
experimentally carry out the related measurement, a sound choice of weights is
$1/k_{\alpha}$. Finally, one defines the weighted Bures length by optimizing
the measurement strategy, which implies to maximize the weighted sum of local
distances over all possible partitions:

$\displaystyle
D_{B}(\rho,\,\sigma):=\max\limits_{P_{k_{\alpha}}}\sum_{a}\frac{1}{k_{\alpha}}B\left(\rho_{k_{\alpha}},\,\sigma_{k_{\alpha}}\right).$
(4)

The weighted Bures length meets a set of desirable properties:

  * •

$D_{B}\rho_{N},\sigma_{N})\geq 0$ (non-negativity)

  * •

$D_{B}(\rho_{N},\sigma_{N})=0\iff\rho_{N}=\sigma_{N}$ (faithfulness)

  * •

$D_{B}(\rho_{N},\sigma_{N})\geq
D(\Lambda_{1}(\rho_{N}),\Lambda_{1}(\sigma_{N})),\,\,\forall\Lambda_{1}$
(contractivity under single qubit operations $\Lambda_{1}$)

  * •

$D_{B}(\rho_{N},\sigma_{N})\leq
D_{B}(\rho_{N},\tau_{N})+D_{B}(\tau_{N},\sigma_{N})$ (triangle inequality)

The weighted Bures length has also a second operational meaning that is not
shared by the standard Bures length. It is shown to be the lower bound of
experimental cost of the state transformation
$\rho_{N}=U\sigma_{N}U^{\dagger},U=e^{-i\,H\,t}$:

$N\,E\,t\geq D_{B}(\rho_{N},\sigma_{N}),$ (5)

in which $E=(\lambda_{max}-\lambda_{min})/2$, being $\lambda_{max(min)}$ the
largest (smallest) eigenvalue of the Hamiltonian. Hence, the weighted Bures
length lower bounds the cost of transforming $\rho_{N}$ into $\sigma_{N}$ (and
vice versa), as quantified by the product of the size of the system $N$, the
energy parameter $E$, and the available time $t$ [4].

While the weighted Bures length enjoys important properties, one can build a
parent weighted distance for each standard one. Here, we define the weighted
Hilbert-Schmidt distance:

$\displaystyle
D_{HS}(\rho_{N},\sigma_{N}):=\max\limits_{P_{k_{\alpha}}}\sum_{a}\frac{1}{k_{\alpha}}d_{HS}(\rho_{k_{\alpha}},\sigma_{k_{\alpha}}),$
(6)

where $d_{HS}$ is the (square root of the) standard Hilbert-Schmidt distance,
defined as

$\displaystyle
d_{HS}(\rho_{N},\sigma_{N}):=\sqrt{\text{Tr}\left(\rho_{N}^{2}+\sigma_{N}^{2}-2\,\rho_{N}\sigma_{N}\right)}.$
(7)

Note that the square root is here crucial. We will run a numerical comparison
with the weighted Bures length, so both quantities need to be functions of the
state eigenvalues elevated to the same powers. The weighted Hilbert-Schmidt
distance inherits the following properties:

  * •

$D_{HS}(\rho_{N},\sigma_{N})\geq 0$ (non-negativity)
Proof: A weighted distance is the sum of standard distances with positive
weights, so the property is satisfied.

  * •

$D_{HS}(\rho_{N},\sigma_{N})=0\iff\rho_{N}=\sigma_{N}$ (faithfulness)
Proof: Since all the weights are positive, the weighted sum for an arbitrary
partition $P_{k_{\alpha}}$ is non-zero if and only if there is at least a non-
zero term $d_{HS}(\rho_{k_{\alpha}},\sigma_{k_{\alpha}})$. Hence, the claim is
proven.

  * •

$D_{HS}(\rho_{N},\sigma_{N})\leq
D_{HS}(\rho_{N},\tau_{N})+D_{HS}(\tau_{N},\sigma_{N})$ (triangle inequality)
Proof: For an arbitrary term of the weighted sum related to an arbitrary
partition, one has
$\frac{1}{k_{\alpha}}d_{HS}\left(\rho_{k_{\alpha}},\sigma_{k_{\alpha}}\right)\leq\frac{1}{k_{\alpha}}\left\\{d_{HS}\left(\rho_{k_{\alpha}},\tau_{k_{\alpha}}\right)+d_{HS}\left(\tau_{k_{\alpha}},\sigma_{k_{\alpha}}\right)\right\\}$.
Calling $\hat{k}_{\alpha}$ the weights related to the partition that maximizes
the weighted sum of the terms
$d_{HS}\left(\rho_{k_{\alpha}},\sigma_{k_{\alpha}}\right)$, one has

$\displaystyle D_{HS}(\rho_{N},\sigma_{N})$
$\displaystyle=\sum_{\alpha}\frac{1}{\hat{k}_{\alpha}}d_{HS}\left(\rho_{\hat{k}_{\alpha}},\sigma_{\hat{k}_{\alpha}}\right)$
$\displaystyle\leq\sum_{\alpha}\frac{\left\\{d_{HS}\left(\rho_{\hat{k}_{\alpha}},\tau_{\hat{k}_{\alpha}}\right)+d_{HS}\left(\tau_{\hat{k}_{\alpha}},\sigma_{\hat{k}_{\alpha}}\right)\right\\}}{\hat{k}_{\alpha}}$
$\displaystyle\leq D_{HS}(\rho_{N},\tau_{N})+D_{HS}(\tau_{N},\sigma_{N}).$

Note that the weighted Hilbert-Schmidt distance is not monotonically
decreasing under local operations, as the related standard distance can
increase under noisy channels [2, 22]. Yet, since the Hilbert-Schmidt distance
is a function of purities of the states and their overlaps, it is manifestly
easy to compute. Also, it is experimentally friendly. Indeed, state purities
and overlaps can be quantified without full state tomography and full spectrum
reconstruction [23, 25, 26, 24, 27, 28, 29].

In the next section, we will run a comparison of these two quantities to
evaluate the difference between an ideal state and its corrupted version. We
will observe that the same subset of single-qubit Pauli errors generate states
closer to an input cluster state according to both the weighted Bures length
and the weighted Hilbert-Schmidt distance, even if the latter is not in
general contractive under quantum channels.

##  II Case Study: Evaluation of unitary errors in cluster states by weighted
distances

123 | 1234
---|---
(a) | (b)
12345 | 1234
(c) | (d)
Table 1: Graphs (a)-(d) depict the four different configurations of cluster
states that are here under scrutiny.

###  II.1 Cluster states and Pauli errors

Cluster states are a subset of graph states which are simultaneous eigenstates
with eigenvalue one of commuting Pauli operators. They can be employed to
perform one-way (also called “measurement-based”) quantum computations [11,
12, 13]. By using the stabilizer formalism, the density matrix of $N$-qubit
cluster states can be written in a compact form [9, 30]:

$\displaystyle\rho=\prod_{i=1}^{N}\frac{I_{i}+g_{i}}{2},$ (8)

where $I_{i}$ is the bidimensional identity matrix and
$g_{i}=X_{i}\bigotimes_{j\in N(i)}Z_{j}$ are the stabilizing operators. Here,
$X_{i}$ and $Z_{j}$ are Pauli $X$ and $Z$ matrices, respectively, while $N(i)$
denotes the neighbourhood of $i$-th qubit (consisting of all the qubits that
are adjacent to the $i$-th qubit in the graphical representation of the
state). Each cluster state represents a specific correlation structure of
qubits placed at vertices of a lattice.

The stabilizer formalism of graph states, including cluster states, allows us
to write their reduced density matrices in terms of their stabilizers [8, 10].
For the sake of clarity, we provide the Reader with the explicit expressions
of the global and marginal density matrices of the cluster states that we
selected for this study (identity matrices are omitted when possible, e.g.,
$X_{1}X_{2}\equiv X_{1}X_{2}I_{345}$), which are also depicted in Figure 1.

Three-qubit one-dimensional cluster states:

$\displaystyle\rho_{123}$
$\displaystyle=\frac{1}{8}(I_{123}+X_{1}Z_{2})(I_{123}+Z_{1}X_{2}Z_{3})(I_{123}+Z_{2}X_{3})$
$\displaystyle=\frac{1}{8}(I_{123}+Z_{2}X_{3}+X_{1}Z_{2}+X_{1}X_{3}$
$\displaystyle\quad+Z_{1}X_{2}Z_{3}+Z_{1}Y_{2}Y_{3}+Y_{1}Y_{2}Z_{3}-Y_{1}X_{2}Y_{3}),$
$\displaystyle\rho_{12}$ $\displaystyle=\frac{1}{4}(I_{12}+X_{1}Z_{2}),$
$\displaystyle\rho_{13}$ $\displaystyle=\frac{1}{4}(I_{13}+X_{1}X_{3}),$
$\displaystyle\rho_{23}$ $\displaystyle=\frac{1}{4}(I_{23}+Z_{2}X_{3}).$

Four-qubit one-dimensional cluster states:

$\displaystyle\rho_{1234}^{1D}$
$\displaystyle=\frac{1}{16}(I_{1234}+X_{1}Z_{2})(I_{1234}+Z_{1}X_{2}Z_{3})$
$\displaystyle\quad(I_{1234}+Z_{2}X_{3}Z_{4})(I_{1234}+Z_{3}X_{4})$
$\displaystyle=\frac{1}{16}(I_{1234}+Z_{3}X_{4}+X_{1}Z_{2}+Z_{2}X_{3}Z_{4}+Z_{2}Y_{3}Y_{4}$
$\displaystyle\quad+Z_{1}X_{2}Z_{3}+Z_{1}X_{2}X_{4}+X_{1}X_{3}Z_{4}+X_{1}Y_{3}Y_{4}$
$\displaystyle\quad+Y_{1}Y_{2}Z_{3}+Y_{1}Y_{2}X_{4}+Z_{1}Y_{2}Y_{3}Z_{4}-Z_{1}Y_{2}X_{3}Y_{4}$
$\displaystyle\quad+X_{1}Z_{2}Z_{3}X_{4}-Y_{1}X_{2}Y_{3}Z_{4}+Y_{1}X_{2}X_{3}Y_{4}),$
$\displaystyle\rho_{123}^{1D}$
$\displaystyle=\frac{1}{8}(I_{123}+X_{1}Z_{2})(I_{123}+Z_{1}X_{2}Z_{3}),$
$\displaystyle\rho_{124}^{1D}$
$\displaystyle=\frac{1}{8}(I_{124}+X_{1}Z_{2})(I_{124}+Z_{1}X_{2}X_{4}),$
$\displaystyle\rho_{134}^{1D}$
$\displaystyle=\frac{1}{8}(I_{134}+Z_{3}X_{4})(I_{134}+X_{1}X_{3}Z_{4}),$
$\displaystyle\rho_{234}^{1D}$
$\displaystyle=\frac{1}{8}(I_{234}+Z_{2}X_{3}Z_{4})(I_{234}+Z_{3}X_{4}),$
$\displaystyle\rho_{12}^{1D}$ $\displaystyle=\frac{1}{4}(I_{12}+X_{1}Z_{2}),$
$\displaystyle\rho_{34}^{1D}$ $\displaystyle=\frac{1}{4}(I_{34}+Z_{3}X_{4}),$
$\displaystyle\rho_{13}^{1D}$
$\displaystyle=\rho_{14}^{1D}=\rho_{23}^{1D}=\rho_{24}^{1D}=\frac{1}{4}I_{ij,\,\,i=1,2,j=3,4}.$

Four-qubit two-dimensional cluster states:

$\displaystyle\rho_{1234}^{2D}$
$\displaystyle=\frac{1}{16}(I_{1234}+Z_{4}X_{1}Z_{2})(I_{1234}+Z_{1}X_{2}Z_{3})$
$\displaystyle\quad(I_{1234}+Z_{2}X_{3}Z_{4})(I_{1234}+Z_{1}X_{4}Z_{3})$
$\displaystyle=\frac{1}{16}(I_{1234}+X_{1}X_{3}+X_{2}X_{4}+Z_{1}X_{4}Z_{3}+Z_{2}X_{3}Z_{4}$
$\displaystyle\quad-
Y_{2}X_{3}Z_{4}+X_{1}Z_{2}Z_{4}-Y_{1}Y_{3}X_{4}-X_{1}Y_{2}Y_{4}$
$\displaystyle\quad-
Y_{1}X_{2}Y_{3}+Z_{1}X_{2}Z_{3}+Z_{1}Z_{2}Y_{3}Y_{4}+Z_{1}Y_{2}Y_{3}Z_{4}$
$\displaystyle\quad+Y_{1}Z_{2}Z_{3}Y_{4}+Y_{1}Y_{2}Z_{3}Z_{4}+X_{1}X_{2}X_{3}X_{4}),$
$\displaystyle\rho_{123}^{2D}$
$\displaystyle=\frac{1}{8}(I_{123}+Z_{1}X_{2}Z_{3})(I_{123}+X_{1}X_{3}),$
$\displaystyle\rho_{124}^{2D}$
$\displaystyle=\frac{1}{8}(I_{124}+Z_{4}X_{1}Z_{2})(I_{124}+X_{2}X_{4}),$
$\displaystyle\rho_{134}^{2D}$
$\displaystyle=\frac{1}{8}(I_{134}+Z_{1}X_{4}Z_{3})(I_{134}+X_{1}X_{3}),$
$\displaystyle\rho_{234}^{2D}$
$\displaystyle=\frac{1}{8}(I_{234}+Z_{2}X_{3}Z_{4})(I_{234}+X_{2}X_{4}),$
$\displaystyle\rho_{13}^{2D}$ $\displaystyle=\frac{1}{4}(I_{13}+X_{1}X_{3}),$
$\displaystyle\rho_{24}^{2D}$ $\displaystyle=\frac{1}{4}(I_{24}+X_{2}X_{4}),$
$\displaystyle\rho_{12}^{2D}$
$\displaystyle=\rho_{14}^{2D}=\rho_{23}^{2D}=\rho_{34}^{2D}=\frac{1}{4}I_{ij,\,\,ij=\\{12,14,23,34\\}}.$

Five-qubit one-dimensional cluster states:

$\displaystyle\rho_{12345}$
$\displaystyle=\frac{1}{32}(I_{12345}+X_{1}Z_{2})(I_{12345}+Z_{1}X_{2}Z_{3})$
$\displaystyle\quad(I_{12345}+Z_{2}X_{3}Z_{4})(I_{12345}+Z_{3}X_{4}Z_{5})$
$\displaystyle\quad(I_{12345}+Z_{4}X_{5})$
$\displaystyle=\frac{1}{32}(I_{12345}+Z_{4}X_{5}+X_{1}Z_{2}+Z_{3}X_{4}Z_{5}+Z_{3}Y_{4}Y_{5}$
$\displaystyle\quad+Z_{2}X_{3}Z_{4}+Z_{2}X_{3}X_{5}+Z_{1}X_{2}Z_{3}+X_{1}X_{3}Z_{4}$
$\displaystyle\quad+X_{1}X_{3}X_{5}+Y_{1}Y_{2}Z_{3}+Z_{2}Y_{3}Y_{4}Z_{5}$
$\displaystyle\quad-
Z_{2}Y_{3}X_{4}Y_{5}+Z_{1}X_{2}X_{4}Z_{5}+Z_{1}X_{2}Y_{4}Y_{5}$
$\displaystyle\quad+Z_{1}Y_{2}Y_{3}Z_{4}+Z_{1}Y_{2}Y_{3}X_{5}+X_{1}Z_{2}Z_{4}X_{5}$
$\displaystyle\quad+X_{1}Y_{3}Y_{4}Z_{5}-X_{1}Y_{3}X_{4}Y_{5}+Y_{1}Y_{2}X_{4}Z_{5}$
$\displaystyle\quad+Y_{1}Y_{2}Y_{4}Y_{5}-Y_{1}X_{2}Y_{3}Z_{4}-Y_{1}X_{2}Y_{3}X_{5}$
$\displaystyle\quad+Z_{1}X_{2}Z_{3}Z_{4}X_{5}-Z_{1}Y_{2}X_{3}Y_{4}Z_{5}+Z_{1}Y_{2}X_{3}X_{4}Y_{5}$
$\displaystyle\quad+X_{1}Z_{2}Z_{3}X_{4}Z_{5}+X_{1}Z_{2}Z_{3}Y_{4}Y_{5}+Y_{1}Y_{2}Z_{3}Z_{4}X_{5}$
$\displaystyle\quad+Y_{1}X_{2}X_{3}Y_{4}Z_{5}-Y_{1}X_{2}X_{3}X_{4}Y_{5}),$
$\displaystyle\rho_{1234}$
$\displaystyle=\frac{1}{16}(I_{1234}+X_{1}Z_{2})(I_{1234}+Z_{1}X_{2}Z_{3})(I_{1234}+Z_{2}X_{3}Z_{4}),$
$\displaystyle\rho_{1235}$
$\displaystyle=\frac{1}{16}(I_{1235}+X_{1}Z_{2})(I_{1235}+Z_{1}X_{2}Z_{3})(I_{1235}+Z_{2}X_{3}X_{5}),$
$\displaystyle\rho_{1245}$
$\displaystyle=\frac{1}{16}(I_{1245}+X_{1}Z_{2})(I_{1245}+Z_{4}X_{5})$
$\displaystyle\quad(I_{1245}+Z_{1}X_{2}X_{4}Z_{5}),$
$\displaystyle\rho_{1345}$
$\displaystyle=\frac{1}{16}(I_{1345}+Z_{3}X_{4}Z_{5})(I_{1345}+Z_{4}X_{5})$
$\displaystyle\quad(I_{1345}+X_{1}X_{3}Z_{4}),$ $\displaystyle\rho_{2345}$
$\displaystyle=\frac{1}{16}(I_{2345}+Z_{2}X_{3}Z_{4})(I_{2345}+Z_{3}X_{4}Z_{5})$
$\displaystyle\quad(I_{2345}+Z_{4}X_{5}),$ $\displaystyle\rho_{123}$
$\displaystyle=\frac{1}{8}(I_{123}+X_{1}Z_{2})(I_{123}+Z_{1}X_{2}Z_{3}),$
$\displaystyle\rho_{124}$
$\displaystyle=\rho_{125}=\frac{1}{8}(I_{12i,\,i=4,5}+X_{1}Z_{2}),$
$\displaystyle\rho_{134}$
$\displaystyle=\frac{1}{8}(I_{134}+X_{1}X_{3}Z_{4}),$
$\displaystyle\rho_{135}$
$\displaystyle=\frac{1}{8}(I_{135}+X_{1}X_{3}X_{5}),$
$\displaystyle\rho_{145}$
$\displaystyle=\rho_{245}=\frac{1}{8}(I_{i45,\,i=1,2}+Z_{4}X_{5}),$
$\displaystyle\rho_{234}$
$\displaystyle=\frac{1}{8}(I_{234}+Z_{2}X_{3}Z_{4}),$
$\displaystyle\rho_{235}$
$\displaystyle=\frac{1}{8}(I_{235}+Z_{2}X_{3}X_{5}),$
$\displaystyle\rho_{345}$
$\displaystyle=\frac{1}{8}(I_{345}+Z_{3}X_{4}Z_{5})(I_{345}+Z_{4}X_{5}),$
$\displaystyle\rho_{12}$ $\displaystyle=\frac{1}{4}(I_{12}+X_{1}Z_{2}),$
$\displaystyle\rho_{45}$ $\displaystyle=\frac{1}{4}(I_{45}+Z_{4}X_{5}),$
$\displaystyle\rho_{13}$
$\displaystyle=\rho_{14}=\rho_{15}=\rho_{23}=\rho_{24}=\rho_{25}=\rho_{34}$
$\displaystyle=\rho_{35}=\frac{1}{4}I_{ij,\,i=1,2,3,j=3,4,5,\,i\neq j}.$

We will now evaluate the detectability of Pauli errors when they are
perturbing these cluster states. Any single-qubit Pauli errors will transform
cluster states into orthogonal states. Thus, standard distance functions, when
being computed between the ideal cluster state and its corrupted version, will
always reach the maximal value, regardless of how many and what kind of
single-qubit Pauli errors are present in the cluster states. In other words,
overlap-based distances are not fully adequate to discriminate how much
different errors affect a quantum computation. Since the preparation of
cluster states only requires controlled-$Z$ gates to act between the nearest-
neighbouring qubits in the $\left|+\right\rangle$ basis, the most common
experimental errors on cluster states are single-qubit unwanted rotations
(bit/phase flips) of a specific system component or of the neighbouring qubits
[11, 12, 8, 13, 9, 10, 30]. Hence, it is important to be able to properly
quantify the influence of single-qubit Pauli errors on cluster states, as they
are arguably the most relevant ones for practical purposes.

###  II.2 Evaluation of Pauli errors by the weighted Bures length

Unlike standard distance functions, weighted distances take into the
consideration the statistical distinguishability of marginal as well global
density matrices, in order to assess the difference between two quantum
states. The construction is particularly appealing when we want to compare
states that are invariant under (all possible, or at least some) subsystem
permutations. In such a case, the maximization of the weighted sum over all
system partitions in Eq. (4) is easily computable.

First, we employ the weighted Bures length to quantify how cluster states are
affected by Pauli errors. We consider four different cluster states: Three-,
four- and five qubit one-dimensional cluster states, and four-qubit two-
dimensional cluster states, as shown in Figure 1. We show how different
single-qubit rotations change such states, by evaluating the weighted Bures
length between the cluster states before and after the error is applied.
The results are reported in Table 1. They show that, surprisingly, different
single-qubit rotations generate states that are placed at different distances
from the original cluster states in the manifold of quantum states. Hence, the
detectability of such errors is different. For instance, consider the $Z_{2}$
error on four-qubit one- and two-dimensional cluster states. The possible
elements of a four-qubit partition $P_{k_{\alpha}}$ are
$\\{\\{1\\}\mathrel{,}\\{2\\}\mathrel{,}\\{3\\}\mathrel{,}\\{4\\}\mathrel{,}\\{12\\}\mathrel{,}\\{13\\}\mathrel{,}\\{14\\}\mathrel{,}\\{23\\}\mathrel{,}\\{24\\}\mathrel{,}\\{34\\}\mathrel{,}\\{123\\}\mathrel{,}\\{124\\}\mathrel{,}\\{134\\}\mathrel{,}\\{234\\}\mathrel{,}\\{1234\\}\\}$.
Since the one-body reduced density matrices of four-qubit cluster states are
maximally mixed, local unitary operations will not be detectable by comparing
their one-body reduced density matrices:
$B(\rho_{i},\sigma_{i})=0,\,i=1,2,3,4$, in which $\rho_{i},\sigma_{i}$ are the
cluster state input and output single-qubit marginal density matrices,
respectively. However, the $Z_{2}$ error changes the two-body density matrix
of four-qubit two-dimensional cluster states $\rho_{24}^{2D}$.

On the other hand, the $Z_{2}$ error cannot be detected by any of the two-body
marginals of four-qubit one-dimensional cluster states, so in this case the
output state is closer to the ideal cluster state. Instead, it changes the
three-body marginals like
$\rho_{123}^{1D}=\frac{1}{8}(I_{123}+X_{1}Z_{2})(I_{123}+Z_{1}X_{2}Z_{3})$.
Therefore, the effect of the $Z_{2}$ gate on four-qubit one-dimensional
cluster states is different than on four-qubit two-dimensional cluster states,
as captured by different values of weighted Bures length. The reason is that
the system partition that maximizes the weighted sum in Eq.(4) is different.

Cluster states |  $\qquad\mathbf{D_{\mathbf{B}}=\pi/6}$ |  $\qquad\mathbf{D_{\mathbf{B}}=\pi/4}$
---|---|---
Three-qubit
one-dimensional |  $X_{1},\mathrel{\,}X_{3},\mathrel{\,}Z_{2}$ |  $Z_{1},\mathrel{\,}Z_{3},\mathrel{\,}X_{2},\mathrel{\,}Y_{1},\mathrel{\,}Y_{2},\mathrel{\,}Y_{3}$
Four-qubit
one-dimensional |  $X_{1},\mathrel{\,}X_{4},\mathrel{\,}Z_{2},\mathrel{\,}Z_{3}$ |  $Z_{1},\mathrel{\,}Z_{4},\mathrel{\,}X_{2},\mathrel{\,}X_{3},\mathrel{\,}Y_{1},\mathrel{\,}Y_{2},\mathrel{\,}Y_{3},\mathrel{\,}Y_{4}$
Four-qubit
two-dimensional |  $X_{1},\mathrel{\,}X_{2},\mathrel{\,}X_{3},\mathrel{\,}X_{4}$ |  $Z_{1},\mathrel{\,}Z_{2},\mathrel{\,}Z_{3},\mathrel{\,}Z_{4},\mathrel{\,}Y_{1},\mathrel{\,}Y_{2},\mathrel{\,}Y_{3},\mathrel{\,}Y_{4}$
Five-qubit
one-dimensional |  $X_{1},\mathrel{\,}X_{3},\mathrel{\,}X_{5},\mathrel{\,}Z_{2},\mathrel{\,}Z_{3},\mathrel{\,}Z_{4},\mathrel{\,}Y_{3}$ |  $Z_{1},\mathrel{\,}Z_{5},\mathrel{\,}X_{2},\mathrel{\,}X_{4},\mathrel{\,}Y_{1},\mathrel{\,}Y_{2},\mathrel{\,}Y_{4},\mathrel{\,}Y_{5}$
Table 1: Weighted Bures length between cluster states before and after they
have been affected by single-qubit Pauli errors. In the first column, we list
the cluster states under scrutiny. In the second and third columns, for each
cluster state, we identify the Pauli errors that generate output states whose
weighted Bures length to the initial state are $\pi/6$ and $\pi/4$,
respectively. Note that the standard Bures length reaches the maximal value
$\pi/2$ in all these cases.

Also, we observe that, for one dimensional states, the subset of single-qubit
Pauli-$Z$ errors with a smaller weighted distance measure seems determined by
the geometry of cluster states. Specifically, unwanted phase flips of
“central” qubits ($Z_{2}$ for three-qubit states, $Z_{2},Z_{3}$ for four-qubit
states, one dimensional states, and $Z_{2},Z_{3},Z_{4}$ for five-qubit states)
are more difficult to detect than peripheral ones.

###  II.3 Evaluation of Pauli errors by weighted Hilbert-Schmidt distance

Cluster states |  $\qquad\mathbf{D_{\mathbf{H}S}=\sqrt{2}/3}$ |  $\qquad\mathbf{D_{\mathbf{H}S}=1/2}$
---|---|---
Three-qubit
one-dimensional |  $X_{1},\mathrel{\,}X_{3},\mathrel{\,}Z_{2}$ |  $Z_{1},\mathrel{\,}Z_{3},\mathrel{\,}X_{2},\mathrel{\,}Y_{1},\mathrel{\,}Y_{2},\mathrel{\,}Y_{3}$
Cluster states |  $\qquad\mathbf{D_{\mathbf{H}S}=\sqrt{2}/4}$ |  $\qquad\mathbf{D_{\mathbf{H}S}=1/2}$
Four-qubit
one-dimensional |  $X_{1},\mathrel{\,}X_{4},\mathrel{\,}Z_{2},\mathrel{\,}Z_{3}$ |  $Z_{1},\mathrel{\,}Z_{4},\mathrel{\,}X_{2},\mathrel{\,}X_{3},\mathrel{\,}Y_{1},\mathrel{\,}Y_{2},\mathrel{\,}Y_{3},\mathrel{\,}Y_{4}$
Cluster states |  $\qquad\mathbf{D_{\mathbf{H}S}=\sqrt{2}/4}$ |  $\qquad\mathbf{D_{\mathbf{H}S}=1/2}$
Four-qubit
two-dimensional |  $X_{1},\mathrel{\,}X_{2},\mathrel{\,}X_{3},\mathrel{\,}X_{4}$ |  $Z_{1},\mathrel{\,}Z_{2},\mathrel{\,}Z_{3},\mathrel{\,}Z_{4},\mathrel{\,}Y_{1},\mathrel{\,}Y_{2},\mathrel{\,}Y_{3},\mathrel{\,}Y_{4}$
Cluster states |  $\qquad\mathbf{D_{\mathbf{H}S}=1/3}$ |  $\,\qquad\mathbf{D_{\mathbf{H}S}=1/2}$
Five-qubit
one-dimensional |  $X_{1},\mathrel{\,}X_{3},\mathrel{\,}X_{5},\mathrel{\,}Z_{2},\mathrel{\,}Z_{3},\mathrel{\,}Z_{4},\mathrel{\,}Y_{3}$ |  $Z_{1},\mathrel{\,}Z_{5},\mathrel{\,}X_{2},\mathrel{\,}X_{4},\mathrel{\,}Y_{1},\mathrel{\,}Y_{2},\mathrel{\,}Y_{4},\mathrel{\,}Y_{5}$
Table 2: Weighted Hilbert-Schmidt distance between cluster states before and
after they have been affected by single-qubit Pauli errors. In the first
column, we list the cluster states under scrutiny. In the second and third
columns, for each cluster state, we list the Pauli errors and the related
weighted Hilbert-Schmidt distance between input and output states. Note that
the standard Hilbert-Schmidt distance takes the maximal value $\sqrt{2}$ in
all these cases.

We now repeat the calculation by employing the weighted Hilbert-Schmidt
distance introduced in Eq.(6), which is in general simpler to evaluate than
the weighted Bures length and other distances. Also, we want to verify whether
unitaries of the same dimension still generate states at different distances
from the input. That is, we investigate if this surprising fact depends on the
employed distance function, rather than being a generic feature of quantum
dynamics.
As we said before, single-qubit Pauli errors transform ideal cluster states
into orthogonal states. Therefore, the input/output global state overlap is
zero. This means that the weighted Hilbert-Schmidt distance of cluster states
to their alterations depends only on the global and marginal purities and the
overlaps between the state marginals.

The results are reported in Table 2. As it happened by using the weighted
Bures length, different errors yield different values of the weighted Hilbert-
Schmidt distance. Remarkably, we can establish a hierarchy among Pauli
matrices in terms of how much they affect the cluster states, independently of
the employed distance. For example, for three-qubit cluster states, the very
same $X_{1},\,X_{3},\,Z_{2}$ errors that affect the least the initial state,
as quantified by a smaller weighted Bures length, also output the closest
state according to the weighted Hilbert-Schmidt distance
$\left(\sqrt{2}/3\approx 0.47\right)$. For the rest of the Pauli errors, the
weighted Hilbert-Schmidt distance is $1/2$. (The optimal partitition is made
of a pair of two-body marginal states.) In the case of four-qubit one-
dimensional cluster states, given the $X_{1},\,X_{4},\,Z_{2},\,Z_{3}$ errors,
the optimal partition is the full four-body one (only global measurements can
distnguish between the input/output states): therefore, the weighted Hilbert-
Schmidt distance is $\sqrt{2}/4\approx 0.35$. Again, all the other errors
generate further states. Similarly, for $X_{1},\,X_{2},\,X_{3},\,X_{4}$
errors, the weighted Hilbert-Schmidt distance between inputs and outputs for
four-qubit two-dimensional states is $\sqrt{2}/4$. The least affecting errors
for the five-qubit case are instead
$X_{1},\,X_{3},\,X_{5},\,Z_{2},\,Z_{3},\,Z_{4},\,Y_{3}$: the optimal
measurement is a three-body one and the weighted Hilbert-Schmidt distance
takes the value $1/3$.
Finally, by employing the weighted Hilbert-Schmidt distance, we observe again
how the structure of one-dimensional states affects the detectability of
Pauli-$Z$ errors. Central $Z$-errors are still the most difficult to spot via
measurements. We conjecture that, considering one-dimensional cluster states
of increasing size, Pauli $Z$ errors on the inner qubits of the cluster states
would still generate states that are closer to the inputs. Also, more complex
two-dimensional states than the one studied here may be also prone to hide
centrally located errors.

## Conclusion

We evaluated how local unitary errors alter cluster states by means of the
weighted Bures length and the newly defined weighted Hilbert-Schmidt distance.
We showed that, while all single-qubit Pauli errors transform ideal cluster
states into orthogonal erroneous states, the distinguishability of such
corrupted states with respect to the input configuration can be different.
Unitary errors of the same dimension produce states that have different
weighted distance from the initial state, which physically means that the size
of the optimal measurements that detect them depends on the specific error.

Our results show how weighted distances can be more informative than standard
distances in evaluating important properties of many-body quantum systems. As
potential follow-on projects, we anticipate that, just like standard
distances, weighted distances can be split into genuine “quantum” and
“classical” parts [31]. These more refined weighted quantum distances could be
employed to evaluate how errors affect quantum resources rather than the whole
quantum states. This is much needed to investigate properties of large-
dimensional entangled states [32], and their resistance to various error
sources. Other interesting avenues of investigation are extensions of our case
study to other classes of multipartite quantum states with complex correlation
structure, e.g., other types of graph states. Finally, our findings call for a
rigorous proof that the structure of cluster states determines what Pauli
errors are more difficult to detect, regardless of the employed weighted
distance.

## Acknowledgments

C. P. S. is thankful to Kwek Leong Chuan and Konstantin Tiurev for private
discussions. C. P. S. is sponsored by Erasmus+ EU Funds for the duration of
study. D. G. acknowledges financial support from the Italian Ministry of
Research and Education (MIUR) by a starting package of Politecnico di Torino,
grant number 54_RSG20GD01.

## References

  * [1] I. Bengtsson and K. Życzkowski, Geometry of Quantum States (Cambridge University Press, 2007).
  * [2] D. Spehner, Quantum correlations and distinguishability of quantum states, J. Math. Phys. 55, 075211 (2014).
  * [3] Y.-C. Liang, Y.-H. Yeh, P. E. M. F. Mendonça, R. Y. Teh, M. D. Reid, and P. D. Drummond, Quantum fidelity measures for mixed states, Rep. Prog. Phys. 82, 076001 (2019).
  * [4] D. Girolami and F. Anzà, Quantifying the difference between many-body quantum states, Phys. Rev. Lett. 126, 170502 (2021).
  * [5] L. Li, K. Bu, D. E. Koh, A. Jaffe, and S. Lloyd, Wasserstein complexity of quantum circuits, arXiv:2208.06306.
  * [6] P. Kurzyński, Weighted Bures length uncovers quantum state sensitivity, Phys. Rev. E 104, L052202 (2021).
  * [7] A. Grudka, P. Kurzyński, A. S. Sajna, J. Wójcik, and A. Wójcik, Exposing Hypersensitivity in Quantum Chaotic Dynamics, arXiv:2307.14678.
  * [8] M. Hein, J. Eisert, and H. J. Briegel, Multiparty entanglement in graph states, Phys. Rev. A 69, 062311 (2004).
  * [9] G. Tóth and Gühne, Entanglement detection in the stabilizer formalism, Phys. Rev. A 72, 022340 (2005).
  * [10] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, H. J. Briegel, Entanglement in graph states and its applications, Proceedings of the International School of Physics “Enrico Fermi”, Volume 162: Quantum Computers, Algorithms and Chaos, pp. 115-218 (2006).
  * [11] R. Raussendorf, Measurement-based quantum computation with cluster states, Phd thesis, Ludwig-Maximilians-Universität München (2003).
  * [12] R. Raussendorf, D. Browne, and H. J. Briegel, Measurement-based quantum computation on cluster states, Phys. Rev. A 68, 022312 (2003).
  * [13] M. A. Nielsen, Cluster-state quantum computation, Rep. Math. Phys. 57, pp. 147-161 (2006).
  * [14] W. Wootters, A Measure of the Distinguishability of Quantum States. In: P. Meystre, M. O. Scully (eds), Quantum Optics, Experimental Gravity, and Measurement Theory. NATO Adv. Sc. Inst. Series 94 (1983).
  * [15] W. K. Wootters, Statistical distance and Hilbert space, Phys. Rev. D 23, 357 (1981).
  * [16] G. Fubini, Sulle metriche definite da una forme Hermitiana, Attidel Reale Istituto Veneto di Scienze, Lettere ed Arti 63, 502 (1904).
  * [17] E. Study, Kürzeste Wege im komplexen Gebiet, Mathematische, Annalen, Springer Science and Business Media LLC. 60, 321 (1905).
  * [18] A. Uhlmann, The “transition probability” in the state space of a *-algebra, Rep. Math. Phys. 9, pp. 273-239 (1976).
  * [19] C. A. Fuchs and C. M. Caves, Ensemble-dependent bounds for accessible information in quantum mechanics, Phys. Rev. Lett. 73, pp. 3047-3050 (1994).
  * [20] R. Jozsa, Fidelity for mixed quantum states, J. Mod. Opt. 41, pp. 2315-2323 (1994).
  * [21] A. Gilchrist, N. K. Langford, and M. A. Nielsen, Distance measures to compare real and ideal quantum processes, Phys. Rev. A 71, 062310 (2005).
  * [22] X. Wang and S. Schirmer, On the contractivity of Hilbert-Schmidt distance under open system dynamics, Phys. Rev. A 79, 052326 (2009).
  * [23] C. Zhang, B. Yadin, Z.-B. Hou, H. Cao, B.-H. Liu, Y.-F. Huang, R. Maity, V. Vedral, C.-F. Li, G.-C. Guo and D. Girolami, Detecting metrologically useful asymmetry and entanglement by a few local measurements, Phys. Rev. A 96, 042327 (2017).
  * [24] T. Zhang, G. Smith, J. A. Smolin, L. Liu, X.-J. Peng, Q. Zhao, D. Girolami, X. Ma, X. Yuan, and H. Lu, Quantification of Entanglement and Coherence with Purity Detection, arXiv:2308.07068.
  * [25] C. Moura Alves and D. Jaksch, Multipartite entanglement detection in bosons, Phys. Rev. Lett. 93, 110501 (2004).
  * [26] R. Islam, R. Ma, P. M. Preiss, M. E. Tai, A. Lukin, M. Rispoli, and M. Greiner, Measuring entanglement entropy in a quantum many-body system, Nature 528, pp. 77-83 (2015).
  * [27] A. K. Ekert, C. Moura Alves, D. K. L. Oi, M. Horodecki, P. Horodecki, and L. C. Kwek, Direct estimations of linear and nonlinear functionals of a quantum state, Phys. Rev. Lett. 88, 217901 (2002).
  * [28] R. Filip, A device for feasible fidelity, purity, Hilbert-Schmidt distance and entanglement witness measurements, Phys. Rev. A 65, 062320 (2002).
  * [29] T. A. Brun, Measuring polynomial functions of states, Quant. Inf. and Comp. 4, 401 (2004).
  * [30] K. Tiurev and A. S. Sørensen, Fidelity measurement of a multiqubit cluster state with minimal effort, Phys. Rev. Research 4, 033162 (2022).
  * [31] D. Girolami, How difficult is it to prepare a quantum state?, Phys. Rev. Lett. 122, 010505 (2019).
  * [32] J. K. Stockton, J. M. Geremia, A. C. Doherty, and H. Mabuchi, Characterizing the entanglement of symmetric many-particle spin-1/2 systems, Phys. Rev. A 67, 022112 (2003).


# The doubly asymmetric simple exclusion process, the colored Boolean process,
and the restricted random growth model

Yuhan Jiang  Department of Mathematics, Harvard University, USA
<EMAIL_ADDRESS>
###### Abstract.

The multispecies asymmetric simple exclusion process (mASEP) is a Markov chain
in which particles of different species hop on a one-dimensional lattice. This
paper studies the doubly asymmetric simple exclusion process DASEP(n,p,q) in
which q particles with species 1 through p hop on a circular lattice with n
sites, but also the particles are allowed to spontaneously change their
species. In this paper, we introduce two related Markov chains called the
colored Boolean process and the restricted random growth model, and we show
that the DASEP lumps to the colored Boolean process, and the colored Boolean
process lumps to the restricted random growth model. This allows us to
generalize a theorem of David Ash on the relations between sums of steady
state probabilities. We also give explicit formulas for the stationary
distribution of DASEP(n,2,2).

##  1\. Introduction

The asymmetric simple exclusion process (ASEP) is a Markov chain for particles
hopping on a one-dimensional lattice such that each site contains at most one
particle. The ASEP was introduced independently in biology by Macdonald-Gibbs-
Pipkin [5], and in mathematics by Spitzer [16]. There are many versions of the
ASEP: the lattice can have open boundaries, or be a ring, not necessarily
finite (see Liggett [11],[12]). Particles can have different species, and this
variation is called the multispecies ASEP (mASEP). The asymmetry can be
partial, so that particles are allowed to hop both left and right, but one
side is $t$ times more probable, and this is called the partially asymmetric
exclusion process (PASEP). The ASEP is closely related to a growth model
defined by Kardar-Parizi-Zhang [9], and various methods have been invented to
study the ASEP, such as the matrix ansatz introduced by Derrida et al. in [6].
The combinatorics of the ASEP was studied by many people, see
[7][2][3][13][4].

A partition $\lambda$ is a weakly decreasing sequence of $n$ nonnegative
integers $\lambda=(\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}\geq 0)$.
We denote the sum of all parts by $|\lambda|=\lambda_{1}+\cdots+\lambda_{n}$.
We will write a partition as an $n$-tuple
$\lambda=(\lambda_{1},\lambda_{2},\dots,\lambda_{n})$. Let
$m_{i}=m_{i}(\lambda)$ be the number of parts of $\lambda$ that equal $i$. As
in [17, Section 7.2], we also denote a partition by
$\lambda=1^{m_{1}}2^{m_{2}}\cdots$. Let $\operatorname{parts}^{+}(\lambda)$
denote the number of nonzero (positive) parts of $\lambda$. We have
$\operatorname{parts}^{+}(\lambda)=\sum_{i}m_{i}(\lambda)$. We write
$S_{n}(\lambda)$ as the set of all permutations of
$(\lambda_{1},\dots,\lambda_{n})$. The mASEP can be thought of a Markov chain
on $S_{n}(\lambda)$.

Let $n$ be the number of positions on the lattice, $p$ be number of types of
species, and $q$ be the number of particles. David Ash [1] defined the _doubly
asymmetric simple exclusion process_ $\operatorname{DASEP}(n,p,q)$. The DASEP
is a variant of the mASEP but also allows particles to change species. If
$p=1$, $\operatorname{DASEP}(n,1,q)$ is the usual 1-species PASEP on a ring.

######  Definition 1.1.

[1] For all positive integers $n,p,q$ with $n>q$, the _doubly asymmetric
simple exclusion process_ $\operatorname{DASEP}(n,p,q)$ is a Markov process on
the following set

$\Gamma^{p,q}_{n}=\bigcup_{\begin{subarray}{c}\lambda_{1}\leq p,\\\
\operatorname{parts}^{+}(\lambda)=q\end{subarray}}S_{n}(\lambda).$

The transition probability $P(\mu,\nu)$ on two permutations $\mu$ and $\nu$ is
as follows:

  * •

If $\mu=(\mu_{1},\dots,\mu_{k},i,j,\mu_{k+2},\dots,mu_{n})$ and
$\nu=(\mu_{1},\dots,\mu_{k},j,i,\mu_{k+2},\dots,\mu_{n})$ with $i\neq j$, then
$P(\mu,\nu)=\frac{t}{3n}$ if $i>j$ and $P(\mu,\nu)=\frac{1}{3n}$ if $j>i$.

  * •

If $\mu=(i,\mu_{2},\mu_{3},\dots,\mu_{n-1},j)$ and
$\nu=(j,\mu_{2},\mu_{3},\dots,\mu_{n-1},i)$ with $i\neq j$, then
$P(\mu,\nu)=\frac{t}{3n}$ if $j>i$ and $P(\mu,\nu)=\frac{1}{3n}$ if $i>j$.

  * •

If $\mu=(\mu_{1},\dots,\mu_{k},i,\mu_{k+2},\dots,\mu_{n})$ and
$\nu=(\mu_{1},\dots,\mu_{k},i+1,\mu_{k+2},\dots,\mu_{n})$ with $i\leq p-1$,
then $P(\mu,\nu)=\frac{u}{3n}$.

  * •

If $\mu=(\mu_{1},\dots,\mu_{k},i+1,\mu_{k+2},\dots,\mu_{n})$ and
$\nu=(\mu_{1},\dots,\mu_{k},i,\mu_{k+2},\dots,\mu_{n})$ with $i\geq 1$, then
$P(\mu,\nu)=\frac{1}{3n}$.

  * •

If none of the above conditions apply but $\nu\neq\mu$ then $P(\mu,\nu)=0$. If
$\nu=\mu$ then $P(\mu,\mu)=1-\sum_{\nu\neq\mu}P(\mu,\nu)$.

As we are interested in the stationary distribution of DASEP, we denote the
un-normalised stationary distribution by $\\{p_{\mu}:\mu\in
S_{n}(\lambda)\\}$, which is uniquely defined if we require the $p_{\mu}$ to
be polynomials with greatest common divisor equal to 1.

######  Remark 1.2.

There is an inherent symmetry in the definition of DASEP, we denote the un-
normalized steady state probability of a state $\mu$ by $p_{\mu}$, which are
uniquely defined if we require them to be polynomials with trivial greatest
common divisor.

01$\frac{1}{6}$$\frac{t}{6}$$\frac{u}{6}$$\frac{1}{6}$100220$\frac{u}{6}$$\frac{1}{6}$$\frac{1}{6}$$\frac{t}{6}$

110101011102201210120021012220202022

Figure 1. The state diagram of $\operatorname{DASEP}(2,2,1)$ and
$\operatorname{DASEP}(3,2,2)$. We omit self-loops at each state. Bold edges
denote changes in species, while regular edges denote exchanges of particles
of different species or between particles and holes. Dashed arrows denote hops
of particles.

Our first main result is about the ratio between the sums of certain groups of
$p_{\mu}$. For each partition $\lambda$ and each binary word
$w=(w_{1},\dots,w_{n})\in S_{n}(1^{q}0^{n-q})$, define

$S_{n}^{w}(\lambda):=\\{\mu\in S_{n}(\lambda)|\mu_{i}\neq 0\text{ if and only
if }w_{i}\neq 0\\}$

as the set of all permutations of $\lambda$ whose zeros are aligned with the
binary word $w$. Then if $\lambda_{1}\leq p$ and
$\operatorname{parts}^{+}(\lambda)=q$, we have
$|S_{n}(\lambda)|=\binom{n}{n-q,m_{1},\dots,m_{p}}$ and
$|S_{n}^{w}(\lambda)|=\binom{q}{m_{1},m_{2},\dots,m_{p}}$.

######  Example 1.3.

For the partition $\lambda=(2,1)$, we have $|\lambda|=2+1+1=4$. For $n=3$, we
have $|S_{3}^{011}((2,1))|=\binom{2}{1,1}=2$. For $n=4$, we have
$|S_{4}((2,1))|=\binom{4}{2,1,1}=12$.

######  Theorem 1.4.

Consider $\operatorname{DASEP}(n,p,q)$ for any positive integers $n,p,q$ with
$n>q$.

  1. (1)

For any two binary words $w,w^{\prime}\in S_{n}(1^{q}0^{n-q})$, we have
$p_{w}=p_{w^{\prime}}$.

  2. (2)

For any binary word $w\in S_{n}(1^{q}0^{n-q})$ and partition
$\lambda=1^{m_{1}}2^{m_{2}}\cdots p^{m_{p}}$ such that

$m_{1}+\cdots+m_{p}=q,$

we have

$\sum_{\mu\in
S_{n}^{w}(\lambda)}p_{\mu}=u^{|\lambda|-q}\binom{q}{m_{1},m_{2},\dots,m_{p}}p_{w}=u^{|\lambda|-q}|S_{n}^{w}(\lambda)|p_{w}.$

In other words, the sum of steady state probabilities of states within one
equivalence class is proportional to each other and the ratio only depends on
the sum of all parts and the multiplicities in the partition; all steady state
probabilities with respect to binary words are equal.

######  Remark 1.5.

In the special case of $\operatorname{DASEP}(3,p,2)$, 1.4 was proved by David
Ash [1, Theorem 5.2].

$\mu$ | $p_{\mu}$
---|---
011 | $u+3t+4$
012 | $u(u+4t+3)$
021 | $u(u+2t+5)$
022 | $u^{2}(u+3t+4)$

$\mu$ | $p_{\mu}$
---|---
0011 | $u+2t+3$
0101 | $u+2t+3$
0022 | $u^{2}(u+2t+3)$
0202 | $u^{2}(u+2t+3)$
0012 | $u(u+3t+2)$
0102 | $u(u+2t+3)$
0021 | $u(u+t+4)$

Table 1. Unnormalized steady state probabilities of
$\operatorname{DASEP}(3,2,2)$ and $\operatorname{DASEP}(4,2,2)$. We present
all states up to cyclic symmetry. The shaded rows on the left belong to
$S_{3}^{011}((2,1))$, and on the right belong to $S_{4}^{0011}((2,1))$.

######  Example 1.6.

In $\operatorname{DASEP}(3,2,2)$, we compute the steady state probabilities
for the binary word $w=011$ and permutations of $(1,1,0),(2,1,0),(2,2,0)$
aligned with $w$ as shown in Table 1. By 1.4, we have
$p_{012}+p_{021}=2up_{011}$ and $p_{022}=u^{2}p_{011}$, which can be seen from
Table 1.

Similarly, in $\operatorname{DASEP}(4,2,2)$, we compute the steady state
probabilities for binary words $0011$ and $0101$ in Table 1. We have
$p_{0012}+p_{0021}=2up_{0011}$. Since $0201$ is a cyclic permutation of
$0102$, we have $p_{0201}=p_{0102}$, and $p_{0102}+p_{0201}=2up_{0101}$ as
asserted by 1.4.

To prove 1.4, we also introduce a new Markov chain that we call the _colored
Boolean process_ (see 2.1), and we show that the DASEP _lumps_ to the colored
Boolean process. This gives a relationship between the stationary distribution
of colored Boolean process and the DASEP, see 2.3.

######  Corollary 1.7.

For the $\operatorname{DASEP}(n,p,q)$ defined by positive integers
$n,p,q,n>q$, and $\lambda,\mu$ two partitions with $\lambda_{1}\leq
p,\mu_{1}\leq
p,\operatorname{parts}^{+}(\lambda)=\operatorname{parts}^{+}(\mu)=q$, we have

$\frac{\sum_{\nu\in S_{n}(\lambda)}p_{\nu}}{\sum_{\nu\in
S_{n}(\mu)}p_{\nu}}=\frac{|S_{n}(\lambda)|u^{|\lambda|}}{|S_{n}(\mu)|u^{|\mu|}}.$

In 4.1, we also give explicit formulas for the stationary distributions of the
infinite family $\operatorname{DASEP}(n,2,2)$ for any $n\geq 3$. The formulas
depend on whether $n$ is odd or even. Both are described by polynomial
sequences given by a second-order homogeneous recurrence relation (see 4.1).
When we specialize to $u=t=1$, the polynomial sequences specialize to
trinomial transform of Lucas number A082762 and binomial transform of the
denominators of continued fraction convergents to $\sqrt{5}$ A084326 [15].

The structure of this paper is as follows. In Section 2, we define the
_colored Boolean process_ , and we show that the DASEP _lumps_ to the colored
Boolean process. In Section 3, we define the _restricted random growth model_
, which is a Markov chain on Young diagrams, and we show that the colored
Boolean process lumps to the restricted random growth model. In Section 4, we
give explicit formulas for the stationary distributions of the infinite family
$\operatorname{DASEP}(n,2,2)$.

## Acknowledgements

We thank Lauren Williams for suggesting the problem and helping me better
understand ASEP.

##  2\. The DASEP lumps to the colored Boolean process

In this section, we define the _colored Boolean process_ , and we show that
the DASEP _lumps_ to the colored Boolean process. We compute the ratios
between steady states probabilities in the colored Boolean process, leading us
to prove 1.4.

######  Definition 2.1.

The _colored Boolean process_ is a Markov chain dependent on three positive
integers $n,p,q$ with $n>q$ on states space

$\Omega^{p,q}_{n}=\\{(w,\lambda)|w\in S_{n}(1^{q}0^{n-q}),\lambda_{1}\leq
p,\operatorname{parts}^{+}(\lambda)=q\\}$

with the following transition probabilities:

  * •

$Q((w,\lambda),(w,\lambda^{\prime}))=\frac{m_{i}u}{3n}$ if $\lambda$ contains
$m_{i}\geq 1$ parts equal to $i$ and $\lambda^{\prime}$ is obtained from
$\lambda$ by changing a part equal to $i$ to a part equal to $i+1$.

  * •

$Q((w,\lambda),(w,\lambda^{\prime}))=\frac{m_{i}}{3n}$ if $\lambda$ contains
$m_{i}\geq 1$ parts equal to $i$ and $\lambda^{\prime}$ is obtained from
$\lambda$ by changing a part equal to $i$ to a part equal to $i-1$.

  * •

$Q((w,\lambda),(w^{\prime},\lambda))=\frac{1}{3n}$ if $w^{\prime}$ is obtained
from $w$ by $01\to 10$ at a unique position (allowing wrap-around at the end).

  * •

$Q((w,\lambda),(w^{\prime},\lambda))=\frac{t}{3n}$ if $w^{\prime}$ is obtained
from $w$ by $10\to 01$ at a unique position (allowing wrap-around at the end).

  * •

If none of the above conditions apply but $w\neq w^{\prime}$ or
$\lambda\neq\lambda^{\prime}$, then
$Q((w,\lambda),(w^{\prime},\lambda^{\prime}))=0$.

  * •

$Q((w,\lambda),(w,\lambda))=1-\sum_{(w^{\prime},\lambda^{\prime})\neq(w,\lambda)}Q((w,\lambda),(w^{\prime},\lambda^{\prime})).$

We denote the stationary distribution of $\Omega^{p,q}_{n}$ by $\pi$.

We think of parts of different sizes as particles of different colors, or
species, hence the name.

The relation between the colored Boolean process and the DASEP is captured by
the following notion.

######  Definition 2.2.

[10, Section 6.3][14, Definition 2.5, Theorem 2.6] Let $\\{X_{t}\\}$ be a
Markov chain on state space $\Omega_{X}$ with transition matrix $P$, and let
$f:\Omega_{X}\to\Omega_{Y}$ be a surjective map. Suppose there is an
$|\Omega_{Y}|\times|\Omega_{Y}|$ matrix $Q$ such that for all
$y_{0},y_{1}\in\Omega_{Y}$, if $f(x_{0})=y_{0}$, then

$\sum_{x:f(x)=y_{1}}P(x_{0},x)=Q(y_{0},y_{1}).$

Then $\\{f(X_{t})\\}$ is a Markov chain on $\Omega_{Y}$ with transition matrix
$Q$. We say that $\\{f(X_{t})\\}$ is a _lumping_ of $\\{X_{t}\\}$ and
$\\{X_{t}\\}$ is a _lift_ of $\\{f(X_{t})\\}$.

101110011102,201210,120021,012202220022 Figure 2. Transition diagram of
$\Omega^{2,2}_{3}$, as a lumping of $\operatorname{DASEP}(3,2,2)$ as shown on
the right hand side in Figure 1. The bold edges denote the changes of species,
while the regular edges denote the exchanges between particles of different
species or between particles and holes.

######  Theorem 2.3.

The projection map $f:\Gamma^{p,q}_{n}\to\Omega^{p,q}_{n}$ sending each
$\mu\in S_{n}^{w}(\lambda)$ to $(w,\lambda)$ is a lumping of
$\operatorname{DASEP}(n,p,q)$ onto the colored Boolean process
$\Omega^{p,q}_{n}$.

###### Proof.

Fix $(w_{0},\lambda_{0})$ and $(w_{1},\lambda_{1})$, we want to show that for
any $\mu_{0}\in S_{n}^{w_{0}}(\lambda_{0})$, the quantity

$\sum_{\mu:f(\mu)\in S_{n}^{w_{1}}(\lambda_{1})}P(\mu_{0},\mu)$

is independent of the choice of $\mu_{0}$ and equal to
$Q((w_{0},\lambda_{0}),(w_{1},\lambda_{1}))$. We may assume
$(w_{0},\lambda_{0})\neq(w_{1},\lambda_{1})$, because the probabilities add up
to 1.

This quantity is nonzero only in the following cases:

  * •

$w_{0}=w_{1}$ and if $\lambda_{0}=1^{m_{1}}2^{m_{2}}\cdots p^{m_{p}}$ there
exists a unique $i\in[1,p-1]$ with $m_{i}\geq 1$ such that $\lambda_{1}=\cdots
i^{m_{i}-1}(i+1)^{m_{i+1}+1}\cdots$. We upgrade the species of a particle from
$i$ to $i+1$, and there are again $m_{i}$ ways to do it, where each transition
probability $P(\mu_{0},\mu)=\frac{u}{3n}$, so the quantity is equal to
$\frac{m_{i}u}{3n}$.

  * •

$w_{0}=w_{1}$ and if $\lambda_{0}=1^{m_{1}}2^{m_{2}}\cdots p^{m_{p}}$ there
exists a unique $i\in[2,p]$ with $m_{i}\geq 1$ such that
$\lambda_{1}=\cdots(i-1)^{m_{i-1}+1}i^{m_{i}-1}\cdots$. We downgrade the
species of a particle from $i$ to $i-1$, and there are $m_{i}$ ways to do it,
so there are $m_{i}$ number of $\mu$’s in $S_{n}^{w_{1}}(\lambda_{1})$ with
nonzero $P(\mu_{0},\mu)=\frac{1}{3n}$, so the quantity is equal to
$\frac{m_{i}}{3n}$.

  * •

$\lambda_{0}=\lambda_{1}$ and $w_{1}$ is obtained from $w_{0}$ by $01\to 10$
at a unique position (allowing wrap-around at the end). This quantity is equal
to $\frac{1}{3n}$.

  * •

$\lambda_{0}=\lambda_{1}$ and $w_{1}$ is obtained from $w_{0}$ by $10\to 01$
at a unique position (allowing wrap-around at the end). This quantity is equal
to $\frac{t}{3n}$.

The nonzero transition probabilities of $\Omega$ in each of the four cases
above is the same as we defined. ∎

We may use the stationary distribution of $\\{X_{t}\\}$ to compute that of its
lumping.

######  Proposition 2.4.

[10, Section 6.3] Suppose $p$ is a stationary distribution for $\\{X_{t}\\}$,
and let $\pi$ be the measure on $\Omega_{Y}$ defined by
$\pi(y)=\sum_{x:f(x)=y}p(x)$. Then $\pi$ is a stationary distribution for
$\\{f(X_{t})\\}$.

Thus, we may use the stationary distribution of $\Omega^{p,q}_{n}$ to study
that of $\Gamma_{n}^{p,q}$. We have the following corollary due to 2.4 and
2.3.

######  Corollary 2.5.

The unnormalized steady state probabilities
$\\{\pi(w,\lambda)|(w,\lambda)\in\Omega^{p,q}_{n}\\}$ of the colored Boolean
process and the unnormalized steady state probabilities
$\\{p_{\mu}|\mu\in\Gamma^{p,q}_{n}\\}$ of the DASEP are related as follows:

$\pi(w,\lambda)\propto\sum_{\mu\in S_{n}^{w}(\lambda)}p_{\mu}.$

######  Theorem 2.6.

Consider the colored Boolean process $\Omega^{p,q}_{n}$.

  1. (1)

The steady state probabilities of all binary words are equal, i.e.,
$\pi(w,1^{q}0^{n-q})=\pi(w^{\prime},1^{q}0^{n-q})$ for any $w,w^{\prime}\in
S_{n}(1^{q}0^{n-q})$.

  2. (2)

The steady state probability $\pi(w,\lambda)$ of an arbitrary state
$(w,\lambda)$ can be expressed in terms of the steady state probability
$\pi(w,1^{q}0^{n-q})$ (of the corresponding state $(w,1^{q}0^{n-q})$ with the
trivial partition $(1^{q}0^{n-q})$) as follows:

(1)
$\pi(w,\lambda)=u^{|\lambda|-q}\binom{q}{m_{1},\dots,m_{p}}\pi(w,1^{q}0^{n-q}).$

###### Proof.

The colored Boolean process is again an ergodic markov chain, so we only need
to show that the above relations satisfy the balance equations given by the
transition matrix of $\Omega$.

Let us first check it for $\lambda=1^{q}0^{n-q}$. For any binary word $w$,
denote $\pi(w,1^{q}0^{n-q})$ by $p_{w}$. Let $b_{w}$ be the number of blocks
of consecutive $1$’s in $w$ (allowing wrap-around). Notice that any occurrence
of $01$ in $w$ must begin a block, and any occurrence of $10$ must signify the
end of a block. We have

(2) $(qu+b_{w}+b_{w}t)p_{w}=q\pi(w,1^{q-1}2)+b_{w}t\sum_{\underset{10\to
01}{w^{\prime}\to w}}p_{w^{\prime}}+b_{w}\sum_{\underset{01\to
10}{w^{\prime\prime}\to w}}p_{w^{\prime\prime}}.$

Expanding the multinomial coefficient, we are left with

$b_{w}(1+t)p_{w}=b_{w}t\sum_{\underset{10\to 01}{w^{\prime}\to
w}}p_{w^{\prime}}+b_{w}\sum_{\underset{01\to 10}{w^{\prime\prime}\to
w}}p_{w^{\prime\prime}}$

which will be satisfied if we set all $p_{w}$’s to be equal.

For generic $\lambda=1^{m_{1}}2^{m_{2}}\cdots p^{m_{p}}$, Equation 2 is only
modified where $qu$ on the left hand side becomes $au+b$ where
$a=m_{1}+\cdots+m_{p-1}$ and $b=m_{2}+\cdots+m_{p}$. On the right hand side we
change the first term of Equation 2 to

$\sum_{i<p}(m_{i+1}+1)\pi(w,\cdots
i^{m_{i}-1}(i+1)^{m_{i+1}+1}\cdots)+\sum_{i>1}(m_{i-1}+1)u\pi(w,\cdots(i-1)^{m_{i-1}+1}i^{m_{i}-1}\cdots).$

Expand this using Equation 1, the multinomial coefficients gives the ratios

$\displaystyle\frac{\pi(w,\cdots
i^{m_{i}-1}(i+1)^{m_{i+1}+1}\cdots)}{\pi(w,1^{m_{1}}2^{m_{2}}\cdots
p^{m_{p}})}$ $\displaystyle=\frac{m_{i}u}{m_{i+1}+1}$
$\displaystyle\frac{\pi(w,\cdots(i-1)^{m_{i-1}+1}i^{m_{i}-1}\cdots)}{\pi(w,1^{m_{1}}2^{m_{2}}\cdots
p^{m_{p}})}$ $\displaystyle=\frac{m_{i}}{(m_{i-1}+1)u}$

for all $i$. Then we have a term by term equality for each $i$ where $a$
corresponds to the first summation and $b$ corresponds to the second. ∎

###### Proof of 1.4.

This follows directly from 2.4, 2.3 and 2.6. ∎

##  3\. The colored Boolean process lumps to the restricted random growth
model

In this section, we define the _restricted random growth model_ , which is a
Markov chain on the set of Young diagrams fitting inside a rectangle, and we
show it to be a lumping of the colored Boolean process.

######  Definition 3.1.

[17] For partitions $\mu$ and $\lambda$, the _reverse lexicographic order_ is
a partial order such that $\nu\leq\lambda$ if either $\nu=\lambda$ or for some
$j$,

$\nu_{1}=\lambda_{1},\dots,\nu_{j-1}=\lambda_{j-1},\nu_{j}<\lambda_{j}.$

We say that _$\lambda$ covers $\nu$ at $i$_ if there exists a unique $j$ such
that $\lambda_{j}=\nu_{j}+1=i$ and for all $k\neq j$ we have
$\lambda_{k}=\nu_{k}$, in which case we write $\lambda\gtrdot_{i}\nu$. We say
that _$\nu$ is covered by $\lambda$ at $i$_ if there exists a unique $j$ such
that $\nu_{j}=\lambda_{j}-1=i$ and for all $k\neq j$ we have
$\nu_{k}=\lambda_{k}$, in which case we write $\nu\lessdot_{i}\lambda$. In
both cases, we have $m_{i}(\nu)=m_{i}(\lambda)+1$ where $m_{i}(\nu)$ is the
number of parts of $\nu$ equal to $i$.

######  Example 3.2.

The partition $(2,2,1,0,0)$ covers $(2,1,1,0,0)$ at 2, and the latter is
covered by the former at 1.

######  Definition 3.3.

Define the _restricted random growth model_ on the the state space
$\chi^{p,q}=\\{\lambda:\lambda_{1}\leq
p,\operatorname{parts}^{+}(\lambda)=q\\}$ which includes all partitions that
fit inside a $q\times p$ rectangle but do not fit inside a shorter rectangle,
with transition probabilities $d^{(n)}_{\nu,\lambda}$ as follows:

  * •

If $\nu\lessdot_{i}\lambda$, then
$d^{(n)}_{\nu,\lambda}=\frac{m_{i}(\nu)u}{3n}$.

  * •

If $\nu\gtrdot_{i}\lambda$, then
$d^{(n)}_{\nu,\lambda}=\frac{m_{i}(\nu)}{3n}$.

  * •

In all other cases where $\nu\neq\lambda$, $d^{(n)}_{\nu,\lambda}=0$.

  * •

$d^{(n)}_{\lambda,\lambda}=1-\sum_{\nu:\nu\neq\lambda}d^{(n)}_{\nu,\lambda}$.

As in [17], we denote the number of parts of the partition $\nu$ that equal to
$i$ by $m_{i}(\nu)$.

1,12,12,2$2u$$1$$u$$2$

1,12,1$\cong$1,22,2$u$$u$$1$$1$$u$$u$$1$$1$

Figure 3. The state diagram of the restricted random growth model on
$\chi^{2,2}$. We omit an overall factor of $\frac{1}{3n}$, and omit self-loops
which make the probabilities add up to 1. The Markov chain on the left can be
viewed as a lumping of the Markov chain on the right in which we do not
rearrange the parts in weakly decreasing order.

######  Remark 3.4.

In other words, the transitions either add or remove a box from a uniformly
chosen part of the Young diagram of the partition (conditioned on staying in
the $q\times p$ rectangle) as shown on the right hand side of Figure 3, then
rearrange the parts in weakly decreasing order as shown on the left hand side
of Figure 3.

The 1d random growth model [8] is a growth model on diagrams not necessarily
arranged in weakly decreasing order. The diagrams do not need to fit in a
rectangle, and the times between arrivals are independent i.i.d..

######  Theorem 3.5.

The projection map on state spaces $g:\Omega^{p,q}_{n}\to\chi^{p,q}$ sending
$(w,\lambda)$ to $\lambda$ (forgetting the positions of 0’s) is a lumping of
the colored Boolean process $\Omega^{p,q}_{n}$ to the restricted random growth
$(\chi^{p,q},d^{(n)})$. It follows that the steady state probabilities
$\\{q_{\lambda}|\lambda\in\chi^{p,q}\\}$ of the restricted random growth and
the unnormalized steady state probabilities
$\\{\pi(w,\lambda)|(w,\lambda)\in\Omega^{p,q}_{n}\\}$ of the colored Boolean
process are related as follows:

$q_{\lambda}\propto\sum_{w\in S_{n}(1^{q}0^{n-q})}\pi(w,\lambda).$

###### Proof.

By 2.2, we need to show that for any $\nu,\lambda$ and binary word $w$ the
following equation holds:

$d^{(n)}_{\nu,\lambda}=\sum_{w^{\prime}}Q((w,\nu),(w^{\prime},\lambda)).$

It suffices to check this for all $\nu\neq\lambda$ since the probabilities add
up to 1. Then $Q((w,\nu),(w^{\prime},\lambda))\neq 0$ only if $w=w^{\prime}$
by 2.1, and this quantity is either $\frac{m_{i}(\nu)u}{3n}$ when
$\nu\lessdot_{i}\lambda$ or $\frac{m_{i}(\nu)}{3n}$ when
$\nu\gtrdot_{i}\lambda$. ∎

######  Theorem 3.6.

The steady state probabilities $\\{q_{\lambda}|\lambda\in\chi^{p,q}\\}$ of the
restricted random growth model satisfy the following relations for all
partitions $\nu,\lambda\in\chi^{p,q}$:

$\frac{q_{\lambda}}{q_{\nu}}=\frac{|S_{n}(\lambda)|u^{|\lambda|}}{|S_{n}(\nu)|u^{|\nu|}}.$

###### Proof.

This follows from 3.5 and 2.6 and a computation on multinomial coefficients. ∎

###### Proof of 1.7.

This follows from 2.4, 3.5 and 3.6. ∎

##  4\. The stationary distribution of DASEP(n,2,2)

If there were only one species of particle, i.e. $p=1$, the stationary
distribution of $\operatorname{DASEP}(n,1,q)$ is uniform. If there were only
one particle, i.e., $q=1$, then the unnormalized steady state probabilities of
$\operatorname{DASEP}(n,p,1)$ are given by powers of $u$, not involving $t$
due to cyclic symmetry. We now study the first nontrivial case of
$\operatorname{DASEP}(n,p,q)$ in more detail, namely
$\operatorname{DASEP}(n,2,2)$. In this section, we give a complete description
of the stationary distributions when there are two particles and two species,
while the number of sites can be arbitrary.

######  Theorem 4.1.

Let $(a_{k})_{k\geq 0}$ and $(b_{k})_{k\geq-1}$ be polynomial sequences in
$u,t$ satisfying the recurrence relation

(3) $\displaystyle a_{k}$ $\displaystyle=(u+2t+3)a_{k-1}-(t+1)^{2}a_{k-2}$ (4)
$\displaystyle b_{k}$ $\displaystyle=(u+2t+3)b_{k-1}-(t+1)^{2}b_{k-2}.$

with initial conditions $b_{-1}=0,a_{0}=b_{0}=1,a_{1}=u+3t+4$.

We can fully describe the unnormalized steady state probabilities of the
infinite family
$\operatorname{DASEP}(n,2,2)$ as follows. When $n=2k+1$ is odd,

$\begin{array}[]{|c|c|c|}\hline\cr\mu&p_{\mu}\\\ \hline\cr
S_{n}((1,1,0,\dots,0))&a_{k}\\\ \hline\cr 0\dots 010^{m}20\dots
0&ua_{k}+u(t-1)(t+1)^{m}a_{k-m-1},(0\leq m<k)\\\ \hline\cr 0\dots
020^{m}10\dots 0&ua_{k}-u(t-1)(t+1)^{m}a_{k-m-1},(0\leq m<k)\\\ \hline\cr
S_{n}((2,2,0,\dots,0))&u^{2}a_{k}\\\ \hline\cr\end{array}$

When $n=2k+2$ is even,

$\begin{array}[]{|c|c|c|}\hline\cr\mu&p_{\mu}\\\ \hline\cr
S_{n}((1,1,0,\dots,0))&b_{k}\\\ \hline\cr 0\dots 010^{m}20\dots
0&ub_{k}+u(t-1)(t+1)^{m}b_{k-m-1},(0\leq m\leq k)\\\ \hline\cr 0\dots
020^{m}10\dots 0&ub_{k}-u(t-1)(t+1)^{m}b_{k-m-1},(0\leq m\leq k)\\\ \hline\cr
S_{n}((2,2,0,\dots,0))&u^{2}b_{k}\\\ \hline\cr\end{array}$

###### Proof.

We need to show that these formula satisfy balance equation at each state. Let
$p_{w}$ for any binary word $w$ be $x$, then $p_{\mu}$ for $\mu\in
S_{n}((2,2,0,\dots,0))$ would be equal to $u^{2}x$ by 2.6. Let $p_{\dots
10^{m}2\dots}$ be $q^{+}_{m}$ and $p_{\dots 20^{m}1\dots}$ be $q^{-}_{m}$ for
$m\in[0,k]$ or $[0,k)$. The following equations hold.

(5) $\displaystyle(2u+t+1)x$ $\displaystyle=(t+1)x+q^{+}_{1}+q^{-}_{1}$ (6)
$\displaystyle(u+2t+2)q^{-}_{0}$
$\displaystyle=(t+1)q^{-}_{1}+(u+u^{2})x+q^{+}_{0}$ (7)
$\displaystyle(u+2t+3)q^{-}_{m}$
$\displaystyle=(t+1)q^{-}_{m+1}+(u+u^{2})x+(t+1)q^{-}_{m-1}$ (8)
$\displaystyle(t+3)u^{2}x$ $\displaystyle=(t+1)u^{2}x+u(q^{+}_{0}+q^{-}_{0})$

When $n$ is odd, Equation 7 is true for $m\in[1,k-2]$, and we have an
additional equation

(9) $\displaystyle(u+2t+3)q^{-}_{k-1}$
$\displaystyle=(t+1)(q^{-}_{k-2}+q^{+}_{k-1})+(u+u^{2})x.$

When $n$ is even, Equation 7 is true for $m\in[1,k-1]$, and we have an
additional equation

(10) $\displaystyle(u+2t+3)q^{-}_{k}$
$\displaystyle=(t+1)(q^{-}_{k-1}+q^{+}_{k-1})+(u+u^{2})x.$

By 1.4, we have $q^{+}_{i}+q^{-}_{i}=2ux$ for all $i$. Applying this to
Equation 5, Equation 8, and Equation 10, we see that all of them hold
trivially.

To show Equation 6, we may assume $n$ is odd, since the even case would be the
same. Deduce $u(u+t+3)x$ from both sides then divide both sides by $u(t-1)$,
we are left with

$x-(u+2t+2)a_{k-1}=-(t+1)^{2}a_{k-2}+a_{k-1}$

which is the same as

$x=(u+2t+3)a_{k-1}-(t+1)^{2}a_{k-2}.$

Since $x=a_{k}$, this is true by Equation 3.

To show Equation 7, we rewrite the recurrence relations Equation 3 and
Equation 4 into

$(t+1)(q^{-}_{m-1}-ux)=(u+2t+3)(q^{-}_{m}-ux)-(t+1)(q^{-}_{m+1}-ux),$

eliminating $x$ out of the equations, hence proving Equation 7.

To show Equation 9, we deduce $u(u+2t+3)x$ from both sides then divide both
sides by $u(t-1)(t+1)^{m-1}$ so that we are left with

$-(u+2t+3)=-a_{1}+t+1$

which is true since $a_{1}=u+3t+4$. ∎

## References

  * [1] David W. Ash  “Introducing DASEP: the doubly asymmetric simple exclusion process”, 2023  arXiv:2201.00040 [math.CO]
  * [2] Richard A. Blythe, Wolfhard Janke, Desmond A. Johnston and Ralph Kenna  “Dyck paths, Motzkin paths and traffic jams”  In _Journal of Statistical Mechanics: Theory and Experiment_ 2004, 2004, pp. P10007
  * [3] Richard Brak and John Essam  “Simple asymmetric exclusion model and lattice paths: bijections and involutions”  In _Journal of Physics A: Mathematical and Theoretical_ 45, 2012
  * [4] Sylvie Corteel, Olya Mandelshtam and Lauren K. Williams  “From multiline queues to Macdonald polynomials via the exclusion process”  In _American Journal of Mathematics_ 144, 2018, pp. 395 –436
  * [5] MacDonald CT, Gibbs JH and Pipkin AC.  “Kinetics of biopolymerization on nucleic acid templates”  In _Biopolymers_ 6.1, 1968, pp. 1–5
  * [6] B. Derrida, M. R. Evans, V. Hakim and V. Pasquier  “Exact solution of a 1D asymmetric exclusion model using a matrix formulation”  In _Journal of Physics A: Mathematical and General_ 26.7, 1993, pp. 1493  DOI: 10.1088/0305-4470/26/7/011
  * [7] Enrica Duchi and Gilles Schaeffer  “A combinatorial approach to jumping particles”  In _J. Comb. Theory, Ser. A_ 110, 2004, pp. 1–29
  * [8] Patrik L. Ferrari, H. Spohn Durham University and Tu Munich  “Random Growth Models”, 2010
  * [9] Mehran Kardar, Giorgio Parisi and Yi Zhang  “Dynamic scaling of growing interfaces.”  In _Physical review letters_ 56 9, 1986, pp. 889–892
  * [10] John G. Kemeny and J. Laurie Snell  “Finite Markov Chains”, Undergraduate Texts in Mathematics  Springer New York, NY, 1976
  * [11] Thomas M. Liggett  “Ergodic theorems for the asymmetric simple exclusion process”  In _Transactions of the American Mathematical Society_ 213, 1975, pp. 237–261
  * [12] Thomas M. Liggett  “Interacting Particle Systems”  Springer Berlin Heidelberg, 1985  DOI: 10.1007/b138374
  * [13] James B. Martin  “Stationary distributions of the multi-type ASEP”  In _Electronic Journal of Probability_ , 2018
  * [14] C. Y. Amy Pang  “Lumpings of Algebraic Markov Chains Arise from Subquotients”  In _Journal of Theoretical Probability_ , 2015, pp. 1–41
  * [15] Neil J. A. Sloane and The OEIS Foundation Inc.  “The on-line encyclopedia of integer sequences”, 2020  URL: http://oeis.org/?language=english
  * [16] Frank Spitzer  “Interaction of Markov processes”  In _Advances in Mathematics_ 5, 1970, pp. 66–110
  * [17] Richard P. Stanley  “Enumerative Combinatorics” 2, Cambridge Studies in Advanced Mathematics  Cambridge University Press, 1999  DOI: 10.1017/CBO9780511609589