# A real-time, scalable, fast and highly resource efficient decoder for a
quantum computer

Ben Barber  Riverlane, Cambridge, UK.  Kenton M. Barnes  Riverlane, Cambridge,
UK.  Tomasz Bialas  Riverlane, Cambridge, UK.  Okan Buğdaycı  Riverlane,
Cambridge, UK.  Earl T. Campbell  Riverlane, Cambridge, UK.  Department of
Physics and Astronomy, University of Sheffield, UK  Neil I. Gillespie
Riverlane, Cambridge, UK.  Kauser Johar  Riverlane, Cambridge, UK.  Ram Rajan
Riverlane, Cambridge, UK.  Adam W. Richardson  Riverlane, Cambridge, UK.  Luka
Skoric  Riverlane, Cambridge, UK.  Canberk Topal  Riverlane, Cambridge, UK.
Mark L. Turner  Riverlane, Cambridge, UK.  Abbas B. Ziad  Riverlane,
Cambridge, UK.

(September 2023)

###### Abstract

Quantum computers promise to solve computing problems that are currently
intractable using traditional approaches. This can only be achieved if the
noise inevitably present in quantum computers can be efficiently managed at
scale. A key component in this process is a classical decoder, which diagnoses
the errors occurring in the system. If the decoder does not operate fast
enough, an exponential slowdown in the logical clock rate of the quantum
computer occurs. Additionally, the decoder must be resource efficient to
enable scaling to larger systems and potentially operate in cryogenic
environments. Here we introduce the Collision Clustering decoder, which
overcomes both challenges. We implement our decoder on both an FPGA and ASIC,
the latter ultimately being necessary for any cost-effective scalable
solution. We simulate a logical memory experiment on large instances of the
leading quantum error correction scheme, the surface code, assuming a circuit-
level noise model. The FPGA decoding frequency is above a megahertz, a
stringent requirement on decoders needed for e.g. superconducting quantum
computers. To decode an 881 qubit surface code it uses only $4.5\%$ of the
available logical computation elements. The ASIC decoding frequency is also
above a megahertz on a 1057 qubit surface code, and occupies 0.06 mm2 area and
consumes 8 mW of power. Our decoder is optimised to be both highly performant
and resource efficient, while its implementation on hardware constitutes a
viable path to practically realising fault-tolerant quantum computers.

##  I Introduction

Quantum computers have the potential to solve computational problems that are
out of reach of classical computers. However, to realise this potential all
architectures need to deal with the fragility of their quantum bits (qubits)
[1, 2, 3, 4]. Qubits are highly likely to interact with the environment, or
decohere, which leads to a loss of information stored and errors in the
corresponding computation. Fortunately, Quantum Error Correction (QEC)
protocols enable fault-tolerant computation in the presence of this noise. By
adding redundancy, information can be protected by encoding it into logical
qubits. Errors can still corrupt the information in this setting, and so a
signal is periodically generated from the logical data, which characterises
the errors that have occurred. This signal, called a syndrome, is processed by
a decoder running on classical hardware whose output is the best guess of the
error that has occurred on the logical data. This information is passed back
to the control system so that corrective steps can be taken in subsequent
operations.

Figure 1:  Quantum Error Correction using a rotated planar surface code. (a)
The logical information is encoded by combining multiple physical qubits laid
out on a surface (orange and teal grid). The physical qubits can be divided
into data qubits ($D_{i}$, empty circles) encoding the state, and syndrome
qubits ($S$, full circles). Repeated measurements of syndrome qubits provides
information about errors. Possible error mechanisms can be represented by a
graph in which nodes represent differences between syndrome measurements in
consecutive rounds (potential defects) and edges represent error mechanisms
that create the corresponding pair of defects (see Section II.3 for more
details). Error mechanisms that trigger only one defect (teal nodes) are in
addition connected to a fictitious boundary node (not drawn). Z and X parity
check patches (teal and orange squares) protect against X and Z errors
respectively and result in two equivalent and disjoint graphs – only the Z
check graph is shown here. (b) Quantum circuits to measure the Z (top) and X
(bottom) parity checks. The circuit is continuously repeated until the
computation ends and all qubits are measured out. (c) Two rounds of syndrome
measurements displaying only a part of the circuit that involves a single data
and two syndrome qubits (top). The possible error mechanisms are depicted with
different colours: data (red), measurement (blue), and hook (purple) errors
and result in corresponding edges in the decoding graph (bottom). (d)
Comparison of defect rate for phenomenological and circuit-level noise models
with the same noise rate on distance 23 rotated planar surface code. While the
decoding of circuit-level noise is made more complicated by the presence of
hook edges, it also results in approximately 3.5 times more defects due to
more possible error locations.

QEC must be performed continuously creating a stream of syndrome data, and
therefore, as systems scale and lower logical error rates are required, the
amount of data that needs to be processed by a decoder increases
significantly. For large computations, this will require real-time decoders
that can process the data at the rate it is received to avoid the creation of
a backlog that grows exponentially with the depth of the computation [5, 6],
ultimately slowing it down to a halt. Superconducting quantum devices, for
example, generate a round of syndrome data in less than $1\mu$s (a rate of
MHz), setting a stringent requirement on decoder speed. Future utility-scale
quantum computers will therefore require an optimised hardware decoder
integrated in a tight loop at the heart of the control system.

There are several fast and accurate decoders implemented in software languages
such as Python and C++ [7, 8, 9]. Most experiments to date have used software
decoders to decode offline [2, 10, 11, 12]: rather than decoding in real-time,
the syndrome data is processed after the experiment has concluded. However,
real-time decoding is essential for logic branching required to implement non-
Clifford gates to realise the full potential of quantum computation [13]. Even
if software decoders were run during experiments, the non-deterministic
latency of software would make it difficult to tightly integrate with the
control system of a quantum computer. Hardware decoders based on Field
Programmable Gate Arrays (FPGAs) or Application Specific Integrated Circuits
(ASICs) can execute within a deterministic number of clock cycles, and also
tightly integrate into control systems. Therefore, to meet the challenge of
developing real-time decoders, the community has begun to implement decoders
on dedicated hardware, specifically FPGAs [14, 15, 16, 17], and provide models
of ASIC implementations [18, 16].

FPGAs will be sufficient for decoding problems in the medium term. They
provide the flexibility to adapt and change implementations of decoders, and
can be easily integrated into control systems. This level of flexibility will
clarify the parameters that need to be optimised to improve the overall
performance of the system. Until recently, only small instances of surface
code decoders have been implemented on FPGAs [14, 17, 16]. Promising results
have appeared on larger examples, where decoding one round of syndrome data of
a $881$ qubit surface code in under 1 $\mu$s was demonstrated [15]. However,
only a toy noise model was used and the design required significant FPGA
resources.

FPGA systems have high per unit cost and power consumption and so are not
long-term solutions for scaling to millions of qubits. Once the architecture
design of a fault-tolerant quantum computer is understood, cost-effective
scaling can only be achieved with ASICs, which additionally provide improved
performance and power consumption at the cost of longer development times.
ASICs will also be needed if tight integration is required between decoders
and control systems in a cryogenic environment [19].

One of the central challenges facing the community is how to efficiently scale
Quantum Processing Units (QPUs) to larger numbers of qubits, particularly the
numbers required for fault-tolerant quantum computing. To meet this challenge,
it is crucial to make as many components of the QPU as efficient and simple as
possible, including the decoder. We introduce the Collision Clustering (CC)
decoder to satisfy these and the above requirements. It is a clustering
decoding algorithm designed to have low FPGA utilisation and low ASIC power
and area, while at the same time performant enough to keep up with the
syndrome generation time of the QPU. To demonstrate this, we implement the CC
decoder on a Xilinx Ultrascale+ XCVU3P FPGA and a modern 12 nm FinFET ASIC
process node 111ASIC implementation means the design has been signed-off using
industry-leading Electronic Design Automation (EDA) tooling, top-tier foundry
silicon-proven multi-Vt libraries, SRAM IP and spice models. This ensures high
quality results which include all the fabrication process variations of device
models and parasitic effects from the power network, clock-tree synthesis,
place and route stages.. Assuming a circuit-level noise model with error rate
$p=0.1\%$, on the FPGA we decode a 881 qubit surface code in 810 ns using only
$4.5\%$ of the available computational elements (Logic LUTs) and 10 KB of
memory. Moreover, we obtain a threshold of $0.78\%$. Our implementation on the
ASIC decodes 1057 qubit surface code in 240 ns, using only 0.06 mm2 of area
and 8 mW of power.

##  II Background

###  II.1 Surface codes

Surface codes are a family of codes that have been studied extensively since
their discovery over twenty years ago [21]. They can be implemented on 2D
architectures with fixed nearest neighbour interactions, e.g. superconducting
qubits, and there are known techniques to perform fault-tolerant computation
[22, 23, 24, 13]. Surface codes also have high thresholds that have proved
difficult to improve upon [25], meaning they have been implemented in several
near term error correction experiments [2, 10, 11]. Combined, these
observations make surface codes likely candidates for the error correction
schemes used in the first fault-tolerant devices. In this work, we focus
mainly on the rotated planar surface code (Fig. 1) [26].

The surface code is defined on a square lattice by operators that check the
parity of sets of qubits in either the Pauli $Z$ or $X$ basis (see Fig. 1).
These operators are measured repeatedly to generate the syndrome and project
the qubits into a logical computation space. We call a single round of
measuring all the parity check operators a round of syndrome measurements, and
the measurement data generated a round of syndrome data. For the rotated
planar code, a round of syndrome measurements requires $d^{2}-1$ syndrome
qubits for a $d\times d$ surface code, giving a total of $2d^{2}-1$ qubits.
The logical qubit is defined by logical Pauli operators forming a path between
opposite boundaries. The _distance_ of the surface code is the minimum number
of Pauli operators in such a logical operator, which is just the side length
$d$ of the lattice.

Quantum algorithms demonstrating industrially relevant advantage over
classical computation consistently require at least a trillion reliable
quantum operations [27, 28, 29, 30, 31, 32]. Therefore, any error correction
scheme needs to be able to generate logical error rates of $10^{-12}$ or
better. To achieve these error rates, we can use larger distance surface codes
which exponentially suppress errors. In addition to using more physical
qubits, this significantly increases the amount of information that needs to
be processed by the decoder. The time to generate a round of syndrome data
remains constant, so to avoid the backlog problem we need to solve a harder
problem in the same amount of time. It is therefore important to demonstrate
decoding performance on large distance surface codes.

