# F$in$A: Fairness of Adverse Effects in Decision-Making of Human-Cyber-
Physical-System

Tianyu Zhao  University of California, Irvine
Irvine, CA
<EMAIL_ADDRESS>Salma Elmalaki  University of California, Irvine
Irvine, CA
<EMAIL_ADDRESS>
###### Abstract

Ensuring fairness in decision-making systems within Human-Cyber-Physical-
Systems (HCPS) is a pressing concern, particularly when diverse individuals,
each with varying behaviors and expectations, coexist within the same
application space, influenced by a shared set of control actions in the
system. The long-term adverse effects of these actions further pose the
challenge, as historical experiences and interactions shape individual
perceptions of fairness. This paper addresses the challenge of fairness from
an equity perspective of adverse effects, taking into account the dynamic
nature of human behavior and evolving preferences while recognizing the
lasting impact of adverse effects. We formally introduce the concept of
Fairness-in-Adverse-Effects (F _in_ A) within the HCPS context. We put forth a
comprehensive set of five formulations for F _in_ A, encompassing both the
instantaneous and long-term aspects of adverse effects. To empirically
validate the effectiveness of our F _in_ A approach, we conducted an
evaluation within the domain of smart homes, a pertinent HCPS application. The
outcomes of our evaluation demonstrate that the adoption of F _in_ A
significantly enhances the overall perception of fairness among individuals,
yielding an average improvement of 66.7% when compared to the state-of-the-art
method.

###### Index Terms:

human-cyber-physical-systems, fairness, decision-making, adverse-effect

##  I Introduction

The ubiquitous integration of smart technologies into our daily lives offers
unprecedented opportunities but also presents a lot of challenges. A key
challenge lies in understanding the interplay between humans and Cyber-
Physical Systems (CPS) to shape the societal consequences of future CPS
technologies. As we move towards a future defined by the coexistence of humans
and smart technologies, understanding their interactions is essential, as
suggested by recent studies [1, 2]. Within the realm of Human-Cyber-Physical
Systems (HCPS), one central challenge emerges when CPS decisions can affect
individuals with diverse preferences and perceptions within the same
environment. This scenario is common in systems like smart buildings, smart
cities, smart traffic management, and smart crowd control, where fairness,
privacy, equity, and personalization issues intersect, sparking new societal
tensions [3, 4, 5].

Existing research in sociology, particularly Social Exchange Theory [6, 7] and
Equity Theory [8] has substantiated a direct link between “equity” and
prosocial behavior. The higher an individual perceives a system as equitable,
the greater the likelihood of that individual engaging in prosocial behavior
[9, 10, 8]. This, in turn, significantly impacts the overall performance of
the system. Specifically, the greater the number of individuals who engage in
prosocial behavior, the higher the likelihood of compliance and acceptance of
the system’s decisions, ultimately leading to an enhancement in overall system
performance [11, 12, 13]. Given that CPS decision-making often aims to
optimize system performance while adhering to operational constraints, it is
essential to develop formal metrics and objective functions that enhance the
human perception of these decisions, ultimately fostering more prosocial
behavior and improving overall system performance.

In this paper, we are interested in formalizing some of the equity objectives
in decision-making HCPS. We will start by exploring a notion of fairness from
the equity perspective. In particular, we will focus on what we term Fairness-
in-Adverse-Effects (F _in_ A). Decision-making agents in HCPS employ a range
of control actions. However, these control actions can have different adverse
effects on a diverse population, each with its own preferences. Hence, the
HCPS needs to adapt its decision-making to continuously match different
populations across time and ensure that it meets the preferences of as many
populations as possible. Our motivation in examining the adverse effects or
the harmful impact of decision-making in HCPS stems from the psychology
concept “loss aversion–Losses loom larger than gains” which implies that
losses can be twice as powerful, psychologically, as gains [14]. This concept
underscores the significance of minimizing adverse effects to promote fairness
within HCPS.

##  II Related Work

HCPS systems are centered on the challenge of designing adaptable, real-time
decision-making processes that take into account the social context, including
considerations of fairness, social welfare, ethical concerns, and societal
norms [15, 16]. A substantial body of work in the field of game theory
explores various facets of fairness, often framed as incentive markets among
competing entities or communities striving to achieve fairness [17, 18]. In
the domain of machine learning, interventions to enhance fairness have been
introduced, aiming to ensure that models’ decisions are devoid of
discrimination [19, 20, 21, 22, 23]. In the context of decision-making
systems, where agents express favoritism for one action over another,
questions surrounding fairness become even more significant, especially within
multi-agent systems [24, 25, 26, 27, 28, 29, 30, 31]. However, imposing
fairness constraints as static, one-time decisions akin to conventional
supervised learning methods while neglecting dynamic feedback and long-term
consequences, particularly in sequential decision-making systems, can
inadvertently lead to disparities that affect specific sub-populations [32,
33].

Recent research has also shed light on the long-term ramifications of
Reinforcement Learning (RL), revealing that addressing control decisions’
immediate effects in single steps does not ensure fairness in subsequent
decision actions [34, 35]. Nevertheless, a significant portion of this
research has predominantly focused on fairness through the lens of equality,
with an emphasis on eliminating favoritism or bias within the system, and
relatively less attention has been given to the concept of fairness from an
equity perspective, particularly in the context of sequential decision-making
[36]. Notably, ensuring fairness in sequential decision-making systems becomes
increasingly complex as policies deemed fair at one point may inadvertently
become discriminatory over time due to shifts in human preferences influenced
by the inter- and intra-human variation [37].

The concept of “group fairness” has been introduced in the literature to
tackle fairness concerns arising when the same adaptive model impacts multiple
individuals. One notion is “Equalized Odds” which concentrates on achieving a
level of uniform prediction accuracy across various groups, primarily within
the context of binary classification tasks. The central objective is to ensure
that a predictive model exhibits comparable true positive rates (sensitivity)
and true negative rates (specificity) across diverse groups [38]. A second
notion is “Equal opportunity,”, which aims to guarantee that a predictive
model affords an equal likelihood of beneficial outcomes for all groups. It
places a specific requirement on the true positive rate, mandating that it
should be approximately equivalent for each group [38].

Prior research in CPS has explored fairness in various ways. For instance,
fairness-aware resource allocation and scheduling algorithms have been
developed for CPS, addressing issues like energy consumption and real-time
constraints while considering equitable distribution among system components
[39]. The concept of fairness in communication protocols for CPS has been
established through strategies to ensure fair access to network resources for
different devices and applications [40]. Furthermore, fairness challenges in
decentralized CPS environments have been examined, focusing on ensuring fair
decision-making in multi-agent systems [41].

However, it’s worth noting that much of the existing CPS literature
concentrates on system-level performance and efficiency, often at the cost of
individual-level fairness considerations. In contrast, this paper aims to
delve deeper into the aspects of fairness within HCPS, addressing the
interplay between human preferences, the temporal dimension of adverse
effects, and perceptions of fairness. This approach allows for a more
comprehensive understanding of fairness in the context of HCPS decision-
making, particularly in systems where individuals’ preferences and perceptions
can evolve over time.

###  II-A Paper contribution

This paper’s contributions can be summarized as follows:

  * •

Fairness-in-Adverse-Effect (F _in_ A): In this paper, we introduce a novel
concept known as “Fairness-in-Adverse-Effect (F _in_ A).” F _in_ A takes a
fresh perspective by considering equity in adverse effects within Human-Cyber-
Physical Systems (HCPS) decision-making. We address scenarios where adaptive
decisions made within HCPS can impact multiple individuals with diverse
preferences. By formalizing F _in_ A, we provide a means to ensure that the
adverse effects of decision-making are distributed fairly among the system’s
users

  * •

Long-term effects: Our work extends beyond the immediate effect of CPS
decision-making. We delve into the temporal dimension of adverse effects,
recognizing that the impact of these decisions can have lasting consequences.
The interplay between human preferences, historical data, and the evolving
perception of fairness adds complexity to the notion of fairness. We introduce
five different approaches to formalize F _in_ A within CPS decision-making to
account for the relationship between the instantaneous adverse effects, long-
term adverse effects, and the overall perception of fairness.

  * •

Generalization to different HCPS setups: We acknowledge that the nature of
adverse effects and fairness considerations can vary across different domains.
Therefore, we offer a general formalization of F _in_ A that can be applied to
various HCPS scenarios. Additionally, we conduct thorough evaluations in the
domain of smart home to illustrate the trade-offs between various
interpretations and implementations of F _in_ A. This demonstrates the
flexibility and effectiveness of our approach across diverse HCPS settings.

The rest of the paper is organized as follows: We first introduce the notion
of Fairness-in-Adverse-Effects (F _in_ A) within Human-Cyber-Physical Systems
(HCPS) in Section III. We formally define F$in$A using five different
approaches in considering the instantaneous and the long-term adverse effects
while considering the human perception of fairness in Sections III-B, III-C,
III-D, III-E and III-F. Afterward, we numerically evaluate these approaches
using a smart home HCPS application while comparing with the state-of-the-art
in Section IV.

##  III Approach

We consider a CPS depicted in Figure 1, which serves multiple individuals
sharing the same CPS environment, each with different preferences. The control
action generated by the decision-making agent in CPS can cause different
adverse effects on those individuals.

Figure 1: Human-Cyber-Physical-System with multiple individuals sharing the
same environments with different preferences. The decision-making agent
control action can cause different adverse effects on those individuals.

To achieve Fairness-in-Adverse-Effects (F _in_ A) within Human-Cyber-Physical
Systems (HCPS), we propose five distinct approaches to guide CPS decision-
making when selecting control actions affecting multiple humans sharing the
same environment. These approaches are rooted in the recognition that
individuals who exhibit pro-social attitudes might be willing to tolerate
certain discrepancies between their preferences and CPS actions for a limited
duration [9]. However, it is important to acknowledge that this willingness to
forgive may not be indefinite, as the magnitude and persistence of
discrepancies play a pivotal role in shaping individuals’ perception of
fairness [9]. Moreover, the extent of an individual’s willingness to forgive
is contingent upon the CPS’s responsiveness in addressing and rectifying such
discrepancies [7].

