# A Master Equation for Power Laws

Sabin Roman1,2 and Francesco Bertolotti3 1Centre for the Study of Existential
Risk, University of Cambridge
2Odyssean Institute
3Carlo Cattaneo University LIUC

###### Abstract

We propose a new mechanism for generating power laws. Starting from a random
walk, we first outline a simple derivation of the Fokker-Planck equation. By
analogy, starting from a certain Markov chain, we derive a master equation for
power laws that describes how the number of cascades changes over time
(cascades are consecutive transitions that end when the initial state is
reached). The partial differential equation has a closed form solution which
gives an explicit dependence of the number of cascades on their size and on
time. Furthermore, the power law solution has a natural cut-off, a feature
often seen in empirical data. This is due to the finite size a cascade can
have in a finite time horizon. The derivation of the equation provides a
justification for an exponent equal to 2, which agrees well with several
empirical distributions, including Richardson’s law on the size and frequency
of deadly conflicts. Nevertheless, the equation can be solved for any exponent
value. In addition, we propose an urn model where the number of consecutive
ball extractions follows a power law. In all cases, the power law is manifest
over the entire range of cascade sizes, as shown through log-log plots in the
frequency and rank distributions.

††preprint: APS/123-QED

##  I Introduction

A power law is a non-linear relationship between two quantities $x$ and $y$
that can be modelled generically by the following formula: $y=ax^{k}$, where
$k$ and $a$ are constants, respectively the exponent of the power law, and the
width of the scaling relationship. The power law is scale-invariant
relationship $f(xc)\propto f(x)$ that holds for any value of $c$. Graphically,
it implies that the curve describing the relationship between $x$ and $y$
maintain its shape under any possible dilatation. Moreover, power laws can be
represented as straight lines on a log-log plot, called the signature of the
power law.

The signature can be employed to analyze empirical data by comparing the
distribution of the data on a log-log plot with the best fitting power law.
Likely, this representation was first introduced by J. C. Wills in 1922 to
plot the distribution of the number of species in a genus [1]. Many log-normal
relationships appear as power laws when plotted for small ranges. As a
consequence, to assert that a relationship between two variables is a power
law, it should hold for at least two orders of magnitudes [2].

In the next section, we enumerate some representative examples of power law
distributions from physics, biology, ecology and social sciences. Furthermore,
we list the most well-known mechanisms for generating power laws. In the third
section, we proceed to propose a Markov process model for generating power
laws. First, we outline a derivation of the Fokker-Planck equation by starting
from a random walk and taking a continuum limit from a discrete state space.
This is a well-known approach for deriving the Fokker-Planck equation. We
provide our own treatment of this procedure by changing the difference
operator $\Delta$ acting on discrete functions to the differential operator
$d$ that acts on real variables. We then propose a Markov chain that displays
a power law in its long-term equilibrium distribution. Based on this and in
analogy with the Fokker-Planck equation derivation, we obtain a master
equation for power laws that we simplify to an analytically tractable form.
Surprisingly, the solution can be written in closed-form. Afterwards, in the
fourth section, we propose an urn model where the number of cascades
(consecutive balls drawn) scales according to a power law. This improves on an
urn model by Brunk [3] that display a power law relationship only in a limited
range. Finally, we summarize our results in the conclusion.

##  II Background

The main challenge regarding power law distributions is understanding their
origin. Broadly speaking, there are two ways power laws can emerge:
probability transformations and generative processes. Probability
transformations derive power law distributions from other distributions.
Generative processes are algorithms that create new distributions. Here, we
provide more details on generative processes, because our own work is of this
nature. To the best of our knowledge, there does not exist a comprehensive
review of all the power law distribution generative models (even if [1] finds
a large set), and it is not in the scope of this paper to provide one.

There are three main strategies to obtain a power law distribution by
transforming an existing probability distribution: combining exponential
distributions, inverting quantities or looking at the extreme values of
distributions.

In the first case, the transformation consists of substituting the variable of
an exponential distribution with another exponential distribution. The
resulting distribution follows a power law, in which parameters depend on the
original exponential distribution. The distribution of sizes of populations
that grow exponentially (i.e., with infinite carrying capacity) and can
suddenly become extinct at any time step with the same probability follows a
power law that can be derived from this model [4].

The second case requires the inversion of the quantities of the probability
distribution. If these quantities pass through zero, the transformation
results in a power law distribution with exponent equal to $2$, resulting from
the derivation of an inverted variable. The most notable example of a power
law distribution obtained in this way occurs in the paramagnetic phase of the
Ising model [5, 6].

The third way originates from the extreme value theorems which provide results
on the asymptotic behavior of the extreme realizations. The
Pickands–Balkema–de Haan theorem [7, 8] states that the conditional
distribution of a random variable above a certain threshold tends to a Pareto
distribution when the threshold tends to infinity. Therefore, it provides a
rationale for the widespread observation of Pareto or power law behavior,
since it is the limiting behavior of large events for a whole class of
probability distributions [9]. Analogously, the Fisher–Tippett–Gnedenko
theorem [10, 11] describes the possible distributions that the maximum value
can have; this can shed light in cases where a simple power law does not
appear from the application of the Pickands–Balkema–de Haan theorem [12].

In addition, we identified in the literature at least four notable generative
processes for power law distributions: phase transitions (along with self-
organized criticality), random walks, sample-space reduction processes, and
the Yule processes.

The idea underlying phase transitions and critical phenomena is simple but
powerful. In systems governed by a single length scale, the scale can diverge
in some given conditions, giving birth to scale-free systems in which
quantities are distributed as a power law. The precise point at which the
length-scale diverges is called a critical continuous point, or phase
transition. Nevertheless, it is unlikely that the parameters that regulate the
phase-transition of a real-world system happen to fall on that specific value.
So, the existence of critical phenomena is not enough to explain the presence
of power law distributions in many natural and social systems. But some
systems appear to self-organize to lay close to critical points, independently
from the initial conditions. This phenomenon, called self-organized
criticality, can be exemplified by the classic sandpile model [13], which
generates avalanches whose sizes are distributed according to a power law.
Other examples of how self-organized criticality generates power law
distributions includes earthquakes [14], neuronal avalanches [15], and forest
fires [1, 16]. However, the emergence and applicability of self-organized
criticality is debatable [17].

Random walks are a succession of randomly-generated steps on a given space
[18]. The statistical properties of random walks tend toward universal
distributions when the steps are independent of each other, and their number
grows unbounded [19]. As a consequence, they have the ability to generate
power law distributions even when the underlying rules are very simple. One of
the most famous examples (and likely the simplest) relates to the first-return
time. It can be proved that, under specific conditions, the distributions of
the first-return times follows a power law [19, 1].

The sample-space reduction process models history-dependent systems, such as
the formation of sentences, whose number of possible different meanings is
progressively reduced the more words are added to it. Corominas-Murtra et al.
demonstrate that a power law distribution can be generated from such a process
[20]. More specifically, Zipf’s law necessarily emerges from the reduction
over time of the number of possible states in which a system can be, as a
consequence of symmetry breaking in random sampling processes [20] or from
dependency structures in component systems [21]. The reduction space process
explains some well-known domain-specific power law generation models, such as
preferential attachment.

The Yule process is a generative model developed by G. Udny Yule to explain
the power law distribution of the number of species in taxonomic groups [22].
It derives from simple rules. Firstly, starting from a pool of groups, the
probability for a group to increase by one is proportional to the number of
its elements. Secondly, at any speciation event, there is a possibility of
generating a new specie belonging to a brand-new taxonomic group. The model is
a simplification of reality since it ignores extinction events. Nevertheless,
it has been customized to explain the emergence of power laws in other systems
such as city sizes [23] or paper citations [24].

Finally, other generative processes include highly optimized tolerance [25,
26], the coherent noise model of biological extinction [27], the repeated
fragmentation model of fixed length elements [1], the dynamic of times between
records in a random process [28], the Hawkes processes [29] and out-from-
criticality feedback [30].

A master equation for power laws has been previously obtained in the
literature [31, 32, 33, 34, 35] but only considers stationary distributions or
transient dynamics, while our results give a non-stationary solution [36].
Also, our choice of transition rates has not been considered before.

To the best of our knowledge, the above examples and mechanisms for generating
power laws do not generally address the question: How do power laws change (or
are preserved) over time? Answering this question requires a way to specify
the time evolution of the power law distribution. Furthermore, in many cases,
empirical power laws have a cut-off point above which the relationship no
longer holds [1] and this is has not been captured by generative models, which
are realistic only in specific value ranges. The next section provides a
mechanism by which an equation dictating the time-evolution of power laws can
be obtained. In addition, the solution displays a natural cut-off beyond a
certain time horizon.

Figure 1: Discrete state Markov chains for: (a) a continuous time random walk,
with multi-step transition probabilities satisfying equation (3), (b) a
continuous time process, with multi-step transition probabilities satisfying
equation (8). The stationary distribution of the embedded Markov chain is a
power law, as shown in derivation (7).

##  III Markov process models

Below we present an outline for a well-known derivation of the Fokker-Planck
equation starting from a discrete Markov chain and taking a continuum limit.
By analogy, we introduce a discrete Markov chain that has a power law
stationary distribution and then we derive a master equation for power laws.

###  III.1 Fokker-Planck equation

The transition probabilities for a 1D random walk are:

$\displaystyle P_{i,i+1}$ $\displaystyle=p$ (1) $\displaystyle P_{i,i-1}$
$\displaystyle=1-p=q$

The probability for $x$ jumps to the right and $n-x$ jumps to the left is:

$\displaystyle P(x,n)$ $\displaystyle=\binom{n}{x}p^{x}q^{n-x}$ (2)
$\displaystyle\sim\cfrac{1}{\sqrt{2\pi
npq}}\exp\left[{-\cfrac{(x-np)^{2}}{2npq}}\right]$

where in the limit of large enough $n$ we can can approximate the binomial
distribution with a Gaussian. Let $i,s$ be arbitrary states. For a continuous
time Markov chain we write $p_{i}(t)=P_{si}(0;t)$. For the Markov chain in
Fig. 1(a), we can write down the following equation for $p_{i}(t)$:

$\displaystyle\frac{dp_{i}(t)}{dt}$
$\displaystyle=d_{i-1}p_{i-1}+b_{i+1}p_{i+1}-d_{i}p_{i}-b_{i}p_{i}$ (3)
$\displaystyle=-(a_{i+1}p_{i+1}-a_{i}p_{i})$
$\displaystyle\;\;\;\;\;+d_{i-1}p_{i-1}-2d_{i}p_{i}+d_{i+1}p_{i+1}$

where $b_{i},d_{i}$ are the rates at which the process leaves state $i$ to
state $i-1$, respectively to state $i+1$. Furthermore, we define
$a_{i}=d_{i}-b_{i}$. Using the forward and backward difference operators
$\Delta x_{n}=x_{n+1}-x_{n}$ and $\nabla x_{n}=x_{n}-x_{n-1}$, the above
equation can be written:

$\displaystyle\frac{dp_{i}(t)}{dt}$
$\displaystyle=-\Delta(a_{i}p_{i}(t))+\Delta\nabla(d_{i}p_{i}(t))$ (4)
$\displaystyle\downarrow$ $\displaystyle\frac{\partial p(x,t)}{\partial t}$
$\displaystyle=-\frac{\partial}{\partial
x}(a(x)p(x,t))+\frac{\partial^{2}}{\partial x^{2}}(d(x)p(x,t))$

which in the continuous limit gives the Fokker-Planck equation. If $a(x)=0$
and $d(x)=D$ where $D$ is constant, then the solution with initial condition
$p(0,x)=\delta(x-x_{0})$ is given by:

