# Pricing of Short Circuit Current in High IBR-Penetrated System

Zhongda Chu, Jingyi Wu, Fei Teng
Department of Electrical and Electronic Engineering
Imperial College London, London, UK
{z.chu18, jingyi.wu19<EMAIL_ADDRESS>
###### Abstract

With the growing penetration of Inverter-Based Resources (IBRs) in power
systems, stability service markets have emerged to incentivize technologies
that ensure power system stability and reliability. Among the various
challenges faced in power system operation and stability, a prominent issue
raised from the increasing integration of large-scale IBRs is the significant
reduction of the Short-Circuit Current (SCC) level in the system, which poses
a considerable threat to system voltage stability and protection. Thus, a
proper market mechanism to incentivize the provision of SCC as a stability
service is desired. However, the pricing of this service within the future
stability market has not yet been fully developed, due to the nonconvex nature
of SCC constraints and the locational property of SCC. To address these
problems, this work aims to explore, for the first time, a pricing model for
SCC service by incorporating a linearized SCC constraint into the Unit
Commitment (UC) problem, to achieve the desired SCC level and extract the
shadow price for SCC through different pricing methods.

###### Index Terms:

short-circuit current, ancillary service pricing, unit commitment.

##  I Introduction

Growing awareness and acknowledgment of environmental issues like global
warming and escalating pollution have motivated policymakers worldwide to
commit to ambitious decarbonization targets [1]. In recent years, there has
been a profound transformation in the composition of the power generation mix.
Particularly in Europe, electric systems are undergoing a shift towards a
Renewable Energy Sources (RESs) dominated architecture[2] [3].

Interfaced with the grid through power electronic devices, IBRs provide much
less SCC compared with traditional Synchronous Generators (SGs) due to their
limited overloading capability [4]. Therefore, with the increasing penetration
of IBRs and the retirements of SGs, a decreasing trend of SCC levels in power
systems is anticipated. CIRED Workshop predicts a reduction in SCC level for
rural nodes in Germany [5]. Also, according to System Operability Framework
Document by National Grid ESO, an overall decline of around 15% in the
national SCC level from 2019 to 2023 is expected [6].

The reduction of SCC levels in power systems leads to threads in various
aspects. Protection devices may take longer or even not be able to detect
faults in the system, posing risks to system operation and stability [7].
Additionally, inadequacy in SCC may cause unsettled voltage oscillations in
the network and would further cause loss of synchronization of the Phase-
Locked Loop (PLL) [8] and transient voltage stability issues. Therefore,
enhancing the SCC and addressing the related issues have been an important
procedure in high IBR-penetrated systems. Various attempts have been proposed
on this, including physically improving the overloading capabilities of
semiconductors by inserting phase-change material into chips [9], and
allocating additional synchronous condensers in the system to maintain the
system minimum SCC [10]. However, these approaches bring additional cost to
either IBR manufacturers or system operators, and therefore how to incentivize
the provision of SCC in the system becomes an essential element for the future
SCC market development.

European Union Emissions Trading Scheme (EUETS) classifies the typical
ancillary services procured by Transmission System Operators (TSOs) into
frequency control services (regulation, load following, operating reserves)
and non-frequency control services (voltage control, ramp limit, SCC, etc.)
[11], which are considered as the main ancillary services in existing
electricity markets [12]. Although some of these markets have been well
established based on duality theory, difficulties still exist. In order to
determine the price of SCC in the system, it is necessary to integrate the SCC
constraint into the system scheduling model. However, due to the complicated
SCC calculation, proper linearization methods such as [13, 14] to relax the
nonlinearity and nonconvexity in the SCC constraint have to be incorporated.

Another key challenge lies in determining the marginal costs of uplift
payment, which is associated with the inherent nonconvexity in power systems:
the binary nature of the commitment decision for thermal units. This makes it
impractical to apply duality theory directly, even when pricing energy in
energy markets [15]. Some approaches have been proposed to address this issue.
The dispatchable method relaxes the commitment decisions of thermal units from
binary variables to continuous ones. This approach converts the original MILP
formulation of the UC problem into an LP problem where the dual variables can
be defined properly [16]. Nevertheless, it has a limitation in capturing the
complete technical characteristics of generators, therefore prices computed
through this method might not correspond to feasible operating points for
power systems [17]. The restricted pricing method, on the other hand, computes
the SCC price by solving the UC problem twice. In the first time, the original
MILP is solved as usual to obtain the optimal commitment decisions;
Subsequently, a second optimization is performed by relaxing the binary
variables while employing equality constraints to enforce the commitment
variables to retain their optimal values. Thereby the operating conditions of
the power system can be accurately represented when determining the dual
variables. However, this approach adds a new term to the Lagrangian function,
where a “price for commitment” is thus created, leading to a side payment for
units associated with a commitment decision variable [18]. The concept of
marginal unit price is introduced in [19] to determine the prices in integer
programs, where the right-hand side resource availability can only be varied
in a discrete manner. However, none of the above methods have been studied in
the SCC market setting.

Moreover, even with proper relaxation of the nonconvex SCC constraints,
applying the duality theory only gives the SCC price at each sink (nodes
requiring SCC) and it is not clear how this price should be allocated to
different SCC sources (units contributing SCC). There is no research that has
looked into this problem. In this context, to incentivize system components
such as conventional SGs and IBRs to provide sufficient SCC at critical
locations, the pricing schemes of SCC are investigated and analyzed. Our main
contributions include the following:

  * •

A novel SCC pricing scheme is developed by incorporating linearized SCC
constraints into the system UC problem such that the contribution to the SCC
from different devices in the system can be properly quantified.

  * •

The nonconvexity due to the existence of binary variables is dealt with by
applying three different methods, namely the dispatchable method, the
restricted method, and the marginal unit price method.

  * •

The prices obtained by different schemes are compared, and the impact of
system conditions on the SCC price is analyzed in the modified IEEE 39-bus
system with valuable information obtained for future SCC market development.

The rest of this paper is structured as follows. Section II introduces the SCC
constraint and its linearization approach. The SCC pricing schemes based on
the SCC-constrained UC problem are developed in Section III, followed by case
studies in Section IV. Finally, Section V concludes the paper and discusses
the future work.

##  II SCC Constraint Representation and Linearization

Consider a general multi-machine system with SGs $g\in\mathcal{G}$ and IBRs
$c\in\mathcal{C}$. By modeling the IBR as current sources, the SCC constraint
$I_{sc_{F}}^{{}^{\prime\prime}}\geq I_{F_{\mathrm{lim}}}^{{}^{\prime\prime}}$
in a high IBR-penetrated system can be derived based on the superposition
principle [13]:

$\displaystyle I_{sc_{F}}^{{}^{\prime\prime}}$
$\displaystyle=\frac{-\sum_{g\in\mathcal{G}}Z_{F\Psi(g)}I_{g}x_{g}-\sum_{c\in\mathcal{C}}Z_{F\Phi(c)}I_{c}\alpha_{c}}{Z_{FF}}\geq
I_{F_{\mathrm{lim}}}^{{}^{\prime\prime}}$ (1a) $\displaystyle Z$
$\displaystyle=Y^{-1}$ (1b)

where $I_{sc_{F}}^{{}^{\prime\prime}}$ and
$I_{F_{\mathrm{lim}}}^{{}^{\prime\prime}}$ are the short circuit current at
bus $F$ and the corresponding limit; $\Psi(g)/\Phi(c)$ maps
$g\in\mathcal{G}/c\in\mathcal{C}$ to the corresponding bus index;
$I_{g}/I_{c}$ is the SCC contribution from SG $g$/IBR $c$; $x_{g}$ is the
binary variable representing the SG online status; $\alpha_{c}$ is the online
capacity in percentage of IBR $c$; $\mathbb{I}_{N}$ is $N$-dimensional
identity matrix; $Z/Y$ is the system impedance/admittance matrix, defined as
follows:

$Y=Y^{0}+Y^{g},$ (2)

where $Y^{0}$ is the admittance matrix of the transmission lines only; $Y^{g}$
denotes the additional $Y$ matrix increment due to SGs’ subtransient
reactance. Depending on the state of SGs, the elements in $Y^{g}$ can be
expressed as:

$Y_{ij}^{g}=\begin{cases}\frac{1}{X_{dg}^{{}^{\prime\prime}}}x_{g}\;\;&\mathrm{if}\,i=j\land\exists\,g\in\mathcal{G},\,\mathrm{s.t.}\,i=\Psi(g)\\\
0\;\;&\mathrm{otherwise}.\end{cases}$ (3)

It is understandable that due to the dependence of $Y$ on $x_{g}$, the matrix
inverse with binary decision variables in (1b) is in general difficult to be
included in an optimization problem, which is essential for SCC pricing. The
data-driven method proposed in [13] is adapted to linearize the SCC
constraint, which is briefly discussed as follows. Introduce a set of new
parameters $\mathcal{K}=\left\\{k_{Fg},\;k_{Fm},\;k_{Fc}\right\\},\,\forall
F,g,m,c$ as the coefficients in the linearized SCC constraint, which
reformulates (1) into:

$\displaystyle
I_{{F}_{L}}^{{}^{\prime\prime}}=\sum_{g\in\mathcal{G}}k_{Fg}x_{g}+\sum_{c\in
C}k_{Fc}\alpha_{c}+\sum_{m\in M}k_{Fm}\eta_{m}\geq
I_{{F}_{\mathrm{lim}}}^{{}^{\prime\prime}},$ (4)

where $I_{{F}_{L}}^{{}^{\prime\prime}}$ is the linearized SCC. The
interactions between every pair of SGs are captured by the second-order term
$\eta_{m}$ to accommodate the nonlinearity in (1), which is defined as:

$\displaystyle\eta_{m}$
$\displaystyle=x_{g_{1}}x_{g_{2}},\quad\mathrm{s.t.}\\{g_{1},\,g_{2}\\}=m$
(5a) $\displaystyle m\in\mathcal{M}$ $\displaystyle=\\{g_{1},\,g_{2}\mid
g_{1},\,g_{2}\in\mathcal{G}\\}.$ (5b)

The product of two binary variables can be further linearized by:

$\displaystyle\eta_{m}$ $\displaystyle\leq x_{g_{1}}$ (6a)
$\displaystyle\eta_{m}$ $\displaystyle\leq x_{g_{2}}$ (6b)
$\displaystyle\eta_{m}$ $\displaystyle\geq x_{g_{1}}+x_{g_{2}}-1.$ (6c)

The parameters in $\mathcal{K}$ are determined by solving the following
optimization problem:

$\displaystyle\min_{\mathcal{K}}\quad$
$\displaystyle\sum_{\omega\in\Omega_{2}}\left(I_{sc_{F}}^{{}^{\prime\prime}(\omega)}-I_{F_{L}}^{{}^{\prime\prime}(\omega)}\right)^{2}$
(7a) $\displaystyle\mathrm{s.t.}\quad$ $\displaystyle
I_{F_{L}}^{{}^{\prime\prime}(\omega)}<I_{F_{\mathrm{lim}}}^{{}^{\prime\prime}},\,\,\forall\omega\in\Omega_{1}$
(7b) $\displaystyle I_{F_{L}}^{{}^{\prime\prime}(\omega)}\geq
I_{F_{\mathrm{lim}}}^{{}^{\prime\prime}},\,\,\forall\omega\in\Omega_{3}$ (7c)

with $(\cdot)^{(\omega)}$ denoting quantities associated with sample $\omega$,
and
$\omega=\\{x_{g}^{(\omega)},\,\alpha_{c}^{(\omega)},\,I_{sc_{F}}^{{}^{\prime\prime}(\omega)}\\}\in\Omega$
denoting the data set. It is generated by evaluating the SCC at each bus in
representative system conditions. $\Omega_{1},\,\Omega_{2}$ and $\Omega_{3}$
are the subsets of $\Omega$, being defined as follows:

$\displaystyle\Omega$ $\displaystyle=\Omega_{1}\cup\Omega_{2}\cup\Omega_{3}$
(8a) $\displaystyle\Omega_{1}$ $\displaystyle=\left\\{\omega\in\Omega\mid
I_{sc_{F}}^{{}^{\prime\prime}(\omega)}<I_{F_{\mathrm{lim}}}^{{}^{\prime\prime}}\right\\}$
(8b) $\displaystyle\Omega_{2}$ $\displaystyle=\left\\{\omega\in\Omega\mid
I_{F_{\mathrm{lim}}}^{{}^{\prime\prime}}\leq
I_{sc_{F}}^{{}^{\prime\prime}(\omega)}<I_{F_{\mathrm{lim}}}^{{}^{\prime\prime}}+\nu\right\\}$
(8c) $\displaystyle\Omega_{3}$ $\displaystyle=\left\\{\omega\in\Omega\mid
I_{F_{\mathrm{lim}}}^{{}^{\prime\prime}}+\nu\leq
I_{sc_{F}}^{{}^{\prime\prime}(\omega)}\right\\}.$ (8d)

Given (7b) and (8b), all the below-limit SCC can be classified correctly by
the linearized function. Ideally, it is also desired to identify all the
above-limit SCC. However, this may cause infeasibility due to the restricted
linear structure in (4). Therefore, a parameter $\nu\in\mathbb{R}^{+}$ is
introduced to define $\Omega_{2}$ and $\Omega_{3}$ as in (8c) and (8d). In
this way, all the data points in $\Omega_{3}$ will be classified correctly and
misclassification can only occur in $\Omega_{2}$. Furthermore, $\nu$ should be
chosen as small as possible while ensuring feasibility.

##  III Pricing SCC Services

In order to better explain the concept of SCC price, we first define two sets
of nodes, i) SCC sources ($\mathcal{S}_{1}$): all the nodes that provide SCC
to other nodes during faults, i.e., SG and IBR nodes and ii) SCC sinks
($\mathcal{S}_{2}$): all the nodes with SCC shortage. It is therefore desired
to obtain the SCC price from each source to each sink, leading to an overall
price matrix
$p_{SCC}\in\mathbb{R}^{|\mathcal{S}_{1}|}\times\mathbb{R}^{|\mathcal{S}_{2}|}$.
To derive the SCC prices, the SCC-constrained UC model is formulated as
follows.