Our first approach formalizes F _in_ A by examining the concept of
instantaneous adverse effects, focusing on the immediate impact of CPS control
actions (Section III-B). In this context, we recognize that individuals may
exhibit a degree of patience when faced with minor or unintentional
discrepancies between their preferences and CPS actions. This approach is
predicated on the assumption that in scenarios of minimal and short-term
discrepancies, individuals may still perceive the CPS as acting in their best
interest.

Nonetheless, the second approach acknowledges that as the severity and
persistence of discrepancies increase, individuals, even those with pro-social
attitudes, may become less forgiving (Section III-C). Thus, the historical
aspect of adverse effects becomes a critical factor. It is during extended
periods of inconsistency that individuals may experience a diminishing
willingness to tolerate disparities. This approach takes into account the
temporal dimension of adverse effects, recognizing that extended discrepancies
may erode the perception of fairness [42].

In our third approach, we examine a balance between the instantaneous adverse
effect and the historical record of adverse effects (Section III-D). By
combining these two dimensions, we aim to provide a tradeoff that accounts for
both short-term variations and long-term consequences. This approach is
particularly valuable in situations where CPS must navigate the delicate
balance between immediate and lasting impact.

Building on the well-established literature on fair resource distribution, we
acknowledge that fairness is not synonymous with equal resource allocation
[42]. Humans’ perception of fairness is intrinsically tied to how they compare
their resource distribution with that of others in the same system. In the
fourth approach, we consider the collective perception of fairness among
individuals who share the same CPS environment as a metric for formalizing F
_in_ A (Section III-E). This approach recognizes that individuals may be more
forgiving of discrepancies if they perceive that others are experiencing
similar variations in resource allocation.

Lastly, our fifth approach introduces a tradeoff between human perception of
fairness and a budget of allowable discrepancy between individual preferences
and the applied CPS control action (Section III-F). By imposing limits on the
magnitude of permissible discrepancies, this approach provides a tradeoff
between accommodating individual preferences and ensuring collective fairness.

###  III-A Fairness-in-Adverse-Effect (F$in$A) Setup

In all of these five approaches, we consider a society $S$ that consists of
$N$ different individuals and a CPS that serves this society by providing
shared control actions $a$ that may be tailored toward the preferences and
behavior of some of those individuals. We assume that every individual $n\in
N$ has a different set of $g$ preferred actions
$A_{n}=\\{a^{n}_{1},a^{n}_{2},\dots,a^{n}_{g}\\}$ that can serve them
better111While in our first definition $A_{n}$ we assume a discrete set of
preferred actions, this can be extended to a continuous range of preferred
actions.. Suppose an adverse effect $v_{n}(a)$ on individual $n$ occurs due to
the chosen control action $a$. An initial mechanism to measure the adverse
effect on each $v_{n}(a)$ is to assume that a preferred action $a_{g}^{n}\in
A_{n}$ is inversely proportional to its adverse effects. That is, to measure
the adverse effects of a chosen control action $v_{n}(a)$ on human $n$, we can
use the distance between the set of preferred actions $\mathcal{A}_{n}$ and
the chosen control action $a$, i.e.,
$v_{n}(a)=\max_{a_{g}^{n}\in\mathcal{A}_{n}}\|a_{g}^{n}-a\|$.

###  III-B Approach I: Formalizing the definition of F$in$A with instantaneous
effect

In our first approach, we formalize F _in_ A by examining instantaneous
adverse effects, delving into the immediate consequences of CPS control
actions.

Hence, an initial definition of F$in$A can be:

$\text{F}in\text{A}=\min_{a\in\mathcal{A}}\|\mathbf{v}(a)-\frac{1}{N}\mathds{1}^{T}\mathbf{v}(a)\otimes\mathds{1}\|+\lambda\|\frac{1}{N}\mathds{1}^{T}\mathbf{v}(a)\|,$
(1)

where $\mathbf{v}(a)=[v_{1}(a),v_{2}(a),\dots,v_{N}(a)]^{\intercal}$ and
$\mathcal{A}=\bigcup_{n=1}^{N}A_{n}$. In other words, Equation (1) aims to
choose the control action $a$, out of all possible $A_{n}$, that minimizes the
difference between the individual adverse effects on every individual $v_{n}$
and the average of the adverse effects across all individuals
$\frac{1}{N}\sum_{n=1}^{N}v_{n}(a)=\frac{1}{N}\mathds{1}^{T}\mathbf{v}(a)$.
Indeed, one trivial solution will be to increase the adverse effect on all
individuals to achieve the same average. Therefore, the second term in
Equation (1) asks that the chosen control action also aims to minimize the
average adverse effect.

###  III-C Approach II: Formalizing the definition of F$in$A using long-term
temporal variations in adverse effect

In the second approach, the historical context of adverse effects plays a
pivotal role. Prolonged instances of inconsistency are where individuals may
exhibit a reduced willingness to endure disparities. This approach places a
significant emphasis on the temporal dimension of adverse effects,
acknowledging that extended discrepancies can undermine the perception of
fairness [42].

We define a long-term adverse effect $\mathbf{v}_{n}$ by monitoring the
adverse effect for every applied action $a$ over a time horizon $T$ on human
$n$.

$\displaystyle\mathbf{v}_{n}=[v_{n}^{0},v_{n}^{1},\dots,v_{n}^{T-1}]^{\intercal},$
(2)

where $v_{n}^{j}$ represents the adverse effect occurred at time $j$ for human
$n$. However, to focus more on the recent adverse effects, we assign different
weights to $v_{n}^{j}$ and calculate an accumulated value $u_{n}^{t}$ that
represents the current history of adverse effects on human $n$ from time $t-T$
till $t-1$.

$\displaystyle
u_{n}^{t}=\frac{1}{T}\sum_{j=0}^{T-1}\frac{j}{T}v_{n}^{j},\text{ for
}n=1,2,\dots,N$ (3)

The historical adverse effect on all $N$ individuals can be represented by:

$\displaystyle\mathbf{u}=[u_{1}^{t},u_{2}^{t},\dots,u_{N}^{t}]^{\intercal}$
(4)

We can then formally define F$in$A as:

$\displaystyle\begin{split}\text{F}in\text{A}=&\min_{a\in\mathcal{A}}\
\mathcal{B}\\\ s.t.\\\ &\mathbf{v}(a)<\mathcal{B}-\mathbf{u},\end{split}$ (5)

In this equation,
$\mathbf{v}(a)=[v_{1}(a),v_{2}(a),\dots,v_{N}(a)]^{\intercal}$ represents the
current adverse effect of action $a$ on each individual. To elaborate,
Equation (5) contains $N$ constraints, with each constraint governing the
current adverse effect $v_{n}(a)$ to remain below a specific budget
$\mathcal{B}$. However, it’s essential to note that this budget $\mathcal{B}$
is gauged on the historical adverse effects of each individual, denoted as
$u_{n}^{t}$. In this context, F _in_ A tries to identify the minimum budget
$\mathcal{B}$ that satisfies all N constraints. Consequently, if a human
individual, say $n$, has a substantial historical adverse effect value, the
constraint $\mathcal{B}-u_{n}^{t}$ will direct the optimization process toward
finding an action $a$ that results in a minimal $v_{n}(a)$. This approach is
designed to steer the optimization’s focus towards individuals with higher
historical adverse effect values, encouraging the selection of new actions
that minimize their adverse effects.

###  III-D Approach III: Formalizing the definition of F$in$A as a tradeoff
between instantaneous and long-term adverse effect

In our third approach, we delve into the balance between immediate adverse
effects and cumulative historical adverse effects. To achieve this, we augment
Equation (1) with a term that considers the historical adverse effects,
denoted as $u_{n}^{t}$ as defined in Equation (3).

The extended formulation can be expressed as:

$\displaystyle\begin{split}\text{F}in\text{A}=\min_{a\in\mathcal{A},\mathbf{b}}\
&\alpha\Big{(}\|\mathbf{v}(a)-\frac{1}{G}\mathds{1}^{T}\mathbf{v}(a)\otimes\mathds{1}\|+\lambda\|\frac{1}{G}\mathds{1}^{T}\mathbf{v}(a)\|\Big{)}\\\
&+\beta\mathbf{u}^{\intercal}\mathbf{b},\\\ s.t.\\\
&\mathbf{v}(a)<\mathbf{b}\end{split}$ (6)

In this formulation, $\mathbf{b}=[b_{1},b_{2},\dots,b_{N}]^{\intercal}$ and
$\mathbf{u}=[u_{1}^{t},u_{2}^{t},\dots,u_{N}^{t}]^{\intercal}$. Essentially,
the first term in Equation (6) is from the instantaneous adverse effect
(Equation (1)), and then we introduce $N$ new optimization variables, $b_{n}$,
for each individual $n$, which represents the budget allocated for the adverse
effect ($v_{n}(a)$) for each individual $n$. Importantly, these budgets
$\mathbf{b}$ are weighted by the values of the long-term adverse effects
$\mathbf{u}$.

In other words, we have $N$ constraints for different budgets for adverse
effects that are bounded for every individual ($\mathbf{v}(a)<\mathbf{b}$).
Accordingly, F$in$A needs to minimize these budgets $\mathbf{b}$ to minimize
the overall adverse effects. However, the upper bound for these budgets is
weighted by the accumulated historical adverse effects. Hence, the term
$\mathbf{u}^{\intercal}\mathbf{b}$ is appended to the definition of F$in$A.

To modulate the tradeoff between immediate and long-term adverse effects, we
introduce parameters $\alpha$ and $\beta$.

###  III-E Approach IV: Formalization the definition of F$in$A using human
perception of fairness