###  II.2 Decoding the surface code

The core challenge in quantum error correction is to preserve a logical state,
known as logical memory [2]. For the surface code, this involves initialising
a logical state, performing several rounds of syndrome measurements, and
finishing with a logical Pauli measurement. We are concerned with the overall
effect of errors on the outcome of the logical measurement. Therefore, the
decoding problem is to determine whether the logical measurement has been
flipped given the observed syndrome and logical measurements.

The circuit used to measure the parity check operators (see Fig. 1b) has a
syndrome qubit that is reset and measured, single qubit gates, and two-qubit
gates that map errors onto the syndrome qubit. In addition to the noise on the
data qubits, each of these operations potentially introduces additional noise
mechanisms. This is why the parity check operators are measured repeatedly,
forming the syndrome. If no errors occur, these measurements produce the same
results in consecutive rounds. Therefore, an error is detected when there is a
change in the outcome of a measurement from one round to the next. We call
these changes in measurement outcomes _defects._

The syndrome is best represented in a decoding graph (Fig. 1a). The vertices
of the decoding graph correspond to all possible defects. If an error
mechanism triggers two defects, we connect the corresponding vertices by an
edge. Some error mechanisms only trigger a single defect e.g. errors on the
data qubits on the boundaries of the lattice. To capture these error
mechanisms, we connect the corresponding defects to virtual boundary vertices.
By taking the XOR of consecutive rounds of syndrome measurements, we can
identify the syndrome with the set of defects that have been triggered. The
decoding problem can now be rephrased as determining the most likely logical
measurement given the defects in the decoding graph.

###  II.3 Noise model

Noise models vary both in the level of errors they produce as well as the
types of error mechanism that can occur, which have a significant impact on
the decoder performance. Throughout this work, we sample syndromes using the
Clifford circuit simulator Stim [33] with several independent noise channels,
parameterized by a single probability $p$, that give a rough approximation of
noise channels characteristic of a generic superconducting device:

  * •

Depolarisation of both qubits after each 2-qubit gate with probability $p$.

  * •

Depolarisation of each idle qubit and after each single-qubit gate, including
measurement and reset operations, with probability $p/10$.

  * •

Randomly change the result of a measurement with probability $p$.

We use the parametrisation where depolarising a single qubit means applying a
random non-identity Pauli error:

$\mathcal{E}(\rho)=(1-p)\rho+\frac{p}{3}(X\rho X+Y\rho Y+Z\rho Z)$ (1)

Depolarising two qubits means applying one of the 15 non-identity two qubit
Pauli errors uniformly at random (so that each two qubit error occurs with
probability $p/15$).

Our circuit-level noise model generates a larger quantity and variety of
defects than the phenomenological noise model [34] which abstracts away the
details of generating the syndrome. On a distance $d=23$ rotated planar
surface code with $p=0.1\%$, our noise model produces defects at a rate of
$1.35\%$ (or about 3.6 defects per round), while the phenomenological noise
model [15] with the same probability $p$ produces defects at a rate of
$0.38\%$ (or about 1 defect per round, see Fig. 1d).

##  III The Collision Clustering decoder

We introduce the Collision Clustering (CC) decoding algorithm to meet the
various challenges set out in Section I. CC is an example of a clustering
decoding algorithm. Given a decoding graph with a set of defects, CC takes the
set of defects and partitions it into distinct subsets, known as clusters,
which can be explained locally. Each cluster is then analysed to determine its
effect on the logical measurement. To do this, CC uses a reference logical
operator, which we take to be a logical Pauli operator running along one of
the boundaries of the lattice. We call the corresponding boundary in the
decoding graph the logical boundary. After clustering, the correction bit
returned by CC is the parity of the number of odd sized clusters that touch
the logical boundary.

Before we describe how CC generates its clusters, we turn to another
clustering decoding algorithm, Union-Find, first proposed by Delfosse et al.
[35]. In the Union-Find micro-architecture of Das et al. [18], a key component
is the data structure used to help keep track of the state of emerging
clusters, called the spanning tree memory (STM). Based on our simulations of
their design, we identified that the main performance bottleneck was reading
from and writing into the STM data structure. This suggests using a different
data structure to help keep track of the state of emerging clusters that does
not require a lot of memory could be beneficial in a clustering decoding
algorithm.

###  III.1 Cluster Growth Stack and Parent Table

In the CC decoder, each defect begins in its own cluster. The clusters then
_grow_ in the decoding graph, and, if two clusters overlap, they _merge_ to
form one cluster. A cluster continues to grow so long as it has an odd number
of defects within it, or until it touches one of the open boundaries of the
code. Once all clusters have stopped growing, this growth and merge stage of
the algorithm terminates.

We keep track of the growing clusters in the Cluster Growth Stack (CGS) data
structure. It contains an entry for each defect, and each entry contains three
pieces of information:

  1. 1.

A _vertex_id_ to represent which defect the entry is for.

  2. 2.

A _growth_radius_ to represent how far this defect has grown. The maximum
required distance a defect will have to grow depends on the structure of a
decoding graph.

  3. 3.

A _valid_bit_ , set to 1 if this defect should be grown in the next round of
growth, and set to 0 otherwise.

In the CGS the growth step is performed by updating the growth radius for the
valid entries of the stack. This is a single read and write operation per
defect.

To keep track of which cluster a vertex belongs to, we use the Parent Table.
It has an address in memory for each defect holding the address of the
corresponding parent defect. Upon initialisation, each defect is its own
parent. We call any such entry with this property a root. When two clusters
merge, we set the root of one cluster equal to the root of the other cluster.
The choice of which cluster to update is arbitrary.

To determine if two clusters merge, we take each pair of defects (one defect
from each cluster), calculate the distance between them in the decoding graph,
and check if the sum of their growths is greater than this distance. If it is,
the two clusters merge. For a CGS with $s$ entries, this leads to $s^{2}/2$ of
these collision detection comparisons.

The key to checking cluster mergers is efficient computation of the distance
between two defects along the edges of the graph. In a general graph, this can
be implemented using a lookup table of pre-computed distances. Here, we
further minimise the power and area requirements of the design by exploiting
the structure of the surface code to develop combinatorial functions that
compute the distances without the need to traverse the graph. The structure of
the decoding graphs is essentially encoded in these functions, and it leads to
fast collision detection operations. For a phenomenological noise model, this
function will consist of computing the Manhattan distance on a cubic lattice,
with modifications to account for boundaries. Further modifications are
required to account for extra space-time edges when using the circuit-level
noise model.

##  IV Collision Clustering micro-architecture

Figure 2: Collision clustering decoder. (a) Schematic of the CC decoder on an
example of a single round of a rotated planar surface code. First, in the Init
step, the data structures are initialised with every defect being its own
parent. In the main loop, the Grow step calculates the validity of the
clusters and increases the diameter of all valid clusters. The clusters are
checked for collisions in the Merge step and colliding pairs of clusters are
pushed to the Merge stack. The Union step pops the pairs from the Merge stack,
makes one cluster root the root of the other, and updates the parity, boundary
and logical registers of the root of the cluster. When all clusters are
invalidated, the final logical correction is calculated. (b) Micro-
architecture diagram of the CC decoder computation engine, with annotated data
flow. The input and output of the decoder is accessible through programmable
registers. The logical correction bit is recalculated on the fly during Grow.
The Merge processing element consists of Match and Union sub-units active in
parallel. (c) The floorplan of a distance $d=23$ ASIC implementing the CC
decoder. Annotated: _Parent Table_ , _Merge Stack_ and _Cluster Stack_ SRAM
cells; _CC control_ logic formed of Init, Grow, and Merge processing units
that are implemented as Finite State Machines (FSM). _Core sysreg_ logic
contains input syndrome registers, control registers and the Metric Generation
Unit. Other coloured regions contain clocking, IO and other miscellaneous
logic.

In this section we describe the micro-architecture of the CC decoder, shown in
Fig. 2b. It is composed of shared memories and registers, and three processing
units: Initialisation, Growth and Merge.

###  IV.1 Shared memories and registers

The processing units are supplemented by a set of internal memories and
registers keeping the intermediary computational state. The growth of the
clusters is tracked in the Cluster Growth Stack memory as described in Section
III. Recall also that the Parent Table keeps track of the clusters; each
defect is represented by an address in memory, and the data represents its
corresponding parent defect. Additionally, three registers keep track of
parameters for each growing cluster, the Boundary, Logical and Parity
registers. In each register, a defect is represented by an address. For the
Boundary and Logical registers, the bit is set if the corresponding cluster
touches the boundary, respectively logical boundary. In the parity register,
the bit is set if the parity of the cluster is odd.

###  IV.2 Processing units

The _Init_ unit is active on first initialisation of the decoder with a new
syndrome and configuration. It is responsible for processing the decoder
configuration, loading of the input syndrome data and loading the appropriate
data into the storage elements.

The _Grow_ unit is responsible for the growth stage of the algorithm, as
outlined in Section III. It updates the Cluster Growth Stack cluster entries
at every iteration, finding the root of a cluster, then writing the radius and
validity status. While processing a cluster, the Grow unit also checks for
collisions with either boundary, writing the colliding vertex and the virtual
boundary or virtual logical vertex to the Merge stack. Finally, the Grow unit
also simultaneously computes the logical correction bit resulting from the
growth stage. The correction is discarded and recomputed on the next growth
cycle if growth is required, or is kept and used as the correction output on
successful termination of the decode cycle.

The _Merge_ unit is composed of _Match_ and _Union_ sub-units, which operate
in parallel. At every iteration, the Match sub-unit performs collision
detection comparisons from CGS data. It then writes colliding defect pairs
onto the Merge stack. The Union sub-unit reads collided vertex entries from
the Merge stack, then searches the Parent Table for the two roots. It then
updates the Parent Table, Logical, Boundary and Parity registers with the
results of the clusters’ union.

The execution of the algorithm and the associated data structures are shown on
a simple example in Fig. 2a and the associated micro-architecture in Fig. 2b.

##  V Physical implementation

###  V.1 FPGA