###  III-A SCC-constrained UC

The objective of the UC problem is to minimize the expected cost over all
nodes in the given scenario tree:

$\min\sum_{n\in\mathcal{N}}\pi(n)\left(\sum_{g\in\mathcal{G}}C_{g}(n)+\Delta
t(n)c^{s}P^{s}(n)\right),$ (9)

where $\pi(n)$ is the probability of scenario $n\in\mathcal{N}$ and $C_{g}(n)$
is the operation cost of unit $g\in\mathcal{G}$ in scenario n including
startup, no-load and marginal cost; $\Delta t(n)c^{s}P^{s}(n)$ represents the
cost of the load shedding in scenario n with the three terms being the time
step of scenario n, load shedding cost and shed load. The objective function
(9) is subjected to a number of constraints, including the linearized SCC
constraint (4). All other conventional UC constraints such as those related to
power balance, thermal units and transmission lines are not listed in the
paper. The readers can refer to [20] for details.

However, even with the linearized SCC constraints, the binary nature of the
commitment decision for thermal units makes it impractical to apply the
duality theory for SCC pricing. Hence, three pricing schemes, namely the
dispatchable method, the restricted method, and the marginal unit price
method, are investigated to cope with the non-continuity in the short-circuit
current constraint. With relaxed and convex SCC constraints, the duality
theory can be applied to extract the SCC prices in the system. The pros and
cons of each method and their applying conditions are discussed in the
following sections.

###  III-B Pricing schemes for SCC service

Note that the main issue to be addressed in order to extract a meaningful SCC
dual variable is the discrete online/offline characteristic of SGs and the
fact that they do not provide SCC in a continuous manner. Regarding this
problem, three alternative pricing methods have been proposed in this section.

####  III-B1 Dispatchable Pricing

This approach involves direct linear relaxation of the binary decision
variables $x_{g}$, i.e replacing the original constraint $x_{g}\in\\{0,1\\}$
with

$0\leq x_{g}\leq 1,\,\forall g\in\mathcal{G}.$ (10)

However, this causes the quadratic term $\eta_{m}=x_{g_{1}}\cdot x_{g_{2}}$ in
(4) now to become a product of two continuous decision variables and can no
longer be linearized with the big-M method. Some attempts have been proposed
to deal with this type of bilinear product terms. Reference [21] proposes a
piecewise linear method which divides the quadratic term into multiple
segments that are approximated by straight lines. However, additional binary
decision variables must be introduced to ensure proper segmentation and
weighing of each fragment for the closest approximation, which reproduces
nonconvexity in the problem. Therefore, in order to apply the dispatchable
pricing method the term $\eta_{m}$ in constraint (4) is removed, resulting in
the SCC constraint with the form below:

$\displaystyle
I_{{F}_{L}}^{{}^{\prime\prime}}=\sum_{g\in\mathcal{G}}k_{Fg}x_{g}+\sum_{c\in
C}k_{Fc}\alpha_{c}\geq I_{{F}_{\mathrm{lim}}}^{{}^{\prime\prime}}.$ (11)

This simplification incurs the drawback of sacrificing some generality for
this model, where the extracted price might not align with a viable operating
point for the system. Nevertheless, the price of the SCC as a service can be
obtained from the Karush Kuhn Tucker (KKT) conditions of the SCC-constrained
optimization problem. Since the SCC constraints are linear, the price is
immediately obtained from the dual variables of the constraints. The terms
associated with SCC constraints and their corresponding Lagrange multipliers
take the form:

$\displaystyle-\lambda_{SCC}\left(\sum_{g\in\mathcal{G}}k_{Fg}x_{g}+\sum_{c\in
C}k_{Fc}\alpha_{c}-I_{{F}_{\mathrm{lim}}}^{{}^{\prime\prime}}\right).$ (12)

The shadow price for SCC at sink $F\in\mathcal{S}_{2}$ with contribution from
all the sources can then be obtained by evaluating the KKT stationary
condition, which is given by differentiating the Lagrangian with respect to
$I_{{F}_{\mathrm{lim}}}^{{}^{\prime\prime}}$:

$p_{SCC}^{\varsigma
F}=\frac{\mathrm{d}\,\mathcal{L}}{\mathrm{d}\,I_{{F}_{\mathrm{lim}}}^{{}^{\prime\prime}}}=\lambda_{SCC}.$
(13)

The price from a single SCC source $E\in\mathcal{S}_{1}$ to the sink
$F\in\mathcal{S}_{2}$ can then be calculated by considering its weighted
contribution as indicated in (1):

$p_{SCC}^{E\rightarrow
F}=\frac{Z_{FE}I_{E}}{\sum_{E\in\mathcal{S}_{1}}Z_{FE}I_{E}}p_{SCC}^{\varsigma
F},$ (14)

where $I_{E}$ is the equivalent current injection, i.e., $I_{g}x_{g}$ in (1).
However, as discussed in the introduction, relaxation of the binary variables
in (10), may lead to infeasible operating conditions for the system. To
address this issue, the following two methods are considered.

####  III-B2 Restricted Pricing

In the restricted model, the original MILP-based UC problem is solved first,
with the optimal decisions regarding the binary decision variables $x_{g}$
being recorded. Then, the optimization problem is solved again with the binary
variables $x_{g}$ being set to their optimal values $x_{g}^{*}$ based on the
solution of the previous problem. Therefore, in the second problem,
constraints that confine binary variables are replaced with:

$\displaystyle x_{g}$ $\displaystyle=x_{g}^{\ast}$ (15a)
$\displaystyle\eta_{m}$ $\displaystyle=\eta_{m}^{\ast}.$ (15b)

Subsequently, the terms associated with SCC constraints and their
corresponding Lagrange multipliers can be expressed:

$\displaystyle-$
$\displaystyle\lambda_{SCC}\left(\sum_{g\in\mathcal{G}}k_{Fg}x_{g}+\sum_{c\in
C}k_{Fc}\alpha_{c}+\sum_{m\in
M}k_{Fm}\eta_{m}-I_{{F}_{\mathrm{lim}}}^{{}^{\prime\prime}}\right)$
$\displaystyle+$
$\displaystyle\lambda_{commit}\left(x_{g}^{\ast}-x_{g}\right).$ (16)