Drawing upon extensive research in the realm of equitable resource
distribution, we recognize that fairness does not necessarily mean equal
resource allocation [42]. Instead, the perception of fairness in individuals
is fundamentally linked to how they gauge their own resource distribution
concerning that of their peers within the same system. In particular, fairness
in this setup can be viewed generally as “variances” [42] of the “utility”
shared by individuals. Hence, we exploit the notion of the coefficient of
variation ($CoV$) of the utilities [42]. In our setup, we define this utility
for human $n$ at time $t$ as the temporal accumulated adverse effect caused by
the control actions of the CPS in the shared environment, denoted by
$u_{n}^{t}$ as expressed in Equation (3).

$\displaystyle
CoV_{\mathbf{u}}=\sqrt{\frac{1}{N-1}\sum_{n=1}^{N}\frac{(u_{n}-\bar{\mathbf{u}})^{2}}{\bar{\mathbf{u}}^{2}}}$
(7)

In Equation (7), $\bar{\mathbf{u}}=\frac{1}{N}\sum_{n=1}^{N}u_{n}^{t}$
represents the average utility (accumulated adverse effect at time $t$) of all
$N$ humans. The system is said to be more fair if and only if the $CoV$ is
smaller. The value of $CoV$ can be anywhere between $0$ and infinity. Hence,
we use the fairness index ($FI$) transformation to have a value between $0$
and $1$ to be easily interpreted as a fairness percentage. In other words, if
$FI$ is $1$, it means the system is $100\%$ fair, otherwise, if disparity
increases between individuals, this $FI$ value will decrease [42].

$\displaystyle FI_{\mathbf{u}}=\frac{1}{1+CoV_{\mathbf{u}}^{2}}$ (8)

Accordingly, we can define F$in$A to maximize the fairness index. The core
idea is to minimize the reciprocal of this fairness index, represented as $y$
in the optimization.

$\displaystyle\begin{split}&\text{F}in\text{A}=\min_{a\in\mathcal{A}}\ y\\\
s.t.\\\ &y\geq
1+\frac{1}{N}\sum_{n=1}^{N}\left(\frac{|u_{n}-\bar{\mathbf{u}}|}{\bar{\mathbf{u}}}\right)^{2}\\\
&\frac{|u_{n}-\bar{\mathbf{u}}|}{\bar{\mathbf{u}}}\leq\epsilon,\text{ for
}n=1,2,\ldots,N.\\\ \text{where:}\\\ &u_{n}=u_{n}^{t}+v(a)\end{split}$ (9)

In this formulation, $u_{n}^{t}$ is a constant value that represents the
accumulated history of the adverse effect up till time $t-1$ (Equation (3))
before applying the new $a$ that will add the new adverse effect $v(a)$ on
human $n$. We also add the constraint
$\frac{|u_{n}-\bar{\mathbf{u}}|}{\bar{\mathbf{u}}}\leq\epsilon,\text{ for
}n=1,2,\ldots,N$ that sets a limit on how much each individual’s adverse
effect can deviate from the average adverse effect. The parameter $\epsilon$
defines the maximum allowable difference.

###  III-F Approach V: Formalizing the definition of FinA using the human
perception of fairness with a tradeoff for a budget for long-term adverse
effect

Lastly, our fifth approach introduces a tradeoff between human perception of
fairness and a budget of allowable discrepancy between individual preferences
and the applied CPS control action. In particular, we combine our definition
of F$in$A in Equation (5) and Equation (9) to provide a tradeoff between
fairness index and adverse effect budget $\mathcal{B}$.

$\displaystyle\begin{split}&\text{F}in\text{A}=\min_{a\in\mathcal{A}}\
\alpha.y+\beta.\mathcal{B}\\\ s.t.\\\ &y\geq
1+\frac{1}{N}\sum_{n=1}^{N}\left(\frac{|u_{n}-\bar{\mathbf{u}}|}{\bar{\mathbf{u}}}\right)^{2}\\\
&\mathbf{v}(a)<\mathcal{B}-\mathbf{u}\\\ \text{where:}\\\
&u_{n}=u_{n}^{t}+v(a)\\\ \end{split}$ (10)

The $\alpha$ and $\beta$ weights allow us to adjust the tradeoff between
fairness index and adverse effect budget.

Figure 2: Human 1 activity pattern. |  Figure 3: Human 2 activity pattern. |  Figure 4: Human 3 activity pattern.
---|---|---

##  IV Evaluation

We designed an HCPS application in the domain of smart house. Recent
literature focuses on enhancing human satisfaction in smart heating,
ventilation, and air conditioning (HVAC) systems by employing various
techniques to adjust the set-point based on human activity and preferences
[43, 37]. These HCPS systems consider the current state and individual
preferences, such as body temperature changes during sleep or physical
activity. To evaluate different approaches of F$in$A in this application, we
consider a setup where multiple humans share a house with a single HVAC
system, and their activities determine individual HVAC set-point preferences.

We exploited recent work in the literature [37] that simulated a thermodynamic
model of a house incorporating the house’s shape and insulation type. To
regulate indoor temperature, a heater and a cooler with specific flow
temperatures ($50^{\circ}c$ and $10^{\circ}c$) were employed. A thermostat
maintained the indoor temperature within $2.5^{\circ}c$ around the desired set
point. An external controller controls the setpoint running the optimization
of F$in$A. A pictorial figure of the application setup is shown in Figure 5.

Figure 5: A smart house with three humans. Each human has a different
activity, which requires different desired indoor temperature setpoints
$T_{d}$. An external controller running F$in$A selects the applied setpoint
$T_{a}$ based on the calculations of instantaneous and long-term adverse
effects.

We implemented our proposed five approaches using CVXPY, a Python-embedded
modeling language for convex optimization problems [44].

The human was modeled as a heat source, with heat flow dependent on the
average exhale breath temperature ($EBT$) and the respiratory minute volume
($RMV$). These parameters depend on human activity [45]. We simulated three
humans with four activities: sleeping, relaxing, medium domestic work, and
working from home. Randomness was introduced by allowing multiple activity
choices during the same time slot. The different activity schedules depicted
in Figures 2, 3, and 4. The humans were simulated in separate rooms as seen in
Figure 5, each exhibiting unique behavioral patterns: (1) $h_{1}$ followed an
organized and repetitive weekly routine, (2) $h_{3}$ had a more random and
unpredictable life pattern, and (3) $h_{2}$ displayed intermediate randomness,
alternating between sleeping, being away from home, domestic activities, and
relaxation. The Mathworks thermal house model was extended to include a
cooling system and a human model222While more complex simulators like
EnergyPlus [46] exist, considering energy consumption and electric loads, we
opted for a simpler model to assess F$in$A..

The desired preferred action (temperature setpoint) per human
$a_{g}^{n}=T_{n}$, for $n=1,2,$ and $3$, can be obtained through fixed policy
configuration. We exploit existing approaches [47] for estimating the desired
HVAC setpoint based on activity and thermal comfort. The desired setpoints for
the considered activities are domestic activity ($72^{\circ}$F), relaxed
activity ($77^{\circ}$F), sleeping ($62^{\circ}$F), and work from home
($67^{\circ}$F). These setpoints aim to enhance thermal comfort [48].

| Accumulated adverse effect($\mathbf{u}$) | Hist. temperature difference $|T_{diff}|$ | Satisfaction rate (SR) % | Hist. satisfaction rate (SR)
---|---|---|---|---
Approach I |  |  |  |
Approach II |  |  |  |
Approach III |  |  |  |
Approach IV |  |  |  |
Approach V |  |  |  |
Mean |  |  |  |
Round Robin |  |  |  |
TABLE I: Comparison between all the different five approaches of F$in$A, mean approach, and Round Robin | $FI_{\mathbf{u}}$ | $CoV_{\mathbf{u}}$ | $FI_{\mathbf{SR}}$ | $CoV_{\mathbf{SR}}$
---|---|---|---|---
Approach I |  |  |  |
Approach II |  |  |  |
Approach III |  |  |  |
Approach IV |  |  |  |
Approach V |  |  |  |
Mean |  |  |  |
Round Robin |  |  |  |
TABLE II: Comparison between all the different five approaches of F$in$A, mean
approach, and Round Robin

###  IV-A Experiment setup

In this application, we used the difference between the desired temperature
($T_{d}$) and the applied temperature ($T_{a}$) as a measure of the adverse
effect:

$v(a)=\|T_{a}-T_{d}\|_{2},\text{ where }T_{a}\in[60-80]^{\circ}F$

We use the most recent $100$ samples for our history of adverse effects for
the three humans $\mathbf{v}_{1},\mathbf{v}_{1}$ and $\mathbf{v}_{3}$ (as
explained in Equation (2)) with sampling time $t_{s}=6$ min. Hence, every
$t_{s}$, we compute $\mathbf{u}=[u_{1},u_{2},u_{3}]^{\intercal}$ for the three
humans (as explained in Equation (4)), where
$u_{n}=\frac{1}{100}\sum_{j=0}^{99}\frac{j}{100}v_{n}^{j}$, and
$v_{n}^{j}=\|T_{a}^{j}-T_{d_{1}}^{j}\|_{2}$ for $n=1,2,$ and $3$.

The simulation was executed using a total of 3,000 samples, roughly equivalent
to approximately 12 days. This extended duration allowed us to accurately
capture changes in the behavioral patterns of the three individuals. We only
ran F$in$A when the desired temperatures of these three individuals were not
identical.

We consider that the human is satisfied if the $T_{a}$ is within
$2.5^{\circ}F$ difference from the desired temperature. We measure the
satisfaction rate by considering the $100$ sample window in $\mathbf{v}_{n}$.
Hence, the satisfaction rate ($SR$) for human $n$ is computed every $t_{s}$
computed as:

$SR_{n}=\sum_{j=0}^{99}\mathds{1}(v(a)\leq 2.5),\text{ for all
}v(a)\in\mathbf{v}_{n}$

Hence, the $SR$ can give us a measure in $\%$ since the total number of
samples we consider is $100$. We use this SR to compute $CoV$ and $FI$ as a
function of the $SR$ similar to Equations (7) and (8) respectively.

$\displaystyle
CoV_{\mathbf{SR}}=\sqrt{\frac{1}{N-1}\sum_{n=1}^{N}\frac{(SR_{n}-\overline{\mathbf{SR}})^{2}}{\overline{\mathbf{SR}}^{2}}},$
(11)