$p(x,t)=\cfrac{1}{\sqrt{4\pi Dt}}\exp\left[-\cfrac{(x-x_{0})^{2}}{4Dt}\right]$
(5)

(a) |  (b)
---|---
Figure 2: Log-log plots of: (a) The stationary distribution (dotted black
line) of the Markov chain with transition probabilities (6) for $k=2,3$, along
with a linear fit (solid grey line). (b) Solution (12) (dotted black line) to
equation (9) for $b/a=2,3$ up to times $t=10^{2},10^{4}$, along with linear
fits (solid grey line).

###  III.2 Power law equation

We consider the Markov chain with the following transition matrix:

$\displaystyle P_{i,i+1}$ $\displaystyle=\exp\left(-\frac{k}{i+1}\right)$ (6)
$\displaystyle P_{i,0}$ $\displaystyle=1-\exp\left(-\frac{k}{i+1}\right)$

The dominant contribution to the long-term equilibrium distribution is given
by:

$\displaystyle\pi(x)$ $\displaystyle\simeq\Pi_{i\leq x}P_{i,i+1}$ (7)
$\displaystyle=\exp(-k\sum_{i}1/i)$ $\displaystyle\sim\exp(-k\ln{x})$
$\displaystyle=x^{-k}$

In Fig. 2(a) we compare numerical solutions for the equilibrium distribution
with the approximation (7), showing that the power law approximation is highly
accurate. The Markov chain given by (6) is the embedded chain of the
continuous time Markov process in Fig. 1(b). Using the same notation as in the
previous section, the probability $p_{i}(t)$ satisfies the following
differential equation:

$\frac{dp_{i}(t)}{dt}=a_{i-1}p_{i-1}-a_{i}p_{i}-b_{i}p_{i}$ (8)

We can write (8) using the backward difference operator. If we let the space
index go from discrete to continuous, such as in the previous section where
$i\rightarrow x$, then equation (8) becomes:

$\displaystyle\frac{dp_{i}(t)}{dt}$
$\displaystyle=-\nabla(a_{i}p_{i}(t))-b_{i}p_{i}(t)$ (9)
$\displaystyle\downarrow$ $\displaystyle\frac{\partial p(x,t)}{\partial t}$
$\displaystyle=-\frac{\partial}{\partial x}(a(x)p(x,t))-b(x)p(x)$

which gives:

$\frac{\partial p(x,t)}{\partial t}=-a(x)\frac{\partial p(x,t)}{\partial
x}-(a^{\prime}(x)+b(x))p(x)$ (10)

where $a(x)=ae^{-k/x},b(x)=b(1-e^{-k/x})$ and $a,b$ are constants. By Taylor
expanding up to $1/x$, we get $a(x)\simeq a-\frac{ak}{x}$ and
$a^{\prime}(x)+b(x)\simeq\frac{bk}{x}$. Without loss of generality we can
relabel $bk$ as $b$ and the equation reduces to:

$\frac{\partial p(x,t)}{\partial t}=-a\frac{\partial p(x,t)}{\partial
x}-\frac{b}{x}p(x,t)$ (11)

The term containing $a/x$ can be neglected because the probability $p(x,t)$
depends on a power of $x$ (see below), and so each term on the right-hand side
is of (11) is of the same order in $x$.

Let $c(x,t)$ be the unnormalized solution of equation (11). The solution
$c(x,t)$ has a closed form expression for $x>0$ and $x<at$:

$c(x,t)=c_{0}\left(\frac{at}{x}-1\right)^{b/a}$ (12)

where $c(x,0)=c_{0}$. In Fig.2(b) we plot the solution (12) for different
values of $b/a$ and see a power law behaviour over a range of scales that
increases over time. The tail of the solution falls off abruptly just as we
see in many real-world examples of power law distributions [1].

(a) |  (b)
---|---
Figure 3: Log-log plots of the rank distribution of: (a) Cascade sizes (black
dots) in Brunk’s model, showing a narrow range where a power law is observed,
along with a linear fit (solid grey line). (b) Cascade sizes (black dots) in
the model we propose with exponent $k=1.5$, along with a linear fit (solid
grey line). The line of best fit has slope $0.49$, in good agreement with the
theoretical value of $k-1=0.5$.

Equation (11) posits that cascades (consecutive transitions) occur over time
in inverse proportion to their size. Furthermore, there is a constant rate $a$
at which they can increase in size. For a finite time horizon $t$, there is a
maximum size that a cascade can reach, namely $at$, as can be seen in the
solution (12).

We can get additional insights from equation (10) if we consider the second
order Taylor expansion of $a^{\prime}(x)+b(x)\simeq\frac{bk}{x}+\frac{2ak-
bk^{2}}{2x^{2}}$. If $k=2a/b$ then the $1/x^{2}$ term cancels, and this
implies an exponent of $2$ in the solution (12). This is not necessary in
deriving equation (11) but can serve as a rationale for the experimental
observation of power laws with exponent $2$.

##  IV Urn model

Building on the insights of the previous section, we propose an urn model that
display power law behaviour. We can approximate the probability (8) to move
from $i$ to $i+1$ state as:

$\exp\left(-\frac{k}{i+1}\right)\simeq 1-\frac{k}{i+1}$ (13)

for large enough $i$. Hence, if an adequate value of $k$ is chosen, then we
can expect to see a power law emerging even in a simple model.

[3] proposes a model claiming to exhibit cascades that occur with frequencies
inversely proportional to the cascade size, and provides graphs showing that a
power law distribution emerges. We attempted to reproduce the results of the
paper but we obtained an exponential distribution instead of a power law. A
power law relationship is seen to occur in a narrow range of scales that the
graphs in the article use, see Fig. 3(a). Furthermore, we can analytically
prove that the distribution that emerges is an exponential distribution and
not a power law. The article [3] has been cited in recent years, and we
consider it important to highlight the limitations of the model.

Assume the urn contains $N$ balls in total, with $K$ balls black and the rest
white. The model has the following steps:

  1. 1.

A ball is drawn, if it is black then the next ball is drawn, and the process
is repeated until a white ball is drawn. This constitutes a cascade within the
model. Black balls are drawn without replacement.

  2. 2.

Each time a white ball is drawn the number of black balls is increased by a
fraction $g$, while the number of white balls stay the same. If a white ball
is drawn, then we repeat from step 1.

The probability of that a cascade of size $n$ occurs, i.e., $n$ black balls
are drawn followed by a white ball, is:

$\displaystyle P(S=n)$
$\displaystyle=\frac{K}{N}\cdot\frac{K-1}{N-1}\cdot\ldots\cdot\frac{K-n+1}{N-n+1}\cdot\frac{N-K}{N-n}$
(14)
$\displaystyle=\frac{K!}{N!}\cdot\frac{(N-n)!}{(K-n)!}\cdot\frac{N-K}{N-n}$
$\displaystyle\approx\frac{K^{K+1/2}}{N^{N+1/2}}\cdot\frac{(N-n)^{N-n+1/2}}{(K-n)^{K-n+1/2}}\cdot\frac{N-n-(K-n)}{N-n}$
$\displaystyle=\left(1-\frac{n}{N}\right)^{N+1/2}\left(1-\frac{n}{K}\right)^{-(K+1/2)}$
$\displaystyle\;\;\;\;\left(\frac{K-n}{N-n}\right)^{n}\left(1-\frac{K-n}{N-n}\right)$

If $K\lesssim N$ then the first two term in the last row of (14) cancel to a
large extent. If we take the logarithm of (14), we get:

$\displaystyle\log P(S=n)$ $\displaystyle\approx
n\log{\left(\frac{K-n}{N-n}\right)}+\log{\left(1-\frac{K-n}{N-n}\right)}$ (15)
$\displaystyle\approx n\log(f)+\log(1-f)$

where $f=(K-n)/(N-n)\simeq K/N$ is approximately the fraction of black balls
in the urn. Equation (15) shows that probability of a cascade is exponentially
distributed, at least as long as $n\ll N$. Furthermore, as $K$ increases then
$f\rightarrow 1$, which implies an uniform distribution.

We propose a different urn model. Let $N_{0},K_{0}$ and $W$ be the initial
number of balls, respectively black and white ones. The procedure of the model
is as follows:

  1. 1.

Black balls are drawn with replacement. The number of black balls is increased
by $W/k$ after each draw. We continue to draw until a white ball is drawn.

  2. 2.

The process repeats with resetting the number of ball to their original values
$N=N_{0},K=K_{0}$.

The rank distribution of the cascade sizes is plotted in Fig. 3(b) for
$k=1.5$. As we can see, the graph is very well fit by a straight line,
indicating that a genuine power law emerges across the entire range of cascade
sizes.

At the $i$-th extraction we have the total number of balls $N_{i}$, of black
balls $K_{i}$ and white balls $W$. Then:

$N_{i}=K_{i}+W$ (16)

The urn model is designed such that at each extraction the ratio of $K_{i}$
and $N_{i}$ is approximately given by:

$\frac{K_{i}}{N_{i}}=e^{-k/(i+1)}$ (17)

Using the previous two equations we obtain that:

$\displaystyle K_{i}$ $\displaystyle=\frac{e^{-k/(i+1)}}{1-e^{-k/(i+1)}}W$
(18) $\displaystyle\simeq\left(\frac{i+1}{k}-1\right)W$

The number of black balls is increased after each draw by:

$K_{i+1}-K_{i}\simeq\frac{W}{k}$ (19)

If a constant $C$ number of black balls is added after each draw, then
$k=W/C$.

##  V Discussion

The relevance of this study relies upon two aspects: the increasing importance
of understanding statistical laws in complex systems due to the availability
of larger datasets [37], and the presence of power law distributions in
various application domains [4, 38, 39]. The applicability of the models
proposed in section 3III.2 is restricted to phenomena where time plays a key
role in increasing cascade sizes. The more time passes from the initial
observation, the greater the chances of seeing a larger cascade (which would
place it at the right-end tail of the distribution at the time of
observation). These phenomena can appear in a wide variety of disciplinary
fields.

The frequency versus the amplitude of earthquakes [1] and avalanches [40, 41]
follows a power law, as well as the distribution of the peak gamma-ray
intensity of solar flares [42], and the size of moon craters per surface area
[43]. The largest observed cascade in these examples depends on time, with
more extreme examples being discovered the longer the observation record is.

The social sciences also offer numerous examples of power laws distributions
[44] that naturally evolve in time (but whose time dependence has not
necessarily been quantified), such as the range of time between two deaths in
serial killers’ behavioural patterns [45], in narrative structure [46] or in
the budget distribution of movies [47]. In economics, they mainly derive from
aggregation and rich-get-richer processes. The existence of power laws in the
distribution of wealth and income are known at least from the 19th century
[48]. Notably, the work of Pareto was the first one to discover the presence
of a power law distribution in a social system [39]. Power law distributions
also appear in markets. For example, the frequency of firms size, measured by
the number of employees, is distributed according to a power law [49].
Specifically, the exponent of this power law is approximately $1.06$, which
suggests there exists a “Zip’s law” for firms [39].

Western popular music markets present power law distributions in the lifetime
of albums [50]. Stock markets exhibited power law distributions since their
very beginning [51]. It has been shown that the number of trades per day, the
size of price movements when a large volume of shares are bought or sold, and
the number of shares traded per time period are power law distributed with
exponents $3$, $0.5$ and $1.5$, respectively [52, 53, 54]. Inter-trading times
also exhibit scaling properties consistent with power laws [55].