It should be noted that with this method, the product terms $\eta_{m}$ no
longer need to be neglected as in (11). Instead, (4) can be used in the UC
problem, leading to the expression in (III-B2).

As a result, two prices can be derived accordingly. For the SCC price, the
same result as the dispatchable method holds, i.e.,

$\frac{\mathrm{d}\,\mathcal{L}}{\mathrm{d}\,I_{{F}_{\mathrm{lim}}}^{{}^{\prime\prime}}}=\lambda_{SCC}.$
(17)

However, due to the discontinuity nature of the SG online status, forcing
$x_{g}$ to be their optimal value by introducing (10) is very likely to make
the SCC constraint non-binding, which causes $\lambda_{SCC}$ (the SCC price)
to be zero. To address this issue, another price is defined here that reflects
the value an SG being committed online, which can be derived by taking the
derivative of the Lagrange function with respect to $x_{g}^{*}$:

$\frac{\mathrm{d}\,\mathcal{L}}{\mathrm{d}\,x_{g}^{*}}=\lambda_{commit}.$ (18)

This price has a different interpretation from the SCC price. The latter
represents the increment of the system operation cost (the price the system
operator is willing to pay) if the SCC requirement is increased by
$1\,\mathrm{p.u.}$, whereas in this case the price is defined for each
generator $g\in\mathcal{G}$ and reflects the variation in system operation
cost due to the change in the SGs’ commitment status.

However, as mentioned earlier this approach has several pitfalls. An
implication is the introduction of a side payment for the committed units,
which can potentially result in insufficient revenue for the system operator.
Furthermore, the extracted shadow price $\lambda_{commit}$ can exhibit high
volatility between large positive numbers and zero, leading to frequent
instances of seemingly unfair outcomes. Additionally, the unit commitment
price defined by (18) contains not only the cost to maintain the SCC
constraints, since the unit commitment decisions of SGs are also coupled with
other constraints that influence the system operation cost, such as power
balance constraints. Therefore, the price obtained in this way could
potentially be much higher than the actual price of the SCC service. To
decouple the impact of the SG commitment decision on the SCC from other
constraints in the system, an alternative marginal unit pricing scheme is
discussed in the next subsection.

####  III-B3 Marginal Unit Pricing

This approach shares a similar physical interpretation to the restricted
pricing model but does not require the application of the duality theory.
Therefore, it can deal with the situation where the marginal price defined by
the gradient of the Lagrange function does not exist due to the nonconvex
nature of the resources. The marginal unit price quantifies the economic value
of the SCC contribution provided by different generation units. It is obtained
by solving the system scheduling model, where a commitment price is defined
for each SG according to its contribution to system SCC.

First, solve the original optimization problem defined in Section III-A, which
is denoted by the following compact form:

$\displaystyle\min_{\mathsf{X}}\;\;$ $\displaystyle\mathsf{f}(\mathsf{X})$
(19a) $\displaystyle\mathrm{s.t.}\;\;$
$\displaystyle\mathsf{K}^{\mathsf{T}}\mathsf{X}\geq
I_{{F}_{\mathrm{lim}}}^{{}^{\prime\prime}}$ (19b) $\displaystyle
h(\mathsf{X})\geq 0,$ (19c)

where $\mathsf{X}$ is the decision variable; $\mathsf{f}(\mathsf{X})$ is the
objective function; (19b) is the system SCC constraint and $h(\mathsf{X})$ is
the rest of the constraints in the UC problem. Denote the optimal value of
problem (19) as $\mathsf{f}^{*}$. To determine the economic value of an SCC
source $E\in\mathcal{S}_{1}$, the following problem is solved.

$\displaystyle\min_{\mathsf{X}}\;\;$ $\displaystyle\mathsf{f}(\mathsf{X})$
(20a) $\displaystyle\mathrm{s.t.}\;\;$
$\displaystyle(\mathsf{K}+\Delta\mathsf{K}^{E})^{\mathsf{T}}\mathsf{X}\geq
I_{{F}_{\mathrm{lim}}}^{{}^{\prime\prime}}$ (20b) $\displaystyle
h(\mathsf{X})\geq 0.$ (20c)

The vector $\Delta\mathsf{K}^{E}$ and is of the same dimension as
$\mathsf{K}$, which is defined as:

$\displaystyle\Delta\mathsf{K}^{E}_{i}=$
$\displaystyle\begin{cases}0\qquad\quad\;,\mathrm{if}\,i\neq E\\\
-\mathsf{K}_{i}\qquad,\mathrm{if}\,i=E\\\ \end{cases}$ (21)

where $(\cdot)_{i}$ denotes the $i$-th element of the vector. With the above
definition, the coefficient in $\mathsf{K}+\Delta\mathsf{K}^{E}$ corresponding
to the $E$-th element in $\mathsf{X}$, becomes zero, thus eliminating the SCC
provision from the SCC source $E$, whereas its impacts on the operation cost
(20a) and other constraints (20c) remain the same. Denoting the optimal value
of problem $\eqref{UC_delta}$ as $\mathsf{f}^{*}_{E}$ enables us to define the
unit price of the source $E\in\mathcal{S}_{1}$ with contribution to the sink
$F\in\mathcal{S}_{2}$:

$p_{unit}^{E\rightarrow F}=\mathsf{f}^{*}_{E}-\mathsf{f}^{*}.$ (22)

##  IV Results

In order to investigate the value of SCC provision from different resources,
and how it is influenced by system operation, we consider an optimization
problem with a time horizon of 24 hours and a time step of 1 hour, which is
implemented in Matlab with the YALMIP toolbox [22] and solved by Gurobi
(10.0.0) on a PC with Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz and RAM of 16
GB. The weather conditions are obtained from online numerical weather
prediction [23].

The simulation is carried out based on the modified IEEE 39-bus system to
illustrate the validity of the proposed SCC linearization models and verify
the feasibility of the pricing schemes. The topology of this system is as
shown in Fig. 1, which consists of 10 synchronous generators (SCC sources), 39
buses, 46 lines and 4 IBRs (SCC sinks). Some system parameters are set as
follows: load demand $P^{D}\in[5.16,6.24]\,\mathrm{GW}$, base power
$S_{B}=100\mathrm{MVA}$. Other parameters can be found in [24, 20].

Figure 1: Modified IEEE-39 bus system.

###  IV-A SCC Constraint Validation

To obtain an accurate approximation of the SCC constraint, the number of wind
conditions considered when training the fitting model (7), should be large
enough so that the mapping defined in (4) can effectively cover a wide range
of real-world weather conditions. In this particular case study, $\mathcal{K}$
is defined with respect to all combinations of the SG’s commitment statuses
with ten different wind capacity values, ranging from $0$ to
$0.9\,\mathrm{p.u.}$ with a step of $0.1\,\mathrm{p.u.}$, which gives a total
of $(2^{10}-1)\times 10=10230$ different scenarios. We exclude the scenario
where all SGs are offline, as it is not realistic considering the system
demand throughout the day. Having obtained $\mathcal{K}$, the observed
$I_{{sc}_{F}}^{{}^{\prime\prime}}$ and linearized
$I_{F_{L}}^{{}^{\prime\prime}}$ can be aligned for comparison, as illustrated
in Fig. 2. Note that only the SCC at IBR 1 bus is shown as a similar trend can
be observed for the others.

Figure 2: Observed and linearized SCC for IBG buses (margin $\nu$ = 1)

In order to examine the performance of the linearization method, two types of
errors are analyzed with Type I being the SCC which satisfies the constraint
according to the linearized value but actually violates and Type II being the
opposite:

$\displaystyle\text{Type I}:I_{F_{L}}^{{}^{\prime\prime}}\geq
I_{F_{\mathrm{lim}}}$
$\displaystyle\cap\,I_{{sc}_{F}}^{{}^{\prime\prime}}<I_{F_{\mathrm{lim}}}$
(23a) $\displaystyle\text{Type
II}:I_{F_{L}}^{{}^{\prime\prime}}<I_{F_{\mathrm{lim}}}$
$\displaystyle\cap\,I_{{sc}_{F}}^{{}^{\prime\prime}}\geq
I_{F_{\mathrm{lim}}}.$ (23b)

In terms of the actual consequences for power systems, the occurrence of Type
I errors is much more severe than Type II errors, as they may lead to insecure
operating conditions, thus being undesired. Each type of error is quantified
by their total number of occurrences $N_{e}$ and the averaged relative value
$err$, defined as:

$N_{e}=|\mathcal{E}|$ (24)
$err=\frac{1}{N_{e}}\sum_{\mathcal{E}}\frac{I_{F_{L}}^{{}^{\prime\prime}(\mathcal{E})}-I_{{sc}_{F}}^{{}^{\prime\prime}(\mathcal{E})}}{I_{{sc}_{F}}^{{}^{\prime\prime}(\mathcal{E})}},$
(25)

in which $\mathcal{E}$ denotes the set of errors. Results evaluated at
different IBR buses are presented in Table I. As expected, the SCC
approximation completely eliminates Type I error and produces only a small
amount of Type II errors, hence presenting a good performance.

TABLE I: SCC Linearization Errors at IBR Buses

Location | Type I Error | Type II Error
---|---|---
$N_{e}$ | $err$ | $N_{e}$ | $err$
IBR 1 | $0$ | $0$ | $609$ | $-0.55\%$
IBR 2 | $0$ | $0$ | $624$ | $-0.63\%$
IBR 3 | $0$ | $0$ | $687$ | $-0.89\%$
IBR 4 | $0$ | $0$ | $666$ | $-0.79\%$

To demonstrate the effectiveness of the implemented SCC constraints, the
actual SCC before and after adding the constraint at the IBR bus, represented
by “Uncontr.” and “Constr.” respectively is depicted in Fig. 3. Note that due
to the similarity, only the situation in IBR 1 is shown. It can be clearly
identified that once the constraint is enforced, all SCC values that are
initially below the limit in the unconstrained situation are now raised to
meet the constraint. Also, it is worth noticing that the overlapping parts of
the Constr. and Unconstr. lines indicate that the unconstrained current at
this period of time is originally well above the limit, thus remaining
unchanged. Furthermore, it is evident that the linearized values do not align
with the actual SCC values for most of the hours in the constrained case.
However, as long as the actual SCC and the linearized one are on the same side
of the limit, the error is of no concern, as explained in Section II.