where $N=3$ and $\overline{\mathbf{SR}}=[SR_{1},SR_{2},SR_{3}]^{\intercal}$
computed for the three humans every $t_{s}$.

Similarly, we consider the $FI_{\mathbf{SR}}$ as follows:

$\displaystyle FI_{\mathbf{SR}}=\frac{1}{1+CoV_{\mathbf{SR}}^{2}}$ (12)

Furthermore, we compared the five proposed approaches for F$in$A with two more
approaches:

  * •

Mean approach: In this case, the applied temperature $T_{a}$ is the mean of
the desired temperature from the three humans.

  * •

Round Robin: In this case, the applied temperature $T_{a}$ is selected in
rotation between the desired temperature from the three humans.

  * •

FaiRIoT [37]: We compare with the state-of-the-art FaiRIoT, which uses
hierarchical reinforcement learning to assign weights to the desired actions
to compute the applied action. Hence, $T_{a}=\sum_{n=1}^{3}w_{n}T_{d_{n}}$.

In all of the experiments, we set the tradeoff parameters $\alpha=\beta=0.5$.

###  IV-B Results

We plot in Table I, the accumulated adverse effect
($\mathbf{u}=[u_{1},u_{2},u_{3}]^{\intercal}$), the histogram of the absolute
temperature difference between $|T_{diff}|=|T_{a}-T_{d}|$, the satisfaction
rate ($SR$), and the histogram of the satisfaction rate ($SR$), across all
approaches for the three individuals in three rooms.

First column in Table I compares the differences in the individual’s adverse
effect ($\mathbf{u}=[u_{1},u_{2},u_{3}]^{\intercal}$) across all approaches.
Approach II and V show the smallest difference which is also reflected in
average $CoV_{\mathbf{u}}$ in Table III. Approach IV has a higher
$CoV_{\mathbf{u}}$ (0.027) but it can bound $\mathbf{u}$ within a smaller
value compared with other approaches observed in Table I.

|  $|T_{diff}|$ overlap% |  $SR$ JSD |  $Avg.$ $FI_{\mathbf{u}}$ |  $Avg.$ $CoV_{\mathbf{u}}$ |  $Avg.$ $FI_{\textbf{SR}}$ |  $Avg.$ $CoV_{\textbf{SR}}$
---|---|---|---|---|---|---
Appr. I |  22.4% |  0.086 |  0.998 |  0.026 |  0.994 |  0.057
Appr. II |  86.5% |  0.010 |  0.999 |  0.004 |  0.994 |  0.066
Appr. III |  37.6% |  0.639 |  0.998 |  0.038 |  0.870 |  0.365
Appr. IV |  19.2% |  0.659 |  0.998 |  0.027 |  0.929 |  0.624
Appr. V |  83.4% |  0.139 |  0.999 |  0.004 |  0.992 |  0.077
Mean |  24.8% |  0.648 |  0.974 |  0.157 |  0.868 |  0.370
RR |  68.4% |  0.723 |  0.973 |  0.160 |  0.984 |  0.124
TABLE III: Comparison of the overlap area percentage, Satisfaction JSD, and
average Fairness Index ($FI$) and the average coefficient of variation ($CoV$)
of adverse effect(u) and satisfaction(SR), respectively.

We compare the distribution of $|T_{diff}|$ across all the approaches in Table
I second column. Approach II has the highest overlap percentage $86.5\%$ as
calculated in Table III which indicates that this approach can make all $3$
rooms have a more similar experience compared with other approaches. Round
robin (RR) has a large overlap percentage due to the fact that each room can
have a $|T_{diff}|=0$ on its turn in the round. However, RR will result in
significant $|T_{diff}|$, which is larger than $10^{\circ}F$ in a notable
number of the samples.

Table I third and fourth columns present the satisfaction rate ($SR$) across
all approaches. We report the Jensen-Shannon Divergence (JSD) of the histogram
for $SR$ in Table III333The Jensen–Shannon divergence is a method of measuring
the similarity between two probability distributions. The JSD is symmetric and
always non-negative, with a value of $0$ indicating that the two distributions
are identical, and a value greater than $0$ indicating that the two
distributions are different.. Approach II has the lowest JSD, indicating
closer $SR$ across rooms. RR has the highest overall $SR$ but it has the
highest JSD indicating no fairness in the $SR$ among $3$ rooms.

In Table II, we show $FI$ and $CoV$ calculated over the adverse
effect($\mathbf{u}$) and the satisfaction ($SR$). The fairness index ($FI$) is
a metric ranging from $0$ to $1$, where $1$ means absolute fair as explained
in Section III-E.

Table II first and second columns show that Approach I, II, III, and IV have
$FI_{\mathbf{u}}$ values close to $1$ and their $CoV_{\mathbf{u}}$ values are
less than $0.04$. On the contrary, Mean and RR have $FI_{\mathbf{u}}$ around
0.97 and a $CoV_{\mathbf{u}}$ of 0.16.

###  IV-C Comparison between these approaches

Based on these analysis from Tables I, II, and III we observe that Approach
II, and Approach V provide the best results in terms of $FI_{\mathbf{u}}$, and
$CoV_{\mathbf{u}}$, while Approach I provides better results in terms of
$FI_{\mathbf{SR}}$, and $CoV_{\mathbf{SR}}$.

###  IV-D Compare with the state of the art FaiRIoT [37]

The closest to our approach is FaiRIoT which computes the applied action
through a weighted sum of all the desired actions by the $N$ individuals
$T_{a}=\sum_{n=1}^{N}w_{n}T_{d_{n}}$. FaiRIoT uses a notion of utility which
is the average weight assigned by a layer called “Mediator RL” for a
particular human $h$ over a time horizon $[0:t]$. In particular, FaiRIoT
measures the fairness of the Mediator RL using the coefficient of variation
($CoV$) of the human utilities. The Mediator RL is said to be more fair if and
only if the $CoV$ is smaller. Accordingly, in Figure 6, we compare the $CoV$
in FaiRIoT with the $CoV_{\mathbf{u}}$ in all approaches in this paper.
Approaches I - V achieve average $CoV$ around $0.20$, while FaiRIoT $CoV$ is
larger than $0.6$. Approach II and IV has the lowest $CoV$ at $0.04$. Hence,
using F$in$A approaches improves the fairness where CoV is reduced by
$\mathbf{66.7\%}$ on average.

Figure 6: Coefficient of Variation ($CoV$) comparison between FaiRIoT and all
approaches.

##  V Discussion and Conclusion

Addressing fairness in decision-making not only aligns with the principles of
ethical AI and responsible technology, but also highlights the importance of
socially-aware CPS, as individuals are more likely to cooperate with, and
ultimately accept, systems that they perceive to treat them fairly. In this
paper, our approaches to formalizing F _in_ A within CPS decision-making
capture the interplay between human preferences, the temporal dimension of
adverse effects, and perceptions of fairness. Recognizing the complexities of
these interactions is essential for designing more equitable Human-Cyber-
Physical Systems. These approaches offer a multifaceted perspective on
addressing the challenges posed by the impact of CPS control actions on
diverse individuals within shared environments.

## Acknowledgment

This research was partially supported by NSF award # CNS-2105084.