Another field in which power law distributions are pervasive is urban studies,
where there are many scaling relationships between quantifiable city
properties [56], such as between the number of gas stations and population
levels [57], and the distribution of the population of cities in a given
geographic area [58]. This latter distribution appears in different geographic
areas [59] and depends on the granularity of the sampling [60]. Power law
distributions also characterize digital infrastructure. The network analysis
of internet topology shows that at the end of the ’90s the degrees of the
nodes were already power law distributed [61, 62]. Also, the number of
connections to a server in a single day, by a specific subsection of internet
users, follows a power law [63].

Furthermore, the academic system generates power laws. As first noted by
Price, the number of citations of papers follows a power law distribution
[64]. Similar features in academic systems can be observed in recent times,
even in specific disciplinary areas. For instance, the cumulative number of
citations over time for papers dealing with protein kinases is distributed as
a power law. This is a consequence of a phenomenon called the Harlow-Knapp
(H-K) effect, which is the propensity of the biomedical and pharmaceutical
research communities to concentrate their research on a tiny fraction of the
proteome [65, 66].

In history, the well-known Richardson’s law states that the frequency of wars’
sizes (measured in causalities) are power law distributed. This law is
considered one of the few robust statistical regularities in studies of
political conflict [67]. Nevertheless, some recent studies seem to cast doubt
on Richardson’s law, or at least suggest having a greater caution regarding it
[68]. Another example from history regards the Roman Empire [69], for which
the survival time of its emperors is distributed according to a power law
[70].

Certain power law relationships do not dependent on the observation period and
the proposed models would not apply. For example, in physics, the well-known
Stefan–Boltzmann law describes a power law relationship between the total
amount of energy radiated per time from a black body due to its temperature
[71, 72]. Furthermore, in particle physics and astrophysics there are numerous
examples of power laws, from the Tully-Fisher relation between a galaxy’s
luminosity and its rate of rotation [73], to the proportionality of the spin
and mass of hadrons [74] and the density of eigenvalues of the Dirac operator
in certain theories [75, 76]. Other examples come from biology, where many
works describe a scaling relationship between the basal metabolic rate and the
body mass of animals [77, 78, 79], such as the well-known Kleiber’s law, which
indicates that the basal metabolism of mammals increases according to
$m^{3/4}$ where $m$ is the overall body mass [80].

Another well known example (with no time dependence) is Zipf’s law, which
states that the rank frequency distribution of words in any sufficiently long
text is distributed as a power law [81]. This law is independent of the
language and holds even for artificial languages such as Esperanto [82]. While
Zipf investigates specifically the distribution of words, a generalization of
this law was later developed by Mandelbrot [83].

We end the discussion with a cautionary note on the discovery of power law in
data and models. As is well-noted in the literature [1], linear relationships
in log-log plots in the frequency distributions of observations is
insufficient to robustly establish that a power law holds. A more reliable
test is to check if the linear relationship holds in log-log plots of rank
distributions. As we have shown, the model proposed by Brunk [3] does not show
power law behaviour. Another example where a power law is claimed to be
observed is in the emergence of a scale-free network in systems with bounded
rationality [84]. As other work has shown [85], the topology is not scale-free
but rather of a core-periphery type.

##  VI Conclusion

In this paper, we have proposed a new mechanism to generate power laws based
on Markov models. By analogy with the derivation of the Fokker-Planck
equation, we have obtained a master equation for power laws. The result is
supported by the fact that the underlying embedded Markov chain has an
equilibrium distribution that is a power law and because a simplified version
of the equation admits a closed form solution that is a power law.

We proposed three models: a discrete time and discrete space Markov chain with
transition probabilities (6), a continuous time and discrete space Markov
chain shown in Fig. 2(b) and a Markov process (continuum in both time and
space), with master equation given by (9). A simplified form of (9) is
equation (11), which is valid in the limit of large cascades sizes. Further
considerations indicate that an exponent of $k=2$ gives additional
cancellations independent of cascade size. This value of $k$ is consistent
with exponents observed in Richardson’s law [68] and in the net worth of
Americans [1]. Nevertheless, equation (11) has a closed form solution for any
exponent value.In addition, the equation provides the time dynamics for the
power law relationship along with a natural cut-off size depending on the time
horizon.

The stationary solutions for the general equation are given by a first order
differential equation, whose solutions have been explored elsewhere [32].
However, a stationary solution to the power law equation might not always be
well defined, as our time-dependent solution (12) for the simplified equation
(11) shows (the time derivative is non-zero). The insight we get from the
exact time-dependent solution (5) of the Fokker-Planck equation is that the
standard deviation of spatial displacements is proportional to the square root
of time, which is characteristic of Brownian motion. Similarly, the time-
dependent solution (12) gives the largest cascade size we can expect to see is
linearly proportional to time.

Based on the insights from the Markov process, we propose a simple urn model
that illustrates power law behaviour over the entire range of cascade sizes.
The model only considers a constant addition of balls over time and despite
the simplicity of the mechanism, a robust power law is observed to emerge. Our
results are in contrast to a prior model by Brunk [3] which we prove does not
show a genuine power law distribution. Finally, we discuss some possible
applications of the proposed model to phenomena where power laws are observed
and where the duration of the period of observation is important. As far as we
know, all the contributions build on existing literature in novel ways.

###### Acknowledgements.

This work was supported by the Grantham Foundation for the Protection of the
Environment. We also thank the World University Network (WUN) for early
support of this work in 2014.