Figure 3: SCC at the bus of IBR 1: constrained vs unconstrained.

###  IV-B SCC Pricing

The SCC prices obtained with different methods are demonstrated in this
section. For simplicity, only one sink is active in each UC problem.

####  IV-B1 Dispatchable Method

Figure 4: SCC prices at IBR buses during one-day operation.

The SCC prices at each hour for each sink $(p_{SCC}^{\varsigma F})$, obtained
based on the dispatchable method are illustrated in Fig. 4. On average, the
SCC prices for the IBR 1, IBR 2, IBR 3, and IBR 4 buses are approximately
60.46 £/h, 27.18 £/h, 45.49 £/h, and 105.17 £/h, respectively. Furthermore,
these prices vary at different IBR buses and hours during the day. The
variations are mainly attributed to the differences between the unconstrained
SCC and the limits at different IBR buses: buses with a greater need for SCC
enhancement tend to have higher marginal costs. The spikes in prices are
related to the start-up cost of the thermal units, as more SGs are needed for
the SCC provision. In addition, the periods when the SCC price equals zero
indicate that the SCC constraints during these hours are non-binding. This
means that no ancillary service is required because the committed units,
determined by other predominant constraints, have already provided sufficient
SCC. The payment from each SCC sinks to different sources can also be
determined by evaluating $p_{SCC}^{E\rightarrow F}(Z_{FE}/Z_{FF})I_{E}$,
giving the results in Table II. In general, an SG with higher capacity and
shorter electrical distance to the SCC sink contributes more SCC, thus being
paid with more money, such as ${10\rightarrow 1}$ and ${3\rightarrow 2}$
(arrows indicating SCC direction).

TABLE II: SCC Payment from Different Sinks

Sink | Source (SGs) [$\mathrm{\times 10^{2}\pounds/h}$]
---|---
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
IBR 1 | $3.3$ | $1.4$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $9.1$
IBR 2 | $1.5$ | $1.6$ | $2.7$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
IBR 3 | $0.6$ | $0.4$ | $0$ | $0.3$ | $7.8$ | $0$ | $0$ | $0$ | $0$ | $0$
IBR 4 | $6.0$ | $2.6$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1.9$ | $0$ | $0$

####  IV-B2 Restricted Method

As discussed earlier, the SCC price obtained with this method is zero for all
hours. This is because forcing the SG commitment decisions to be their optimal
value makes the SCC constraint non-binding, as the SGs provide the SCC in a
discrete manner. Therefore, the prices for the unit commitment decisions are
investigated. It is observed that the restricted method is not suitable for
SCC pricing due to the extremely high prices up to $38\,\mathrm{k\pounds/h}$
(results not shown due to the space limitation).

Possible reasons for this could be that the objective function is highly
sensitive to changes in commitment status, which directly influence the no-
load cost and start-up cost of SGs. Also, the generator states indirectly
impact the operational cost through the power balance constraints, which may
lead to a significant price due to the high penalty of load shedding.
Therefore, the dual variables extracted with respect to the commitment
decisions reflect not only the effect of SCC constraint variation, but also
all other constraints correlated to $x_{g}$. The binary nature of these
variables makes the price highly volatile. It is not possible to isolate
$y_{g}$ in SCC constraint from all other relevant terms, hence this approach
is not applicable to SCC pricing.

####  IV-B3 Marginal Unit Price Method

Figure 5: SG commitment prices for different IBRs.

Similar to the restricted method, the averaged prices of SGs during 24-hour
operation at different IBR buses are depicted in Fig. 5. It can be observed
that the first three SGs have a significant commitment price for the SCC
provision, whereas the commitment prices for other SGs are close to zero. This
is due to the fact that the first three SGs have a larger capacity and lower
marginal cost, and hence are dispatched online most of the time, providing
most of the SCC in the system. Therefore, the values of SCC supplied from
these units are much higher than the rest, since their not providing SCC
renders more operation cost, induced by forcing other units with higher cost
online. As for the differences between the commitment prices of the same unit
for different IBRs, this is due to the fact that the contribution of SGs to
the SCC at different IBR buses varies depending on the electric distance
between them. As a result, the SG tends to have a higher price for the SCC
enhancement at a closer bus.

Figure 6: SG commitment prices during one-day operation.

Furthermore, the SG commitment prices at each hour during one-day operation is
depicted in Fig. 6, where only the contribution to the bus of IBR 1 is shown
due to the space limitation and only the first four SGs are plotted for
clarity. It is clear from the figure that the SGs that have a larger capacity
and are closer to IBR 1 have a higher value in the SCC improvement. Similar to
the dispatchable method, in the hours when the SCC is sufficient, the
commitment price for the SGs is also zero.

##  V Conclusion

An SCC pricing model in high IBR-penetrated systems is developed in this work
by incorporating the SCC constraints into the system scheduling problem. Three
different pricing schemes dealing with the nonconvex nature of the SCC-
constrained UC problem are analyzed and compared. The results obtained based
on the modified IEEE 39-bus system show that the SCC prices with the
dispatchable method and marginal unit prices of the SGs are sensitive to the
locations and system operating conditions. The restricted method is
demonstrated to be not suitable for the SCC pricing due to the coupling with
other constraints. The future work involves investigating the SCC and unit
prices considering the interactions among different sinks and sources.

## References

  * [1] R. FALKNER, “The Paris Agreement and the new logic of international climate politics,” _International Affairs_ , vol. 92, no. 5, pp. 1107–1125, 08 2016\.
  * [2] G. Rancilio, A. Rossi, D. Falabretti, A. Galliani, and M. Merlo, “Ancillary services markets in europe: Evolution and regulatory trade-offs,” _Renewable and Sustainable Energy Reviews_ , vol. 154, p. 111850, 2022.
  * [3] J. Hu, R. Harmsen, W. Crijns-Graus, E. Worrell, and M. van den Broek, “Identifying barriers to large-scale integration of variable renewable electricity into the electricity market: A literature review of market design,” _Renewable and Sustainable Energy Reviews_ , vol. 81, pp. 2181–2195, 2018.
  * [4] X. Zhang, Y. Liu, J. Zhao, J. Liu, M. Korkali, and X. Chen, “Short-circuit current constrained unit commitment and transmission switching model for improving renewable integration: An milp formulation,” _IET Generation, Transmission & Distribution_, vol. 16, no. 9, pp. 1743–1755, 2022.
  * [5] A. Kubis, S. Rüberg, and C. Rehtanz, “Development of available short-circuit power in germany from 2011 up to 2033,” 06 2014.
  * [6] nationalgridESO, “System operability framework: Impact of declining short circuit levels,” Tech. Rep. 135561, December 2018.
  * [7] Australian Energy Market Operator, “System strength requirements methodology,” Tech. Rep., July 2018.
  * [8] nationalgridESO, “Performance of phase-locked loop based converters,” Tech. Rep. 102876, December 2017.
  * [9] W. Shao, D. Kastha, P. Bajpai, L. Zhou, R. Wu, L. Ran, H. Jiang, P. Mawby, D. Rogers, T. Green, T. Coombs, and K. Yadley, “A power module for grid inverter with in-built short-circuit fault current capability,” _IEEE Transactions on Power Electronics_ , vol. PP, pp. 1–1, 03 2020.
  * [10] J. Jia, G. Yang, A. Nielsen, P. Weinreich-Jensen, E. Muljadi, and V. Gevorgian, “Synchronous condenser allocation for improving system short circuit ratio,” in _International Conference on Electric Power and Energy Conversion Systems (EPECS)_ , Kitakyushu, Japan, 04 2018.
  * [11] “Frequency response service,” National Grid ESO, Tech. Rep., 2023.
  * [12] A. Banshwar, N. K. Sharma, Y. R. Sood, and R. Shrivastava, “Renewable energy sources as a new participant in ancillary service markets,” _Energy Strategy Reviews_ , vol. 18, pp. 106–120, 2017.
  * [13] Z. Chu and F. Teng, “Short circuit current constrained uc in high ibg-penetrated power systems,” _IEEE Transactions on Power Systems_ , vol. 36, no. 4, pp. 3776–3785, 2021.
  * [14] S. Li, K. Cao, X. Gu, L. Yan, Z. Li, and W. Tian, “Explicit linear model of bus impedance with unknown branch status,” _IEEE Transactions on Power Systems_ , pp. 1–4, 2023.
  * [15] L. Badesa, F. Teng, and G. Strbac, “Pricing inertia and frequency response with diverse dynamics in a mixed-integer second-order cone programming formulation,” _Applied Energy_ , vol. 260, p. 114334, 2020.
  * [16] M. Paturet, U. Markovic, S. Delikaraoglou, E. Vrettos, P. Aristidou, and G. Hug, “Economic valuation and pricing of inertia in inverter-dominated power systems,” 05 2020.
  * [17] L. Badesa, C. Matamala, Y. Zhou, and G. Strbac, “Assigning shadow prices to synthetic inertia and frequency response reserves from renewable energy sources,” _IEEE Transactions on Sustainable Energy_ , vol. 14, no. 1, pp. 12–26, 2023.
  * [18] B. Zhang, P. B. Luh, E. Litvinov, T. Zheng, and F. Zhao, “On reducing uplift payment in electricity markets,” in _2009 IEEE/PES Power Systems Conference and Exposition_. IEEE, 2009, pp. 1–7.
  * [19] S. Mukherjee and A. K. Chatterjee, “The average shadow price for milps with integral resource availability and its relationship to the marginal unit shadow price,” _European journal of operational research_ , vol. 169, no. 1, pp. 53–64, 2006.
  * [20] Z. Chu and T. Teng, “Stability constrained optimization in high ibr-penetrated power systems-part ii: Constraint validation and applications,” _arXiv preprint arXiv:2307.12156_ , 2023.
  * [21] “Integer programming tricks,” _AIMMS Modeling Guide_ , pp. 81–83, 2023.
  * [22] J. Lofberg, “Yalmip : a toolbox for modeling and optimization in matlab,” in _2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No.04CH37508)_ , 2004, pp. 284–289.
  * [23] “Met Office. Weather Forecasts,” 2023, accessed: 2023-5-18. [Online]. Available: https://www.metoffice.gov.uk/public/weather
  * [24] T. Athay, R. Podmore, and S. Virmani, “A practical method for the direct analysis of transient stability,” _IEEE Transactions on Power Apparatus and Systems_ , vol. PAS-98, no. 2, pp. 573–584, 1979.