## References

  * [1] A. Annaswamy, K. Johansson, and G. Pappas, “Control for societal-scale challenges roadmap 2030,” 2023.
  * [2] A. M. Annaswamy, P. P. Khargonekar, F. Lamnabhi-Lagarrigue, and S. K. Spurgeon, _Cyber-Physical-Human Systems: Fundamentals and Applications_. John Wiley & Sons, Inc., 2023.
  * [3] M. K. Lee, J. T. Kim, and L. Lizarondo, “A human-centered approach to algorithmic services: Considerations for fair and motivating smart community service management that allocates donations to non-profit organizations,” in _Proceedings of the 2017 CHI conference on human factors in computing systems_ , 2017, pp. 3365–3376.
  * [4] R. Wang, F. M. Harper, and H. Zhu, “Factors influencing perceived fairness in algorithmic decision-making: Algorithm outcomes, development procedures, and individual differences,” in _Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems_ , 2020, pp. 1–14.
  * [5] C. Stangor, “Conflict, Cooperation, Morality, and Fairness,” in _Principles of Social Psychology - 1st International Edition_. BCcampus Pressbooks, 2014.
  * [6] G. C. Homans, “Social behavior: Its elementary forms,” 1974.
  * [7] K. S. Cook and R. M. Emerson, “Social exchange theory,” 1987.
  * [8] J. S. Adams, “Towards an understanding of inequity.” _The journal of abnormal and social psychology_ , vol. 67, no. 5, p. 422, 1963.
  * [9] J. W. Thibaut and H. H. Kelley, _The social psychology of groups_. Routledge, 1959.
  * [10] M. Redmond, “Social exchange theory,” 2015.
  * [11] R. Cialdini, _Influence: The Psychology of Persuasion_. Harper Collins, 2007.
  * [12] ——, _Presuasion: A revolutionary way to influence and persuade_. Simon and Schuster, 2016.
  * [13] N. M. Huijts, E. J. Molin, and L. Steg, “Psychological factors influencing sustainable energy technology acceptance: A review-based comprehensive framework,” _Renewable and sustainable energy reviews_ , vol. 16, no. 1, pp. 525–531, 2012.
  * [14] D. Kahneman and A. Tversky, “Prospect theory: An analysis of decision under risk,” in _Handbook of the fundamentals of financial decision making: Part I_. World Scientific, 2013, pp. 99–127.
  * [15] J. Sztipanovits, X. Koutsoukos, G. Karsai, S. Sastry, C. Tomlin, W. Damm, M. Fränzle, J. Rieger, A. Pretschner, and F. Köster, “Science of design for societal-scale cyber-physical systems: challenges and opportunities,” _Cyber-Physical Systems_ , vol. 5, no. 3, pp. 145–172, 2019.
  * [16] P. P. Khargonekar and M. Sampath, “A framework for ethics in cyber-physical-human systems,” _IFAC-PapersOnLine_ , vol. 53, no. 2, pp. 17 008–17 015, 2020.
  * [17] L. J. Ratliff and T. Fiez, “Adaptive incentive design,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 8, pp. 3871–3878, 2020.
  * [18] L. J. Ratliff, R. Dong, S. Sekar, and T. Fiez, “A perspective on incentive design: Challenges and opportunities,” _Annual Review of Control, Robotics, and Autonomous Systems_ , vol. 2, no. 1, pp. 1–34, 2018.
  * [19] S. A. Friedler, C. Scheidegger, S. Venkatasubramanian, S. Choudhary, E. P. Hamilton, and D. Roth, “A comparative study of fairness-enhancing interventions in machine learning,” in _Proceedings of the conference on fairness, accountability, and transparency_ , 2019, pp. 329–338.
  * [20] T. B. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang, “Fairness without demographics in repeated loss minimization,” _arXiv preprint arXiv:1806.08010_ , 2018.
  * [21] A. Chouldechova and A. Roth, “The frontiers of fairness in machine learning,” _arXiv preprint arXiv:1810.08810_ , 2018.
  * [22] S. Kannan, J. H. Morgenstern, A. Roth, B. Waggoner, and Z. S. Wu, “A smoothed analysis of the greedy algorithm for the linear contextual bandit problem,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 2227–2236.
  * [23] N. Goel, M. Yaghini, and B. Faltings, “Non-discriminatory machine learning through convex fairness criteria,” in _Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society_ , 2018, pp. 116–116.
  * [24] S. Jabbari, M. Joseph, M. Kearns, J. Morgenstern, and A. Roth, “Fairness in reinforcement learning,” in _International Conference on Machine Learning_ , 2017, pp. 1617–1626.
  * [25] M. Joseph, M. Kearns, J. H. Morgenstern, and A. Roth, “Fairness in learning: Classic and contextual bandits,” in _Advances in Neural Information Processing Systems_ , 2016, pp. 325–333.
  * [26] Y. Yu, T. Wang, and S. C. Liew, “Deep-reinforcement learning multiple access for heterogeneous wireless networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 37, no. 6, pp. 1277–1290, 2019.
  * [27] S. Gillen, C. Jung, M. Kearns, and A. Roth, “Online learning with an unknown fairness metric,” in _Advances in neural information processing systems_ , 2018, pp. 2600–2609.
  * [28] U. Siddique, P. Weng, and M. Zimmer, “Learning fair policies in multi-objective (deep) reinforcement learning with average and discounted rewards,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 8905–8915.
  * [29] E.-J. Shin, R. Yus, S. Mehrotra, and N. Venkatasubramanian, “Exploring fairness in participatory thermal comfort control in smart buildings,” in _Proceedings of the 4th ACM International Conference on Systems for Energy-Efficient Built Environments_ , 2017, pp. 1–10.
  * [30] J. Jiang and Z. Lu, “Learning fairness in multi-agent systems,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 13 854–13 865.
  * [31] E. Hughes, J. Z. Leibo, M. Phillips, K. Tuyls, E. Dueñez-Guzman, A. G. Castañeda, I. Dunning, T. Zhu, K. McKee, R. Koster _et al._ , “Inequity aversion improves cooperation in intertemporal social dilemmas,” in _Advances in neural information processing systems_ , 2018, pp. 3326–3336.
  * [32] E. Creager, D. Madras, T. Pitassi, and R. Zemel, “Causal modeling for fairness in dynamical systems,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 2185–2195.
  * [33] L. T. Liu, S. Dean, E. Rolf, M. Simchowitz, and M. Hardt, “Delayed impact of fair machine learning,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 3150–3158.
  * [34] S. Kannan, A. Roth, and J. Ziani, “Downstream effects of affirmative action,” in _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , 2019, pp. 240–248.
  * [35] S. Milli, J. Miller, A. D. Dragan, and M. Hardt, “The social cost of strategic classification,” in _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , 2019, pp. 230–239.
  * [36] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan, “A survey on bias and fairness in machine learning,” _ACM Computing Surveys (CSUR)_ , vol. 54, no. 6, pp. 1–35, 2021.
  * [37] S. Elmalaki, “Fair-iot: Fairness-aware human-in-the-loop reinforcement learning for harnessing human variability in personalized iot,” in _Proceedings of the International Conference on Internet-of-Things Design and Implementation_ , 2021, pp. 119–132.
  * [38] M. Hardt, E. Price, and N. Srebro, “Equality of opportunity in supervised learning,” _Advances in neural information processing systems_ , vol. 29, 2016.
  * [39] A. Iosup, X. Zhu, A. Merchant, E. Kalyvianaki, M. Maggio, S. Spinner, T. Abdelzaher, O. Mengshoel, and S. Bouchenak, “Self-awareness of cloud applications,” _Self-Aware Computing Systems_ , pp. 575–610, 2017.
  * [40] S. Huaizhou, R. V. Prasad, E. Onur, and I. Niemegeers, “Fairness in wireless networks: Issues, measures and challenges,” _IEEE Communications Surveys & Tutorials_, vol. 16, no. 1, pp. 5–24, 2013.
  * [41] F. Ho, R. Geraldes, A. Gonçalves, B. Rigault, B. Sportich, D. Kubo, M. Cavazza, and H. Prendinger, “Decentralized multi-agent path finding for uav traffic management,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 2, pp. 997–1008, 2020.
  * [42] R. K. Jain, D.-M. W. Chiu, W. R. Hawe _et al._ , “A quantitative measure of fairness and discrimination,” _ACM Transaction on Computer System_ , 1984.
  * [43] W. Jung and F. Jazizadeh, “Towards integration of doppler radar sensors into personalized thermoregulation-based control of hvac,” in _Proceedings of the 4th ACM International Conference on Systems for Energy-Efficient Built Environments_. ACM, 2017, p. 21.
  * [44] S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization,” _Journal of Machine Learning Research_ , vol. 17, no. 83, pp. 1–5, 2016.
  * [45] R. G. Carroll, “Pulmonary system,” in _Elsevier’s Integrated Physiology_. Elsevier, 2007, ch. 10, pp. 99–115.
  * [46] M. Gerber, “energyplus energy simulation software,” 2014.
  * [47] M. Taherisadr, S. A. Stavroulakis, and S. Elmalaki, “Adaparl: Adaptive privacy-aware reinforcement learning for sequential decision making human-in-the-loop systems,” in _Proceedings of the 8th ACM/IEEE Conference on Internet of Things Design and Implementation_. ACM, 2023, pp. 262–274.
  * [48] P. O. Fanger, “Thermal comfort. analysis and applications in environmental engineering.” _Thermal comfort. Analysis and applications in environmental engineering._ , 1970.


#  Low-Complexity Linear Programming Based Decoding of Quantum LDPC codes
††thanks: The work of S. Javed and M. F. Flanagan was supported by Science
Foundation Ireland under the US-Ireland R&D Partnership Programme (CoQREATE,
Grant Number SFI/21/US-C2C/3750). The work of F. Garcia-Herrero was supported
by the QuantERA grant EQUIP (Spain MCIN/AEI/10.13039/501100011033, grant
PCI2022-132922), funded by Agencia Estatal de Investigación, Ministerio de
Ciencia e Innovación, Gobierno de España and by the European Union
“NextGenerationEU/PRTR”. Bane Vasić acknowledges the support of the NSF under
grants CIF-1855879, CCF-2100013, CIF-2106189, CCSS-2027844, CCSS-2052751,
CIF-2106189, and ERC-1941583 (CoQREATE), as well as the support of NASA
through the SURP Program. Bane Vasić has disclosed an outside interest in
Codelucida to the University of Arizona. Conflicts of interest resulting from
this interest are being managed by The University of Arizona in accordance
with its policies.

Sana Javed∗, Francisco Garcia-Herrero†, Bane Vasić ‡ and Mark F. Flanagan∗
∗ School of Electrical and Electronic Engineering, University College Dublin,
Belfield, Dublin 4, Ireland,
† Department of Computer Architecture and Automatics, Complutense University
of Madrid, Madrid, Spain
‡ Department of Electrical and Computer Engineering, The University of
Arizona, Tucson, AZ, 85721 USA
Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper proposes two approaches for reducing the impact of the error floor
phenomenon when decoding quantum low-density parity-check codes with belief
propagation based algorithms. First, a low-complexity syndrome-based linear
programming (SB-LP) decoding algorithm is proposed, and second, the proposed
SB-LP is applied as a post-processing step after syndrome-based min-sum (SB-
MS) decoding. For the latter case, a new early stopping criterion is
introduced to decide when to activate the SB-LP algorithm, avoiding executing
a predefined maximum number of iterations for the SB-MS decoder. Simulation
results show, for a sample hypergraph code, that the proposed decoder can
lower the error floor by two to three orders of magnitude compared to SB-MS
for the same total number of decoding iterations.

###### Keywords:

Quantum error correction, quantum LDPC codes, linear programming based
decoding.

##  I INTRODUCTION

Quantum algorithms that involve a large number of qubits (between thousands
and millions) play a pivotal role in advancing quantum computing, unlocking
the ability to tackle intricate problems that are beyond the reach of
classical computers [1]. However, noise in quantum systems, generated by
factors such as decoherence, crosstalk, and environmental interference,
represents a significant hurdle [2], making it challenging to maintain the
integrity of quantum computation, especially when the number of qubits scales
[1]–[3].

To reduce the effects of noise, many new codes and decoders for quantum error
correction have been designed over the past few decades [2]. Some of the most
intensively studied codes are surface codes [4], initially suggested for noisy
intermediate-scale quantum (NISQ) devices. Unfortunately, these codes have
some limitations when the objective is to protect a large number of logical
qubits, as they have a low code rate and consequently an impractical overhead
in terms of physical qubits.

As an alternative with a higher code rate, quantum low-density parity-check
(QLDPC) codes offer benefits by reducing the qubit overhead and also improving
the minimum distance [5], [6]. Despite their potential, there are still open
problems such as the fault-tolerant implementation of the encoding process on
the quantum side and the design of efficient decoders that can obtain very low
logical error rates [7]. This paper will focus on addressing the latter
limitation.