## References

  * Newman [2005] M. E. Newman, Power laws, Pareto distributions and Zipf’s law, Contemporary Physics 10.1080/00107510500052444 (2005), arXiv:0412004 [cond-mat] .
  * Stumpf and Porter [2012] M. P. Stumpf and M. A. Porter, Critical truths about power laws (2012).
  * Brunk [2000] G. G. Brunk, Understanding self-organized criticality as a statistical process, Complexity 10.1002/(SICI)1099-0526(200001/02)5:3¡26::AID-CPLX6¿3.0.CO;2-C (2000).
  * Reed [2001] W. J. Reed, The Pareto, Zipf and other power laws, Economics Letters 10.1016/S0165-1765(01)00524-9 (2001).
  * Jan  _et al._ [1999] N. Jan, L. Moseley, T. Ray, and D. Stauffer, Is the fossil record indicative of a critical system?, Advances in Complex Systems 10.1142/s0219525999000084 (1999).
  * Krasnytska  _et al._ [2021] M. Krasnytska, B. Berche, Y. Holovatch, and R. Kenna, Generalized ising model on a scale-free network: An interplay of power laws, Entropy 10.3390/e23091175 (2021).
  * Balkema and de Haan [1994] A. A. Balkema and L. de Haan, Residual Life Time at Great Age, The Annals of Probability 10.1214/aop/1176996548 (1994).
  * Pickands [1975] J. Pickands, Statistical Inference using Extreme Order Statistics, The Annals of Statistics (1975).
  * Alfarano and Lux [2010] S. Alfarano and T. Lux, Extreme Value Theory as a Theoretical Background for Power Law Behavior, World (2010).
  * Fisher and Tippett [1928] R. A. Fisher and L. H. Tippett, Limiting forms of the frequency distribution of the largest or smallest member of a sample, Mathematical Proceedings of the Cambridge Philosophical Society 10.1017/S0305004100015681 (1928).
  * Gnedenko [1943] B. Gnedenko, Sur La Distribution Limite Du Terme Maximum D’Une Serie Aleatoire, The Annals of Mathematics 10.2307/1968974 (1943).
  * Sornette [2006] D. Sornette,  _Critical Phenomena in Natural Sciences. Chaos, Fractals, Selforganization and Disorder: Concepts and Tools_ (Springer, 2006) pp. 12–21.
  * Bak  _et al._ [1987] P. Bak, C. Tang, and K. Wiesenfeld, Self-organized criticality: An explanation of the 1/f noise, Physical Review Letters 10.1103/PhysRevLett.59.381 (1987).
  * Olami  _et al._ [1992] Z. Olami, H. J. S. Feder, and K. Christensen, Self-organized criticality in a continuous, nonconservative cellular automaton modeling earthquakes, Physical Review Letters 10.1103/PhysRevLett.68.1244 (1992).
  * Beggs and Plenz [2003] J. M. Beggs and D. Plenz, Neuronal Avalanches in Neocortical Circuits, Journal of Neuroscience 10.1523/jneurosci.23-35-11167.2003 (2003).
  * McKenzie and Kennedy [2012] D. McKenzie and M. C. Kennedy, Power laws reveal phase transitions in landscape controls of fire regimes, Nature Communications 10.1038/ncomms1731 (2012).
  * Frigg [2003] R. Frigg, Self-organised criticality—what it is and what it isn’t, Studies in History and Philosophy of Science Part A 34, 613 (2003).
  * Hughes [1995] B. D. Hughes,  _Random Walks and Random Environments: Random walks, Volume 1_ (Cleradon Press, 1995).
  * Vignat and Plastino [2006] C. Vignat and A. Plastino, Power-law random walks, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 10.1103/PhysRevE.74.051124 (2006), arXiv:0606768 [cond-mat] .
  * Corominas-Murtra  _et al._ [2015] B. Corominas-Murtra, R. Hanel, and S. Thurner, Understanding scaling through history-dependent processes with collapsing sample space, PNAS 10.1073/pnas.1420946112 (2015), arXiv:1407.2775 .
  * Mazzolini  _et al._ [2018] A. Mazzolini, J. Grilli, E. De Lazzari, M. Osella, M. C. Lagomarsino, and M. Gherardi, Zipf and Heaps laws from dependency structures in component systems, Physical Review E 10.1103/PhysRevE.98.012315 (2018), arXiv:1801.06438 .
  * E. and Yule [1925] F. Y. E. and G. U. Yule, A Mathematical Theory of Evolution Based on the Conclusions of Dr. J. C. Willis, F.R.S., Journal of the Royal Statistical Society 10.2307/2341419 (1925).
  * Simon [1955] H. A. Simon, On a Class of Skew Distribution Functions, Biometrika 10.2307/2333389 (1955).
  * Krapivsky  _et al._ [2000] P. L. Krapivsky, S. Redner, and F. Leyvraz, Connectivity of growing random networks, Physical Review Letters 10.1103/PhysRevLett.85.4629 (2000), arXiv:0005139 [cond-mat] .
  * Carlson and Doyle [1999] J. M. Carlson and J. Doyle, Highly optimized tolerance: A mechanism for power laws in designed systems, Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics 10.1103/PhysRevE.60.1412 (1999).
  * Carlson and Doyle [2000] J. M. Carlson and J. Doyle, Highly optimized tolerance: Robustness and design in complex systems, Physical Review Letters 10.1103/PhysRevLett.84.2529 (2000).
  * Sneppen and Newman [1997] K. Sneppen and M. E. Newman, Coherent noise, scale invariance and intermittency in large systems, Physica D: Nonlinear Phenomena 10.1016/S0167-2789(97)00128-0 (1997), arXiv:9611229 [cond-mat] .
  * Sibani and Littlewood [1993] P. Sibani and P. B. Littlewood, Slow dynamics from noise adaptation, Physical Review Letters 10.1103/PhysRevLett.71.1482 (1993).
  * Kanazawa and Sornette [2020] K. Kanazawa and D. Sornette, Nonuniversal Power Law Distribution of Intensities of the Self-Excited Hawkes Process: A Field-Theoretical Approach, Physical Review Letters 10.1103/PhysRevLett.125.138301 (2020), arXiv:2001.01195 .
  * Schulman [2021] L. S. Schulman, Apparent power laws can occur without criticality, Entropy 10.3390/e23111486 (2021).
  * Biro and Néda [2017] T. S. Biro and Z. Néda, Dynamical stationarity as a result of sustained random growth, Physical Review E 95, 032130 (2017).
  * Biro and Neda [2018] T. S. Biro and Z. Neda, Unidirectional random growth with resetting, Physica A: Statistical Mechanics and its Applications 499, 335 (2018).
  * Biró  _et al._ [2019] T. S. Biró, Z. Néda, and A. Telcs, Entropic divergence and entropy related to nonlinear master equations, Entropy 21, 993 (2019).
  * Gere  _et al._ [2021] I. Gere, S. Kelemen, G. Tóth, T. S. Biró, and Z. Néda, Wealth distribution in modern societies: Collected data and a master equation approach, Physica A: Statistical Mechanics and its Applications 581, 126194 (2021).
  * Biró  _et al._ [2021] T. S. Biró, L. Csillag, and Z. Néda, Transient dynamics in the random growth and reset model, Entropy 23, 306 (2021).
  * Inácio and Velhinho [2022] I. Inácio and J. Velhinho, Comments on mathematical aspects of the biró–néda model, Mathematics 10, 644 (2022).
  * Gerlach and Altmann [2019] M. Gerlach and E. G. Altmann, Testing Statistical Laws in Complex Systems, Physical Review Letters 10.1103/PhysRevLett.122.168301 (2019), arXiv:1904.11624 .
  * Pinto  _et al._ [2012] C. M. Pinto, A. Mendes Lopes, and J. A. Machado, A review of power laws in real life phenomena (2012).
  * Gabaix [2016] X. Gabaix, Power laws in economics: An introduction (2016).
  * Naisbitt  _et al._ [2008] A. Naisbitt, R. Forster, K. Birkeland, and W. Harrison, Avalanche frequency and magnitude: using power-law exponents to investigate snow avalanche size proportions through space and time, Proceedings of the 2008 International Snow Science Workshop (2008).
  * Polizzi  _et al._ [2021] S. Polizzi, F. J. Pérez-Reche, A. Arneodo, and F. Argoul, Power-law and log-normal avalanche size statistics in random growth processes, Physical Review E 10.1103/PhysRevE.104.L052101 (2021), arXiv:2107.08002 .
  * Lu and Hamilton [1991] E. T. Lu and R. J. Hamilton, Avalanches and the distribution of solar flares, The Astrophysical Journal 10.1086/186180 (1991).
  * Neukum and Ivanov [1994] G. Neukum and B. Ivanov, Crater Size Distributions and Impact Probabilities on Earth from Lunar, Terrestrial Planeta, and Asteroid Cratering Data (1994).
  * Turcotte and Rundle [2002] D. L. Turcotte and J. B. Rundle, Self-organized complexity in the physical, biological, and social sciences, PNAS 10.1073/pnas.012579399 (2002).
  * Simkin and Roychowdhury [2014] M. V. Simkin and V. P. Roychowdhury, Stochastic modeling of a serial killer, Journal of Theoretical Biology 355, 111 (2014).
  * Gessey-Jones  _et al._ [2020] T. Gessey-Jones, C. Connaughton, R. Dunbar, R. Kenna, P. MacCarron, C. O’Conchobhair, and J. Yose, Narrative structure of A Song of Ice and Fire creates a fictional world with realistic measures of social complexity, PNAS 10.1073/pnas.2006465117 (2020), arXiv:2012.01783 .
  * Bertolotti and Roman [2022] F. Bertolotti and S. Roman, Risk sensitive scheduling strategies of production studios on the US movie market: An agent-based simulation, Intelligenza Artificiale 16, 81 (2022).
  * Pareto [1896] V. Pareto,  _Écrits sur la courbe de la répartition de la richesse_ (1896).
  * Axtell [2001] R. L. Axtell, Zipf Distribution of U.S. Firm Sizes, Science 293, 1818 (2001).
  * Schneider and Gros [2019] L. Schneider and C. Gros, Five decades of US, UK, German and Dutch music charts show that cultural processes are accelerating, Royal Society Open Science 10.1098/rsos.190944 (2019), arXiv:1908.10694 .
  * Ribeiro  _et al._ [2018] A. S. Ribeiro, F. L. Pinheiro, F. C. Santos, A. Polónia, and J. M. Pacheco, Structural and temporal patterns of the first global trading market, Royal Society Open Science 10.1098/rsos.180577 (2018).
  * Plerou  _et al._ [2005] V. Plerou, P. Gopikrishnan, and H. E. Stanley, Quantifying fluctuations in market liquidity: Analysis of the bid-ask spread, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 10.1103/PhysRevE.71.046131 (2005).
  * Bouchaud  _et al._ [2009] J. P. Bouchaud, J. D. Farmer, and F. Lillo, How Markets Slowly Digest Changes in Supply and Demand, in  _Handbook of Financial Markets: Dynamics and Evolution_ (North Holland, 2009) arXiv:0809.0822 .
  * Kyle and Obizhaeva [2013] A. S. Kyle and A. A. Obizhaeva, Market Microstructure Invariance: Theory and Empirical Tests (2013), not published in a journal.
  * Ivanov  _et al._ [2004] P. C. Ivanov, A. Yuen, B. Podobnik, and Y. Lee, Common scaling patterns in intertrade times of us stocks, Physical Review E 69, 056107 (2004).
  * Wu  _et al._ [2019] L. Wu, C. Gong, and X. Yan, Taylor’s power law and its decomposition in urban facilities, Royal Society Open Science 10.1098/rsos.180770 (2019).
  * Kühnert  _et al._ [2006] C. Kühnert, D. Helbing, and G. B. West, Scaling laws in urban supply networks, Physica A: Statistical Mechanics and its Applications 10.1016/j.physa.2006.01.058 (2006).
  * Gabaix and Ioannides [2004] X. Gabaix and Y. M. Ioannides, The evolution of city size distributions, in  _Handbook of Regional and Urban Economics_ (North Holland, 2004).
  * Rozenfeld  _et al._ [2011] H. D. Rozenfeld, D. Rybski, X. Gabaix, and H. A. Makse, The area and population of cities: New insights from a different perspective on cities, American Economic Review 10.1257/aer.101.5.2205 (2011), arXiv:1001.5289 .
  * Mori  _et al._ [2020] T. Mori, T. E. Smith, and W. T. Hsu, Common power laws for cities and spatial fractal structures, PNAS 10.1073/pnas.1913014117 (2020).
  * Barabási and Albert [1999] A. L. Barabási and R. Albert, Emergence of scaling in random networks, Science 10.1126/science.286.5439.509 (1999), arXiv:9910332 [cond-mat] .
  * Faloutsos  _et al._ [1999] M. Faloutsos, P. Faloutsos, and C. Faioutsos, On power-law relationships of the internet topology, Computer Communication Review 10.1145/316194.316229 (1999).
  * Adamic and Huberman [2005] L. Adamic and B. A. Huberman, The Nature of Markets in the World Wide Web, SSRN Electronic Journal 10.2139/ssrn.166108 (2005).
  * De Solla Price [1965] D. J. De Solla Price, Networks of scientific papers, Science 10.1126/science.149.3683.510 (1965).
  * Grueneberg  _et al._ [2008] D. A. Grueneberg, S. Degot, J. Pearlberg, W. Li, J. E. Davies, A. Baldwin, W. Endege, J. Doench, J. Sawyer, Y. Hu, F. Boyce, J. Xian, K. Munger, and E. Harlow, Kinase requirements in human cells: I. Comparing kinase requirements across various cell types, PNAS 10.1073/pnas.0808019105 (2008).
  * Fedorov  _et al._ [2010] O. Fedorov, S. Müller, and S. Knapp, The (un)targeted cancer kinome (2010).
  * Clauset and Wiegel [2010] A. Clauset and F. W. Wiegel, A generalized aggregation-disintegration model for the frequency of severe terrorist attacks, Journal of Conflict Resolution 10.1177/0022002709352452 (2010), arXiv:0902.0724 .
  * Zwetsloot [2018] R. Zwetsloot, Testing Richardson’s Law: A (Cautionary) Note on Power Laws in Violence Data, SSRN Electronic Journal 10.2139/ssrn.3112804 (2018).
  * Roman and Palmer [2019] S. Roman and E. Palmer, The growth and decline of the western roman empire: quantifying the dynamics of army size, territory, and coinage, Cliodynamics 10 (2019).
  * Ramos  _et al._ [2021] P. L. Ramos, L. F. Costa, F. Louzada, and F. A. Rodrigues, Power laws in the Roman Empire: A survival analysis, Royal Society Open Science 10.1098/rsos.210850 (2021), arXiv:2008.10344 .
  * Stefan [1879] J. Stefan, Uber die beziehung zwischen der war̈mestrahlung und der temperatur, Wiener Ber. II 79 (1879).
  * Boltzmann [1884] L. Boltzmann, Ableitung des Stefan’schen Gesetzes, betreffend die Abhängigkeit der War̈mestrahlung von der Temperatur aus der electromagnetischen Lichttheorie, Ann. der Phys. und Chemie 22 (1884).
  * Tully and Fisher [1977] R. B. Tully and J. R. Fisher, A new method of determining distances to galaxies, Astronomy and Astrophysics 54, 661 (1977).
  * Chew and Frautschi [1962] G. F. Chew and S. C. Frautschi, Regge trajectories and the principle of maximum strength for strong interactions, Physical Review Letters 8 (1962).
  * Cheng  _et al._ [2013] A. Cheng, A. Hasenfratz, G. Petropoulos, and D. Schaich, Scale-dependent mass anomalous dimension from dirac eigenmodes, Journal of High Energy Physics 2013, 1 (2013).
  * Del Debbio  _et al._ [2013] L. Del Debbio, B. Lucini, C. Pica, A. Patella, A. Rago, and S. Roman, Large-volume results in su (2) with adjoint fermions, arXiv preprint arXiv:1311.5597 (2013).
  * Brody and Lardy [1946] S. Brody and H. A. Lardy, Bioenergetics and growth., The Journal of Physical Chemistry 50, 168 (1946).
  * Benedict and Others [1938] F. G. Benedict and Others, Vital energetics. A study in comparative basal metabolism., Vital energetics. A study in comparative basal metabolism. (1938).
  * Kleiber and Others [1961] M. Kleiber and Others, The fire of life. An introduction to animal energetics., The fire of life. An introduction to animal energetics. (1961).
  * Niklas and Kutschera [2015] K. J. Niklas and U. Kutschera, Kleiber’s Law: How the Fire of Life ignited debate, fueled theory, and neglected plants as model organisms., Plant signaling & behavior 10, e1036216 (2015).
  * Zipf [1949] G. K. Zipf,  _Human behavior and the principle of least effort_ (Cambridge, (Mass.): Addison-Wesley, 1949) p. pp. 573.
  * Manaris  _et al._ [2006] B. Manaris, L. Pellicoro, G. Pothering, and H. Hodges, Investigating Esperanto’s statistical proportions relative to other languages using neural networks and Zipf’s law, in  _Proceedings of the IASTED Int. Conf. on Artificial Intelligence and Applications, AIA 2006_ (2006).
  * Mandelbrot [1968] B. Mandelbrot, Information theory and psycholinguistics: A theory of word frequencies, Readings in mathematical social science (1968).
  * Kasthurirathna and Piraveenan [2015] D. Kasthurirathna and M. Piraveenan, Emergence of scale-free characteristics in socio-ecological systems with bounded rationality, Scientific reports 5, 1 (2015).
  * Roman and Brede [2017] S. Roman and M. Brede, Topology-dependent rationality and quantal response equilibria in structured populations, Physical Review E 95, 052310 (2017).


#  Graphical quantum Clifford-encoder compilers from the ZX calculus