MQBC with parity-phase interactions]Universal MBQC with generalised parity-phase interactions and Pauli measurements

Aleks Kissinger
Radboud University Nijmegen

John van de Wetering
Radboud University Nijmegen

We introduce a new family of models for measurement-based quantum computation which are deterministic and approximately universal. The resource states which play the role of graph states are prepared via 2-qubit gates of the form $\exp(-i\frac{\pi}{2^{n}} Z\otimes Z)$. When $n = 2$, these are equivalent, up to local Clifford unitaries, to graph states. However, when $n > 2$, their behaviour diverges in two important ways. First, multiple applications of the entangling gate to a single pair of qubits produces non-trivial entanglement, and hence multiple parallel edges between nodes play an important role in these generalised graph states. Second, such a state can be used to realise deterministic, approximately universal computation using only Pauli $Z$ and $X$ measurements and feed-forward. Even though, for $n > 2$, the relevant resource states are no longer stabiliser states, they admit a straightforward, graphical representation using the ZX-calculus. Using this representation, we are able to provide a simple, graphical proof of universality. We furthermore show that for every $n > 2$ this family is capable of producing all Clifford gates and all diagonal gates in the $n$-th level of the Clifford hierarchy.

Keywords: Measurement-Based Quantum Computation, ZX-calculus, Clifford hierarchy

§ INTRODUCTION

Measurement-based quantum computation (MBQC) describes a family of alternatives to the quantum circuit model, where one starts with a highly entangled resource state and performs all computation via measurements.
While individual measurements introduce non-determinism, a deterministic quantum computation can be recovered by allowing future operations to depend on past measurement outcomes, a concept known as feed-forward.
The most prevalent model of MBQC is the one-way model, first described by Briegel and Raussendorf [21], which makes use of cluster states or more generally graph states and single-qubit measurements.
Graph states are a family of stabiliser states that can be described by an undirected graph, where each edge represents a pair of qubits entangled via a controlled-$Z$ operation. Since they are stabiliser states, any computation involving just Pauli measurements will be efficiently classically simulable, due to the Gottesman-Knill theorem [1]. In fact, any computation involving Pauli measurements can be done in a single time-step [20]. Hence, the entire computational power of the one-way model comes from introducing non-stabiliser measurements to a computation.

It is natural to ask if we can invert this problem: is it possible to obtain universal computation by means of a non-stabiliser resource state and just Pauli measurements?
There are several ways to achieve this. For example, one could consider resource states which are prepared just like cluster states, but with certain qubits prepared in a $\ket{T}$ magic state rather than the usual $\ket{+}$ state.
One can also consider hypergraph states [11], a generalisation of graph states produced by multi-qubit $n$-controlled-$Z$ operations, represented graphically as hyperedges. These were recently shown to admit a universal model of computation using Pauli measurments and feed-forward [24]. A different approach was taken in [16], where a resource state was created that allowed non-deterministic approximately universal computation using just X, Y and Z measurements.

In this paper, we introduce a new family of generalisations of graph states which admit universal deterministic computation using only Pauli X and Z measurements and feed-forward. We call these parity-phase graph states, or P-graph states. Edges in P-graph states represent an application of the following parity-phase gate, for some fixed value of $\alpha$:

\[\hfill P(\alpha) = \exp(-i\frac\alpha2 Z\otimes Z) \hfill\]

We refer to this as a parity-phase gate because it introduces a relative phase of $\alpha$ between its even-parity eigenstates $\ket{00}, \ket{11}$ and its odd parity eigenstates $\ket{01}, \ket{10}$.

We focus on parity-phase gates because they are a popular primitive two-qubit entangling gate in hardware implementations of quantum computation, such as ion trap qubits (via Mølmer Sørensen gates [4, 12]) and, in transmon-based superconducting qubits [25]. We comment briefly toward the end of the paper on near-future prospects of implementing this scheme using the latter.

When $\alpha = \frac\pi2$, we obtain resource states which are equivalent to graph states from the one-way model up to local Clifford operations. However, if $\alpha = \frac\pi4$, we can construct resources which are approximately universal for quantum computation using only single-qubit Pauli $X$ and $Z$ measurements and feed-forward. We call this the PPM model, for parity-phase with Pauli measurements.[Note that, in a previous version of this article, this model was referred to as MSPM, for Mølmer-Sørensen with Pauli measurments.]

A key feature which distinguishes P-graph states from standard graph states is that, unlike for controlled-Z gates, $P(\alpha)P(\alpha) \neq 1$, except in the degenerate case where $\alpha = \pi$. Hence it is possible, and even desirable, to consider resource states described by graphs with multiple, parallel edges between nodes, e.g.

\begin{equation}\label{eq:first-ex}
\tikzfig{ms-graph-state}
\end{equation}

These parallel edges correspond to multiple applications of the entangling gate $P(\alpha)$ to the adjacent qubits. For example, a doubled edge above indicates the application of $P(\alpha)^2 = P(2\alpha)$. In the graph theory literature, graphs such as (<ref>) are sometimes referred to as undirected multigraphs.

In the PPM model, doubled edges play a special role. Since $P(\frac\pi4)^2 = P(\frac\pi2)$ is equivalent, up to local Clifford operations, to a controlled-Z gate, subgraphs of a P-graph state containing only doubled edges behave in much the same way as traditional graph states. However, P-graph states additionally yield the ability to selectively inject $\pi/4$ phases into computations via nodes connected by single edges, giving universality with just Pauli measurements.

Notably, this dichotomy gives a clean separation of the efficiently simulable parts of the computation and the rest. In deriving a universal scheme for computation with P-graph states, we will note the feed-forward is only required in the vicinity of single edges. So, much like the case in the one-way model, the entire `Clifford' part of the computation can be done in a single time step. In section <ref> we will generalise this construction and let a single edge denote an application of $P(\frac{\pi}{2^{n-1}}) \propto \exp(-i \frac{\pi}{2^n} Z \otimes Z)$. We will show that this leads to a deterministic computational scheme, still only using Pauli measurements, which can furthermore implement any diagonal gate of the $n$-th level of the Clifford hierarchy.

Related work. This work relies heavily on the ZX-calculus [7, 2] as a tool for representing and simplifying qubit calculations. In particular, we use a variation of the translation from graph states and measurement patterns into ZX-diagrams given by Duncan and Perdrix [10] to prove the correctness of our computation scheme. To give a proof of completeness, we introduce `hairy brickwork states', which are inspired by the brickwork states introduced in [5] for universal computation in the one-way model. Alternatives to the one-way model have been considered, notably in a broad range of models by Gross et al [13], which even include a variation on graph states using two-qubit interactions that are Clifford-equivalent to $P(\pi/4)$. However, our approach is distinct in that we use very limited measurements and rely on the fact that P-graph states are a more powerful resource than standard graph states. Our scheme also has the property of the one-way model that all errors can be corrected via feed-forward, eliminating the need for `trial-until-success' strategies used by [13] to implement computations on a wide variety of resource states.
In [16] a model based on hypergraph states is constructed that only needs Pauli measurements to become universal, but its structure is more complex than ours and the protocols used are not deterministic.
Deterministic protocols using hypergraph states and Pauli measurements have been proposed since the appearance of this article in preprint, namely those in [24] and [11]. However, our protocol remains interesting for several reasons. First, parity-phase interactions are typically more primitive, in that they have simpler realisations within the gate sets of current hardware proposals. Second, the universal gate set we produce in our model is Clifford+T (or more generally, Clifford + arbitrary diagonal Clifford-hierarchy gates), as opposed to CCZ+Hadamard. While the latter is also universal, it requires extra overhead for encoding computations in a higher-dimensional space [22]. Third, and perhaps most importantly, we introduce a drastically different methodology to existing approaches. This yields a rather flexible family of models that enable us to explore a variety of multi-qubit interactions and graph topologies. Indeed it is a topic of active research to extend these techniques to hypergraph-based models, where the role of the ZX-calculus is played by the recently-introduced ZH-calculus [3].

§ THE PPM MODEL

A P-graph state is described by an undirected graph, where we allow multiple edges between vertices. In practice, we will only need to consider two cases: either a single edge or a double edge:
A single edge describes the application of an $P(\pi/4)$ gate, whereas a double edge describes the application of an $P(\pi/2) = P(\pi/4)^2$ gate.

A measurement pattern is a P-graph state where each node is labelled by a measurement expression of the form “$b \leftarrow \phi(a_1, \ldots, a_n)$” where $b$ is a fresh name called the output value and $\phi$ is a classical function from boolean variables $a_1, \ldots, a_n$ to a single boolean value. In this case, we say for each $a_i$ that $b$ depends on $a_i$. An MS-pattern is well-founded if there are no cyclic dependencies between variables, such as in the following pattern:

These expressions do not have any explicit time-ordering, but there are restrictions on the order in which measurements can be made, due to dependencies on prior outcomes, i.e. feed-forward. As a matter of convention, we will typically draw earlier measurements below later ones, i.e. `time' flows upward.

Computations are performed as follows:

* A qubit is initialised in the $\ket +$ state for each vertex in a P-graph state.

* For every edge in the graph, $P(\frac\pi4)$ is applied to the two qubits at its source and target. In particular, $P(\frac\pi2) = P(\frac\pi4)^2$ is applied to every pair of qubits connected by a double edge.

* For a qubit labelled “$b \leftarrow \phi(a_1, \ldots, a_n)$”, where the values $a_1, \ldots, a_n$ are known, measure in the $X$-basis if $\phi(a_1, \ldots, a_n) = 0$ and the $Z$-basis otherwise. In either case, store the measurement result in $b$.

* Optionally, perform some classical post-processing on the measurement results.

As with the one-way model, the two-qubit gates all commute, so the order of application is irrelevant, leaving only the undirected graph structure.

To show that this model is universal, we will compose smaller patterns into larger ones. In order to do this, we give a notion of pattern fragment analogous to the notion given for the one-way model. A pattern fragment is just like a measurement pattern, with the exception that we additionally identify two (not necessarily disjoint) subsets of vertices $I, O \subseteq V$ which respectively correspond to inputs and outputs. Inputs correspond to qubits that can be in an arbitrary state, rather than the fixed state $\ket{+}$. Ouputs correspond to qubits which remain unmeasured after the application of the pattern-fragment.

Each vertex in $I$ is labelled with an input error expression of the form: “$(z, x) \leftarrow \square$” for fresh variables $z$ and $x$ which captures whether a Z or X error is being fed forward into this vertex. Unless the input vertex is also an output, the vertex will also be labelled with a measurement expression.
Measurement choice functions $\phi$ in the fragment are allowed to depend on the input errors as well as other measurements occurring within the fragment.

Each vertex in the output set $O$ is labelled by an expression of the form: “$\square \leftarrow (\zeta, \xi)$” consisting of a pair of classical functions $\zeta, \xi$ which again can depend on the input errors and the results of measurements in the pattern fragment. Vertices in $O$ are not measured so they do not contain a measurement expression.

Here is an example of a pattern fragment where the bottom left qubit is an input, and the top left qubit is an output:
We say a pattern fragment implements a gate $G$ if, for any input state of the form: $X^x Z^z \ket\psi$, performing the pattern fragment yields $X^\xi Z^\zeta G \ket\psi$. This extends in the natural way to gates with multiple input/output qubits:

\[\hfill
(X^{x_1}Z^{z_1} \otimes \ldots \otimes X^{x_n}Z^{z_n}) \ket\psi
\ \ \mapsto\ \
(X^{\xi_1}Z^{\zeta_1} \otimes \ldots \otimes X^{\xi_m}Z^{\zeta_m}) G \ket\psi
\hfill\]

Composing pattern fragments then results in the composition of their associated gates, hence it suffices for the sake of universality to show we can implement a universal set of quantum gates via pattern fragments.

§ ZX-NOTATION

To derive a universal set of measurement patterns for the MSPM model, it is convenient to use ZX-notation, which is a superset of the usual quantum circuit notation. It is used to depict linear maps from qubits to qubits, put together in the usual way via composition and tensor product. We will provide a brief overview. For a (very) in-depth reference see [8].

The only operations in ZX-notation are swap gates, identities, and special linear maps called spiders. These come in two varieties, Z-spiders depicted as white dots:

\[\hfill \tikzfig{Zsp-a} \ \ :=\ \ \ketbra{0 \cdots 0}{0 \cdots 0} + e^{i \alpha} \ketbra{1 \cdots 1}{1 \cdots 1} \hfill\]

and X-spiders depicted as grey dots:

\[\hfill \tikzfig{Xsp-a} \ \ :=\ \ \ketbra{+ \cdots +}{+ \cdots +} + e^{i \alpha} \ketbra{- \cdots -}{- \cdots -} \hfill\]

A special case is when spiders have a single input and output, in which case they form Z-phase and X-phase gates (up to a global phase):

\[\hfill \tikzfig{Z-a} \ \ =\ \ \ketbra{0}{0} + e^{i \alpha} \ketbra{1}{1} = Z(\alpha) \hfill\]

\[\hfill \tikzfig{X-a} \ \ =\ \ \ketbra{+}{+} + e^{i \alpha} \ketbra{-}{-} = X(\alpha) \hfill\]

Note that we adopt the convention for $\alpha$ such that the Pauli $Z$ and $X$ gates are obtained as $Z(\pi)$ and $X(\pi)$, respectively. Another special case is when $\alpha = 0$, in which case we omit the label:

\[\hfill \tikzfig{Zsp} \ \ :=\ \ \ketbra{0 \cdots 0}{0 \cdots 0} + \ketbra{1 \cdots 1}{1 \cdots 1} \hfill\]

\[\hfill \tikzfig{Xsp} \ \ :=\ \ \ketbra{+ \cdots +}{+ \cdots +} + \ketbra{- \cdots -}{- \cdots -} \hfill\]

In particular, when these phaseless spiders have single input and output they are the identity:

Phaseless spiders can be thought of as a generalisation of the GHZ state to a linear map. Indeed the Z-spider with 0 inputs and 3 outputs is the usual GHZ state (up to normalisation):

\[\hfill \tikzfig{ghz} \ =\ \ket{000} + \ket{111} \hfill\]

Furthermore, the $\ket{0}$ and $\ket{+}$ states are just one-legged spiders:

\begin{equation}\label{eq:spider-basis1}
\hfill
\tikzfig{ket-+}\ \ =\ \ \ket{0} + \ket{1} \ \propto \ket{+}
\qquad\qquad
\tikzfig{ket-0}\ \ =\ \ \ket{+} + \ket{-} \ \propto \ket{0}
\hfill
\end{equation}

The $\ket{1}$ and $\ket{-}$ states are these states followed by respectively a $Z(\pi)$ and $X(\pi)$ gate:

\[\hfill \tikzfig{ket--}\ \ =\ \ \ket{0} + e^{i\pi} \ket{1} \ \propto \ket{-} \hfill\]

\[\hfill \tikzfig{ket-1}\ \ =\ \ \ket{+} + e^{i\pi} \ket{-} \ \propto \ket{1} \hfill\]

Note that hence forth we will ignore non-zero scalar factors and we will cease to write $\propto$ instead of $=$, as scalar factors will not enter into our calculations.

While spiders are typically non-unitary, and hence not quantum gates, they can be used to construct a universal family of quantum gates. We already saw Z- and X-phase gates, while the CNOT gate can be constructed as follows:

\[
\textit{CNOT}\ :=\ \tikzfig{cnot} \ =\ \tikzfig{cnot-left} \ =\ \tikzfig{cnot-right}
\]

Note that we can always reverse the direction of a wire connecting two spiders without changing the value of the linear map, hence we can write the leftmost diagram above without ambiguity. More generally, diagrams of spiders are less rigid than circuits. Much like diagrammatic depictions of tensor networks (e.g. [19]), any two diagrams of spiders with the same connectivity and ordering of inputs/outputs describe the same linear map.

The power of the ZX-notation comes from the set of rewrite rules associated to it, collectively known as the ZX-calculus. The ZX-calculus has a couple of variations. We will only need a minimal set of rules. The first two are the spider-fusion rules, which says adjacent spiders of the same colour fuse together, and their phases add:

\[\hfill
\tikzfig{spider-fusion-Z} \qquad\qquad
\tikzfig{spider-fusion-X}
\hfill\]

This implies in particular that $Z$ and $X$ phase gates commute through spiders of the same colour. Pauli $Z$ and $X$ gates can be pushed through spiders of the opposite colour, but they change the sign of the angle:

\begin{equation}\label{eq:z-stab}
\hfill\tikzfig{Zsp-stab2}\hfill
\end{equation}

\begin{equation}\label{eq:x-stab}
\hfill\tikzfig{Xsp-stab2}\hfill
\end{equation}

We'll use the following rules to manipulate the Hadamard gate:

\[\hfill \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}\right) \ =\ \ \tikzfig{had}
\qquad\qquad
\tikzfig{had-self-inv} \hfill\]

The Hadamard gate interchanges the $Z$ and $X$ bases, so that it acts as a colour-changer for spiders:

We also get the following equality, which we will use throughout the paper:

\begin{equation}\label{eq:s-state-eq}
\hfill\tikzfig{S-state-equality}\hfill
\end{equation}

The same equation with the colours reversed also holds.

A final property that we will use is the strong complementarity of the Z and X bases of a qubit, which are captured by the following two diagrammatic rules:
Combining the rightmost equation with the other rules yields a more general version, for any $a \in \{0,1\}$ and $\alpha \in [0,2\pi)$:
We summarise all these rules in Table <ref>. Note that an extended set of these rules has been proven to be complete [17, 14], that is, two diagrams represent the same linear map if and only if they can be rewritten into one another using the rules of the ZX-calculus. The set of rules we will use is in contrast only complete when restricted to the Clifford fragment [2].

The rules of the ZX-calculus, which hold for all $\alpha, \beta \in [0, 2 \pi)$ and $a \in \{0,1\}$. Note that we ignore scalar factors in equalities between diagrams. Due to $(\bm{i2})$ all rules also hold with the colours interchanged.

§ PPM IN THE ZX-CALCULUS

In order to express the PPM model in the ZX-calculus, we give graphical presentations for the parity-phase gate and for Pauli measurements.
Recall that $P(\alpha) = \exp(-i\frac\alpha2 Z\otimes Z)$. It is easy to check that as a matrix in the computational basis, we have:

\[\hfill \exp(-i\frac\alpha2 Z\otimes Z) =  e^{-i\frac\alpha2}\left(\begin{matrix}
1  & 0 & 0 & 0 \\
0 & e^{i \alpha} & 0 & 0 \\
0 & 0 & e^{i \alpha} & 0 \\
0 & 0 & 0 & 1  \\
\end{matrix}\right)\hfill\]

If we interchange the third and fourth computational state ($\ket{10}$ and $\ket{11}$), we obtain (up to a global phase):

\[\hfill I\otimes Z(\alpha) = \left(\begin{matrix}
1  & 0 & 0 & 0 \\
0 & e^{i \alpha} & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & e^{i \alpha}  \\
\end{matrix}\right)
\hfill\]

Hence we obtain the parity-phase gate by pre- and post-composing the above matrix with CNOTs:

\[\hfill P(\alpha) = \text{CNOT}(I\otimes Z(\alpha))\text{CNOT} \ =\ \tikzfig{ms-complex} \hfill\]

This simplifies as a routine calculation in the ZX-calculus (see e.g. [8]):
where we repeatedly used spider fusion and in the second to last step we used the strong complementarity of the $Z$ and $X$ spiders. Hence, we have:

\begin{equation}\label{eq:virtual-qubit}
\hfill P(\alpha) \ =\ \tikzfig{zx-msgate}\hfill
\end{equation}

The Pauli Z and X measurements non-deterministically introduce projections onto their respective eigenstates, namely $\{ \bra{0}, \bra{1} \}$ for $Z$-measurements and $\{ \bra{+}, \bra{-} \}$ for $X$-measurements. Because basis elements of one colour can be expressed as spiders of the other colour, we can depict measurements as follows:

\begin{equation}\label{eq:meas-effects}
\begin{split}
\textit{\small Z-measure} & := \left\{ \tikzfig{gray-a-effect}\right\}_{a\in\{0,1\}} \\
\textit{\small X-measure} & := \left\{\tikzfig{white-a-effect}\right\}_{a\in\{0,1\}}
\end{split}
\end{equation}

The appearance of the `virtual qubit', i.e. the state being input between the two wires in equation (<ref>) is quite suggestive. We can interpret this node as a magic state that is waiting to be applied to one of its neighbouring (actual) qubits to introduce a phase. More specifically, if we prepare the second qubit in the $\ket{+}$ state and then measure it in the Z basis, we obtain an Z-phase gate $Z(\pm \alpha)$, depending on the measurement outcome:

If we take $\alpha=\frac\pi2$ we can rewrite the expression of $P(\frac\pi2)$ in the ZX-calculus a bit further:

\begin{equation}\label{eq:mscx}
\hfill\tikzfig{ms-cnot} \hfill
\end{equation}

Written in this way it is clear that the gate is equivalent, up to single-qubit Clifford unitaries to the controlled-Z gate $CZ$, which is represented in ZX-notation as:

\[\hfill\tikzfig{cz} \hfill\]

Since $P(\alpha)P(\beta) = P(\alpha+\beta)$ we get that $P(\frac\pi2) = P(\frac\pi4)^2$, so that the gate $P(\frac\pi4)$ is within local Cliffords of a $\sqrt{CZ}$ gate.

§ COMPUTING GATES FROM PATTERNS

There is an evident translation between P-graph states and ZX diagrams, which is very similar to the one given in [10]. Qubits become white dots with a single output and single/double edges become edges decorated by the appropriate phases as follows:

It will be convenient to deform the right-hand side to match the topology of the associated P-graph state, in which case we can drop the qubit labels:
Note that all of the wires with a free end correspond to outputs, so there is no need to draw them exiting to the right of the diagram.

To compute the result of a measurement pattern, we post-compose with the appropriate effects $\{ \bra{0}, \bra{1} \}$ for $Z$-measurements and $\{ \bra{+}, \bra{-} \}$ for $X$-measurements using equation (<ref>). This enables us to write patterns (without feed-forward) as a single ZX-diagram:
We could also represent the feed-forward within the diagram (e.g. by conditionally applying Hadamard gates to outputs), but for our purposes, it will be simpler just to do some simple case-distinctions.

Finally, pattern fragments can be expressed by not measuring outputs, and adding a new input wire for each input:

\begin{equation}\label{eq:pattern-translate}
\hfill\tikzfig{ms-translate4}\hfill
\end{equation}

In order to implement a gate $G$, we should show that the right-hand side above, pre-composed with possible Pauli errors, implements $G$ followed by some possible Pauli errors. Representing possible Pauli errors as follows:

\begin{equation}\label{eq:errors}
\hfill\tikzfig{error}\hfill
\end{equation}

this amounts to proving the following equation:

Remark: The colours play opposite roles in equations (<ref>) and (<ref>). This is a common theme in the ZX-calculus, and comes from the fact that basis elements of one colour can be described as spiders of the other colour (cf. equation (<ref>)).

The simplest non-trivial example of a pattern fragment implements a single $X(\pi/2) = HSH$, gate:

\[\hfill
\tikzfig{ms-sgate}
\qquad\textrm{where}\ \
\begin{cases}
\ \zeta & \!\!\!=  z\oplus a\\
\ \xi & \!\!\!= z\oplus a\oplus x\oplus 1
\end{cases}
\hfill\]

The bottom qubit is the input of the expression. We always measure it in the X basis ($a\leftarrow 0$) which gives us a measurement result $a$. We record the incoming $Z$ and $X$ error in the variables $z$ and $x$. The resulting $Z$ error at the end is now $z\oplus a$, and the X error is $z\oplus a\oplus x\oplus 1$. We can show the correctness of this fragment by performing translation (<ref>) and reducing using the ZX-calculus:
where all steps are spider-fusion except $(*)$, which uses equation (<ref>) and $(**)$, which is the standard Clifford commutation law of $S^\dagger X \propto X Z S^\dagger $. This commutation follows straightforwardly from (<ref>).

We'll now introduce a more versatile P-graph fragment, shaped like an `E', which can implement a variety of single-qubit gates. The first pattern fragment in the E-shape implements an $Z(\pi/4)$ gate, i.e. an $T$ gate:

\[\hfill
\tikzfig{ms-pattern-fragment}
\textrm{where \footnotesize $\ \
\begin{cases}
\zeta
& \!\!\! = a \oplus c \oplus d \oplus e \oplus x\oplus (b \oplus z)(c \oplus d \oplus z \oplus 1) \\
\xi
& \!\!\! = c \oplus d\oplus z \oplus 1
\end{cases}$}
\hfill\]

Note that now the basis in which the qubit $e$ is measured depends on the incoming $Z$ error and one of the measurement results in the pattern fragment itself. Let's translate this to the ZX-calculus, ignoring for the moment being the Pauli errors that could be at the beginning of the fragment:
We used equation (<ref>) to introduce the Hadamards above. Now we measure $a$, $c$ and $d$ in the $X$-basis and $b$ in the $Z$-basis, each of which can introduce a $\pi$ phase of their respective colour:
The goal of this pattern is to introduce a $\pi/4$ phase. We see that now we either have $\pi/4$ or $-\pi/4$. If we measure $e$ in the X-basis, it gets cut off the main structure, but if we measure it in the Z-basis it introduces an extra $\pi/2$ phase. So, if we got $\pi/4$ (in this case, when $b=0$), we measure $e$ in the X-basis:
and otherwise we measure $e$ in the Z-basis:
so that we indeed implement a $\pi/4$ Z-rotation with some Pauli X and Z error depending on the measurement outcomes. In the presence of of some starting Pauli X and Z errors, the same procedure can be done by being careful to track where the errors spread. Tracking these errors correctly gives the pattern fragment that we started out with. If we decide to measure $e$ in the opposite basis (so in the Z basis when $b=0$ and the X basis when $b=1$), we can implement a $T^\dagger$ gate. Classical control determines the sign of our rotations.

Using the same pattern fragment, but with a different set of measurements on the `hairs' of the fragment we can implement some different operators. For instance, if we measure $a,b,c$ and $e$ in the X basis and $d$ in the Z basis we get a Hadamard gate:
In a similar way we can also produce an $S$-gate by measuring qubit $e$ in the Z basis and the rest in the X basis.

The following fragment implements a CZ-gate:

\[\hfill\tikzfig{ms-cnot2} %\qquad \cong \qquad \tikzfig{zx-cx}
\qquad\textrm{where}\ \ \begin{cases}
\xi_i(z_i) & \!\!\!= x_i \\
\zeta_1 & \!\!\!= z_1\oplus x_2\oplus a \oplus b \oplus 1 \\
\zeta_2 & \!\!\!= z_2\oplus x_1\oplus a \oplus b \oplus 1
\end{cases}
\hfill\]

By conjugating one side with Hadamard gates we get a CNOT gate, and thus we can use this gate to achieve universality.

Note that the top and bottom qubits act as both inputs and outputs, so they are not measured. We measure $a$ in the Z-basis, and $b$ in the X-basis. Writing the resulting diagram out in ZX-calculus (again ignoring incoming Pauli errors for the moment) we get:
Now we can use the conversion rule for Hadamards ($\tikzfig{had}$) on the middle part, giving:
Pauli errors propagate through a CZ in the following way:
and in exactly the same way for the other input. Putting the above derivation together with this error propagation gives the pattern fragment as specified above.

This pattern fragment implementing CZ has the additional property that if we measure $b$ in the Z basis instead of the X basis, it disconnects. It doesn't matter in which basis we measure $a$, but let's take it to be the X basis. This pattern fragment is

In ZX notation (ignoring incoming Pauli's):
Hence, the choice of measurement basis for $b$ `switches' the CZ-gate on or off.

§ PROOF OF UNIVERSALITY

In the previous section we've constructed a pattern fragment that can implement a $T$ gate and an $H$ gate depending on the chosen measurements. Combining these, we can produce $H$ and $T$, which suffice to  approximate any single-qubit unitary. Combining this with the entangling gate we demonstrated at the end of the previous section suffices for universality.

It only remains to combine these patterns into a configuration that allows us to combine them arbitrarily. We will construct a fragment that is a combination of the simple blocks described above which fits neatly into a 2D square lattice. If we simply compose two of the `E'-shaped blocks from the previous section with a CZ block rotated 90 degrees we get:
where the $i$'s denote inputs and $o$'s denote outputs.

These bricks however don't fit together in a square lattice, since there is no useful tiling we can produce without some qubits overlapping. However, we can solve this problem by considering a slightly larger brick:
This brick has extra qubits on the top and on the bottom which function as $S$ gates, although depending on the measurements these can cancel out against each other. Besides that the two `E' blocks that are present are offset one qubit (also note that we moved the middle qubit of the CX fragment up to make room for one of the `E' blocks). This means that while the left `lane' implements a $T$ gate, the right lane effectively implements a $HTH$ gate.

Depending on the choice of measurements such a brick can implement on each qubit a H, S, HSH, HSHS, HTH or a T gate followed by an optional CZ gate.

Since a series of these bricks can implement an arbitrary Clifford+T gate, a family of P-graph states of increasing size where each graph consists of the bricks defined above stacked in a brickwork-like fashion:
will result in a computational model allowing universal quantum computation [5].

The asymmetry present in the brick allows us to efficiently tile them:
We see that all locations in a square grid are used. Qubits whose measurement could potentially depend on prior outcomes are shown in white above. Of those, only the corrections forming part of the T pattern described rely on feed-forward. Hence all of the other qubits can be measured simultaneously at the beginning of the computation.

This graph state can be summarised as consisting of lanes which carry the computation forward and attached to these lanes are `hairs' which introduce extra phases. `Shaving off' all of the hairs reveals a state that has a somewhat similar structure to the brickwork state from [5]:

While our primitive computational `brick' doesn't seem to be particularly canonical, the fact that it is missing some edges from a square lattice could have advantages when thinking about space-limited architectures. For instance, with a bit of folding, this 16-qubit pattern fits nicely into the 17-qubit `ninja star' design of the superconducting chip proposed in [25], which is designed primarily for implementing a 17-qubit surface code:

This means that a proof of concept for this computational model is potentially close at hand. Looking at the way the `E'-shape implements the T-gate we also see that the middle `hair' is actually not necessary. Removing this qubit allows us to fit a universal brick inside the superconducting chip of Ref. [18].

§ CLIMBING THE CLIFFORD HIERARCHY

The construction of a deterministic feed-forward strategy in the previous sections relies on the fact that a sign error in a T gate, i.e. a $\pi/4$ rotation, can be corrected by applying a $\pi/2$ rotation, and then correcting a sign error in a $\pi/2$ rotation by selectively applying a $\pi$ rotation. Since such a $\pi$ rotation can be commuted past all other gates, the resulting error can be handled at the end of the computation in a classical manner.

We will now show that this works not only for $\pi/4$, but for all angles $\pi/2^n$ where $2 \leq n \in \mathbb N$. While the P-graphs of the previous sections had a single edge represent a $P(\frac\pi4)$ gate, we will now let a single edge represent $P(\frac{\pi}{2^n})$. If we have $k$ edges between two vertices then this represents a $P(\frac{\pi}{2^n})^k = P(\frac{k\pi}{2^n})$ gate. Now consider the following fragment:

Here the $2^{n-1}$ refers to the amount of wires between the vertices. I.e. this means that there will be a $P(\pi/2)$ gate between the qubits there. Let us simplify the corresponding diagram in the ZX-calculus. We will not yet apply the measurement of the qubit $e$.

If $b=0$, then we have the rotation we want, so we can measure the remaining qubit $e$ in the $X$ basis, and we see that we are left with a $\pi/2^n$ rotation with some Pauli error. If $b=1$, however, we will measure $e$ in the Z-basis, and we calculate:

If $c\oplus e = 1$, then this is the desired computation. Otherwise, we are left with an unwanted $\pi/2^{n-2}$ rotation. Since this undesired rotation is heralded by the outcome of a measurement, we can however decide to do a $-\pi/2^{n-2}$ in its future to cancel out this rotation using exactly the same procedure. Trying to do this extra $-\pi/2^{n-2}$ rotation could then introduce an unwanted $\pi/2^{n-3}$ rotation. After $n-2$ repetitions of this protocol we are therefore left with a $\pi$ error that can safely be incorporated into the classical feed-forward.

The relevant concept to understand this kind of iteration of rotations is that of the Clifford hierarchy. The first level $\mathcal{C}_1$ is defined to be the set of tensor products of the identity and the Pauli unitaries.
The higher levels are then iteratively defined to be the multiqubit unitaries that send the Pauli unitaries to a lower level of the hierarchy: $\mathcal{C}_n := \{U ~;~ \forall V\in \mathcal{C}_0: UVU^\dagger \in \mathcal{C}_{n-1}\}$.
With this definition we can see that $\mathcal{C}_2$ consists of exactly the usual Clifford operators. While $\mathcal{C}_1$ and $\mathcal{C}_2$ are closed under composition, the higher levels no longer form groups.
In fact, not much is known about the general structure of the higher sets in the Clifford hierarchy.
What we do know however is that the diagonal unitaries in $\mathcal{C}_n$ always form a group, and that for $n\geq 2$ each of these diagonal elements can be constructed using Clifford operations and the $\pi/2^{n-1}$ $Z$ rotation [9].
Using the above description of a deterministic implementation of a $\pi/2^{n-1}$ rotation we have therefore found a deterministic measurement-based model that can implement any diagonal $n$-th level Clifford operation using just Pauli measurements.

§ CONCLUSIONS AND FURTHER WORK

We presented a novel family of graph states that lead to approximately universal quantum computation using just measurements in two bases. Furthermore, depending on the chosen parameter, diagonal gates of arbitrarily high levels of the Clifford hierarchy can be implemented. The interactions needed to make the graph states described in this paper are available in both ion trap and superconducting quantum computing hardware which means proofs of concept could be implemented in a short timeframe. However, it remains unclear if such a measurement-based scheme would yield benefits over the circuit model on such architectures. One avenue of future work is to explore the applicability and/or advantages of the PPM scheme to quantum optics, which has already seen successful implementations of the one-way model [26].

In the scheme we gave, each of the qubits whose measurement depends on previous outcomes is a correction involved in implementing a single $T$-gate. Hence, the number of required measurement/feed-forward cycles is clearly related to the $T$-depth of the associated circuit. We intend to make this relationship precise and relate to similar results known for the one-way model concerning pattern depth and parallelisation of measurements. Another avenue of future work is to understand the general properties of feed-forward in P-graph states. For instance, concepts like Flow and gFlow [6, 15] are likely to apply with little modification to the `double edge' portion of a P-graph state, so it will be interesting to see if this can be extended.

Finally, there is an intriguing link between the form of a parity-phase gate derived in equation (<ref>) and quantum computing with magic states. For instance, on ion trap based architectures, it is possible to introduce $O(n^2)$ parity-phase gates in a single time step using an $n$-qubit interaction [23]. One can wonder if this quick production of $O(n^2)$ `virtual magic states' makes it possible to achieve some kind of advantage in magic state distillation.

Acknowledgements: This work is supported by the ERC under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC grant n$^\text{o}$ 320571. The authors would like to thank Brian Tarasinksi and Martin Sepiol for useful discussions about superconducting qubits and the Mølmer-Sørensen interaction in ion traps, respectively.

[1]
S. Aaronson and D. Gottesman.
Improved simulation of stabilizer circuits.
Physical Review A, 70(5):052328, 2004.

[2]
M. Backens.
The zx-calculus is complete for stabilizer quantum mechanics.
New Journal of Physics, 16(9):093021, 2014.

[3]
M. Backens and A. Kissinger.
ZH: A complete graphical calculus for quantum computations
involving classical non-linearity.
arXiv preprint arXiv:1805.02175, 2018.

[4]
C. Ballance, T. Harty, N. Linke, M. Sepiol, and D. Lucas.
High-fidelity quantum logic gates using trapped-ion hyperfine qubits.
Physical Review Letters, 117(6):060504, 2016.

[5]
A. Broadbent, J. Fitzsimons, and E. Kashefi.
Universal blind quantum computation.
In Foundations of Computer Science, 2009. FOCS'09. 50th Annual
IEEE Symposium on, pages 517–526. IEEE, 2009.

[6]
D. E. Browne, E. Kashefi, M. Mhalla, and S. Perdrix.
Generalized flow and determinism in measurement-based quantum
New Journal of Physics, 9(8):250, 2007.

[7]
B. Coecke and R. Duncan.
Interacting quantum observables.
In Proceedings of the 37th International Colloquium on Automata,
Languages and Programming (ICALP), Lecture Notes in Computer Science, 2008.

[8]
B. Coecke and A. Kissinger.
Picturing Quantum Processes.
Cambridge University Press, 2014.

[9]
S. X. Cui, D. Gottesman, and A. Krishna.
Diagonal gates in the clifford hierarchy.
Physical Review A, 95(1):012329, 2017.

[10]
R. Duncan and S. Perdrix.
Rewriting measurement-based quantum computations with generalised
In Proceedings of ICALP, Lecture Notes in Computer Science,
pages 285–296. Springer, 2010.

[11]
M. Gachechiladze, O. Gühne, and A. Miyake.
Changing the circuit-depth complexity of measurement-based quantum
computation with hypergraph states.
arXiv preprint arXiv:1805.12093, 2018.

[12]
J. Gaebler, T. Tan, Y. Lin, Y. Wan, R. Bowler, A. Keith, S. Glancy, K. Coakley,
E. Knill, D. Leibfried, et al.
High-fidelity universal gate set for be 9+ ion qubits.
Physical Review Letters, 117(6):060505, 2016.

[13]
D. Gross, J. Eisert, N. Schuch, and D. Perez-Garcia.
Measurement-based quantum computation beyond the one-way model.
Phys. Rev. A, 76:052315, Nov 2007.

[14]
E. Jeandel, S. Perdrix, and R. Vilmart.
A Complete Axiomatisation of the ZX-Calculus for Clifford+T Quantum
ArXiv e-prints, May 2017.

[15]
D. Markham and E. Kashefi.
Entanglement, Flow and Classical Simulatability in Measurement
Based Quantum Computation, pages 427–453.
Lecture Notes in Computer Science. Springer International Publishing,

[16]
J. Miller and A. Miyake.
Hierarchy of universal entanglement in 2d measurement-based quantum
npj Quantum Information, 2:16036, 2016.

[17]
K. F. Ng and Q. Wang.
A universal completion of the ZX-calculus.
ArXiv e-prints, June 2017.

[18]
J. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom,
S. Caldwell, N. Didier, E. S. Fried, S. Hong, et al.
Unsupervised machine learning on a hybrid quantum computer.
arXiv preprint arXiv:1712.05771, 2017.

[19]
R. Penrose.
Applications of negative dimensional tensors.
In Combinatorial Mathematics and its Applications, pages
221–244. Academic Press, 1971.

[20]
R. Raussendorf, D. Browne, and H. Briegel.
Measurement-based quantum computation on cluster states.
Physical Review A, 68(2):22312, 2003.

[21]
R. Raussendorf and H. J. Briegel.
A one-way quantum computer.
Phys. Rev. Lett., 86:5188–5191, May 2001.

[22]
Y. Shi.
Both toffoli and controlled-not need little help to do universal
quantum computation.
arXiv preprint quant-ph/0205115, 2002.

[23]
A. Sørensen and K. Mølmer.
Quantum computation with ions in thermal motion.
Physical review letters, 82(9):1971, 1999.

[24]
Y. Takeuchi, T. Morimae, and M. Hayashi.
Quantum computational universality of hypergraph states with pauli-x
and z basis measurements.
arXiv preprint arXiv:1809.07552, 2018.

[25]
R. Versluis, S. Poletto, N. Khammassi, N. Haider, D. Michalak, A. Bruno,
K. Bertels, and L. DiCarlo.
Scalable quantum circuit and control for a superconducting surface
arXiv preprint arXiv:1612.08208, 2016.

[26]
P. Walther, K. J. Resch, T. Rudolph, E. Schenck, H. Weinfurter, V. Vedral,
M. Aspelmeyer, and A. Zeilinger.
Experimental one-way quantum computing.
Nature, 434:169–176, 2005.