One of the main problems in performing efficient decoding for a QLDPC code is
the existence of short cycles within the code’s Tanner graph, which result in
an error floor when belief propagation (BP) based decoders are applied. This
error floor effect means that an improvement in the physical error rate of the
qubits does not translate into an improvement in the logical error rate [8].
To mitigate this problem, two main categories of approach have been followed:
the use of a new standalone decoder based on alternative approaches to
standard BP, and applying a post-processing technique after BP decoding.

For the first category of approach, some more powerful decoding techniques
such as the syndrome-based generalized belief propagation (GBP) algorithm [9]
have been proposed to improve the decoding performance. Unfortunately, these
require a high computational complexity, so additional simplifications are
necessary to obtain practical real-time solutions. Some neural network based
decoders for QLDPC codes have also been explored [10]. However, training and
deploying these algorithms for large QLDPC codes can be computationally
intensive and resource-demanding when the number of qubits grows.

For the second category, ordered statistics decoding (OSD) was proposed in
[11] as a post-processing technique for BP. By seamlessly integrating OSD when
BP decoding fails, this technique can significantly enhance the error
correction capability for some specific QLDPC codes, providing improved error
rates after post-processing. However, OSD decoders are computationally complex
and introduce an extremely large latency due to the requirement, in one of the
steps, of performing Gaussian elimination for the inversion of a dynamic
submatrix of the code’s parity-check matrix; thus, an efficient hardware
implementation that can finish decoding within the required time interval (of
hundreds of nanoseconds to several microseconds) is not feasible [12].

Stabilizer inactivation decoding for QLDPC codes was also recently introduced
in [13] as an alternative post-processing method; this was shown to outperform
OSD in lowering the error floor while also reducing the decoding complexity.
However, it is a list decoding method (the list being computed according to
the BP output), the complexity of which grows with the length of the list.
Serial processing of the list can lead to information loss due to the short
decoherence time, while parallel processing would require high power
consumption. This highlights the importance of continuing the search for
alternative decoding techniques.

Besides these previous algorithms, linear programming (LP) based decoding has
also been recently explored as a solution for quantum codes. As LP decoding
proved to be capable of reducing the error floor for classical LDPC codes
[14], some works such as [15] and [16] adapted classical LP decoding
algorithms to QLDPC codes, also providing theoretical performance guarantees.
Nevertheless, these decoders require the solution of linear programs and thus
these algorithms are not attractive from a complexity and latency perspective.

In this paper, a low-complexity iterative syndrome-based linear programming
(SB-LP) decoder is proposed for decoding QLDPC codes, which can be used as a
standalone decoding algorithm or as a post-processing step after syndrome-
based min-sum (SB-MS) decoding to improve the behavior in the error floor
region and the threshold of the code. Unlike the standalone SB-MS decoder,
which exhibits a high error floor for several QLDPC code classes, the proposed
combination of SB-MS with SB-LP improves the error floor with lower complexity
than OSD and without the need for list decoding as required by stabilizer
inactivation. We also propose a new early stopping criterion for the SB-MS
decoder based on the syndrome Hamming distance, using which the algorithm can
automatically detect misconvergence of the SB-MS decoder and use this to
trigger the SB-LP post-processing.

##  II Background

This section summarizes the depolarizing error model used in our work, and
provides a brief description of the SB-MS decoder which is a de facto standard
for low-complexity BP based decoding. In the following, all vectors are
assumed to be row vectors.

###  II-A Quantum Noise Model

Quantum gates, crosstalk, and other processes applied to qubits (including
maintaining them in an idle state) result in bit-flip errors, phase-flip
errors, or a combination of both. The behavior of errors in a quantum
processor can be described by using a depolarizing noise model [17]. Errors
resulting from bit-flips are described by Pauli X operators and have a
probability of occurrence denoted by $p_{\textrm{X}}$. Phase-flip errors are
described by Pauli Z operators and have a probability of occurrence
$p_{\textrm{Z}}$. Errors involving both bit-flips and phase-flips are
described by Pauli Y operators and occur with probability $p_{\textrm{Y}}$. We
consider an i.i.d. symmetric depolarizing error model for the qubits, such
that each qubit experiences an independent depolarizing error probability $p$
and $p_{\textrm{X}}=p_{\textrm{Y}}=p_{\textrm{Z}}=p/3$. Bit-flip and phase-
flip errors are represented by binary error vectors $\textbf{e}_{\textrm{X}}$
and $\textbf{e}_{\textrm{Z}}$, respectively, in which the $j$-th entry is
equal to $1$ in the presence of a corresponding error on the $j$-th qubit, and
is equal to $0$ if there is no such error. An $[[n,k]]$ QLDPC code, where $k$
logical qubits are encoded using $n$ physical qubits, can be characterized by
two $m\times n$ binary parity-check matrices $\textbf{H}_{\textrm{X}}$ and
$\textbf{H}_{\textrm{Z}}$; the corresponding length-$m$ binary syndrome
vectors
$\textbf{s}_{\textrm{X}}={\textbf{e}_{\textrm{X}}}{{\textbf{H}_{\textrm{Z}}}^{T}}$
and
$\textbf{s}_{\textrm{Z}}={\textbf{e}_{\textrm{Z}}}{{\textbf{H}_{\textrm{X}}}^{T}}$
are measured from the quantum system and can be used to correct X and Z
errors, respectively [5]. For ease of exposition, in the rest of this paper we
will focus on correction of only one type of error, and we will use the
simpler notations H, e and s in place of $\textbf{H}_{\textrm{Z}}$,
$\textbf{e}_{\textrm{X}}$ and $\textbf{s}_{\textrm{X}}$, respectively. Also,
we will assume the syndrome measurement to be error-free.

###  II-B Tanner Graph

The Tanner graph serves as a graphical representation of the $m\times n$
parity-check matrix $\textbf{H}=(\textrm{H}_{ij})$. This graph consists of $n$
variable nodes (VNs) and $m$ check nodes (CNs), connected by a set of edges
$\mathcal{E}$. For each $i\in\\{1,2,\ldots,m\\}$ and $j\in\\{1,2,\ldots,n\\}$,
the $i$-th CN is connected to the $j$-th VN by an edge (i.e.,
$(i,j)\in\mathcal{E}$) if and only if ${\textrm{H}_{ij}}=1$. $\mathcal{N}_{i}$
denotes the set of neighbors of the ${i}$-th CN, while $\mathcal{N}_{j}$
denotes the set of neighbors of the $j$-th VN. For ease of exposition, we
assume that the Tanner graph is regular, i.e., all CNs have the same degree
$d_{c}$ and all VNs have the same degree $d_{v}$. In the QLDPC decoding
context, VNs correspond to entries of the estimated error pattern
${\textbf{e}}=(e_{1}\;e_{2}\;\cdots\;e_{n})$ while CNs correspond to the
entries of the syndrome vector $\textbf{s}=(s_{1}\;s_{2}\;\cdots\;s_{m})$.

###  II-C Syndrome-Based Min-Sum (SB-MS) Algorithm

The SB-MS algorithm is a low-complexity approximation to BP which replaces the
complex CN operation with a simpler minimum operation [18]. Its operation is
given in Algorithm 1.

The SB-MS decoder seeks to find an error pattern $\hat{\textbf{e}}$ that
matches the measured syndrome s. It does this by iteratively exchanging
messages between the VNs and CNs (lines 4 to 7), making hard decisions to
produce an estimate of the error vector $\hat{\textbf{e}}$ (line 8), and
generating the corresponding syndrome $\hat{\textbf{s}}$ (line 9). The
algorithm terminates when either this syndrome matches the measured syndrome
or the maximum number of iterations $I^{\textrm{(MS)}}_{\textrm{max}}$ is
reached.

Here $u_{i,j}$ represents the message from the $i$-th CN to the $j$-th VN, and
$v_{i,j}$ denotes the message sent from the $j$-th VN to the $i$-th CN. The
hard decision operation is defined as