Figure 3: Performance of our FPGA implementation of the CC decoder on the
rotated planar surface code. (a) Logical error probability for varying
physical error rate $p$ and a range of code distances demonstrating threshold
at around $p=7.8\times 10^{-3}$. Each point is acquired with $10^{5}$ samples.
(b) Decoding time per syndrome measurement round as a function of code
distance for different noise rates. Even at a high noise just below threshold
($p=0.5\%$) expected in near-term hardware, our decoder can decode large
($d=11$) codes at sub-1$\mu$s per round rate. (c) Decoding time per round at
$p=0.1\%$ together with a projection of logical error probability to large
distance regime. The decoder is just short of 1$\mu$s per round at distance
$d=23$ on the affordable Xilinx Ultrascale+ XCVU3P hardware while expected
logical error probability is of the order of $10^{-12}$. Each accuracy point
was obtained using $10^{8}$ samples. (d) FPGA memory size usage of different
data structures for varying code distances using $p=0.1\%$. Even at distance
$d=23$ the decoder uses below 13 KB of memory, allowing for implementation on
affordable FPGA hardware.

In Table 1 we present the performance of our FPGA implementation of decoding
the rotated planar surface code across a range of distances from $3$ to $23$
using the CC decoder. The specific FPGA used is the Xilinx Ultrascale+ XCVU3P
[36]. We see that the FPGA decoder can decode below the $1\mu$s threshold up
to distance $21$. The maximum clock frequency (FMax) targeted for this
implementation is 400 MHz. It can be seen that due to the low resource
utilisation, FMax is not significantly impacted by increasing the distance of
the code.

The precise resource requirements of the FPGA, including the percentage of
resource utilised, are also given in Table 1. The only resources required to
implement CC are trivial logic gates along with storage elements. Notably, no
Digital Signal Processing (DSP) elements are used, whose use would increase
the area of the implementation. While results are only provided up to distance
$23$, based on the utilisation percentages, fitting larger distance instances
of the decoder onto the FPGA will be straightforward.

As explained in Section III, one of the main advantages of the CC decoder is
the efficient use of storage resources. Fig. 3d shows, for each code distance,
the storage required for each of the main data structures. The micro-
architecture has other storage elements e.g. Boundary, Logical and Parity
registers. These are typically implemented as flip-flops and the overall
results are given in Table 1. For a distance $23$ implementation, the main
data structure storage requirement is around 13 KB which is a third of a
level-1 data cache size in a typical application CPU. Similar to these caches
on CPUs, the CC memories can be accessed at very high frequencies in a single
clock cycle, enabling performant data processing.

Some of the other known FPGA based hardware decoders [14, 15] require
substantial resources at larger code distances. The data structures are also
sized based on a phenomenological noise model at $p=10^{-3}$, so they have
significantly under-counted resources compared to the requirements for a
circuit-level noise model of the same magnitude.

Code Distance | FPGA Performance | FPGA Utilisation
---|---|---
Fmax [MHz] |  Exec-time [µs] | Logic LUTs | LUTRAMs | FlipFlops | RAMB36 | RAMB18
3 | 449 | 0.07 | 2491 (0.63%) | 12 (0.01%) | 1572 (0.20%) | 0 (0.00%) | 0 (0.00%)
5 | 445 | 0.06 | 2709 (0.69%) | 27 (0.01%) | 1670 (0.21%) | 0 (0.00%) | 0 (0.00%)
7 | 406 | 0.06 | 3092 (0.78%) | 49 (0.02%) | 1984 (0.25%) | 0 (0.00%) | 0 (0.00%)
9 | 408 | 0.07 | 3800 (0.96%) | 100 (0.05%) | 2483 (0.32%) | 0 (0.00%) | 0 (0.00%)
11 | 412 | 0.11 | 4600 (1.17%) | 68 (0.03%) | 3591 (0.40%) | 0 (0.00%) | 1 (0.07%)
13 | 411 | 0.16 | 5914 (1.50%) | 105 (0.05%) | 4136 (0.52%) | 0 (0.00%) | 1 (0.07%)
15 | 403 | 0.25 | 7793 (1.96%) | 60 (0.03%) | 5432 (0.69%) | 1 (0.14%) | 1 (0.07%)
17 | 408 | 0.37 | 10446 (2.66%) | 90 (0.05%) | 7184 (0.91%) | 1 (0.14%) | 1 (0.07%)
19 | 402 | 0.55 | 13331 (3.38%) | 0 (0.00%) | 9277 (1.18%) | 2 (0.28%) | 2 (0.14%)
21 | 405 | 0.81 | 17237 (4.37%) | 0 (0.00%) | 11957 (1.52%) | 2 (0.28%) | 2 (0.14%)
23 | 401 | 1.18 | 21693 (5.50%) | 0 (0.00%) | 15126 (1.92%) | 5 (0.69%) | 1 (0.07%)
Table 1: FPGA results for decoding the rotated planar surface code. (a) Code
distance: the size of the error correcting code. (b) Fmax: the maximum
achieved clock frequency on the targeted FPGA. (c) Exec-time: the execution
time averaged over 100,000 shots, normalised by dividing by the $d$ rounds of
syndrome generation. (d) Logic LUTs: the number of FPGA lookup tables used for
logic primitives. (e) LUTRAMs, FF, RAMB36 and RAMB18: different types of
storage elements. The mapping of CC data structures to a storage element
depend on the size of the structure. The numbers in round bracket are the
percentage of the corresponding type of resource used on the FPGA.

As well as being performant and resource efficient, our implementation needs
to be accurate, that is, effectively suppress physical errors. We demonstrate
that our FPGA CC implementation is indeed accurate using a threshold plot [25]
given in Fig. 3a. Our implementation has a threshold of $0.78\%$, which means
that for values of $p$ less than this errors are suppressed exponentially by
increasing the code distance.

###  V.2 ASIC

In Table 2 we present two physical implementations of the CC decoder on a 12
nm FinFET process node: decoding a distance $7$ and a distance $23$ surface
code. They respectively take $10$ ns and $240$ ns to decode one round of
syndrome measurements, using only $2.75$ mW and $7.85$ mW of power. In the
near term, we believe that the distance $7$ instance will be valuable in
testing error correction experiments with cryogenic CMOS based control
systems.

Code Distance | ASIC Performance | ASIC Area | ASIC Power
---|---|---|---
Fmax [MHz] |  Exec-time [µs] |  Die-size [mm2] | FlipFlops |  Dynamic [mW] |  Leakage [mW]
7 | 2000 | 0.01 | 0.009 | 3957 | 2.73 | 0.02
23 | 2000 | 0.24 | 0.064 | 15840 | 7.72 | 0.13
Table 2: CC ASIC results for decoding the rotated planar surface code using a
12 nm FinFET process assuming p=0.1%. We use industry-leading EDA tools to
determine the frequency of the implementation. To calculate the execution
time, we use this frequency along with the cycle counts of the FPGA
implementations.

A floorplan defines the approximate locations, sizes and shapes of various
logical blocks of the design. The floorplan helps to determine how signals
will interact between different blocks, which enables optimization for
performance, power and area. The floorplan for a distance $23$ implementation
is shown in Fig. 2c. We have integrated SRAM macros as storage elements for
the Cluster Stack, Merge Stack and the Parent Table. For all other storage
elements, flip-flops are used from the Multi-Vt standard cell libraries. This
enables a good balance between optimizing for performance, power and area.

##  VI Discussion

###  VI.1 Related work

To the best of our knowledge, there have been four demonstrations of decoders
implemented on dedicated classical hardware [14, 15, 16, 17]. Lookup table
decoders are implemented on FPGAs in [14] and [17]. In both cases, the error
correction scheme demonstrated is relatively simple; the distance $3$
repetition code [17], and the distance $5$ surface code [14]. The
exponentially scaling memory requirements make lookup table decoders
impractical for surface code distances above $5$.

In [16], the authors implement a neural network decoder on an FPGA.
Measurement errors are not considered, limiting its effectiveness and
understanding of how the decoder will perform with experimental qubits.
Moreover, on an FPGA, they are restricted to a distance $5$ surface code.
Additionally, the corresponding estimated performance, power and area of the
ASIC synthesis all degrade significantly when increasing the distance from $3$
to $5$, implying that the design will not effectively scale.

The most significant prior implementation of a surface code decoder on
classical hardware is found in [15]. The authors demonstrate a highly
distributed implementation Union-Find on an FPGA, assuming a phenomenological
noise model. Each vertex of the decoding graph is assigned a processing unit,
and communication across the design is limited e.g. typically only nearest
neighbour processing units can communicate with each other. They report that a
round of syndrome measurements for a distance $21$ surface code can be decoded
in $11.5$ ns on an FPGA. Given that circuit-level noise results in more
defects (Fig. 1d), this performance would be slower if the authors extended
their noise model to circuit-level noise. Furthermore, a consequence of this
highly distributed approach is that large numbers of lookup tables (LUTs) and
registers are required for the implementation (900k LUTs and 240k registers).
Registers are necessary in a distributed implementation so that data can be
accessed at the same time in a few number of cycles. However, a register can
be an order of magnitude bigger in size and power consumption compared to a
bit in memory. This is reasonable when only a few hundred registers are
needed, but if thousands or more are required, this difference becomes
significant. Hence, the numbers reported by the authors will lead to a large
area and power consumption, and will increase the cost of any chip developed.
This would prevent any such design from being integrated as part of decode
compute close to the cryo-substrate, for instance as part of a cryogenic
control system.

As mentioned above, Das et al. [18] propose a micro-architecture for the
Union-Find decoding algorithm, and model decoding a distance $11$ surface
code. In addition to only considering phenomenological noise, the authors
observe that their micro-architecture is dominated by memory. As memory sizes
increase with increasing surface code distance, latency will also increase due
to the time needed to read and write from and to the memory. No implementation
or cycle-accurate simulation of this decoder is provided limiting the
understanding of how the increased memory size affects performance. The
authors also assume a $4$ GHz frequency, which can be challenging to obtain.

Finally, there are also implementations of decoders in SFQ (Single Flux
Quantum) logic [37, 38]. In these implementations, only relatively small
surface code distances are considered and simple noise models are used.
Moreover, the lack of maturity of the technology compared to CMOS, in both
capabilities (see [18]) and the supporting ecosystem, means that implementing
decoders in SFQ logic which can operate at scale will be challenging.

###  VI.2 Application to other codes

In the future, different target applications will require different code
distances based on the length of the computation to be performed. For this
reason, decoding hardware that can only deal with a very specific code and
code distance has limited value in the real-world.