Andrey Boris Khesin<EMAIL_ADDRESS>Department of Mathematics, Massachusetts
Institute of Technology, Cambridge, MA  Jonathan Z. Lu<EMAIL_ADDRESS>Department of Mathematics, Massachusetts Institute of Technology, Cambridge,
MA  Peter W. Shor<EMAIL_ADDRESS>Department of Mathematics, Massachusetts
Institute of Technology, Cambridge, MA

(January 04, 2024)

###### Abstract

We present a quantum compilation algorithm that maps Clifford encoders,
encoding maps for stabilizer quantum codes, to a unique graphical
representation in the ZX calculus. Specifically, we develop a canonical form
in the ZX calculus and prove canonicity as well as efficient reducibility of
any Clifford encoder into the canonical form. The diagrams produced by our
compiler visualize information propagation and entanglement structure of the
encoder, revealing properties that may be obscured in the circuit or
stabilizer-tableau representation. Consequently, our canonical representation
may be an informative technique for the design of new stabilizer quantum codes
via graph theory analysis.

††preprint: APS/123-QED

##  I Introduction

Quantum algorithms have been shown to solve a broad range of computational
problems ranging from search to physical simulation [1, 2, 3, 4, 5, 6, 7, 8].
Recent progress in the experimental realization of scalable quantum computers
have further generated excitement about the potential of quantum algorithms in
practice [9, 10, 11, 12, 13]. Often, however, a quantum algorithm may not be
in a representation that is most conducive to how one wants to study it. For
example, an algorithm may be expressed in terms of higher-level unitary
operations (e.g. a quantum Fourier transform operator, continuous rotation
gates, etc.), while an actual quantum computer can only implement a finite
(albeit hopefully universal) set of gates. This is akin to the classical
motivation for compilers, which map high-level programming languages in which
algorithms are expressed into a universal set of boolean-circuit gates. A
similar compiler can be devised for the quantum realm, using the famous
Solovay-Kitaev theorem which has been recently been improved to rely on fewer
assumptions about the finite gate set itself [14]. Beyond this fundamental
result, there has been a recent flurry of results related to quantum
compilation from high-level operations to a finite gate set [15, 16, 17, 18,
19, 20, 21]. The choice of finite gate set is typically chosen to be Clifford
(Hadamard, phase, and controlled-NOT gates) set plus the $T$ gate, where
$T=\ket{0}\bra{0}+e^{i\pi/4}\ket{1}\bra{1}$, which is universal [8, 19].

Yet the idea of compilation can extend far beyond the realm of high-to-low-
level transformations of quantum gates; any undesirable property of an
algorithm’s representation can motivate the construction of a compiler that
maps the algorithm into a more useful representation for the task at hand. We
are specifically motivated by the fact that the circuit representation of
quantum operations can often blur the output’s entanglement structure (in the
intuitive sense of understanding how the circuit entangles the input qubits
just by looking at it). The circuit diagram may also obscure the structure of
information propagation, i.e. which qubits affect the values of which other
qubits.

In this paper, we work towards a compiler that resolves such issues by
producing a representation that explicitly illustrates information propagation
and entanglement structure. Our representation technique is designed not for a
universal gate set, but rather the restricted set of Clifford operations. Each
Clifford circuit is mapped into a visual graph diagram that we design to have
the above properties. Although Clifford operations are not universal, they are
used widely in studies of fault-tolerant quantum computation [8, 22] and
quantum coding theory [23, 24, 25, 26, 27, 8]. The central importance of
Clifford operations in quantum error correction motivates us to specifically
compile Clifford circuits that act as encoders for quantum codes. As such, we
specifically design a canonical, diagrammatic form for Clifford circuits such
that the canonical form is the same for all circuits that produce the same
encoding map. This notion is defined formally in the next section.

###  I.1 Related Work

Our paper generalizes the previous work of Hu and Khesin [28], which produces
canonical forms for stabilizer states. Stabilizer states may be thought of as
a complete stabilizer tableau, i.e. an $n$-qubit state which is fully
specified by $n$ Pauli stabilizers, whereas Clifford circuits may be thought
of as incomplete stabilizer tableaus. We show this correspondence more
explicitly in a later section. Building upon Hu and Khesin [28], McElvanney
and Backens [29] derived a different unique canonical form for stabilizer
states that are particularly convenient for measurement-based quantum
computation.

A recent work of Kissinger [30] developed independently of this work also
constructs diagrammatic forms, but restricted further to CSS codes. In this
manner our work can be viewed as a canonicalization and generalization of
Kissinger [30] to all stabilizer codes. Indeed, the CSS construction of [30]
produces diagrammatic representations that are bipartite graphs, while our
diagrams are generalizations of bipartite graphs called semi-bipartite graphs,
which are defined later.

More generally, graphical approaches to quantum error correction have been
considered in two ways. The first is the analysis of code constructions by way
of corresponding diagrammatic forms, such as the study of graph codes in Wu
_et al._ [31]. The second is the use of certain diagrammatic correspondences
to design quantum codes by quantization of classical analogs, e.g. the
construction of Chancellor  _et al._ [32]. Our approach to a new canonical
form takes a step towards the analysis of quantum codes by the properties of
their canonical diagrammatic form, as well as the construction of new and more
general (not necessarily CSS) stabilizer codes based on desirable graph-
theoretic conditions of their corresponding diagram.

##  II Theory & Construction

Our main tool is the ZX-calculus, a graphical language for vectors that has
become of great interest in quantum information research [33, 34, 35, 36, 37,
30]. The ZX-calculus produces visual diagrams that represent quantum states,
circuits, and more. As with any formal logical system, the ZX calculus has a
set of rules which may be iteratively applied to transform diagrams into
equivalent diagrams. These rules are representations of identities in quantum
circuits. The ZX-calculus has become of more interest than ever in fault-
tolerant quantum computation and quantum compiler theory because it can
explicitly visualize quantum properties such as entanglement in an intuitive
manner. It has recently been applied to a host of quantum computation
problems, including lattice surgery [38] and quantum optimization [39].
Importantly, the ZX-calculus is, for stabilizer tableaus, complete (equalities
of tableaus can be derived from corresponding ZX diagrams), sound (vice
versa), and universal (every quantum operation can be expressed in the ZX-
calculus) [33, 40].

We are consequently motivated to leverage the ZX calculus as a graphical
presentation to which quantum circuits can be compiled. We are specifically
interested in circuits that produce stabilizer quantum codes, a new
representation of which may open new pathways to study quantum error
correction. Aside from efficient computability, one desirable property of a
ZX-calculus diagram compiler is uniqueness—any two equivalent input
representations map to the same ZX-calculus diagram. For most compilation
problems (e.g. programming language compilers) such a property is far too
strong. Many heuristic compilers that work well in practice do not satisfy
uniqueness. However, for the case of stabilizer compilation into ZX diagrams
we will show that uniqueness is indeed achievable. We thus denote these
diagrams ZX canonical forms (ZXCFs). An immediate consequence for a ZXCF
compiler is a diagrammatic method of testing equality between stabilizer
codes. Much room for exploration remains for the construction of such forms in
the most general case. As a first step, Hu and Khesin [28] recently
investigated the idea of ZXCFs on stabilizer states, and showed the following.

######  Theorem II.1 (Hu and Khesin [28]).

There exists a ZXCF for stabilizer quantum states, which we call the HK form.

Although Hu and Khesin did not use ZX calculus in their work, their
construction uses graph states decorated with single-qubit operators, which
can be mapped directly to ZX calculus by a manner we will briefly describe. A
HK diagram is constructed by starting with a graph state—a state corresponding
to an undirected graph wherein the nodes become $\ket{+}$ qubits and the edges
become controlled-$Z$ gates. Each node is then endowed with a single free
edge, which does not connect to any other node. Local Clifford operations in
$\langle H,S,Z\rangle$ are then applied to the qubits. Such a construction has
the capacity to express any stabilizer state. A direct mapping enables the
presentation of a HK diagram into the ZX calculus.

  * •

HK vertices become $Z$ nodes, as a vertex in a graph state begins in the state
$\ket+$, which is a $Z$ node with a single output.

  * •

HK (non-free) edges become (non-free) edges with Hadamard gates, as both of
these correspond to $CZ$ gates.

  * •

HK local operations of $S$, $Z$, or $SZ$ become phases on the corresponding
node of $\frac{\pi}{2}$, $\pi$, and $\frac{3\pi}{2}$, respectively. The local
operation $H$ becomes a Hadamard gate on the node’s free edge.

Thus, we will without loss consider HK forms to be in the ZX calculus
representation and denote them ZX-HK forms. We remark that transformations of
similar decorated graph state families into ZX calculus presentations have
been considered in other contexts, such as in Backens [40].

The work of Hu and Khesin [28] analysis motivates our construction of a ZXCF
for quantum circuits, though we restrict ourselves to Clifford circuits. More
precisely, we compile Clifford encoders, in which we quotient Clifford
circuits in a manner most natural for error correction.

######  Definition II.2.

Two circuits are equivalent Clifford encoders if they have the same image over
all possible input states. Equivalently, $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ are equivalent encoders if there exists a unitary $U$ such
that $\mathcal{C}_{1}=\mathcal{C}_{2}U$ or $\mathcal{C}_{2}=\mathcal{C}_{1}U$.

We will first construct a ZXCF that illustrates information propagation and
entanglement. We will then describe the full compilation algorithm and show
that it is efficient. Lastly, we prove that every Clifford encoder maps to a
unique ZXCF, establishing its canonicity.

We note that encoders have the same expressive power as incomplete stabilizer
tableaus—stabilizer matrices of size $k\times n$ that do not fully specify a
state. Complete stabilizer tableaus are the crux of the Gottesman-Knill
theorem, which proves the efficient classical simulatability of Clifford
circuits [41] by using a complete stabilizer tableau to represent a stabilizer
state. On the other hand, because incomplete tableaus do not uniquely pin down
a state, they indirectly encode the logical qubits in stabilizer quantum
codes. In fact, incomplete stabilizer tableaus are exactly equivalent to
Clifford encoders, and are used widely in error-correcting protocols [26, 42,
27]. Consequently, after we construct a graphical compilation procedure for
Clifford encoders, we will do the same for incomplete stabilizer tableaus.

###  II.1 Canonical Form Construction

We follow the standard notation of ZX-calculus graph diagrammatics, specified
in Backens [40]; we refer the reader there for the basics of the ZX calculus
and transformation rules. Green nodes are associated with $Z$ operators, and
red with $X$. Each node may be associated with a local Clifford operator
(which may be expressed as a phase which is a multiple of $\pi/2$), and each
edge may have a Hadamard gate on it. We color an edge blue if it has a
Hadamard gate on it [43] (some papers use instead a line with a box, e.g.
[40]). The circuit takes $n-k$ input qubits to $n$ output qubits, for $k\geq
0$. We define our ZXCF in this paper to be in encoder-respecting form if the
diagram is structured as follows.

######  Definition II.3.

An encoder-respecting form $\mathcal{D}$ has only green nodes, and is
structured as a semi-bipartite graph. A semi-bipartite graph is a graph with
left and right clusters, such that left-cluster nodes may have edges only to
right-cluster nodes, but right-cluster nodes have no such restrictions. In our
case, the left and right cluster are denoted as the input and output clusters,
respectively. The input cluster $\mathcal{I}$ has $n-k$ nodes associated with
the $n-k$ input qubits of the corresponding encoder, and the output cluster
$\mathcal{O}$ has $n$ nodes. Each input node has a free (not connected to any
other nodes) edge—the input edge. Similarly, each output node has a free
output edge. The output edges are numbered from $1$ to $n$—in order from left
to right on an incomplete stabilizer tableau or top to bottom on Clifford
circuit output wires. For convenience, we refer to the node $v$ connected to
an output edge numbered $i$ as the output node numbered $i$.