$\mathrm{HD}(x)=\left\\{\begin{array}[]{ll}0&\text{if }x>0,\\\
1&\text{otherwise.}\end{array}\right.$

and we also define the function

$\mathrm{sgn}(x)=1-2\mathrm{HD}(x)=\left\\{\begin{array}[]{ll}1&\text{if
}x>0,\\\ -1&\text{otherwise.}\end{array}\right.$

${\lambda_{j}}=\log\left(\frac{P(e_{j}=0)}{P(e_{j}=1)}\right)$ represents the
a priori log-likelihood ratio (LLR) of $e_{j}$, while $\alpha$ is a scaling
factor that accelerates the convergence of the algorithm.

1: Input: syndrome s

2: Initialize parameters:

$\lambda_{j}$ = $\ln\left(\frac{1-(2p/3)}{2p/3}\right)$, $\forall
j\in\\{1,2,\ldots,n\\}$

$u_{i,j}=0,\forall(i,j)\in\mathcal{E}$

$I=0$, $\hat{\textbf{s}}=\mathbf{0}$

3: while $\textbf{s}\neq\hat{\textbf{s}}$ and $I$ $\leq$
$I^{\textrm{(MS)}}_{\textrm{max}}$ do

4: for all $(i,j)\in\mathcal{E}$ (in parallel) do
$v_{i,j}=\lambda_{j}+\alpha\sum_{i^{\prime}\in\mathcal{N}_{j}\backslash\\{i\\}}u_{i^{\prime},j}$

5: end for

6: for all $(i,j)\in\mathcal{E}$ (in parallel) do
$u_{i,j}=\mathrm{sgn}(s_{i})\cdot\\!\\!\prod_{j^{\prime}\in\mathcal{N}_{i}\backslash\\{j\\}}\mathrm{sgn}(v_{i,j^{\prime}})\cdot\\!\min_{j^{\prime}\in\mathcal{N}_{i}\backslash\\{j\\}}\left|v_{i,j^{\prime}}\right|$

7: end for

8:
$\hat{e}_{j}=\mathrm{HD}(\lambda_{j}+\alpha\sum_{i\in\mathcal{N}_{j}}u_{i,j}),\forall
j\in\\{1,2,\ldots,n\\}$

9: $\hat{\textbf{s}}=\hat{\textbf{e}}\textbf{H}^{T}$

10: $I=I+1$

11: end while

12: return $\hat{\textbf{e}}$

Algorithm 1 Syndrome-Based Min-Sum (SB-MS) Algorithm

In the case of certain QLDPC codes, the SB-MS decoder is unable to improve the
error rate of the qubits even as the depolarizing error probability improves;
this results in an error floor. The presence of this error floor can be
attributed to the presence of short cycles within the code’s Tanner graph
which the SB-MS decoding algorithm struggles to handle. These cycles lead to
oscillations between different candidate error vectors during the decoding
process so that the SB-MS decoder cannot converge to a unique error pattern
that matches the syndrome. In the next section, we propose an approach to
reduce or eliminate this error floor phenomenon.

##  III Proposed Method

Linear programming based decoding, originally proposed for classical LDPC
codes in [14], relies on a linear programming relaxation approach to achieve a
high-performance decoding solution with theoretical guarantees on performance.
In [19], Vontobel and Koetter proposed low-complexity iterative decoding
algorithms that exploited the unique structure of the linear program to be
solved (in particular, exploiting the sparsity of H). In the following, we
propose an LP-based decoder which is based on modifying Algorithm 1 in [19] to
align with the unique features and requirements of QLDPC codes.

###  III-A Proposed Syndrome-based Linear Programming (SB-LP) Decoder

The details of the proposed SB-LP decoder are given in Algorithm 2. This
algorithm iteratively updates the estimated error vector $\hat{\textbf{e}}$,
guided by the measured syndrome s, until convergence is achieved or the
maximum number of iterations $I^{\textrm{(LP)}}_{\textrm{max}}$ has been
reached. Unlike the SB-MS decoder, the SB-LP decoder does not perform VN-to-CN
and CN-to-VN updates alternately; instead, it simultaneously updates a single
value $\overline{u}_{i,j}$ for each edge $(i,j)\in\mathcal{E}$ (line 9). This
parallel update approach can significantly improve the decoding speed. Also,
$\alpha_{1}$ serves as a scaling factor designed to expedite the algorithm’s
convergence.

1: Input: syndrome s

2: Initialize parameters:

$\lambda_{j}$ = $\ln\left(\frac{1-(2p/3)}{2p/3}\right)$, $\forall
j\in\\{1,2,\ldots,n\\}$

$\overline{u}_{i,j}=0,\forall(i,j)\in\mathcal{E}$

$I=0$, $\hat{\textbf{s}}=\mathbf{0}$

3: while $\textbf{s}\neq\hat{\textbf{s}}$ and $I$ $\leq$
$I^{\textrm{(LP)}}_{\textrm{max}}$ do

4: for all $(i,j)\in\mathcal{E}$ (in parallel) do

5:
$S_{i,j}=\lambda_{j}+\sum_{i^{\prime}\in\mathcal{N}_{j}\backslash\\{i\\}}\overline{u}_{i^{\prime},j}$

6: if $s_{i}=0$ then
$T^{(0)}_{i,j}=\max_{\textbf{b}\in\mathcal{B}_{i},b_{j}=0}\overline{\textbf{u}}_{i,j}\tilde{\textbf{b}}_{j}^{T}$
$T^{(1)}_{i,j}=\max_{\textbf{b}\in\mathcal{B}_{i},b_{j}=1}\overline{\textbf{u}}_{i,j}\tilde{\textbf{b}}_{j}^{T}$

7: else
$T^{(0)}_{i,j}=\max_{\textbf{c}\in\mathcal{C}_{i},c_{j}=0}\overline{\textbf{u}}_{i,j}\tilde{\textbf{c}}_{j}^{T}$
$T^{(1)}_{i,j}=\max_{\textbf{c}\in\mathcal{C}_{i},c_{j}=1}\overline{\textbf{u}}_{i,j}\tilde{\textbf{c}}_{j}^{T}$

8: end if

9:
$\overline{u}_{i,j}=\frac{\alpha_{1}}{2}(T^{(0)}_{i,j}-T^{(1)}_{i,j}-S_{i,j})$

10: end for

11:
$\hat{e}_{j}=\mathrm{HD}(\lambda_{j}+\sum_{i^{\prime}\in\mathcal{N}_{j}}\overline{u}_{i^{\prime},j}),\forall
j\in\\{1,2,\ldots,n\\}$

12: $\hat{\textbf{s}}=\hat{\textbf{e}}\textbf{H}^{T}$

13: $I=I+1$

14: end while

15: return $\hat{\textbf{e}}$

Algorithm 2 Proposed Syndrome-Based Linear Programming (SB-LP) Algorithm

In lines 6 and 7, $\mathcal{B}_{i}$ denotes the single parity-check code of
length $d_{c}$ consisting of all $2^{|d_{c}|-1}$ binary sequences having even
parity, while $\mathcal{C}_{i}=\\{0,1\\}^{|d_{c}|}\backslash\mathcal{B}_{i}$
represents the set of all $2^{|d_{c}|-1}$ binary sequences having odd parity
(note that these vectors are indexed by the set $\mathcal{N}_{i}$). Also,
$\tilde{\textbf{b}}_{j}$ and $\tilde{\textbf{c}}_{j}$ correspond to the
vectors b and c with the $j$-th element removed, respectively. Also, we define
the check-perspective edge value vector
$\overline{\textbf{u}}_{i,j}=(\overline{u}_{i,j^{\prime}})_{j^{\prime}\in\mathcal{N}_{i}\backslash\\{j\\}}$.

With respect to Algorithm 1 in [19], which was proposed for decoding classical
LDPC codes, we have introduced some modifications that enable the algorithm to
decode QLDPC codes. First, we have modified the expressions for
${T^{(0)}_{i,j}}$ and ${T^{(1)}_{i,j}}$ in lines 6 and 7, as they depend on
the $i$-th syndrome bit $s_{i}$; in classical coding, we always have
$s_{i}=0$, while in QLDPC coding we may have $s_{i}=1$ which necessitates
performing the corresponding minimization over the complement
$\mathcal{C}_{i}$ of the single parity check code $\mathcal{B}_{i}$. Second,
we have replaced the “soft minimum” operator in [19] with the minimum operator
in order to reduce the complexity (this was found to give negligible loss in
performance). Finally, we have replaced the successive edge value update rule
in [19] by a fully parallel update rule, and we have made some other minor
simplifications including removing the (unnecessary) dual variables of the LP.

###  III-B SB-LP as Post-Processing after SB-MS Decoding

We can further improve the error floor behavior while reducing the overall
decoding complexity by combining the SB-MS and SB-LP decoders. Algorithm 3
describes our proposed methodology for this. First, we note that the SB-MS
decoder exhibits an oscillatory behavior when it becomes stuck in a trapping
set of the QLDPC code [8]. In such cases, the decoder is not able to identify
an error pattern that matches the measured syndrome, and hence the number of
unmatched syndrome elements begins to oscillate as it seeks to converge to
more than one error vector within the trapping set. If this behavior can be
identified automatically by the decoding algorithm (through an appropriately
designed early stopping criterion, as described in Subsection III-C), the SB-
LP decoder can then be invoked to complete the decoding successfully (as the
SB-MS decoder alone will usually not be capable of converging to a solution in
such cases).

Moreover, to facilitate faster convergence of the iterative SB-LP decoder, we
take advantage of the calculations provided by the SB-MS decoder in the first
stage. Specifically, we use the a posteriori LLR values obtained after the SB-
MS decoder satisfies the proposed stopping criterion (these are computed in
line 8 of Algorithm 3 by adding the CN-to-VN and VN-to-CN messages) as initial
values for the edge variables $\bar{u}_{i,j}$ of the SB-LP decoder. This
provides an improved initialization of the post-processing decoder.

The SB-MS decoder, which has a faster convergence than SB-LP in general,
allows the decoding process to reach a good starting point, reducing
considerably the number of errors; if it encounters issues during this process
(as detected by the early stopping criterion), the SB-LP decoder is then
invoked to remove the small set of residual errors, which are linked to
trapping sets.

Figure 1: Evolution of the number of unmatched syndrome elements with
successive decoding iterations for a sample error vector. Plots are shown for
the SB-MS (blue) and SB-LP (red) decoders for the $[[882,24]]$ QLDPC code B1
from [11].

1: Input: syndrome s

2: Initialize parameters:

$\lambda_{j}$ = $\ln\left(\frac{1-(2p/3)}{2p/3}\right)$, $\forall
j\in\\{1,2,\ldots,n\\}$

$u_{i,j}=0,\forall(i,j)\in\mathcal{E}$

$I=0$, $\hat{\textbf{s}}=\mathbf{0}$

3: do

4: $\hat{\textbf{s}}_{\textrm{pre}}=\hat{\textbf{s}}$

5: Execute lines (4-11) of Algorithm 1

6: $I=I+1$

7: while ${d_{\textrm{H}}}(\hat{\textbf{s}}_{\textrm{pre}},\hat{\textbf{s}})$
$>$ $d_{v}$ and $I$ $\leq$ $I^{\textrm{(MS)}}_{\textrm{max}}$

8: $\overline{u}_{i,j}=u_{i,j}+v_{i,j},\forall(i,j)\in\mathcal{E}$

9: $I=0$

10: Execute lines (3-15) of Algorithm 2

Algorithm 3 Combined SB-MS + SB-LP Decoding Algorithm

###  III-C Early Stopping Criterion for the SB-MS Decoder

As explained in the previous subsection, an appropriately designed early
stopping criterion can reduce the number of decoding iterations by exiting the
SB-MS decoder when it becomes trapped and at the same time provide an improved
initialization to the SB-LP decoder. Fig. 1 shows an example of the evolution
of the number of unmatched syndrome elements during SB-MS decoding in the case
where the decoder becomes stuck in a trapping set. An oscillatory pattern is
observed, indicating that the SB-MS decoder is unable to converge to an error
pattern that matches the measured syndrome. In contrast, the proposed SB-LP
decoder can converge in such cases; however, a high number of iterations is
required.

From Fig. 1 we can conclude that operating the SB-MS decoder for a fixed
number of iterations is not an efficient approach; instead, the SB-MS decoding
procedure should terminate when such oscillatory behavior is detected. In
Algorithm 3, we terminate the SB-MS decoding when the Hamming distance
${d_{\textrm{H}}}(\hat{\textbf{s}},\hat{\textbf{s}}_{\textrm{pre}})$ between
the current syndrome estimate $\hat{\textbf{s}}$ and the previous syndrome
estimate $\hat{\textbf{s}}_{\textrm{pre}}$ is less than or equal to the VN
degree $d_{v}$; this approach was found to be more robust that attempting to
locate the first local minimum of the number of unmatched syndrome elements.
By providing the SB-LP decoder with an improved initialization, this early
stopping criterion leads to fewer required decoding iterations while also
improving the logical error rate.

It is worth mentioning that this early stopping criterion can be applied when
using SB-MS in conjunction with any other post-processing technique, such as
OSD or stabilizer inactivation, to activate the post-processing exactly when
required and reduce the total number of decoding iterations.

##  IV Simulation Results and Discussion

Figure 2: Performance of the SB-MS decoder, the SB-LP decoder, and the
combined SB-MS and SB-LP decoder with and without early stopping criterion,
for the $[[882,24]]$ QLDPC code B1 from [11].

In this section, we compare the simulated performance of the proposed SB-LP
decoder with that of SB-MS, and we also evaluate the performance of the
combined SB-MS and SB-LP decoders. Simulations are performed for the
$[[882,24]]$ QLDPC code designated as code B1 in [11] (similar results were
found for the $[[1922,50]]$ QLDPC code C2 in [11]; these are omitted due to
space limitations). The correction of bit-flip (Pauli X) errors is considered
under the i.i.d. symmetric depolarizing noise model.

Fig. 2 shows the performance curves for the different decoders, with a maximum
number of iterations
$I^{\textrm{(MS)}}_{\textrm{max}}=I^{\textrm{(LP)}}_{\textrm{max}}=100$ for
the SB-MS and SB-LP algorithms respectively; the corresponding scaling factors
are $\alpha=0.75$ and $\alpha_{1}=0.9$. For the case where the SB-MS and SB-LP
decoders are combined (Algorithm 3), the first decoder has
$I^{\textrm{(MS)}}_{\textrm{max}}=25$ iterations while the second decoder is
configured with $I^{\textrm{(LP)}}_{\textrm{max}}=75$. For each point in the
figure, $10,000$ logical errors were simulated in order to ensure that the
results are statistically significant.

The results reveal that the SB-MS decoder introduces an error floor at a
logical error of $10^{-2}$, and is significantly outperformed by the proposed
SB-LP decoder. While the SB-LP decoder exhibits a worse threshold behavior, it
improves the logical error rate for any depolarizing error probability lower
than $0.07$, providing almost two orders of magnitude of improvement in the
logical error rate at a depolarizing error probability of $0.04$.

The figure also shows the performance of the combination of the SB-MS and SB-
LP algorithms, both with and without the early stopping criterion for SB-MS.
Both solutions achieve a good logical error rate for high depolarizing error
probabilities (greater than $0.06$), but without the application of the early
stopping criterion an error floor is introduced due to the poorer quality of
the information passed by the SB-MS decoder to the SB-LP decoder.

Figure 3: Convergence behavior of the combined SB-MS and SB-LP decoder, with
and without early stopping criterion, for the same sample error vector as in
Fig.1.

Figure 4: Average number of iterations for the SB-MS decoder, the SB-LP
decoder, and the combined SB-MS and SB-LP decoder with and without early
stopping criterion, for the $[[882,24]]$ QLDPC code B1 from [11].

Fig. 3 illustrates the effect of the early stopping criterion on the result
achieved by the SB-MS algorithm. In the case where the early stopping
criterion is not employed (dashed line), the SB-MS algorithm will stop when it
reaches the maximum number of iterations, while in the case of early stopping
(solid line) it can be observed that the SB-MS algorithm will stop near the
first local minimum of the number of unmatched syndrome elements.

Note that, even if the SB-MS decoder is halted after a fixed number of
iterations ($25$ in this example), convergence of the subsequent SB-LP
algorithm can still be achieved. However, this comes at the cost of a high
overall number of iterations ($36$ in this example); in particular, a high
number of SB-LP decoder iterations is required because the initialization
provided by the SB-MS algorithm is far from optimal. These additional
iterations can be sufficient to prevent the decoder’s convergence in some
cases, introducing the undesirable error floor in Fig. 2. On the other hand,
for the same error pattern, employing the early stopping criterion in SB-MS
avoids the subsequent oscillations, reducing the number of iterations and
providing the SB-LP decoder with a better initialization. For this example,
only $7$ SB-MS iterations are required to meet the stopping criterion,
followed by $4$ further iterations of the proposed SB-LP decoder.

Fig. 4 shows the average total number of iterations as a function of the
depolarizing error probability $p$. It can be observed that the average number
of iterations of the proposed combined SB-MS and SB-LP with early stopping
criterion is always lower than that obtained with SB-MS or SB-LP alone. From
the figure, two important conclusions can be drawn. The first is that for high
values of depolarizing error probability, the combined SB-MS and SB-LP with
early stopping criterion requires a significantly lower number of iterations
for convergence than that of the SB-MS or SB-LP decoder alone (note that at
these values of $p$, this combined decoder also provides the best logical
error rate, as shown in Fig. 2). The second is that for low values of the
depolarizing error probability, while there is not a substantial difference in
the total number of iterations of the different decoders, the logical error
rate of the combined decoder with early stopping criterion sees a significant
improvement as shown in Fig. 2; while approximately $10$ iterations are
required for all three decoders, the combined decoder provides more than three
orders of magnitude improvement in the logical error rate at $p=0.04$.

##  V Conclusion

We have proposed a novel low-complexity syndrome-based decoder for QLDPC codes
based on linear programming, which can be used either as a standalone decoder
or as a post-processing decoding step for SB-MS decoding. We also proposed an
early stopping criterion for the SB-MS decoder based on the syndrome Hamming
distance that judiciously triggers the transition between the two decoding
algorithms. The proposed approach was shown to be capable of providing a
significant improvement in the logical error rate performance as well as
reducing the total number of decoding iterations.

## References

  * [1] 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_ , vol. 574, no. 7779, pp. 505–510, 2019.
  * [2] A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,” _Phys. Rev. A_ , vol. 54, pp. 1098–1105, Aug 1996.
  * [3] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. Sloane, “Quantum error correction and orthogonal geometry,” _Physical Review Letters_ , vol. 78, no. 3, p. 405, 1997.
  * [4] J. R. Wootton and D. Loss, “High Threshold Error Correction for the Surface Code,” _Physical Review Letters_ , vol. 109, no. 16, oct 2012.
  * [5] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo, “Fifteen years of quantum LDPC coding and improved decoding strategies,” _iEEE Access_ , vol. 3, pp. 2492–2519, 2015.
  * [6] P. Panteleev and G. Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes,” in _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , ser. STOC 2022, 2022, p. 375–388.
  * [7] N. P. Breuckmann and J. N. Eberhardt, “Quantum low-density parity-check codes,” _PRX Quantum_ , vol. 2, no. 4, p. 040101, 2021.
  * [8] N. Raveendran and B. Vasić , “Trapping Sets of Quantum LDPC Codes,” _Quantum_ , vol. 5, p. 562, oct 2021.
  * [9] N. Raveendran, M. Bahrami, and B. Vasic, “Syndrome-generalized belief propagation decoding for quantum memories,” in _ICC 2019-2019 IEEE International Conference on Communications (ICC)_. IEEE, 2019, pp. 1–6.
  * [10] Y.-H. Liu and D. Poulin, “Neural belief-propagation decoders for quantum error-correcting codes,” _Physical review letters_ , vol. 122, no. 20, p. 200501, 2019.
  * [11] P. Panteleev and G. Kalachev, “Degenerate quantum LDPC codes with good finite length performance,” _Quantum_ , vol. 5, p. 585, nov 2021.
  * [12] J. Valls, F. Garcia-Herrero, N. Raveendran, and B. Vasić, “Syndrome-based Min-sum vs OSD-0 decoders: FPGA Implementation and Analysis for Quantum LDPC codes,” _IEEE Access_ , vol. 9, pp. 138 734–138 743, 2021.
  * [13] J. Du Crest, M. Mhalla, and V. Savin, “Stabilizer inactivation for message-passing decoding of quantum LDPC codes,” in _2022 IEEE Information Theory Workshop (ITW)_. IEEE, 2022, pp. 488–493.
  * [14] J. Feldman, M. J. Wainwright, and D. R. Karger, “Using linear programming to decode binary linear codes,” _IEEE Transactions on Information Theory_ , vol. 51, no. 3, pp. 954–972, 2005.
  * [15] J. X. Li and P. O. Vontobel, “LP decoding of quantum stabilizer codes,” in _2018 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2018, pp. 1306–1310.
  * [16] O. Fawzi, L. Grouès, and A. Leverrier, “Linear programming decoder for hypergraph product quantum codes,” in _2020 IEEE Information Theory Workshop (ITW)_. IEEE, 2021, pp. 1–5.
  * [17] M. A. Nielsen and I. L. Chuang, _Quantum computation and quantum information_. Cambridge university press, 2010.
  * [18] M. P. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low-density parity check codes based on belief propagation,” _IEEE Transactions on communications_ , vol. 47, no. 5, pp. 673–680, 1999.
  * [19] P. O. Vontobel and R. Koetter, “Towards Low-Complexity Linear-Programming Decoding,” in _4th International Symposium on Turbo Codes & Related Topics; 6th International ITG-Conference on Source and Channel Coding_, 2006, pp. 1–9.