The Union-Find algorithm itself is very flexible. It works for the same family
of codes as minimum weight perfect matching, i.e. any code for which a
meaningful decoding graph can be derived. In the hardware proposal of Das et
al. [18], some flexibility of the Union-Find algorithm is lost, as the exact
structure of the decoding graph is implicitly represented by the layout of the
STM, and changing this would require all the accesses and address translation
for use of the STM to also change. In CC the decoding graph is encoded by the
distance calculation function, and this is the only part of the design that
has to change based on the code. While CC is more flexible than other proposed
hardware implementations of Union-Find, the current implementation is
optimised for the surface codes where efficient closed form distance functions
exist. For more general decoding graphs that do not have efficient closed-form
distance functions, the design would have to be adapted to include a lookup
table of distances.

##  VII Conclusion

In this work we introduced the Collision Clustering (CC) decoding algorithm
and described a micro-architecture for its implementation. Fault-tolerant
quantum computing requires a decoder to process error syndromes at speed in
order to prevent a decoding backlog that exponentially slows down the logical
clock rate. Moreover, any scalable quantum computer requires a decoder to be
resource efficient, which will also enable tight integration with control
systems in a cryogenic environment. Demonstrations of cryogenic CMOS based
control systems are showing promising results [39, 40, 41] and tightly
integrating a decoder will provide the most cost-effective system. Current
cryogenic systems however have a strict power budget, in the order of 1 W at
the 4 K temperature range [42]. We envisage that this will result in a power
budget of 10s of mW for a decoder, so that the predominant power budget is
reserved for qubit control and readout. To help meet these requirements, we
designed CC to be memory and power efficient. While CC has a quadratic
asymptotic scaling, we show this is remedied with parallelisation and
pipelining for the relevant code distances, demonstrating that CC is a
scalable, fast and highly resource efficient decoder.

To verify that the CC decoder satisfies the performance, power and area
requirements, we implemented it on both an FPGA and ASIC. We decode a logical
memory experiment using large distance surface code examples in under 1 $\mu$s
per syndrome measurement round assuming a $p=0.1\%$ circuit-level noise model.
On the FPGA we showed that CC can decode a distance 21 surface code in $810$
ns per syndrome measurement round, utilising only $4.5\%$ of a modest sized
FPGA (a Xilinx Ultrascale+ XCVU3P). Using a modern $12$ nm FinFET process
node, we showed that CC can decode a distance $23$ surface code in $210$ ns
per syndrome measurement round using only $0.06$ mm2 area and $8$ mW power.

The logical memory experiment simulated in this work preserves a state for a
finite time period. To preserve a logical state indefinitely, _sliding window
decoding_ [34] can be used. While continuous rounds of syndrome measurements
are being generated, the decoder processes only a contiguous set, or _window_
, of these rounds. Utilising the whole window, the decoder commits to a
correction for the longer lived defects in the window, storing it in software.
The window then slides up to include more recent rounds of measurements, the
process repeats, and the correction updated. Certain boundary effects make
this process more complex than the one simulated in this work. Therefore,
developing a fast and efficient sliding window implementation of CC will be an
important next step in the advancement of decoders for fault-tolerant
computation.

##  VIII Acknowledgements

We thank Steve Brierley and Jake Taylor for encouraging this research and
related discussions. We also thank Maria Maragkou for feedback on the
manuscript.

## References

  * Ballance  _et al._ [2016] C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol, and D. M. Lucas, Physical Review Letters 117, 060504 (2016).
  * Acharya  _et al._ [2023] R. Acharya, I. Aleiner, R. Allen, T. I. Andersen, M. Ansmann, F. Arute, K. Arya, A. Asfaw, J. Atalaya, R. Babbush, D. Bacon, J. C. Bardin, J. Basso, A. Bengtsson, S. Boixo, G. Bortoli, A. Bourassa, J. Bovaird, L. Brill, M. Broughton, B. B. Buckley, D. A. Buell, T. Burger, B. Burkett, N. Bushnell, Y. Chen, Z. Chen, B. Chiaro, J. Cogan, R. Collins, P. Conner, W. Courtney, A. L. Crook, B. Curtin, D. M. Debroy, A. Del Toro Barba, S. Demura, A. Dunsworth, D. Eppens, C. Erickson, L. Faoro, E. Farhi, R. Fatemi, L. Flores Burgos, E. Forati, A. G. Fowler, B. Foxen, W. Giang, C. Gidney, D. Gilboa, M. Giustina, A. Grajales Dau, J. A. Gross, S. Habegger, M. C. Hamilton, M. P. Harrigan, S. D. Harrington, O. Higgott, J. Hilton, M. Hoffmann, S. Hong, T. Huang, A. Huff, W. J. Huggins, L. B. Ioffe, S. V. Isakov, J. Iveland, E. Jeffrey, Z. Jiang, C. Jones, P. Juhas, D. Kafri, K. Kechedzhi, J. Kelly, T. Khattar, M. Khezri, M. Kieferová, S. Kim, A. Kitaev, P. V. Klimov, A. R. Klots, A. N. Korotkov, F. Kostritsa, J. M. Kreikebaum, D. Landhuis, P. Laptev, K.-M. Lau, L. Laws, J. Lee, K. Lee, B. J. Lester, A. Lill, W. Liu, A. Locharla, E. Lucero, F. D. Malone, J. Marshall, O. Martin, J. R. McClean, T. McCourt, M. McEwen, A. Megrant, B. Meurer Costa, X. Mi, K. C. Miao, M. Mohseni, S. Montazeri, A. Morvan, E. Mount, W. Mruczkiewicz, O. Naaman, M. Neeley, C. Neill, A. Nersisyan, H. Neven, M. Newman, J. H. Ng, A. Nguyen, M. Nguyen, M. Y. Niu, T. E. O’Brien, A. Opremcak, J. Platt, A. Petukhov, R. Potter, L. P. Pryadko, C. Quintana, P. Roushan, N. C. Rubin, N. Saei, D. Sank, K. Sankaragomathi, K. J. Satzinger, H. F. Schurkus, C. Schuster, M. J. Shearn, A. Shorter, V. Shvarts, J. Skruzny, V. Smelyanskiy, W. C. Smith, G. Sterling, D. Strain, M. Szalay, A. Torres, G. Vidal, B. Villalonga, C. Vollgraff Heidweiller, T. White, C. Xing, Z. J. Yao, P. Yeh, J. Yoo, G. Young, A. Zalcman, Y. Zhang, N. Zhu, and G. Q. AI, Nature 614, 676 (2023).
  * Huang  _et al._ [2019] W. Huang, C. H. Yang, K. W. Chan, T. Tanttu, B. Hensen, R. C. C. Leon, M. A. Fogarty, J. C. C. Hwang, F. E. Hudson, K. M. Itoh, A. Morello, A. Laucht, and A. S. Dzurak, Nature 569, 532 (2019), 1805.05027 .
  * Litinski and Nickerson [2022] D. Litinski and N. Nickerson, Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections (2022), arXiv:2211.15465 [quant-ph] .
  * Terhal [2015] B. M. Terhal, Rev. Mod. Phys. 87, 307 (2015).
  * Skoric  _et al._ [2022] L. Skoric, D. E. Browne, K. M. Barnes, N. I. Gillespie, and E. T. Campbell, Parallel window decoding enables scalable fault tolerant quantum computation (2022), arXiv:2209.08552 [quant-ph] .
  * Higgott and Gidney [2023] O. Higgott and C. Gidney, Sparse blossom: correcting a million errors per core second with minimum-weight matching (2023), arXiv:2303.15933 [quant-ph] .
  * Higgott  _et al._ [2023] O. Higgott, T. C. Bohdanowicz, A. Kubica, S. T. Flammia, and E. T. Campbell, Phys. Rev. X 13, 031007 (2023).
  * Wu and Zhong [2023] Y. Wu and L. Zhong, Fusion blossom: Fast MWPM decoders for QEC (2023), arXiv:2305.08307 [quant-ph] .
  * Ferreira Marques  _et al._ [2021] J. Ferreira Marques, B. Varbanov, M. Moreira, H. Ali, N. Muthusubramanian, C. Zachariadis, F. Battistel, M. Beekman, N. Haider, W. Vlothuizen, A. Bruno, B. Terhal, and L. DiCarlo, Nature Physics 18, 80 (2021).
  * Krinner  _et al._ [2022] S. Krinner, N. Lacroix, A. Remm, A. Di Paolo, E. Genois, C. Leroux, C. Hellings, S. Lazar, F. Swiadek, J. Herrmann, G. J. Norris, C. K. Andersen, M. Müller, A. Blais, C. Eichler, and A. Wallraff, Nature 605, 669 (2022).
  * Postler  _et al._ [2022] L. Postler, S. Heu$\beta$en, I. Pogorelov, M. Rispler, T. Feldker, M. Meth, C. D. Marciniak, R. Stricker, M. Ringbauer, R. Blatt, P. Schindler, M. Müller, and T. Monz, Nature 605, 675 (2022).
  * Litinski [2019] D. Litinski, Quantum 3, 128 (2019).
  * Das  _et al._ [2022a] P. Das, A. Locharla, and C. Jones, in  _Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_, ASPLOS ’22 (Association for Computing Machinery, 2022) p. 541–553.
  * Liyanage  _et al._ [2023] N. Liyanage, Y. Wu, A. Deters, and L. Zhong, Scalable quantum error correction for surface codes using FPGA (2023), arXiv:2301.08419 [quant-ph] .
  * Overwater  _et al._ [2022] R. J. Overwater, M. Babaie, and F. Sebastiano, IEEE Transactions on Quantum Engineering 3, 1 (2022).
  * Ristè  _et al._ [2020] D. Ristè, L. C. G. Govia, B. Donovan, S. D. Fallek, W. D. Kalfus, M. Brink, N. T. Bronn, and T. A. Ohki, npj Quantum Information 6, 71 (2020).
  * Das  _et al._ [2022b] P. Das, C. A. Pattison, S. Manne, D. M. Carmean, K. M. Svore, M. Qureshi, and N. Delfosse, in  _2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_ (2022) pp. 259–273.
  * Charbon  _et al._ [2016] E. Charbon, F. Sebastiano, A. Vladimirescu, H. Homulle, S. Visser, L. Song, and R. M. Incandela, in  _2016 IEEE International Electron Devices Meeting (IEDM)_ (2016) pp. 13.5.1–13.5.4.
  * Note [1] ASIC implementation means the design has been signed-off using industry-leading Electronic Design Automation (EDA) tooling, top-tier foundry silicon-proven multi-Vt libraries, SRAM IP and spice models. This ensures high quality results which include all the fabrication process variations of device models and parasitic effects from the power network, clock-tree synthesis, place and route stages.
  * Kitaev [2003] A. Y. Kitaev, Annals of physics 303, 2 (2003).
  * Chamberland and Campbell [2022] C. Chamberland and E. T. Campbell, PRX Quantum 3, 010331 (2022).
  * Fowler and Gidney [2018] A. G. Fowler and C. Gidney, Low overhead quantum computation using lattice surgery (2018), arXiv:1808.06709 [quant-ph] .
  * Horsman  _et al._ [2012] D. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, New Journal of Physics 14, 123011 (2012).
  * Fowler  _et al._ [2009] A. G. Fowler, A. M. Stephens, and P. Groszkowski, Phys. Rev. A 80, 052312 (2009).
  * Tomita and Svore [2014] Y. Tomita and K. M. Svore, Phys. Rev. A 90, 062320 (2014).
  * Gidney and Ekerå [2021] C. Gidney and M. Ekerå, Quantum 5, 433 (2021).
  * Lee  _et al._ [2021] J. Lee, D. W. Berry, C. Gidney, W. J. Huggins, J. R. McClean, N. Wiebe, and R. Babbush, PRX Quantum 2, 030305 (2021).
  * Häner  _et al._ [2020] T. Häner, S. Jaques, M. Naehrig, M. Roetteler, and M. Soeken, in  _Post-Quantum Cryptography_ , edited by J. Ding and J.-P. Tillich (Springer International Publishing, Cham, 2020) pp. 425–444.
  * Gidney  _et al._ [2021] C. Gidney, M. Newman, A. Fowler, and M. Broughton, Quantum 5, 605 (2021).
  * Blunt  _et al._ [2022] N. S. Blunt, J. Camps, O. Crawford, R. Izsák, S. Leontica, A. Mirani, A. E. Moylett, S. A. Scivier, C. Sünderhauf, P. Schopf, J. M. Taylor, and N. Holzmann, Journal of Chemical Theory and Computation 18, 7001 (2022), pMID: 36355616.
  * Beverland  _et al._ [2022] M. E. Beverland, P. Murali, M. Troyer, K. M. Svore, T. Hoefler, V. Kliuchnikov, G. H. Low, M. Soeken, A. Sundaram, and A. Vaschillo, Assessing requirements to scale to practical quantum advantage (2022), arXiv:2211.07629 [quant-ph] .
  * Gidney [2021] C. Gidney, Quantum 5, 497 (2021).
  * Dennis  _et al._ [2002] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Journal of Mathematical Physics 43, 4452 (2002).
  * Delfosse and Nickerson [2021] N. Delfosse and N. H. Nickerson, Quantum 5, 595 (2021).
  * xil [2021] Xilinx ultrascale+ datasheet (2021), https://docs.xilinx.com/v/u/en-US/ds923-virtex-ultrascale-plus. Accessed: 06/09/2023.
  * Holmes  _et al._ [2020] A. Holmes, M. R. Jokar, G. Pasandi, Y. Ding, M. Pedram, and F. T. Chong, in  _Proceedings of the ACM/IEEE 47th Annual International Symposium on Computer Architecture_, ISCA ’20 (IEEE Press, 2020) pp. 556–569.
  * Ueno  _et al._ [2021] Y. Ueno, M. Kondo, M. Tanaka, Y. Suzuki, and Y. Tabuchi, in  _2021 58th ACM/IEEE Design Automation Conference (DAC)_ (IEEE, 2021) pp. 451–456.
  * Frank  _et al._ [2022] D. J. Frank, S. Chakraborty, K. Tien, P. Rosno, T. Fox, M. Yeck, J. A. Glick, R. Robertazzi, R. Richetta, J. F. Bulzacchelli, D. Ramirez, D. Yilma, A. Davies, R. V. Joshi, S. D. Chambers, S. Lekuch, K. Inoue, D. Underwood, D. Wisnieff, C. Baks, D. Bethune, J. Timmerwilke, B. R. Johnson, B. P. Gaucher, and D. J. Friedman, in  _2022 IEEE International Solid- State Circuits Conference (ISSCC)_, Vol. 65 (2022) pp. 360–362.
  * Bardin  _et al._ [2019] J. C. Bardin, E. Jeffrey, E. Lucero, T. Huang, S. Das, D. T. Sank, O. Naaman, A. E. Megrant, R. Barends, T. White, M. Giustina, K. J. Satzinger, K. Arya, P. Roushan, B. Chiaro, J. Kelly, Z. Chen, B. Burkett, Y. Chen, A. Dunsworth, A. Fowler, B. Foxen, C. Gidney, R. Graff, P. Klimov, J. Mutus, M. J. McEwen, M. Neeley, C. J. Neill, C. Quintana, A. Vainsencher, H. Neven, and J. Martinis, IEEE Journal of Solid-State Circuits 54, 3043 (2019).
  * Pauka  _et al._ [2021] S. J. Pauka, K. Das, R. Kalra, A. Moini, Y. Yang, M. Trainer, A. Bousquet, C. Cantaloube, N. Dick, G. C. Gardner, M. J. Manfra, and D. J. Reilly, Nature Electronics 4, 64 (2021).
  * Krinner  _et al._ [2019] S. Krinner, S. Storz, P. Kurpiers, P. Magnard, J. Heinsoo, R. Keller, J. Lütolf, C. Eichler, and A. Wallraff, EPJ Quantum Technology 6, 1 (2019).