The design of the encoder-respecting form graphically illustrates how
information propagates from input to output (which edges connect $\mathcal{I}$
to $\mathcal{O}$) as well as the entanglement structure (which edges connect
$\mathcal{O}$ to $\mathcal{O}$) of the underlying encoder. Note that the
structure of $\mathcal{D}$ gives rise to a natural binary “partial adjacency
matrix” $M_{\mathcal{D}}$ of size $(n-k)\times n$, which describes the edges
between $\mathcal{I}$ and $\mathcal{O}$ akin to the standard graph adjacency
matrix.

Given a good structure, all that remains in a compiler is to ensure a
canonical form, so that the map from encoder to ZX diagrams is well-defined.
We constrain an encoder-respecting form into a ZXCF via four additional rules.

  1. 1.

Edge Rule: The ZXCF must have exactly one $Z$ node per free edge and every
internal edge in our ZXCF must have a Hadamard gate on it.

  2. 2.

Hadamard Rule: No output node $v$ may both have a Hadamard gate on its output
edge and have edges connecting $v$ to lower-numbered nodes or input nodes.

  3. 3.

RREF Rule: $M_{\mathcal{D}}$ must be in reduced row-echelon form (RREF).

  4. 4.

Clifford Rule: Let $\mathcal{P}\subseteq\mathcal{O}$ be the nodes associated
with the pivot columns of the RREF matrix $M_{\mathcal{D}}$, so that
$|\mathcal{P}|=n-k$. There can be no local Clifford operations
$\\{I,S,Z,SZ,H,HZ\\}$ on input or pivot nodes, or their free edges. There can
be no input-input edges or pivot-pivot edges.

Figure 1: Example of an encoder-respecting form and some ways it might violate
the 4 rules.

Intuitively, the first two rules prevent diagrammatic simplifications via the
ZX transformation identities. The RREF rule allows for the usage of linear
algebra to uniquely reduce the connectivity between the input and output. In
the graphical representation of the ZXCF, pivot nodes correspond to a subset
of nodes in $\mathcal{O}$ that connect to exactly one input; the subset is
such that $\mathcal{P}$ is in one-to-one correspondence with $\mathcal{I}$.
The Clifford rule extends the semi-bipartite constraint on edges by
disallowing connections between pivots.

These four rules are sufficient to produce a ZXCF; we will show the following.

######  Theorem II.4.

Any Clifford encoder has a unique equivalent ZXCF satisfying the Edge,
Hadamard, RREF, and Clifford rules. There is an efficient algorithm to
canonicalize the ZX encoder.

To provide some visual intuition on these 4 rules, Fig. 1 depicts a generic
example of some possible violations to the rules.

The sequence of maps that we develop to reach the ZXCF are shown in Fig. 2.

Figure 2: Schematic map diagram of the sequence of operations into the
compilation of a ZXCF.

We focus first on mapping Clifford encoders to ZXCF, then return to incomplete
tableaus below. To begin, we apply the following lemma, which enables us to
build upon the machinery developed in Hu and Khesin [28].

######  Lemma II.5.

There exists an efficient transformation of a ZX encoder diagram with $n-k$
input edges and $n$ output edges into a corresponding ZX presentation of a
stabilizer state in ZX-HK form, with $n+(n-k)=2n-k$ free edges.

The proof of this lemma is relegated to the Appendix.

Application of Lemma II.5 results in a ZX-HK form. That is, there is one $Z$
node per vertex of the graph in HK form, with any internal edge having a
Hadamard gate on it. Free edges can only have Hadamard gates on them if their
phase is a multiple of $\pi$, corresponding to the local Clifford gates $H$
and $HZ$ in HK form, and if the associated node is not connected to any lower-
numbered nodes. Nodes whose free edges have no Hadamard gate are free to have
any multiple of $\frac{\pi}{2}$ as a phase, corresponding to local Clifford
operations $I$, $S$, $Z$, or $SZ$, respectively.

We are now equipped with a ZX-HK diagram that represents a state. This diagram
has only output edges. To return it into an encoder diagram, we partition the
$2n-k$ free edges into $n-k$ input edges and $n$ output edges. In the circuit
representation, this is equivalent to turning bra’s into ket’s and vice versa
to map between an operator and a state. For example,
$\ket{00}\bra{1}-\ket{11}\bra{0}\leftrightarrow\ket{001}-\ket{110}$. Now, if
there are any edges between input nodes (those in $\mathcal{I}$), we can
simply remove them. They correspond to controlled-$Z$ operations, and we can
take off any unitary operation on the input by the encoder definition. The
same goes for local Cliffords on $\mathcal{I}$.

At this stage, the obtained ZX-HK form is in encoder-respecting form. It also
satisfies the Edge and Hadamard rules—there are no input edges in ZX-HK form
so the analogous rule is enforced only on lowered-numbered nodes, but if we
number the nodes from the beginning such that the input nodes are lowered-
numbered than all output nodes, then the transformed ZX-HK form will satisfy
our ZXCF Hadamard rule. So, all that remains is to simplify the diagram to
obey the RREF and Clifford rules. The former is given by the following
theorem, which is proven in the Appendix.

######  Lemma II.6.

An encoder diagram in ZX-HK form can be efficiently transformed to satisfy the
RREF rule, while continuing to satisfy the Edge and Hadamard rules.

The only remaining task is to enforce the Clifford rule. For any pivot node
$p\in\mathcal{P}$ with a non-zero phase, denote $v_{\text{in}}$ its associated
input node. We apply a local complementation about $v_{\text{in}}$, which
notably does not change the entries of $M_{\mathcal{D}}$. However, this
operation also increases the phase of each neighbors of $v_{\text{in}}$ by
$\frac{\pi}{2}$ (due to multiplication by $S$) so we repeat this process until
the phase of that pivot vanishes. The local complementation transformation is
a ZX equivalence identity, and therefore is a valid operation on our diagram
[40].

Lastly, if there are any edges between pivots $p_{1}$ and $p_{2}$, we can
remove them by applying a different transformation $\phi$ to their pair of
associated input nodes $v_{1}$ and $v_{2}$. Let $N_{1}$ be the set of the
neighbours of $v_{1}$ as well as $v_{1}$ itself and let $N_{2}$ be defined
respectively. The effect of $\phi$ is to toggle all edges in the set
$N_{1}\times N_{2}$, including multiplicity. This means that edges that get
toggled twice are not affected. Any self-edge of the form $(v,v)$ is treated
as a $Z$ operation on vertex $v$. In addition, $\phi$ also applies an
additional local operation of $HZ$ to each of $v_{1}$ and $v_{2}$, but this
can be removed as $v_{1}$ and $v_{2}$ are input vertices. As a result of this,
we have swapped the neighbours of $v_{1}$ and $v_{2}$ as well as toggled the
one pivot-pivot edge we wish to flip, $(p_{1},p_{2})$. Note that $\phi$ does
not violate the RREF rule because once this process is complete we can simply
swap the neighbors back (without any toggling) via a row operation. This also
does not add any local operations to the nodes $p_{1}$ and $p_{2}$, as each is
only in one of $N_{1}$ and $N_{2}$, and thus does not receive a $Z$ operation.
We repeat until no pivot-pivot edges remain. $\phi$ can be shown to be a valid
ZX equivalence identity van de Wetering [44].

With that step, the transformation from Clifford encoder to ZXCF is complete.
Although this process may seem lengthy, all of these steps can be done
systematically in an efficient manner, without having to go back to fix
earlier rules. Specifically, this algorithm takes $O(n^{3})$ time. Creating
the HK diagram for the encoder requires us to apply $O(n)$ Pauli projections,
each of which can be applied in $O(n^{2})$ time. After the HK form is created,
operations such as row-reducing a matrix also take $O(n^{3})$ time. We suspect
that the time complexity cannot be improved in the worst case, but that there
is a lot of room for heuristic runtime improvements and optimizations.

###  II.2 Starting from tableaus

As shown in Fig. 2, we compile an incomplete stabilizer tableau by
transforming it into a Clifford encoder, and then applying the above. We will
construct our circuit in reverse, going from outputs to inputs. For a $k\times
n$ tableau, begin by drawing $n$ output wires. At each step, we first simplify
the tableau by applying a Clifford operation, and then “measure out” one of
the qubits to remove one row and column from the tableau. Repeating
inductively yields a Clifford circuit that takes $n-k$ qubits to $n$ qubits.

The procedure at each step begins by finding a Clifford operation $U$ that
turns the first stabilizer into $Z_{1}=Z\otimes I\otimes\dots\otimes I$, in
the manner dictated by the Gottesman-Knill theorem. $U$ is prepended to the
circuit under construction. We then multiply the remaining rows by the first
until the entire first column of the tableau has only $I$, with the exception
of the first row. This can always be done, since the $n$-qubit Pauli operators
in each row of the matrix must commute. We then post-select on the $+1$ result
of a computational basis measurement by applying $\bra 0$ in the reverse
direction. When reading the circuit in the forward direction, this is
equivalent to initializing an ancillary qubit in the $\ket 0$ state. The
effect of $U$ and the measurement is equivalent to applying $\frac{I+P}{2}$,
where $P$ is the first row of the stabilizer tableau. This is equivalent to
post-selecting on the $+1$ measurement result of that stabilizer. Having
measured the qubit, we remove its corresponding row and column from the
tableau, and repeat on a tableau of $n-1$ qubits and $k-1$ rows, until there
are no rows left, at which point the remaining $n-k$ wires that have not been
measured out become the input qubits in the circuit. We conclude by drawing
$n-k$ input wires for those qubits.

##  III Canonicity Proof & Applications

###  III.1  Proof of Canonicity

We next prove that our proposed ZXCF is indeed canonical. In other words, two
equivalent stabilizer tableaus—generators of the same subspace of the
$n$-qubit Hilbert space—will map to the same ZXCF. Ideally, we could construct
a clear correspondence between a stabilizer tableau and its resulting ZXCF.
This correspondence is achieved for CSS codes in Kissinger [30], wherein each
Pauli operator in the stabilizers of one type, either $X$ or $Z$, has
corresponding edges in the ZX diagram. However, such a technique comes at the
cost of introducing additional vertices with no free edges, that correspond to
stabilizers of the code. We found that for the ZXCF of generic stabilizer
codes and even for some CSS codes, the resulting graphs depend sensitively on
the codes’ stabilizers, in that small changes in the stabilizer tableau can
cause large changes in the ZXCF.

As a consequence, we believe it will be quite complicated to prove uniqueness
by finding an explicit correspondence or inverse between ZXCF diagrams and
tableaus. Instead, we proceed by a counting argument, showing that since the
total number of ZXCF diagrams and stabilizer tableaus are equal, the ZXCF is
unique for a given tableau. This argument does not elucidate the connection
between the two presentations, but does have the advantage of simplicity.

######  Lemma III.1.

The number of stabilizer tableaus on $n$ qubits with $k$ rows is equal to the
number of ZXCF diagrams with $n$ outputs and $n-k$ inputs.

First, the number of incomplete stabilizer tableaus with $k$ stabilizers on
$n$ qubits is

$\frac{\prod\limits_{i=1}^{k}2\cdot 4^{n}/2^{i-1}-2\cdot
2^{i-1}}{\prod\limits_{i=1}^{k}2^{k}-2^{i-1}}=\prod_{i=1}^{k}\frac{2^{2n-i+2}-2^{i}}{2^{k}-2^{i-1}}.$
(1)