# Privacy-Preserving Distributed Optimisation using Stochastic PDMM

###### Abstract

Privacy-preserving distributed processing has received considerable attention
recently. The main purpose of these algorithms is to solve certain signal
processing tasks over a network in a decentralised fashion without revealing
private/secret data to the outside world. Because of the iterative nature of
these distributed algorithms, computationally complex approaches such as
(homomorphic) encryption are undesired. Recently, an information theoretic
method called subspace perturbation has been introduced for synchronous update
schemes. The main idea is to exploit a certain structure in the update
equations for noise insertion such that the private data is protected without
compromising the algorithm’s accuracy. This structure, however, is absent in
asynchronous update schemes. In this paper we will investigate such
asynchronous schemes and derive a lower bound on the noise variance after
random initialisation of the algorithm. This bound shows that the privacy
level of asynchronous schemes is always better than or at least equal to that
of synchronous schemes. Computer simulations are conducted to consolidate our
theoretical results.

Index Terms—  Privacy, distributed optimisation, convex optimisation, PDMM,
asynchronous algorithms

##  1 Introduction

In recent years, the large increase in connected devices and the data that is
collected by these devices has caused a heightened interest in distributed
signal processing. As many practical distributed networks are of heterogeneous
nature, algorithms operating within these networks need to be simple, robust
against network dynamics, asynchronous and resource efficient. Popular
applications of distributed signal processing include telecommunication,
wireless sensor networks, cloud computing and machine learning [1, 2, 3]. Due
to the absence of a central processing point (fusion center),
participants/agents/nodes use their own processing ability to locally carry
out simple computations and transmit only the required and partially processed
data to neighbouring nodes. The transmission of the data could potentially
lead to information leakage. In certain applications like medical systems,
financial analysis, and smart grids [4], the data held by the
agents/participants is privacy sensitive and needs to be protected from being
revealed to the outside world.

One way to protect the data from being revealed is to apply some form of
encryption, like homomorphic encryption [5], to encrypt the private data such
that the adversary cannot decrypt the encrypted data within a certain period
of time. Such approaches e.g. [6, 7] are often computationally complex,
because the encryption functions require high computation overhead.
Alternatively, we could rely on techniques based on information-theoretical
principles where the adversary is assumed to have unbounded compute power but
does not have sufficient information for inferring the secret/private data. In
this paper we will focus on information-theoretic approaches because these
methods are usually computationally lightweight as they do not require heavy
encryption functions.

Existing information-theoretic approaches for privacy-preserving distributed
optimization can be classified into three classes. First, one can use
differential privacy [8] to ensure user privacy, see e.g. [9, 10, 11, 12]. It
guarantees privacy in the worst case that all nodes in the network except one
are not trustworthy. That is, a node’s privacy is ensured to be protected even
though all other nodes in the network can collaborate. While this gives strong
privacy guarantees, the downside is that it compromises accuracy. Second, for
certain distributed optimization problems one can use secret-sharing based
techniques [13], like the work proposed in [14, 15, 16]. Secret sharing works
by splitting the sensitive information into a number of shares, and the
privacy is guaranteed under the assumption that the sensitive information
cannot be reconstructed unless a sufficient number of nodes cooperate
together, which is assumed to be infeasible. The main advantage is that it
achieves privacy at no accuracy cost. However, it is shown to be only
applicable to certain types of problems, and for each problem it requires a
tailored adoption. In addition, it often requires the underlying graph to be
fully-connected, which limits the scalability of the network in practice. The
third privacy-preserving method is the subspace perturbation method [17, 18,
19], which provides a lightweight yet general solution to ensure privacy by
inserting noise in a subspace that is not affected during the iterations. The
noise insertion will obfuscate the private data, but does not affect the
optimization result. Moreover, the method is generally applicable to a variety
of distributed optimization problems.

Although subspace perturbation seems to be a promising method for preserving
the privacy, the results in [17, 18, 19] were derived for a synchronous update
setting. For asynchronous update schemes, however, there does not exist a
subspace that is not affected during the iterations. In this paper we will
investigate such asynchronous schemes and derive a lower bound on the noise
variance that can be used to obfuscate the private data when the probability
of a node being updated is uniform. The bound guarantees that the obtained
privacy level of asynchronous schemes will be higher than (at least equal to)
the original subspace perturbation approach proposed for synchronous schemes,
while the algorithm’s accuracy still remains uncompromised.

##  2 Notations and problem statement

Consider a graphical model $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}$ is the set of vertices representing the nodes/agents in a
network and $\mathcal{E}=\\{(i,j):i,j\in\mathcal{V}\\}$ is the set of
(undirected) edges in the graph representing the communication links in the
network. We use ${\cal E}_{\rm d}$ to denote the set of all directed edges
(ordered pairs). Therefore, $|\mathcal{E}_{\rm d}|=2|\mathcal{E}|$. Hence,
given a graph $G=(\mathcal{V},\mathcal{E})$, only neighbouring nodes are
allowed to communicate with each other directly. We use $\mathcal{N}_{i}$ to
denote the set of all neighbouring nodes of node $i$, i.e.,
$\mathcal{N}_{i}=\\{j:(i,j)\in\mathcal{E}\\}$ and $d_{i}=|{\cal N}_{i}|$
denotes the number of neighbouring nodes of node $i$.

Given a vector $x$, we use $\|x\|$ to denote its $\ell_{2}$-norm. When $x$ is
updated iteratively, we write $x^{(k)}$ to indicate the update of $x$ at the
$k$th iteration. When we consider $x^{(k)}$ as a realisation of a random
variable, the corresponding random variable will be denoted by $X^{(k)}$
(corresponding capital). Furthermore, we use the following notational
conventions: a variable $z_{i}$ is related to node $i$; a variable $z_{i|j}$
is related to edge $(i,j)$ but held by node $i$.

We would like to solve the following optimisation problem:

$\begin{array}[]{ll}\text{minimise}&{\displaystyle\sum_{i\in{\cal
V}}f_{i}(x_{i})}\\\ \rule[11.38109pt]{0.0pt}{0.0pt}\text{subject to}&{\rm
A}_{ij}x_{i}+{\rm A}_{ji}x_{j}={\rm b}_{ij},\quad(i,j)\in\cal E,\end{array}$
(1)

where $f_{i}:\mathbb{R}^{n_{i}}\mapsto\mathbb{R}\cup\\{\infty\\}$ are CCP
functions, ${\rm A}_{ij}\in\mathbb{R}^{m_{ij}\times n_{i}}$ and ${\rm
b}_{ij}\in\mathbb{R}^{m_{ij}}$. Let $n=\sum_{i}n_{i}$ and
$m=\sum_{(i,j)}m_{i,j}$. For simplicity, we will assume that
$n_{i}=n_{j}=m_{ij}$, ${\rm A}_{ij}=-{\rm A}_{ji}={\rm I}$ if $i>j$, and ${\rm
b}_{ij}=0$ for all $(i,j)\in{\cal E}$. This corresponds to simple (consensus)
edge constraints of the form $(\forall(i,j)\in{\cal E})\,\,x_{i}=x_{j}$. The
results, however, can straightforwardly be generalised to arbitrary dimensions
and arbitrary (linear) edge constraints.

The local objective functions $f_{i}$ are a function of the primal
optimisation variable $x_{i}$, but also of data related to node/agent $i$.
Examples of such cost functions are $f_{i}(x_{i})=\|x_{i}-{s}_{i}\|^{2}$ in
the case of average consensus, where ${s}_{i}$ is the local measurement data
that needs to be averaged among the nodes/agents, or $f_{i}(x_{i})=\|{\rm
A}_{i}x_{i}-{\rm b}_{i}\|^{2}$ in the case of linear regression, where the
pair ${s}_{i}=({\rm A}_{i},{\rm b}_{i})$ are the independent (explanatory) and
dependent (response) variables at node $i$. In certain applications like
medical systems, financial analysis, and smart grids, the data is privacy
sensitive and needs to be protected for being revealed to the outside world.
In this paper we will focus on solving (1) while protecting the secret/private
data $s_{i}$ from being revealed to the outside world.

##  3 Background

In this section, we formulate the mathematical background of privacy-
preserving distributed optimisation and introduce the primal-dual method of
multipliers (PDMM) updating equations that will be used in the proof in our
work. For more details regarding PDMM we refer to [20, 21].

###  3.1 PDMM

PDMM is an iterative algorithm that can solve the optimisation problem stated
in (1). An insightful derivation of the algorithm using monotone operator
theory is given in [21]. As derived in [21], PDMM can be formulated as a
monotone inclusion problem that can be iteratively solved using Peaceman-
Rachford splitting (see [22, Sec. 26.4]). This leads to the following PDMM
update equations:

$\displaystyle x^{(k+1)}$
$\displaystyle=\displaystyle\arg\min_{x}\left(f(x)+z^{(k)\raisebox{1.13809pt}{\scriptsize${\rm
T}$\\!}}{\rm C}x+\frac{c}{2}\|{\rm C}x\|^{2}\right),$ (2) $\displaystyle
z^{(k+1)}$ $\displaystyle={\rm P}z^{(k)}+2c{\rm P}{\rm C}x^{(k+1)},$ (3)

where $x\in\mathbb{R}^{n}$ is the primal variable, $z\in\mathbb{R}^{2m}$ an
auxiliary variables, and $c>0$ is a constant that controls the convergence
rate. The matrix ${\rm C}\in\mathbb{R}^{2m\times n}$ is a constraint matrix
constructed as ${\rm C}=(c_{1},c_{2},\ldots,c_{|\mathcal{V}|})$,
$c_{i}\in\mathbb{R}^{2m\times n_{i}}$, where $c_{i}(l)={\rm A}_{ij}$ if and
only if $e_{l}=(i,j)\in\cal E$ and $i<j$, and $c_{i}(l+m)={\rm A}_{ij}$ if and
only if $e_{l}=(i,j)\in\cal E$ and $i>j$. ${\rm P}\in\mathbb{R}^{2m\times 2m}$
is a symmetric permutation matrix exchanging the first $m$ with the last $m$
rows.

Due to the construction of the PDMM algorithm, the update equations are
separable across the nodes of the network and thus can be performed in a
distributed/parallel manner. At every iteration, each node $i$ updates its
local optimisation variable $x_{i}$, and computes, for every neighbouring node
$j\in\mathcal{N}_{i}$, an auxiliary variable $z_{j|i}$. In particular, (2)-(3)
can be computed as

$\displaystyle
x_{i}^{(k+1)}=\displaystyle\arg\min_{x_{i}}\left(\\!f_{i}(x_{i})+\\!\sum_{j\in{\cal
N}_{i}}\\!\\!z_{i|j}^{(k)\raisebox{1.42262pt}{\scriptsize${\rm T}$\\!\\!}}{\rm
A}_{ij}x_{i}+\frac{c}{2}d_{i}x_{i}^{(k+1)}\\!\right)\\!\\!,$ (4)
$\displaystyle(\forall j\in{\cal N}_{i})\quad
z_{j|i}^{(k+1)}=z_{i|j}^{(k)}+2c{\rm A}_{ij}x_{i}^{(k+1)}.$ (5)

PDMM converges for strongly convex and differentiable cost functions. This
holds for both synchronous [21] and asynchronous [23] update schemes. To
guarantee convergence for arbitrary closed, convex and proper (CCP) cost
functions, we can apply operator averaging, resulting in the $\theta$-averaged
auxiliary vector update

$z_{j|i}^{(k+1)}=(1-\theta)z_{j|i}^{(k)}+\theta\big{(}z_{i|j}^{(k)}+2c{\rm
A}_{ij}x_{i}^{(k+1)}\big{)},$ (6)

with $\theta\in(0,1)$.

###  3.2 Threat model and privacy metric

In this paper we will consider two widely-used adversary models: the
eavesdropping and the passive (or honest-but-curious) adversary model. The
passive adversary consists of a number of colluding nodes, referred to as
corrupt nodes, which will follow the algorithm instructions but will use
received information to infer the input data of the other, non-corrupt nodes.
We will refer to the latter as honest nodes. The eavesdropping adversary is
usually neglected in existing schemes since eavesdropping can be prevented by
using channel encryption [24]. However, channel encryption is computationally
expensive. For iterative algorithms where the communication channels are used
many times, channel encryption is less attractive. We thus assume that the
communication in the network is performed through non-secure channels, except
for the communication during the initialisation of the network, as will be
explained later.

Two commonly used metrics for measuring the privacy loss are
$\epsilon$-differential privacy and mutual information [25]. In this paper we
choose mutual information as the individual privacy metric. The reason for it
is twofold. Firstly, it has been proven effective in the context of privacy-
preserving distributed processing [26], and has been applied in various
applications [27]. Secondly, mutual information is closely related to
$\epsilon$-differential privacy (see [28] for more details), and is easier to
realise in practice [29]. Let $S_{i}$ be the secret/private continuous random
variable that relates to node $i$ having variance $\sigma_{S_{i}}^{2}$. Let
$Y_{i}=S_{i}+N_{i}$ be what the adversaries can observe related to $S_{i}$,
where $N_{i}$ is a random variable that is statistically independent of
$S_{i}$, acting as noise obfuscating $S_{i}$. Using $I(S_{i};Y_{i})$ to denote
the mutual information between $S_{i}$ and $N_{i}$, we can define
$\delta$-level privacy as $I(S_{i};Y_{i})\leq\delta$.

##  4 Privacy preservation

To analyse what information the adversaries can deduce, we can express the
primal update equation (4) as

$0\in\partial f_{i}(x_{i}^{(k+1)})+\sum_{j\in{\cal N}_{i}}{\rm
A}_{ij}z_{i|j}^{(k)}+cd_{i}x_{i}^{(k+1)}.$ (7)

The private data of the nodes is present in the objective function $f_{i}$, so
the only term in (7) that contains private data is $\partial
f_{i}(x_{i}^{(k+1)})$. Through knowledge of the PDMM algorithm, adversaries
can use the inclusion stated above to deduce information about the term
$\partial f_{i}(x_{i}^{(k+1)})$. The data that is known to the adversaries
depends on the implementation of PDMM.

Since the adversary can eavesdrop all communication channels, by inspection of
(7), transmitting the auxiliary variables $z_{i|j}^{(k)}$ would reveal
$\partial f_{i}(x_{i}^{(k+1)})$, as $x_{i}^{(k+1)}$ can be determined from
(6). Encrypting $z_{i|j}^{(k)}$ at every iteration would solve the problem but
is computationally too demanding. To overcome this problem, only initial
values $z_{i|j}^{(0)}$ are securely transmitted and $\Delta
z_{i|j}^{(k+1)}=z_{i|j}^{(k+1)}-z_{i|j}^{(k)}$ are transmitted (without any
encryption) during subsequent iterations [19, 30]. As a consequence,
$z_{i|j}^{(k+1)}$ can only be determined whenever $z_{i|j}^{(0)}$ is known.
Let ${\cal N}_{i,h}$ denote the set of honest neighbours of node $i$ and
assume that ${\cal N}_{i,h}\neq\emptyset$. That is, we assume that each honest
node has at least one honest neighbour. After deducing the known terms from
(7), the adversaries can observe