For each row $i$, there are $2\cdot 4^{n}$ possible Pauli strings (including
the sign), but the requirement that they commute with previous rows divides
the count by $2^{i-1}$. Of these $2\cdot 4^{n}/2^{i-1}$ valid strings,
$2^{i-1}$ strings are linear combinations of previous strings, with a factor
of 2 for strings that differ by a sign from previous strings.

We have overcounted, however, since there are many ways to find a set of
stabilizer generators for a particular tableau. In particular, when choosing a
set of generators for a Clifford encoder, we have $2^{k}-1$ choices for the
first generator (subtracting the identity). There are then $2^{k}-2$ ways of
choosing the next element, as we cannot pick anything in the span of the
elements chosen so far. Repeating inductively gives the denominator above.

Next, the number of ZXCF diagrams for the same $n$ and $k$ can be expressed by
the following fourfold recursive function $f$ evaluated at $p=o=0$.

$f(n,k,p,o)=\begin{cases}1&\text{if }n=k=0\\\
A_{n,k,p,o}+B_{n,k,p,o}&\text{else}\end{cases}$ (2)

where

$A_{n,k,p,o}=2^{o}f(n-1,k,p+1,o)$ (3)

if $n\neq k$ and $A_{n,k,p,o}=0$ if $n=k$, and where

$B_{n,k,p,o}=(2^{2p+o+2}+2)f(n-1,k-1,p,o+1)$ (4)

if $k\neq 0$ and $B_{n,k,p,o}=0$ if $k=0$.

This function is computed with a base case of an empty tableau when $n=k=0$.
Derivation of this function is left to the Appendix. We solve for an explicit
form to obtain

$f(n,k,p,o)=\\\
2^{o(n-k)}\prod_{i=1}^{k}\frac{(2^{n+1}-2^{i})(2^{n-i+1+2p+o}+1)}{2^{k}-2^{i-1}}.$
(5)

One can verify by standard induction that $f(n,k,0,0)$ gives the same
expression as Eq. (1), proving that ZXCF is indeed canonical.

###  III.2 Application to Quantum Codes

To more concretely demonstrate the structure of the ZXCF, we provide three
examples on well-known quantum codes. Consider first the nine-qubit code, due
to Shor [26], which uses 9 physical qubits to encode 1 logical qubit. The Shor
code may be represented by the stabilizer tableau

$\displaystyle\begin{bmatrix}Z&Z&I&I&I&I&I&I&I\\\ Z&I&Z&I&I&I&I&I&I\\\
I&I&I&Z&Z&I&I&I&I\\\ I&I&I&Z&I&Z&I&I&I\\\ I&I&I&I&I&I&Z&Z&I\\\
I&I&I&I&I&I&Z&I&Z\\\ X&X&X&X&X&X&I&I&I\\\ X&X&X&I&I&I&X&X&X\end{bmatrix}.$ (6)

Application of our compilation method yields the ZXCF given in Fig. 3(a).
There are three identical sectors of the outputs, two with Hadamarded outputs
and one without. This resembles our expectations from examination of the un-
normalized qubit representation of the Shor code,
$(\ket{000}\pm\ket{111})^{\otimes 3}$. We may compare this to a comparably
simple but non-canonical form in Fig. 3(b) which one might heuristically
construct. We created Fig. 3(b) by using a ZX rule wherein a $Z$ node with two
Hadamarded edges can be replaced with a single non-Hadamarded edge. This
diagram has some similar visualization—and is in some senses simpler—but has
no obvious association of nodes with the qubits, which blurs interpretations
about information propagation or entanglement structure.

Figure 3: (a) a ZXCF of the nine-qubit code versus a (b) non-canonical
variant.

There is an additional simplification we can make to our ZXCF when the encoder
in question is for error correction. In particular, when one transmits encoded
qubits, the set of errors that can be corrected does not change if we apply
local Clifford operations to the encoding, since the space of $p$-qubit Pauli
errors is preserved. As a result, we can disregard the Hadamarded output edges
and the phases on the output nodes off error-correcting encoders. Any code
thus has an equivalent representation up to local Cliffords whose ZXCF
consists of nothing more than a semi-bipartite graph. We have therefore
proven:

######  Theorem III.2.

For any stabilizer code, there exists at least one equivalent code that has a
presentation as a semi-bipartite graph with no local Clifford operations.

A similar example is Steane’s seven-qubit code, a central construction in many
fault-tolerant quantum computation schemes [42]. The code is represented by an
incomplete stabilizer matrix

$\displaystyle\begin{bmatrix}I&I&I&X&X&X&X&\\\ I&X&X&I&I&X&X&\\\
X&I&X&I&X&I&X\\\ I&I&I&Z&Z&Z&Z\\\ I&Z&Z&I&I&Z&Z\\\
Z&I&Z&I&Z&I&Z\end{bmatrix}.$ (7)

In our ZXCF, this code takes the form given in Fig. 4. In particular, the
nodes of the diagram are simply the corners of a cube. A similar picture has
been given in a different context in Duncan and Lucas [45].

Figure 4: ZXCF of the seven-qubit code. The 8 nodes in the diagram form the
vertices of a boolean cube.

We observe that the stabilizers of the 7-qubit code are positioned at exactly
the $1$-indices in the binary representation of a node label. We can see
elegant symmetries in Fig. 4 with the positions of the nodes and their
expressions in binary. The reason why the nodes adjacent to 0 are not 1, 2,
and 4, (respectively 001, 010, and 100 in binary) is because the rules of the
ZXCF require that the Hadamarded output edges not be connected to lower-
numbered nodes.

As a final example we consider the five-qubit code, which is the smallest code
one can achieve for correction of an arbitrary single-qubit error and has been
studied experimentally [27, 46]. Its incomplete stabilizer representation is
given by

$\displaystyle\begin{bmatrix}X&Z&Z&X&I\\\ I&X&Z&Z&X\\\ X&I&X&Z&Z\\\
Z&X&I&X&Z\end{bmatrix}.$ (8)

Our procedure produces the ZXCF shown in Fig. 5.

Figure 5: ZXCF of the five-qubit code.

Note that the stabilizer tableau is just 4 cyclic permutations of the first
row. the ZXCF reflects this cyclic structure in the output explicitly.

##  IV Conclusion & Outlook

We introduced a quantum compiler mapping Clifford encoders and incomplete
stabilizer tableaus into a unique graphical form in the ZX calculus. The
representation of our canonical form as a semi-bipartite graph between input
and output qubits explicitly visualizes information propagation from input to
output, as well as entanglement structure of the output. We then proved
algorithmic efficiency and correctness of the compiler.

Our compilation technique takes a step towards the use of ZX-calculi as a
useful presentation of a general quantum error-correction encoding operation.
Whether the ZXCF technique can be generalized beyond Clifford gates—as our
construction relies crucially on them—is a next step in the exploration of ZX-
based quantum compilers. Most likely, if a generalization of this compiler
were to be designed for a universal gate set, the resulting ZX form would not
be canonical. Otherwise, the compiler could be used to test for equality of
arbitrary quantum circuits, a computationally difficult task. However,
considering other restricted families of circuits or relaxing the requirement
of uniqueness leaves open the door for practical constructions of other
graphical compilers.

An interesting direction of further research is the possibility of applying
our ZXCF to the decomposition of magic states into linear combinations of
stabilizer states. Another important direction is the analysis of the
correspondence between the quality of a code and its properties in the ZXCF
representation, using the machinery of graph theory. For example, perhaps a
particular connectivity structure lends to codes with desirable rates or
threshold. A better understanding of such a correspondence may inform better
ways to design new quantum codes.

## Acknowledgements

ABK was supported by the National Science Foundation (NSF) under Grant No.
CCF-1729369. PWS was supported by the NSF under Grant No. CCF-1729369, by the
NSF Science and Technology Center for Science of Information under Grant No.
CCF-0939370, by the U.S. Department of Energy, Office of Science, National
Quantum Information Science Research Centers, Co-design Center for Quantum
Advantage (C2QA) under contract number DE-SC0012704., and by NTT Research
Award AGMT DTD 9.24.20.