$\partial f_{i}(x_{i}^{(k+1)})+\sum_{j\in{\cal N}_{i,h}}{\rm
A}_{ij}z_{i|j}^{(k)}.$ (8)

By inspection of (8), we conclude that we can obfuscate the secret/private
data $s_{i}$ by making the variance of $Z_{i|j}$ sufficiently large. This can
be achieved by initialising the auxiliary variables $Z_{i|j}^{(0)}$ with
sufficiently large variance, assuming this variance remains sufficiently large
during the iterations. In [17, 18, 19] it has been shown that for a
synchronous update scheme this is indeed the case. The reason for this is that
at every two synchronous PDMM updates the auxiliary variables are only
affected in the subspace $\Psi={\rm ran}({\rm C})+{\rm ran}({\rm P}{\rm C})$
and leave $\Psi^{\perp}={\rm ker}({\rm C}^{\rm T})\cap{\rm ker}(({\rm P}{\rm
C})^{\rm T})$, the orthogonal complement of $\Psi$, unchanged. As shown in
[21], $\Pi_{\Psi}z^{(k)}\to z^{*}$ for any $z^{(0)}$, where
$z^{(k)}_{\Psi}=\Pi_{\Psi}z^{(k)}$ denotes the orthogonal projection of
$z^{(k)}$ onto $\Psi$. Because of this the term $\Pi_{\Psi}z^{(k)}$ will
eventually always have the same value so that $Z^{(k)}_{\Psi}$ will have zero
variance, and cannot be used to obfuscate the private data. For the component
$z_{\Psi^{\perp}}^{(k)}$ in the orthogonal subspace $\Psi^{\perp}$, however,
it has been shown in [30] that

${\mathbb{E}}\left(Z_{\Psi^{\perp}}^{(k)}Z_{\Psi^{\perp}}^{(k)^{\rm
T}}\right)=\Pi_{\Psi^{\perp}}\\!\\!\left(\frac{\sigma^{2}}{2}\left(({\rm
I}+{\rm P})+|1-2\theta|^{2k}({\rm I}-{\rm P})\right)\\!\right).$

This expression indicates that the variance of $Z_{\Psi^{\perp}}^{(k)}$ has a
nonzero asymptotic component that depends on the initialisation variance, and
can be made arbitrarily large to obtain $\delta$-level privacy.

For a stochastic update scheme, however, the $z$-updates are not restricted to
the subspace $\Psi$ anymore [23], and deriving a bound for the variance of the
auxiliary variable $z$ in this case is more involved than in the synchronous
case. In the next section we will derive a lower bound for the variance of
$Z_{\Psi^{\perp}}^{(k)}$ in a stochastic setting111Since in this framework we
transmit differential auxiliary variables $\Delta z_{i|j}$, we assume that
there are no transmission losses. With such losses the algorithm as presented
here will fail to converge..

##  5 Privacy preservation with stochastic PDMM

Following [23], stochastic updates can be defined by assuming that each
auxiliary variable $z_{i|j}$ can be updated based on a Bernoulli random
variable $U_{i|j}\in\\{0,1\\}$. Collecting all random variables $U_{i|j}$ in
the random vector $U\in\mathbb{R}^{2m}$, following the same ordering as the
entries of $z$, let $(U^{(k)})_{k\in\mathbb{N}}$ denote an i.i.d. random
process defined on a common probability space $(\Omega,{\cal A})$. Hence,
$U^{(k)}(\omega)\subseteq\\{0,1\\}^{2m}$ indicates which entries of $z^{(k)}$
will be updated at iteration $k$, where we assume that at every iteration,
entry $z_{i|j}^{(k)}$ has nonzero probability to be updated. With this, a
stochastic PDMM iteration can be expressed as

$Z^{(k+1)}=\left({\rm I}-\theta U^{(k+1)}\right)Z^{(k)}+\theta U^{(k+1)}({\rm
P}Z^{(k)}+2c{\rm P}{\rm C}X^{(k+1)}).$ (9)

We will utilise the following lemma and some properties of the conditional
expectation to derive a lower bound on the variance of
$Z_{\Psi^{\perp}}^{(k)}$ for stochastic PDMM.

######  Lemma 5.1.

Let $\Pi_{\Psi^{\perp}}$ denote the projection onto the subspace
$\Psi^{\perp}$ and ${\rm P}$ denote the PDMM permutation matrix. Then

  * a)

$\displaystyle\Pi_{\Psi^{\perp}}{\rm P}={\rm P}\Pi_{\Psi^{\perp}}$,

  * b)

$\displaystyle\Pi_{\Psi^{\perp}}\mathbb{E}(X)=\mathbb{E}\big{(}\Pi_{\Psi^{\perp}}X\big{)}$,

  * c)

$\displaystyle\Pi_{\Psi^{\perp}}\big{(}{\rm P}{\rm C}x^{(k+1)}\big{)}=0$.

###### Proof.

For a), see [30, Lemma 5.2]. Item b) follows from the linearity of the
expectation operator. Item c) follows from the fact that ${\rm P}{\rm
C}x^{(k+1)}\in\Psi$. ∎

To simplify the analysis, we make use of the observation that in expected
value stochastic PDMM with uniform updating probabilities, that is, $(\forall
i\in{\cal V})(\forall j\in{\cal N}_{i})\,\,{\rm
Pr}(\\{U_{i|j}^{(k)}=1\\})=\mu$, is equivalent to $\mu$-averaged PDMM. This
assumption holds, for example, in the case of asynchronous PDMM where one node
is selected uniformly at random and updated each iteration, so that
$\mu=1/|\cal V|$.

Let $({\cal A}_{k})_{k\geq 1}$ be a filtration on $(\Omega,{\cal A})$ such
that ${\cal A}_{k}:=\sigma\\{U^{(m)}\,:\,m\leq k\\}$, the $\sigma$-algebra
generated by the random variables $U^{(1)},\ldots,U^{(m)}$ and thus ${\cal
A}_{k}\subseteq{\cal A}_{l}$ for $k\leq l$. By taking the conditional
expectation of (9) with respect to ${\cal A}_{0}$, and using the fact that
$U^{(k+1)}$ is independent of $Z^{(k)}$ and $X^{(k+1)}$, we have that

$\displaystyle\mathbb{E}(Z^{(k+1)}|{\cal A}_{0})$ $\displaystyle=\left({\rm
I}-\theta\mathbb{E}(U^{(k+1)})\right)\mathbb{E}(Z^{(k)}|{\cal A}_{0})+$
$\displaystyle\theta\mathbb{E}(U^{(k+1)})\\!\left({\rm
P}\mathbb{E}(Z^{(k)}|{\cal A}_{0})+2c{\rm P}{\rm C}\mathbb{E}(X^{(k+1)}|{\cal
A}_{0})\right)$ $\displaystyle=(1-\theta\mu)\mathbb{E}(Z^{(k)}|{\cal A}_{0})+$
$\displaystyle\theta\mu\\!\left({\rm P}\mathbb{E}(Z^{(k)}|{\cal A}_{0})+2c{\rm
P}{\rm C}\mathbb{E}(X^{(k+1)}|{\cal A}_{0})\right),$

where for the last step we assume equal updating probabilities. As discussed
in Section 4, the part of $Z$ in the subspace $\Psi^{\perp}$ is relevant for
privacy preservation. Hence, we have by Lemma 5.1 that

$\displaystyle\mathbb{E}(Z_{\Psi^{\perp}}^{(k)}|{\cal A}_{0})$
$\displaystyle=\left((1-\theta\mu){\rm I}+\theta\mu{\rm
P}\right)\mathbb{E}(Z_{\Psi^{\perp}}^{(k-1)}|{\cal A}_{0})$
$\displaystyle=\left((1-\theta\mu){\rm I}+\theta\mu{\rm
P}\right)^{k}Z_{\Psi^{\perp}}^{(0)}$ $\displaystyle=\frac{1}{2}\left(({\rm
I}+{\rm P})+(1-2\theta\mu)^{k}({\rm I}-{\rm P})\right)Z_{\Psi^{\perp}}^{(0)},$
(10)

where the last equality is shown in [30] using the eigenvalue decomposition of
$(1-\theta\mu){\rm I}+\theta\mu{\rm P}$. Hence, we have

$\displaystyle\mathbb{E}\left(Z_{\Psi^{\perp}}^{(k)}Z_{\Psi^{\perp}}^{(k)^{\rm
T}}\right)_{(i|j),(i|j)}$
$\displaystyle=\mathbb{E}\left(\left(Z_{\Psi^{\perp}}^{(k)}\right)_{(i|j)}^{2}\right)$
$\displaystyle=\mathbb{E}\left(\mathbb{E}\left(\left(Z_{\Psi^{\perp}}^{(k)}\right)_{(i|j)}^{2}|{\cal
A}_{0}\right)\right)$
$\displaystyle\geq\mathbb{E}\left(\mathbb{E}\left(\left(Z_{\Psi^{\perp}}^{(k)}\right)_{(i|j)}|{\cal
A}_{0}\right)^{2}\right),$

where the last inequality follows from Jensen’s inequality. Hence, if the
auxiliary variable is randomly initialised in such a way that
$\mathbb{E}(Z^{(0)}Z^{(0)^{\rm T}})=\sigma^{2}{\rm I}$, we have that

$\displaystyle{\rm
diag}\\!\left(\mathbb{E}\left(Z_{\Psi^{\perp}}^{(k)}Z_{\Psi^{\perp}}^{(k)^{\rm
T}}\right)\right)$ $\displaystyle\geq{\rm
diag}\\!\left(\mathbb{E}\left(\mathbb{E}\left(Z_{\Psi^{\perp}}^{(k)}|{\cal
A}_{0}\right)\mathbb{E}\left(Z_{\Psi^{\perp}}^{(k)}|{\cal
A}_{0}\right)^{\\!{\rm T}}\right)\\!\right)$ $\displaystyle={\rm
diag}\\!\left(\Pi_{\Psi^{\perp}}\\!\\!\left(\frac{\sigma^{2}}{2}\left(({\rm
I}+{\rm P})+|1-2\theta\mu|^{2k}({\rm I}-{\rm P})\right)\\!\right)\\!\right),$

where the last equality follows from substitution of (10), Lemma 5.1, and the
fact that $\Pi_{\Psi^{\perp}}\Pi_{\Psi^{\perp}}^{\rm T}=\Pi_{\Psi^{\perp}}$.
This inequality provides a lower bound for the variance of the auxiliary
variable that is based on the initialisation variance $\sigma^{2}$. Note that
this bound is equal to the variance of the auxiliary variables for synchronous
$\theta\mu$-averaged PDMM. Since for most practical networks $\theta\mu\ll 1$,
the variance will be lower bounded by the variance of synchronous PDMM.

Fig. 1: Convergence of the variables $x^{(k)}$, $Z_{\Psi}^{(k)}$, and
$Z_{\Psi^{\perp}}^{(k)}$ using asynchronous PDMM for $\theta=1,0.8$, and
$0.5$.

##  6 Numerical results

To validate the variance bound derived in Section 5, we perform distributed
averaging simulations using asynchronous PDMM over a random geometric graph
with $n=10$ nodes having a communication radius $r=\sqrt{2\log n/n}$ so that
the graph is connected with probability at least $1-1/n^{2}$ [31]. The nodes
are being activated each iteration with uniform probability $\mu=1/|\cal V|$.
The values in the private measurement data $s$ were randomly generated from a
zero-mean unit-variance Gaussian distribution and the auxiliary data $Z^{(0)}$
was initialized with zero mean and $\sigma^{2}_{Z^{(0)}}=10^{8}$. To analyse
the variance of $Z^{(k)}$, we performed 100 Monte Carlo runs with different
initialisation $z^{(0)}$ where, for consistency, the sequence of selected
nodes was kept constant for each Monte Carlo run.

Figure 1 shows convergence results of both the primal variable $x$ and the
auxiliary variable $z$ as a function of the number of iterations for different
values of $\theta$. The primal variable $x^{(k)}$ converges to the correct
solution and has, as expected, a decreasing convergence rate for increasing
values of $\theta$. As for the auxiliary variable $z$, we can see that the
variance of $Z_{\Psi}^{(k)}$ goes to zero as $k\to\infty$, whereas the
variance of $Z_{\Psi^{\perp}}^{(k)}$ remains nonzero. Figure 2 shows the
evaluation of $Z_{\Psi^{\perp}}^{(k)}$ in more detail and shows a comparison
with the results obtained with synchronous PDMM [30]. The results show that in
both asynchronous and synchronous PDMM the variance of
$Z_{\Psi^{\perp}}^{(k)}$ is bounded below by a value depending on the variance
of the initialisation $Z_{\Psi^{\perp}}^{(0)}$, and that this variance is
higher in the case of an asynchronous update scheme.

Figure 3 shows the normalized mutual information based on (8) by assuming
there is one honest neighbor $j$ in the neighborhood of node $i$ for different
values of the variance of $Z^{(0)}$. The results show that the larger
$\sigma^{2}_{Z^{(0)}}$ is, the smaller the mutual information is between the
private data and the observations of the adversary. It also confirms the fact
that asynchronous update schemes reveal less information about the private
data during the iterations than synchronous schemes.

Fig. 2: Variance of $Z_{\Psi^{\perp}}^{(k)}$ using synchronous and
asynchronous PDMM for $\theta=1,0.8$, and $0.5$.

Fig. 3: Information loss in asynchronous and synchronous PDMM for
$\sigma^{2}_{Z^{(0)}}=0.5$ and $\sigma^{2}_{Z^{(0)}}=1$.

##  7 Conclusion

In this paper we investigated the privacy preservation of asynchronous
distributed optimisation schemes. We extended the results of subspace
perturbation, originally introduced for synchronous schemes, to stochastic
update schemes. We derived a lower bound on the noise variance that can be
used to obfuscate the private data when the probability of a node being
updated is uniform. The bound guarantees that the obtained privacy level of
asynchronous schemes will be higher than the original subspace perturbation
approach, while the algorithm’s accuracy still remains uncompromised. Computer
simulations confirmed our theoretical findings.

## References

  * [1] T. Richardson and R. Urbanke,  Modern Coding Theory,  Cambridge University Press, 2008.
  * [2] G. Zhang, R. Heusdens, and W. Bastiaan Kleijn,  “Large Scale LP Decoding with Low Complexity,”  IEEE Communications Letters, vol. 17, no. 11, pp. 2152–2155, 2013.
  * [3] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah,  “Randomized gossip algorithms,”  IEEE Trans. Information Theory, vol. 52, no. 6, pp. 2508–2530, 2006.
  * [4] G. Giaconi, D. Gündüz, H. V. Poor,  “Privacy-aware smart metering: Progress and challenges,”  IEEE Signal Process. Mag., vol. 35, no. 6, pp. 59-78, 2018.
  * [5] C. Gentry,  “Fully homomorphic encryption using ideal lattices,”  in STOC, pp.169–178, 2009.
  * [6] Kaihe Xu, Haichuan Ding, Linke Guo, and Yuguang Fang,  “A secure collaborative machine learning framework based on data locality,”  in 2015 IEEE Global Communications Conference (GLOBECOM). IEEE, 2015, pp. 1–5.
  * [7] C. Zhang, M. Ahmad, and Y. Wang,  “ADMM based privacy-preserving decentralized optimization,”  IEEE Trans. Inf. Forensics Security, vol. 14, no. 3, pp. 565–580, 2019.
  * [8] C. Dwork, F. McSherry, K. Nissim, A. Smith,  “Calibrating noise to sensitivity in private data analysis,”  in Proc. Theory of Cryptography Conf. , pp. 265-284, 2006.
  * [9] Z. Huang, S. Mitra, and N. Vaidya,  “Differentially private distributed optimization., pp. 1–10,”  in Proc. Int. Conf. Distrib. Comput. Netw, 2015.
  * [10] E. Nozari, P. Tallapragada, and J. Cortés,  “Differentially private distributed convex optimization via functional perturbation,”  IEEE Trans. Control Netw. Syst., vol. 5, no. 1, pp 395-408, 2018.
  * [11] X. Zhang, M. M. Khalili, and M. Liu,  “Improving the privacy and accuracy of ADMM-based distributed algorithms,”  Proc. Int. Conf. Mach. Lear. pp. 5796–5805, 2018.
  * [12] Y. Xiong, J. Xu, K. You, J. Liu and L. Wu,  “Privacy preserving distributed online optimization over unbalanced digraphs via subgradient rescaling,”  IEEE Trans. Control Netw. Syst., 2020.
  * [13] R. Cramer, I. B. Damgård, and J. B. Nielsen,  “Secure multiparty computation and secret sharing,”  2015\.
  * [14] N. Gupta, J. Katz, N. Chopra,  “Privacy in distributed average consensus,”  IFAC-PapersOnLine, vol. 50, no. 1, pp. 9515-9520, 2017.
  * [15] Q. Li, I. Cascudo, and M. G. Christensen,  “Privacy-preserving distributed average consensus based on additive secret sharing,”  in Proc. Eur. Signal Process. Conf., pp. 1-5, 2019.
  * [16] K. Tjell and R. Wisniewski,  “Privacy preservation in distributed optimization via dual decomposition and ADMM,”  in Proc. IEEE 58th Conf. Decis. Control., pp. 7203–7208, 2020.
  * [17] Q. Li, R. Heusdens and M. G. Christensen,  “Convex optimisation-based privacy-preserving distributed average consensus in wireless sensor networks,”  in Proc. Int. Conf. Acoust., Speech, Signal Process., pp. 5895-5899, 2020.
  * [18] Q. Li, R. Heusdens and M. G. Christensen,  “Convex optimization-based privacy-preserving distributed least squares via subspace perturbation,”  in Proc. Eur. Signal Process. Conf., pp. 2110-2114, 2021.
  * [19] Q. Li, R. Heusdens and M. G. Christensen,  “Privacy-preserving distributed optimization via subspace perturbation: A general framework,”  in IEEE Trans. Signal Process., vol. 68, pp. 5983 - 5996, 2020.
  * [20] G. Zhang and R. Heusdens,  “Distributed optimization using the primal-dual method of multipliers,”  IEEE Trans. on Signal and Information Processing over Networks, vol. 4, no. 1, pp. 173 – 187, 2018.
  * [21] T. W. Sherson, R. Heusdens, and W. B. Kleijn,  “Derivation and Analysis of the Primal-Dual Method of Multipliers Based on Monotone Operator Theory,”  IEEE Transactions on Signal and Information Processing over Networks, vol. 5, no. 2, pp. 334–347, June 2019.
  * [22] Heinz H. Bauschke and Patrick L. Combettes,  Convex Analysis and Monotone Operator Theory in Hilbert Spaces,  CMS Books in Mathematics. Springer International Publishing, Cham, 2017.
  * [23] S. O. Jordan, T. W. Sherson, and R. Heusdens,  “Convergence of stochastic pdmm,”  in Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2023, pp. 1–5.
  * [24] D. Dolev, C. Dwork, O. Waarts, M. Yung,  “Perfectly secure message transmission,”  J. Assoc. Comput. Mach., vol. 40, no. 1, pp. 17-47,, 1993.
  * [25] T. M. Cover and J. A. Thomas,  Elements of information theory,  John Wiley & Sons, 2012.
  * [26] Q. Li, J. S. Gundersen, R. Heusdens and M. G. Christensen,  “Privacy-preserving distributed processing: Metrics, bounds, and algorithms,”  in IEEE Trans. Inf. Forensics Security. vol. 16, pp. 2090–2103, 2021.
  * [27] Y. Bu, S. Zou, and V. V. Veeravalli,  “Tightening mutual information-based bounds on generalization error,”  IEEE J. Sel. Areas Info. Theory. vol. 1, no. 1, pp. 121–130, 2020.
  * [28] P. Cuff and L. Yu,  “Differential privacy as a mutual information constraint,”  in Proc. 23rd ACM SIGSAC Conf. Comput. Commun. Secur., pp 43–54, 2016.
  * [29] M. Gtz, A. Machanavajjhala, G. Wang, X. Xiao, J. Gehrke,  “Publishing search logs—a comparative study of privacy guarantees,”  IEEE Trans. Knowl. Data. Eng. vol. 24, pp. 520 - 532, 2011.
  * [30] Q. Li, R. Heusdens and M. G. Christensen,  “Communication efficient privacy-preserving distributed optimization using adaptive differential quantization,”  Signal Process., 2022.
  * [31] J. Dall and M. Christensen,  “Random geometric graphs,”  Physical review E, vol. 66, no. 1, pp. 016121, 2002.