## References

  * Grover [1996] L. K. Grover, A fast quantum mechanical algorithm for database search, in  _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_ (1996) pp. 212–219.
  * Shor [1999] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review 41, 303 (1999).
  * Brakerski  _et al._ [2021] Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, and T. Vidick, A cryptographic test of quantumness and certifiable randomness from a single quantum device, Journal of the ACM (JACM) 68, 1 (2021).
  * Farhi  _et al._ [2012] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, and P. Shor, Quantum money from knots, in  _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference_ (2012) pp. 276–289.
  * Georgescu  _et al._ [2014] I. M. Georgescu, S. Ashhab, and F. Nori, Quantum simulation, Reviews of Modern Physics 86, 153 (2014).
  * Huang  _et al._ [2020] H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nature Physics 16, 1050 (2020).
  * Harrow  _et al._ [2004] A. Harrow, P. Hayden, and D. Leung, Superdense coding of quantum states, Physical review letters 92, 187901 (2004).
  * Nielsen and Chuang [2002] M. A. Nielsen and I. Chuang, Quantum computation and quantum information (2002).
  * Kandala  _et al._ [2019] A. Kandala, K. Temme, A. D. Córcoles, A. Mezzacapo, J. M. Chow, and J. M. Gambetta, Error mitigation extends the computational reach of a noisy quantum processor, Nature 567, 491 (2019).
  * Larsen  _et al._ [2019] M. V. Larsen, X. Guo, C. R. Breum, J. S. Neergaard-Nielsen, and U. L. Andersen, Deterministic generation of a two-dimensional cluster state, Science 366, 369 (2019).
  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, _et al._ , Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  * Wang  _et al._ [2019] H. Wang, J. Qin, X. Ding, M.-C. Chen, S. Chen, X. You, Y.-M. He, X. Jiang, L. You, Z. Wang, _et al._ , Boson sampling with 20 input photons and a 60-mode interferometer in a 1 0 14-dimensional hilbert space, Physical review letters 123, 250503 (2019).
  * Andersen  _et al._ [2020] C. K. Andersen, A. Remm, S. Lazar, S. Krinner, N. Lacroix, G. J. Norris, M. Gabureac, C. Eichler, and A. Wallraff, Repeated quantum error detection in a surface code, Nature Physics 16, 875 (2020).
  * Bouland and Giurgica-Tiron [2021] A. Bouland and T. Giurgica-Tiron, Efficient universal quantum compilation: An inverse-free solovay-kitaev algorithm, arXiv preprint arXiv:2112.02040 10.48550/arXiv.2112.02040 (2021).
  * Kliuchnikov  _et al._ [2013] V. Kliuchnikov, D. Maslov, and M. Mosca, Asymptotically optimal approximation of single qubit unitaries by clifford and t circuits using a constant number of ancillary qubits, Physical review letters 110, 190502 (2013).
  * Kliuchnikov  _et al._ [2012] V. Kliuchnikov, D. Maslov, and M. Mosca, Fast and efficient exact synthesis of single qubit unitaries generated by clifford and t gates, arXiv preprint arXiv:1206.5236 10.48550/arXiv.1206.5236 (2012).
  * Ross and Selinger [2016] N. J. Ross and P. Selinger, Optimal ancilla-free clifford+ t approximation of z-rotations, Quantum Inf. Comput. 16, 901 (2016).
  * Kliuchnikov  _et al._ [2015] V. Kliuchnikov, D. Maslov, and M. Mosca, Practical approximation of single-qubit unitaries by single-qubit quantum clifford and t circuits, IEEE Transactions on Computers 65, 161 (2015).
  * Selinger [2012] P. Selinger, Efficient clifford+t approximation of single-qubit operators, arXiv preprint arXiv:1212.6253 10.48550/arXiv.1212.6253 (2012).
  * Maronese  _et al._ [2022] M. Maronese, L. Moro, L. Rocutto, and E. Prati, Quantum compiling, in  _Quantum Computing Environments_ (Springer, 2022) pp. 39–74.
  * Moro  _et al._ [2021] L. Moro, M. G. Paris, M. Restelli, and E. Prati, Quantum compiling by deep reinforcement learning, Communications Physics 4, 178 (2021).
  * Gottesman [1997] D. Gottesman,  _Stabilizer codes and quantum error correction_ (California Institute of Technology, 1997).
  * Kitaev [1997] A. Y. Kitaev, Quantum error correction with imperfect gates, in  _Quantum communication, computing, and measurement_ (Springer, 1997) pp. 181–188.
  * Bravyi and Kitaev [1998] S. B. Bravyi and A. Y. Kitaev, Quantum codes on a lattice with boundary, arXiv preprint quant-ph/9811052 10.48550/arXiv.quant-ph/9811052 (1998).
  * Fowler  _et al._ [2012] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Physical Review A 86, 032324 (2012).
  * Shor [1995] P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Physical review A 52, R2493 (1995).
  * Gottesman [2009] D. Gottesman, An introduction to quantum error correction and fault-tolerant quantum computation, arXiv preprint arXiv:0904.2557 10.48550/arXiv.0904.2557 (2009).
  * Hu and Khesin [2022] A. T. Hu and A. B. Khesin, Improved graph formalism for quantum circuit simulation, Physical Review A 105, 022432 (2022).
  * McElvanney and Backens [2022] T. McElvanney and M. Backens, Complete flow-preserving rewrite rules for mbqc patterns with pauli measurements, arXiv preprint arXiv:2205.02009 10.4204/EPTCS.394.5 (2022).
  * Kissinger [2022] A. Kissinger, Phase-free zx diagrams are css codes (… or how to graphically grok the surface code), arXiv preprint arXiv:2204.14038 10.48550/arXiv.2204.14038 (2022).
  * Wu  _et al._ [2023] Z. Wu, S. Cheng, and B. Zeng, A zx-calculus approach to concatenated graph codes, arXiv preprint arXiv:2304.08363 10.48550/arXiv.2304.08363 (2023).
  * Chancellor  _et al._ [2016] N. Chancellor, A. Kissinger, S. Zohren, J. Roffe, and D. Horsman, Graphical structures for design and verification of quantum error correction, Quantum Science and Technology 10.1088/2058-9565/acf157 (2016).
  * Coecke and Duncan [2008] B. Coecke and R. Duncan, Interacting quantum observables, in  _International Colloquium on Automata, Languages, and Programming_ (Springer, 2008) pp. 298–310.
  * Peham  _et al._ [2022] T. Peham, L. Burgholzer, and R. Wille, Equivalence checking of quantum circuits with the zx-calculus, IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12, 662 (2022).
  * Cowtan and Majid [2022] A. Cowtan and S. Majid, Quantum double aspects of surface code models, Journal of Mathematical Physics 63, 042202 (2022).
  * van de Wetering [2021] J. van de Wetering, Constructing quantum circuits with global gates, New Journal of Physics 23, 043015 (2021).
  * East  _et al._ [2022] R. D. East, J. van de Wetering, N. Chancellor, and A. G. Grushin, Aklt-states as zx-diagrams: diagrammatic reasoning for quantum states, PRX Quantum 3, 010302 (2022).
  * de Beaudrap and Horsman [2020] N. de Beaudrap and D. Horsman, The zx calculus is a language for surface code lattice surgery, Quantum 4, 218 (2020).
  * Kissinger and van de Wetering [2020] A. Kissinger and J. van de Wetering, Reducing the number of non-clifford gates in quantum circuits, Physical Review A 102, 022406 (2020).
  * Backens [2014] M. Backens, The zx-calculus is complete for stabilizer quantum mechanics, New Journal of Physics 16, 093021 (2014).
  * Aaronson and Gottesman [2004] S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Physical Review A 70, 052328 (2004).
  * Steane [1996] A. Steane, Multiple-particle interference and quantum error correction, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551 (1996).
  * Duncan  _et al._ [2020] R. Duncan, A. Kissinger, S. Perdrix, and J. Van De Wetering, Graph-theoretic simplification of quantum circuits with the zx-calculus, Quantum 4, 279 (2020).
  * van de Wetering [2020] J. van de Wetering, Zx-calculus for the working quantum computer scientist, arXiv preprint arXiv:2012.13966 10.48550/arXiv.2012.13966 (2020).
  * Duncan and Lucas [2013] R. Duncan and M. Lucas, Verifying the steane code with quantomatic, arXiv preprint arXiv:1306.4532 10.48550/arXiv.1306.4532 (2013).
  * Knill  _et al._ [2001] E. Knill, R. Laflamme, R. Martinez, and C. Negrevergne, Benchmarking quantum computers: The five-qubit error correcting code, Physical Review Letters 86, 5811 (2001).

##  Appendix A Additional Proofs

We begin with the proof of Lemma II.5. Generally, an operator can be
transformed into a state by writing the operator as a linear combination of
projectors $\ket{\phi}\bra{\psi}$, and then flipping the bra’s into ket’s.
This process is known as the Choi-Jamiołkowski isomorphism. We describe how to
perform an analogous transformation in the ZX calculus, along with the
canonicalization into HK form.

###### Proof.

We will turn the encoder diagram into a Clifford circuit, and then map the
output of that circuit (with input the all-$\ket{+}$ state) to HK form. Any
$X$ (red) nodes in the ZX encoder diagram can be transformed into $Z$ (green)
nodes with the same phase surrounded by Hadamard gates. Now, we can interpret
the ZX encoder diagram as a state by treating the input edges as output edges
(the ZX version of the Choi-Jamiołkowski isomorphism).

Our ZX diagram now computes a state, so we can express it entirely in terms of
the following elementary operations and their circuit analogs. First, we could
have a $Z$ node with only one output or only one output. In a circuit, this is
a $\ket+$ qubit or a post-selected $\bra+$ measurement, respectively. We can
also have a Hadamarded edge or a node with $\frac{\pi}{2}$ phase, which are
represented as $H$ or $S$ gates in circuits, respectively. Lastly, we can have
a $Z$ node of degree 3, with either 2 inputs and 1 output or 1 input and 2
outputs that acts as a merge or a split. This is equivalent to applying a $CX$
operation between two qubits where the second qubit is either initialized to
$\ket 0$ before the $CX$ gate or post-selected by the measurement $\bra 0$
after the $CX$ gate, respectively.

Any ZX diagram can be expressed in terms of these operations [40].
Furthermore, as we apply each of these operations we can keep track of the
current HK form for our state. (The Hu and Khesin [28] method shows us how to
keep a diagram in HK form as each operation is applied.) All of these steps
can be done efficiently [28], so this gives us an efficient procedure for
turning a ZX diagram into a corresponding stabilizer state in HK form. ∎

We next give the proof of Theorem II.6.

###### Proof.

The key step is to show that the operations corresponding to row operations on
the partial adjacency matrix $M_{\mathcal{D}}$ can be done without changing
the corresponding stabilizer tableau representation. To do so, let us examine
the action of a stabilizer on the encoder diagram.

The stabilizer is a Pauli matrix. Suppose we apply any row—a Pauli string that
stabilizes the output of the encoder. (The row can be a string of $X$’s and
$Z$’s with a global phase.) That is, this string is sent through the output
edges of the diagram. As the operators pass through the local Clifford
operations on the output vertices, they turn into different operators. For
example, consider a $X$ operator (represented by a $X$ node with a $\pi$
phase) that passes through a free output edge of an output node $v$. (It may
be useful to draw an example to follow along.) By the $\pi$ rule of ZX
calculus, this results in a global phase, negation of the local phase on $v$,
as well as a $X$ node on each internal neighboring edge connected to $v$. As
each $X$ node moves along the internal edge, it will be conjugated past the
internal Hadamard gate, arriving as a $Z$ on the other side of the edge.

In sum, the total action of the entire stabilizer will visually look a
choreographed dance where the nodes act out the following steps.

  1. 1.

Pauli matrices commute past the $H$ gates on the output edges, with some of
them changing colour $(X\leftrightarrow Z)$.

  2. 2.

$Z$ nodes from the stabilizer simply add their phase to the nodes in the
diagram, while the $X$ nodes split into one $X$ node for every internal edge
connected to the output node $v$, and result in a phase flip on every
neighbour of $v$.

Once this dance is complete, all the added phases necessarily cancel and the
added global phase returns to 1, since the string is a stabilizer.

But note that any single $X$ (or $Y$ represented as $iXZ$) sent through an
output node $v$ (after it has already passed through a Hadamard on the output
edge if one exists) may result in some operators (represented as $X$ or $Z$
nodes) that hit an input node via an internal edge connected to the input
node. But at the end of the day, all of the operators on the input edges must
cancel out due to stabilization. This implies that each input node must be
connected to an even number of nodes on which the stabilizers apply $X$ or $Y$
gates after passing through the Hadamard gates on the free output edges.

Consequently, for any pair of input nodes, we are free to connect all of the
neighbors of one to the other via (Hadamarded) internal edges without changing
the parity effect of the stabilizers described above. This corresponds to
adding two rows in $M_{\mathcal{D}}$.

Finally, we note that since any pair of internal edges have Hadamard gates on
them, if we have two edges between the same pair of $Z$ nodes, we can remove
them both by the rules of ZX calculus. In other words, we are effectively free
to perform arbitrary row operations on $M_{\mathcal{D}}$ mod 2. It is easy to
see that these operations do not violate the Edge and Hadamard rules.

This allows us to row-reduce $M_{\mathcal{D}}$ to satisfy the RREF rule. ∎

We conclude this section with the derivation of the recursive counting formula
of ZXCF diagrams, given in Eq. (2). To derive $f$, imagine that, starting with
two empty bins, we must assign the $n-k$ output nodes to be pivots (case $A$)
or non-pivots (case $B$), where pivots need to be matched with input nodes.
The current number of pivots is tracked by $p$ and the number of non-pivot
outputs is tracked by $o$.

Suppose we want the next output node to be a pivot (in $\mathcal{P}$). Since
there is a one-to-one correspondence between pivots and inputs, we can add
pivots only if $n>k$. The matching between pivots and input nodes is fully
constrained by the RREF rule, which sorts the inputs and pivots together. The
Clifford rule says that no pivot nodes may have local Clifford operations, so
we just need to choose the edges connecting them to nodes we have already
assigned. Since there are no pivot-pivot edges and the pivot connects to only
one input, we have exactly $2^{o}$ possibilities. Having made an assignment,
$p$ increases by 1, and $n$ decreases by 1 (both input and output are
decremented since the pivot matches with an input).

Suppose instead we want the next output node to be a non-pivot (in
$\mathcal{O}$). Then we have to choose the local Clifford operation as well as
its edges to previously assigned vertices. If we choose to connect the node to
none of the $p$ assigned inputs, $p$ assigned pivots, or $o$ assigned
vertices, then we are allowed to place any of the 6 local Cliffords on the
node. If any of those edges are present, however, we cannot apply a Hadamard
to the output edge due to the Hadamard rule. Hence, 4 choices remain for the
local Clifford operation. This works out to a total of
$4(2^{2p+o}-1)+6=2^{2p+o+2}+2$ possibilities. To finish, we decrement the
number of output qubits without changing the number of inputs.