††thanks: These two authors contributed equally††thanks: These two authors
contributed equally

# Heralded arbitrary graph states with inefficient quantum emitters

Maxwell Gold  Department of Physics, University of Illinois Urbana-Champaign,
Urbana, IL 61801  Jianlong Lin  Department of Electrical and Computer
Engineering, University of Illinois Urbana-Champaign, Urbana, IL 61801  Eric
Chitambar  Department of Electrical and Computer Engineering, University of
Illinois Urbana-Champaign, Urbana, IL 61801  Elizabeth A. Goldschmidt
Department of Physics, University of Illinois Urbana-Champaign, Urbana, IL
61801

###### Abstract

Quantum emitter-based schemes for the generation of photonic graph states
offer a promising, resource efficient methodology for realizing distributed
quantum computation and communication protocols on near-term hardware. We
present a heralded scheme for making photonic graph states that is compatible
with the typically poor photon collection from state-of-the-art coherent
quantum emitters. We demonstrate that the construction time for large graph
states can be polynomial in the photon collection efficiency, as compared to
the exponential scaling of current emitter-based schemes, which assume
deterministic photon collection. The additional overhead to achieve this
advantage consists of an extra spin system plus one additional spin-spin
entangling gate per photon added to the graph. While the proposed scheme
enables the generation of graph states for arbitrary applications, we show how
it can be further simplified for the specific task of measurement-based
computation, leading to significantly higher rates and removing the need for
photonic memory in certain computations. As an example use-case of our scheme,
we construct a protocol for secure two-party computation that can be
implemented efficiently on current hardware. Estimates of the fidelity to
produce graph states used in the computation are given, based on current
trapped ion experimental benchmarks.

##  I  Introduction

The vast promise of quantum information technologies for faster and more
secure computational and information systems relies on entanglement as a
primary resource. Traditional gate-based quantum computing requires the
ability to perform sequences of joint operations across multiple qubits. An
alternative paradigm, known as measurement-based quantum computation (MBQC),
realizes universal computation through sequences of single qubit measurements
made on an initially prepared entangled resource state [1]. This is an
appealing approach for photonic quantum systems as single photon rotations and
measurements are straightforward using commercial optical elements, and fast
efficient routing solutions are readily available [2]. Furthermore, the
sequential nature of photon emission allows entangled states to be built from
photons emitted at different times by the same emitter [3]. By using entangled
emitters, it then becomes possible to simulate entangling gates between
photons and overcome the difficulty of realizing direct photon-photon
interactions [4]. Indeed, it is known that computationally useful graph states
of photons can be generated using either a small number of coherent quantum
emitters [5], a combination of a single emitter and fusion gates [6], or a
single quantum emitter in a feedback scheme [7].

All of these aforementioned schemes assume a photon is successfully added to
the graph every time an emitter is excited, and we thus term this class of
schemes as being “deterministic”. However, efficient collection from
individual quantum emitters is a challenge that remains largely out of reach
today, making deterministic schemes impractical for generating large graph
states on even near-term hardware [8].

We introduce a procedure for building arbitrary photonic graph states using a
single emitting spin and a fixed number of auxiliary spins, without any
requirement on the collection efficiency of the emitted photons. The rate and
size of feasible graph states generated by the proposed method has polynomial
dependence on the collection efficiency, compared to the exponential
suppression of the feasible graph size for the successive detection of photons
required in current deterministic schemes. This enhanced performance is
achieved by recognizing the possibility of adding each photon to the graph
only after successful spin-photon entanglement generation has been heralded.

In Section II of this work, we describe a non-destructive method for this
heralding that is implementable on current hardware by swapping the
entanglement to another photon, termed the herald-on-swap (HoS) method. More
generally, any non-destructive detection of the photon would be suitable to
implement this “emit then add” method of building graphs for arbitrary use. We
explain in Section III how we can herald on destructive detection of the
photon in certain cases, including MBQC. This enables much higher production
rates and fidelities than any feasible non-destructive heralding method. In
this case, the emitted photon is measured prior to adding it to the graph,
thereby abrogating the need for entanglement swapping or photon storage, and
dramatically speeding up graph construction. In this case, the graph state is
built only virtually as every photon in the graph is necessarily measured. We
refer to this as a herald-on-detection (HoD) method, and Section III provides
more detail on when the HoD method can be applied.

In both the HoS and HoD schemes we propose, the photons are emitted over a
longer time, when compared to other emitter-based methods for building
photonic graph states; this is because most attempts to add a photon to the
graph will result in an unsuccessful herald. Consequently, it is the number of
excitation attempts that can be made during the coherence time of the emitter
that sets the practical limit on the graph size, rather than the collection
efficiency. Trapped neutral atoms and ions in vacuum are well suited to this
scheme as they exhibit long coherence times ($10^{0}-10^{3}$ seconds) [9, 10]
and host high-fidelity deterministic entangling gates ($>99\%$) [11, 12, 13]
with moderate collection efficiencies ($\gtrsim 10\%$ with high-NA optics and
$\gtrsim 40\%$ with parabolic reflectors) [14, 15, 16, 17]. We note here that
some solid-state systems, such as rare-earth emitters, can also exhibit
excellent coherence, spin-spin entangling gates, and reasonable photon
collection via integration into photonic devices [18]. In Section IV we
provide estimates of the rate and fidelity for the production of heralded
graph states via both of our schemes assuming state-of-the-art trapped ion and
photon pair source architectures, which include realistic sources of loss,
noise, and decoherence.

Lastly, in Section V we propose a protocol for performing secure two-party
classical computation, in which two parties privately compute a function of
their input variables with the help of an untrusted referee. Compared to
universal quantum computation, our protocol only requires Pauli measurements,
and so the entire procedure can be performed using only our HoD method. We
demonstrate how secure two-party computation can be achieved using just a
single quantum emitter and two auxiliary spin qubits, regardless of the size
of the party’s input. We provide fidelity estimates to produce the graph
states on current hardware, which suggests this is a highly feasible use-case
for quantum networks in the near term. A security analysis and the resulting
bit error rates with and without classical error correction are also provided.

##  II  Spin-photon entanglement schemes

Figure 1:  Herald-on-swap (HoS) scheme. The components are two initial
entangled pairs: an emitter spin (red square) entangled with a photon (orange
circle) and a signal-idler entangled photon pair (orange and green circle,
respectively). We also assume an existing graph $G$ that contains one or more
auxiliary spins (black square). Entanglement swapping is attempted between the
two initial entangled pairs. Upon success, a two-qubit spin-spin gate
deterministically entangles the emitter spin and auxiliary spin. A local
complementation operation is then performed on the emitter spin, which is
subsequently measured out of the graph. This leaves the idler photon a part of
the graph and the emitter spin reinitialized for the next attempted emission.

We first describe the HoS scheme, shown in Figure 1, for making graph states
for arbitrary applications. Given the technical challenges associated with
photon non-demolition measurement [19], this swapping step is required to
herald without destructive measurement of the photonic qubit on near-term
hardware. Compared to the deterministic scheme described in [5], we include a
local entanglement swapping step between an emitter-photon entangled pair and
a pair of entangled photons, and only add the final photon to the graph upon
success of that swap. A single emitter is initialized onto an unentangled
state and excited to produce a single photon that is entangled with its long-
lived internal spin state and collected with some overall efficiency
$\eta_{e}$. This can be implemented with a wide variety of quantum emitters
including laser-cooled atoms or ions, quantum dots, and defects or dopants in
wide-bandgap semiconductors [3, 20, 8, 21, 22]. Photons can be encoded in
various degrees of freedom including polarization, time-bin, and frequency
[23, 24, 25, 26, 27]. Simultaneously, a pair of entangled photons is
probabilistically produced, which can be implemented via standard nonlinear
optical processes, such as spontaneous parametric down conversion (SPDC) [28,
29]. One member of the photon pair, the signal photon, is wavelength and
bandwidth matched to the emitter photon, and the entangled pair is encoded in
the same degree of freedom as the emitter photon. The emitter photon and
signal photon are sent to a joint measurement apparatus which, upon a
successful measurement outcome, projects the emitter spin and the unmeasured
photon, the idler photon, onto an entangled Bell state [30]. Since only
certain measurement outcomes correspond to entanglement between the emitter
spin and idler photon, and imperfect collection and detection means that fewer
than two photons are detected on most attempts, the procedure is repeated
until a successful herald is flagged. Following each failed attempt, the
emitter is measured and reinitialized for the subsequent attempt at a
successful herald.

We assume the emitter is among a set of spin qubits that can be controllably
entangled in a pair-wise way via local and deterministic two-qubit spin-spin
entangling gates, such as an array of trapped atomic ions or neutral atoms.
Upon a successful herald, the emitter spin is deterministically entangled with
an auxiliary spin, which may already be part of a larger graph state. The
emitter spin is then rotated to a conjugate basis and projectively measured,
removing it from the graph without disturbing any of the other qubits.
Following a correction to the photon based on the outcome of this measurement,
the state of the system is as if the auxiliary spin had directly emitted the
photon itself. This “emit then add” method then allows for the construction of
arbitrary photonic graph states using the methods described in [5]. Namely,
the graph states are built using sequences of two-qubit gates on the spins and
local Clifford gates on the photons. The local gates on each photon can all be
combined and applied as a single rotation prior to using the graph state in
subsequent applications.

The key improvement in our scheme is that the idler photon can be collected
with near unit efficiency upon a successful herald [31]. Attaining the
improvement of this scheme requires one additional two-qubit spin-spin
entangling gate per photon added to the graph plus one additional spin (the
emitter), compared to the requirements for generating graphs via known
deterministic schemes [32]. In addition, the graph is emitted over a much
longer time and thus requires longer spin coherence times. We note an
additional benefit of the scheme in that the idler photon can be at virtually
any wavelength due to the flexibility of standard entangled photon pair
sources [33, 34, 35, 36], which overcomes common challenges due to the
inconvenient emission colors of many atomic qubits. We show here that current
state-of-the-art trapped ion systems can be designed to produce graph states
of tens to hundreds of photons using the proposed method, where extending to
thousands would be made possible with reasonable improvements [10, 12, 14].

##  III  A Heralding Scheme for MBQC

The HoS scheme described in the previous section, or any non-destructive
heralding of successful collection of the emitter photon, can be used to build
arbitrary photonic graph states. However, for many applications, including
MBQC, the nodes are measured sequentially with the choice of measurement basis
on one node depending on outcomes of previous ones. It is not necessary in
this case to build the full graph state before beginning these measurements
[37]. Instead, an emitted photon can be destructively measured as soon as the
correct basis for measurement is determined. This measurement thus serves
doubly as a prescribed step in the MBQC protocol and as a way for detecting
the emitted photon. Upon failure to detect the photon, we reinitialize the
emitter and attempt generation again, having left the larger graph
undisturbed, as in the HoS scheme. Upon successful detection, we perform all
required gates on the emitter and auxiliary spins, measure the emitter out of
the graph, and reinitialize the emitter to attempt generation of the next
photon in the graph.

This simpler HoD scheme is shown in Figure 2, and it has the advantage that it
requires no storage time for the emitted photon prior to measurement. There
are limitations for when this scheme can be employed. Namely, a photon can be
measured using HoD provided the two conditions are satisfied: (1) the correct
measurement basis for that photon, as set by the MBQC protocol, is determined
prior to its emission, and (2) this measurement is either Pauli $Z$ or of the
form $\cos\phi X+\sin\phi Y$. Condition (1) can be met in general, as the
emission order can be chosen to match the measurement order of the
computation, albeit at the cost of using extra auxiliary spins and two-qubit
gates in some cases [32]. The second condition can also be met in principle,
since the specified gate sets are sufficient for universal MBQC [1, 38].

To understand condition (2) in more detail, note that if the full graph state
were built using HoS and two-qubit gates on the auxiliary spins, then each
emitted photon would have a local Clifford error of the form $UZ^{m}$, where
$U$ is a fixed Clifford and $m\in\\{0,1\\}$ is determined by the decoupling
measurement on the emitter spin. If $M$ is the measurement to be subsequently
performed on the photon in the MBQC protocol, then when correcting for the
Clifford error, the effective measurement would be
$M^{\prime}=UZ^{m}MZ^{m}U^{\dagger}$. When $M=Z$, then
$M^{\prime}=UZU^{\dagger}$; or when $M=\cos\phi X+\sin\phi Y$, then
$M^{\prime}=(-1)^{m}UZU^{\dagger}$. In the first case, the dependence on $m$
is completely removed, and the photon can be equivalently measured with
$UZU^{\dagger}$ immediately after it is emitted in the HoD scheme. In the
second case, it can also be immediately measured with $UZU^{\dagger}$, but now
one must perform a bit flip on the classical measurement outcome if $m=1$;
this is because an overall $-1$ factor on a spin observable simply flips the
spin-up/spin-down outcomes. In summary, the correct computation can be
attained through HoD and classical post-processing for observables of the
specified form.

While satisfying conditions (1) and (2) above is sufficient for universal MBQC
using HoD, this is often not the most efficient method in terms of the overall
number of photons used to drive the computation. For example, building out the
graph to a certain depth and measuring in a different sequence than the
emission order can lead to more compact gate implementations [38]. Also, using
MBQC measurements outside of the x-y plane allows for more general forms of
information flow [39]. Nevertheless, as we show in the next section, the HoD
scheme can enable dramatically faster construction and higher fidelity with no
photon storage required. For the HoS (or any non-destructive heralding)
scheme, photon storage is required for at least the time to perform the spin-
spin entangling gates and the decoupling measurement on the emitter.

Figure 2:  Herald-on-detection (HoD) scheme. For certain MBQC protocols, it is
sufficient to perform the deterministic entangling gate between the emitter
and auxiliary spin only upon successful detection of the emitted photon. The
photonic graph state constructed in this case is virtual (represented by
dashed boundaries) and exists as a set of conditional phases stored on the
auxiliary spin(s).

##  IV  Scaling and fidelity for heralded schemes

A major benefit of both schemes comes in scaling up the size of graph states
using near term hardware. The average time to successfully generate an
$n_{p}$-photon graph by directly collecting photons from an emitter in $n_{p}$
subsequent excitation events for computation is
$\mathcal{O}(\eta_{e}^{-n_{p}})$, where $\eta_{e}$ is the emitter collection
efficiency, as any failed detection event truncates the graph. In typical
deterministic quantum emitter-based schemes, any inefficiency in collection
therefore leads to exponentially bad scaling with graph size. Given current
hardware, this severely limits the size and rate of generation for photonic
graph states, particularly those that require multiple spin qubits. We note
that there are loss tolerance and percolation thresholds that improve this
scaling, but they require much better collection efficiency than is feasible
in near-term systems [40, 41, 42]. For the heralded schemes, any failed
detection of the emitter photon simply results in the reinitialization of the
emitter and another attempt at the joint or single photon detection, while the
graph under construction remains unaffected. Therefore, an $n_{p}$-photon
graph state will be created over a time that is
$\mathcal{O}(n_{p}\eta_{e}^{-1})$. As a comparison, the time to make an
$n_{p}$-photon graph state (in units of the repetition period) is shown in
Figure 3 for $\eta_{e}\in\\{0.1,0.25,0.4\\}$ for the deterministic (red), HoS
(blue), and HoD (yellow) schemes. We do not include the time to perform gates
and measurements on the spins for these estimates, and we assume that the
emitter coherence does not limit the graph size for the deterministic scheme
($n_{p}/\tau R_{\rm{rep}}\ll 1$ where $\tau$ is the spin coherence time and
$R_{\text{rep}}$ is the repetition rate of excitation). In practice, however,
the short coherence times of the most efficient photon emitters further limit
the size of graphs that can be produced in the deterministic scheme [27, 8].
For the heralded schemes, all auxiliary spins must remain coherent for the
entire time they are a part of the graph, which is much longer than the
$n_{p}$ repetition cycles over which the graph is generated in the
deterministic scheme. Thus, moving from the deterministic scheme to one
proposed here effectively means moving from a scheme limited by the photon
collection efficiency to a scheme limited by spin coherence. If a hybrid of
the HoS and HoD schemes is employed, the generation time falls somewhere
between the curves for those schemes, with the fraction of photons generated
via each method determining exactly where.

Figure 3:  Time to make photonic graph states of size $n_{p}$ in units of the
repetition period. The deterministic (red), HoS (blue), and HoD (yellow)
schemes are compared. The three curves of each color represent emitter photon
collection efficiencies $\eta_{e}\in\\{0.1,0.25,0.4\\}$. Polynomial scaling in
the heralded schemes allows for the construction of larger graphs. Results are
omitted where decoherence and false heralds bring the fidelity under $50\%$
for reasonable experimental parameters. In the HoS scheme, fidelity can be
sacrificed to improve the rate for the construction of small graph states if
desired. A full description of these estimates is given in Appendix D.

For the two proposed schemes, there are additional factors that affect the
fidelity that are not present in the deterministic scheme, including
decoherence of the emitter and auxiliary spin(s) during the construction time
and multiple photon pair production that limits the fidelity of entanglement
swapping for the HoS scheme. Here we investigate the scaling of these sources
of infidelity and compare them to the limits set by imperfect two-qubit spin-
spin entangling gates, as well as the initial entanglement fidelities of the
emitter photon and photon pair sources. We require one extra spin-spin
entangling gate each time we add a photon to the graph, in addition to the
gates required to make the desired final graph [32], which exponentially
suppresses the fidelity of large photonic graph states if the gates are not
perfect. Additionally, any infidelity of the photon pair source in the HoS
scheme adds to the overall infidelity. Here, we demonstrate that if sufficient
error correction or entanglement purification is possible [43], the additional
sources of infidelity inherent to our scheme do not themselves prohibit
exceedingly large graph states. For a full discussion of our experimental
model and relevant sources of infidelity, see Appendix D.

In modeling decoherence under the usual dephasing map, any emitters or
auxiliary spins will remain invariant with a probability
$D(t,\tau)=\tfrac{1}{2}(1+e^{-t/\tau})$, for the duration $t$ until they are
projectively measured. In either scheme, the emitter is reinitialized with
each attempt to add a new photon to the larger graph, and hence the time it is
required to remain coherent is reset. Furthermore, the classical conditioning
offered by this “emit then add” method means the emitter is only required to
remain coherent for the attempts where the relevant joint or single photon
measurements are a success. Any auxiliary spins, on the other hand, are
required to remain coherent for the duration of time they remain a part of the
larger graph state in construction. The average time for the successful
addition of a new photon to the larger graph goes as $t_{\text{rep}}/P_{s}$,
where $t_{\text{rep}}=R_{\text{rep}}^{-1}$ is the repetition period of the
excitation, and $P_{s}$ is the probability of a successful joint or single
photon measurement for the HoS or HoD schemes, respectively. Note that in the
HoD scheme we assume $P_{s}=\eta_{e}$. Hence, the total contribution to the
final state fidelity from the emitter and any auxiliary spins is

$\displaystyle F_{D}^{(e)}(n_{p})$
$\displaystyle=\left(\frac{1}{2}\left(1+e^{-t_{\text{rep}}/\tau}\right)\right)^{n_{p}},$
(1a) $\displaystyle\langle F_{D}^{(s)}(n_{p},P_{s})\rangle$
$\displaystyle=\frac{1}{2}\left(1+e^{-n_{p}t_{\text{rep}}/P_{s}\tau}\right),$
(1b)

where we include a superscript to denote emitter $(e)$ and auxiliary spin
$(s)$ qubits, and we have used the same coherence time $\tau$ for the emitter
and auxiliary spins in the system.

For the HoS scheme, we assume a standard SPDC source to generate the required
entangled photon pairs [44]. The multi-pair emission of such a source
introduces an additional infidelity in the entanglement swapping procedure. We
denote $P_{t}$ as the overall probability that a true Bell state is heralded
and measured after constructing the graph. In general, $P_{t}<P_{s}$ due to
false heralding. A primary source of false heralding is when the emitter
photon is not collected but the SPDC source produces two or more photon pairs
that lead to a detection pattern, falsely signaling a successful swap. False
heralding due to two signal photons is a well known and ubiquitous problem in
entanglement swapping with photon pair sources based on nonlinear optics [33].
We can write an expression for the fidelity of the entanglement swapping
procedure, $P_{t}/P_{s}$, using the known statistical distribution of
entangled photon pairs produced via SPDC. Here, we assume photon number-
resolved detection and perfect collection and detection of the signal photon
once produced. This is because loss on that channel can generally be minimal
and primarily affects the rate rather than the swapping fidelity (see Appendix
D for the full calculation, including further experimental factors not
discussed here). Furthermore, the intention here is to show that even quite
low efficiency collection of the emitter photon can allow the generation of
graph states. The probability of producing two entangled photon pairs is
proportional to the square of the probability of producing a single entangled
pair, and is controllable via the pump power of the SPDC (parameterized here
by the quantity $\xi$ [33]), thus introducing a tradeoff between rate and
fidelity. The fidelity, $F_{\rm{swap}}=P_{t}/P_{s}$, is given by

$\displaystyle P_{t}(\eta_{e},\xi)=\eta_{e}(1-\xi)^{2}\xi,$ (2a)
$\displaystyle
P_{s}(\eta_{e},\xi)=\left[\eta_{e}\xi+(1-\eta_{e})\xi^{2}\right](1-\xi)^{2},$
(2b) $\displaystyle
F_{\rm{swap}}(\eta_{e},\xi)=\frac{\eta_{e}}{\eta_{e}+(1-\eta_{e})\xi}.$ (2c)

In the absence of decoherence of the spins, we could simply work at $\xi\ll 1$
(very low pair generation rate) to reduce the false heralding and increase the
overall fidelity. However, this slows the rate of the graph production and
introduces infidelity due to decoherence of the auxiliary spin(s). Given a set
of experimental parameters, the rate of pair production can be optimized by
tuning $\xi$ to maximize the overall fidelity of the desired graph state,
balancing the infidelity due to false heralds against the decoherence.

Figure 4:  Graph state fidelity versus photon number ($n_{p}$) for several
different regimes of operations, and variable emitter-photon collection
efficiencies ($\eta_{e}$) and dephasing timescales ($t_{\text{rep}}/\tau$).
Gate and pair generation fidelities (grey) exponentially preclude the
construction of large graph states in any scheme utilizing our “emit then add”
method. With sufficient error correction or purification around these
fidelities, regimes limited by false heralds and decoherence (blue) and
decoherence alone (yellow), allow for the construction of significantly larger
graph states.

We present a simple example comparing these additional sources of infidelity
to the limits set by spin-spin entangling gates and initial entanglement
fidelities, for the case of constructing a graph state on a single auxiliary
spin. Figure 4 depicts these estimates over a few regimes. The combined effect
of false heralds and decoherence (blue) set the fidelity as

$\displaystyle F(n_{p},\eta_{e},\xi)$
$\displaystyle=F_{\text{swap}}(\eta_{e},\xi)^{n_{p}}F_{D}^{(e)}(n_{p})$ (3)
$\displaystyle\quad\quad\quad\quad\times\langle
F_{D}^{(s)}(n_{p},P_{s}(\eta_{e},\xi))\rangle,$

which we optimize over $\xi$, for fixed $n_{p}$ and $\eta_{e}$. When only
limited by decoherence (yellow), we can employ Equation (3), except now fixing
$F_{\text{swap}}(\eta_{e},\xi)=1$ and removing the need to optimize the
fidelity. These estimates are applicable when constructing large star graph
states—the local-unitary equivalent to a Greenberger-Horne-Zeilinger (GHZ)
state—and 1D cluster states.

##  V  Realizing secure two-party computation

As one application of our HoD scheme, we describe a method for securely
computing an arbitrary Boolean function $f:\\{0,1\\}^{\times n}\to\\{0,1\\}$
of either two parties or a restricted class of multi-party functions. As a
special type of MBQC, our protocol performs the calculation through a sequence
of measurements on distributed graph states. Only Pauli measurements are
needed and the protocol can be implemented using the HoD method, for which the
generation of the requisite resource state happens in parallel with the
computation and no photonic memory is required.

Secure multi-party computation (MPC) is a task in which two or more parties
compute some function on their individually held variables without revealing
the values of the variables to each other [45, 46]. For example, in Yao’s
famous millionaire problem, two parties want to determine whose bank account
has the most money without actually revealing how much money is in each
account. MPC is a deeply-studied topic in both classical and quantum
cryptography, and a variety of MPC protocols have been proposed achieving
different levels of security and relying on different operational assumptions
[47]. We propose an unconditionally secure method for restricted MPC that
includes all two-party computations and requires only two rounds of public
communication regardless of the size of the computational input. Our scheme
follows a well-known approach of decomposing an MPC into “offline” and
“online” phases [48, 49, 50]. In the offline phase, some universal
computational resource is distributed to all the parties. Crucially, this
resource does not depend on the particular function being computed other than
its input size. Then in the online phase this resource is used to compute some
chosen function of the parties’ inputs. For example, in the classical setting
one well-known computational resource is a special form of shared randomness
known as “Beaver triples,” which can be used to efficiently compute logical
AND gates in the online phase [51]. The problem of MPC then reduces to secure
and efficient methods for distributing Beaver triples in the offline phase. In
a similar spirit, our protocol involves distributing certain quantum graph
states in the offline phase which then enable the computation of a logical AND
in the online phase. Beyond its relatively low communication costs, a
significant advantage of our protocol is that the parties can, in principle,
use self-testing methods to verify that some untrusted source is faithfully
distributing the correct graph state [52, 53], an ability that does not exist
for classical shared randomness.

Suppose that $N$ parties $\mathbf{P}_{1},\mathbf{P}_{2},\cdots,\mathbf{P}_{N}$
wish to compute some Boolean function
$f(\mathbf{x}_{1},\cdots,\mathbf{x}_{N})$, where $\mathbf{x}_{i}$ is a string
of bits representing the input for party $i$. In addition to correctness, the
evaluation of $f$ should be done securely such that the parties learn no more
information about the individual $\mathbf{x}_{1},\cdots,\mathbf{x}_{N}$ beyond
their own input and what is revealed in the function value
$f(\mathbf{x}_{1},\cdots,\mathbf{x}_{N})$. To achieve this task, we propose a
method of delegated computation in which a non-collaborating Referee is
introduced to assist in the computation of
$f(\mathbf{x}_{1},\cdots,\mathbf{x}_{N})$. To maintain privacy, the Referee
also should not learn any more information about the $\mathbf{x}_{i}$ beyond
what is implied by the computed value
$f(\mathbf{x}_{1},\cdots,\mathbf{x}_{N})$, nor does the Referee reveal any
more information to the other parties than this value.

The protocol uses the fact that every Boolean function $f$ can be expressed in
an algebraic normal form (ANF), which presents $f$ as a sum (mod $2$) of
different variable conjunctions. That is, we can write
$f=\sum_{i=1}^{\mathfrak{R}}c_{i}$, where each $c_{i}$ is the logical AND of a
certain group of input variables. By combining variables belonging to the same
party, every $c_{i}$ becomes the conjunction of at most $N$ variables, each
one belonging to a different party. In this work, we restrict attention to
functions $f$ that admit an ANF whose conjunctions involve no more than two
variables. This covers the entire class of two-party functions, but also
includes certain multi-party functions, such as the three-party majority
function $\varphi_{3}(x,y,z)=xy+xz+yz\mod 2$, which outputs the majority value
among inputs $x,y,z\in\\{0,1\\}$. In general, the functions we consider have
the form $f=\sum_{i=1}^{\mathfrak{R}_{1}}x_{i}y_{i}+\sum_{i=1}^{N}z_{i}$,
which is separated into linear and quadratic parts. By again combining
variables, we can assume that $z_{i}$ is held by party $\mathbf{P}_{i}$ and
computed from her input $\mathbf{x}_{i}$. Furthermore, if each
$\mathbf{x}_{i}$ is no more than $M$ bits, then
$\mathfrak{R}_{1}\leq\binom{N}{2}M^{2}$.

Figure 5:  In Stage I, each computation of a padded AND,
$b_{i}=x_{i}y_{i}+p_{i}$, is accomplished using a graph state $\ket{G_{I}}$ of
this form. The qubits are distributed to parties $\mathbf{A}_{i}$ (Alice),
$\mathbf{B}_{i}$ (Bob), and $\mathbf{R}$ (the Referee) as shown. The numeric
script $k$ above each qubit reflects an example photon emission order.

The protocol involves performing Pauli observables, $X,Y,Z$, on two types of
graph states, $\ket{G_{I}}$ and $\ket{G_{II}}$, depicted in Figures 5 and 6,
respectively. The distribution of these states is conducted during the offline
phase of the protocol. In practice, the states can be generated by some
untrusted quantum source, and their correctness can be certified using self-
testing methods (see Appendix B.4). Specific steps for building both
$\ket{G_{I}}$ and $\ket{G_{II}}$ using a quantum emitter is presented in
Appendix C.2. We note that the nontrivial emission order on $\ket{G_{I}}$ set
by our MPC requires two auxiliary spins to produce [32]. The online phase of
the protocol then involves specific sequences of Pauli measurements and public
communication, and these sequences take place in two different stages.

Stage I uses $\ket{G_{I}}$ to compute the bit values

$b_{i}=x_{i}y_{i}+p_{i},\quad\quad i=1,\cdots,\mathfrak{R}_{1},$ (4)

where each $p_{i}$ is an independent one-time pad bit that is private from all
the parties, including the Referee.

Figure 6:  The graph state $\ket{G_{\text{II}}}$ used to compute values $p$ in
Stage II. The numeric subscript labels both the party $\mathbf{P}_{k}$ and an
example photon emission ordering. In total, $n_{p}=N+1$ photons are required
for the $N$ parties and the Referee.

Stage I. Input: Parties $\mathbf{A}_{i}$ (Alice) and $\mathbf{B}_{i}$ (Bob)
input bits $x_{i}$ and $y_{i}$, respectively.

  1. 1.

The Referee and Bob measure $X$ and $Z$ on qubits $1$ and $2$, respectively,
obtaining a common measurement outcome $s=m_{1}=m_{2}$.

  2. 2.

Bob measures $Z$ on qubit $3$, obtaining $m_{3}$. He announces
$\delta_{i}=y_{i}+m_{3}$. Alice then applies $Z^{\delta_{i}}$ to qubit $4$.

  3. 3.

Alice measures $W^{x_{i}}Z(W^{\dagger})^{x_{i}}$ on qubits $4$ and $5$, where
$W\equiv(iX)^{1/2}$, computing $\alpha_{i}=x_{i}+m_{4}+m_{5}$ from her
outcomes. Note that $WZW^{\dagger}=Y$.

  4. 4.

The Referee measures $V^{s}X(V^{\dagger})^{s}$ on qubit $6$, where
$V\equiv(-iZ)^{1/2}$, obtaining $b_{i}=m_{6}$. Note that $VXV^{\dagger}=Y$.

  5. 5.

Alice measures $Z$ on qubit $7$, obtaining $m_{7}$. She announces
$\gamma_{i}=x_{i}+m_{7}$. Bob then applies $Z^{\gamma_{i}}$ to qubit $8$.

  6. 6.

Bob measure $W^{s}Z(W^{\dagger})^{s}$ on qubit $8$ obtaining
$\beta_{i}=m_{8}$.

As shown in Appendix B.1, the Referee’s measurement outcome in step 4.
satisfies $b_{i}=x_{i}y_{i}+p_{i}$, where $p_{i}=\alpha_{i}+\beta_{i}$. The
above sequence is repeated on a fresh copy of $\ket{G_{I}}$ for each
$i=1,\cdots,\mathfrak{R}_{1}$, with the values of $\alpha_{i}$ and $\beta_{i}$
possibly being obtained by different parties in each iteration. Note that if
the Referee added all the $b_{i}$ at the end of Stage I, the computed value
would be

$\sum_{i=1}^{\mathfrak{R}_{1}}b_{i}=f+\sum_{i=1}^{N}z_{i}+\sum_{i=1}^{\mathfrak{R}_{1}}(\alpha_{i}+\beta_{i})=f+\sum_{i=1}^{N}\mu_{i},$
(5)

where $\mu_{i}$ denotes the sum of the variables in the set
$\\{\alpha_{i},\beta_{i}\\}_{i=1}^{\mathfrak{R}_{1}}\cup\\{z_{i}\\}_{i=1}^{N}$
belonging to party $i$. Stage II then amounts to removing the term
$\sum_{i=1}^{N}\mu_{i}$ from the RHS of Equation (5).

Stage II is performed using an $(N+1)$-party GHZ state $\ket{G_{II}}$ (see
Figure 6) shared between the Referee and the $N$ parties. The following steps
are then taken.

Stage II. Input: Parties $\mathbf{P}_{i}$ input their respective bits
$\\{\mu_{i}\\}_{i=1}^{N}$ obtained from the set
$\\{\alpha_{i},\beta_{i}\\}_{i=1}^{\mathfrak{R}_{1}}\cup\\{z_{i}\\}_{i=1}^{N}$,
as in Equation (5). The Referee inputs $\\{b_{i}\\}_{i=1}^{\mathfrak{R}_{1}}$
obtained from Stage I.

  1. 1.

Party $\mathbf{P}_{k}$ measures $Z$ on qubit $k$ for qubits $1,\cdots,N$. She
then announces $\nu_{k}=\mu_{k}+m_{k}$.

  2. 2.

The Referee measures $X$ to learn $\sum_{k=1}^{N}m_{k}$ and then adds this to
$\sum_{k=1}^{N}\nu_{k}$ to obtain $\sum_{k=1}^{N}\mu_{k}$. The latter is then
added to the sum $\sum_{i=1}^{\mathfrak{R}_{1}}b_{i}$ to obtain $f$, which is
then announced to all the parties.

It should be noted that by parallelization, both Stages I and II can be
performed using just two rounds of simultaneous communication. Indeed, each
party needs to broadcast at most two public messages, the first being no more
than $\log\mathfrak{R}_{1}$ bits, and the second being one bit. When run in
parallel, all the Stage I messages can be broadcast concurrently, and likewise
for the Stage II messages.

Intuitively, this protocol is secure due to the one-time pad bits that are
generated with each measurement on the graph states. While there are a variety
of different approaches to defining security in multipartite computation, in
this work we demand as a security condition that playing honestly does not
reveal any more information about one’s input than what can be inferred from
the final function output. We prove in Appendix B.3 that our protocol
satisfies this condition.

Performance. To handle experimental errors in the above protocol, we can
employ a simple repetition code to suppress the effects of any infidelity in
our ability to make $\ket{G_{I}}$ and $\ket{G_{II}}$ on the output of the
computation $f$. By determining the total bit error probability when computing
each $b_{i}$ in Stage I and $p$ in Stage II, an arbitrarily small total bit
error probability $\epsilon_{f}$ on the computation output $f$ can be chosen
to set the number of repetitions required for each Stage I and II,
respectively. We use this information to estimate the lower bound rate of
computation at which $N$ parties can compute $f$ on their $M$-bit inputs.
Details are proved in Appendix B.2.

Figure 7:  Error corrected two-party computation rate versus the number of
input bits to $f$ using the HoD scheme, shown for two acceptable error
probabilities on the computation ($\epsilon_{f}$). The rate is expressed in
units of the repetition rate of excitation of the chosen quantum emitter,
$R_{\text{rep}}$, which is typically in the range of
$10^{6}-10^{9}~{}\rm{s}^{-1}$ for highly coherent emitters. The individual bit
error probabilities for Stage I and Stage II, respectively, are $0.008$ and
$0.003$, assuming $\eta_{e}=0.4$, $F_{\text{ent}}=0.999$, and
$t_{\text{rep}}/\tau=10^{-9}$ (see. Appendix D for details). We see that these
parameters allow virtually unlimited reduction in the total error probability
with minimal change in the overall rate.

Functionally, our protocol allows for the secure implementation of any two-
party Boolean function, $f$, by repeatedly generating and distributing copies
of the 8-qubit state $\ket{G_{I}}$ and then generating and distributing one
copy of $\ket{G_{II}}$ (which is simply a 3-qubit GHZ state). The number of
required copies of $\ket{G_{I}}$ depends (polynomially) on the size of the
input, $M$, and the desired final error probability, $\epsilon_{f}$. We re-
emphasize here that this can be done with one emitter and two auxiliary spins,
and the spins need only remain coherent for the time to make each copy of
$\ket{G_{I}}$, a requirement easily met with current trapped ion or atom array
systems. Using the fidelity estimates established in Section IV and detailed
in Appendix D, we can conservatively estimate the maximum possible bit error
probability in either Stage from the compliment of the probability that no bit
error occurs, that is, the probability to successfully generate $\ket{G_{I}}$
and $\ket{G_{II}}$ in our proposed HoD scheme. In Figure 7, we plot the lower
bound rate of computation (which is proportional to the number of copies of
$\ket{G_{I}}$ that are required) at which our protocol can operate with error
correction, in units of $R_{\text{rep}}$, against the size of each parties
input, $M$, for total acceptable error probabilities
$\epsilon_{f}=\\{10^{-3},10^{-13}\\}$.

##  VI  Discussion and conclusion

The schemes introduced here naturally lend themselves to various extensions
and modifications to increase functionality. First, combining with a high
degree of multiplexing, such as between many arrays of atoms or ions, would
increase the generation rate with a linear factor in the degree of
multiplexing. Incorporating this with heralding means that photons can be
routed upon successful generation of spin-photon entanglement. Another
extension is the opportunity for substantial spectral engineering of the idler
photon in the HoS scheme. As mentioned above, the idler photon can be produced
at virtually any arbitrary wavelength regardless of the emission wavelength of
the emitting spin, including using a superconducting qubit as the spin and
generating a signal-idler pair with a microwave signal and an optical idler
[54]. We also point out that the bandwidth of the idler photon can be
different than the typically narrow and fixed bandwidth of the emitter.
Filtering, time lensing [55], and/or source engineering [22, 56] can enable
substantial broadening or narrowing of the idler photon compared to the
emitter photon.

In this work, we have demonstrated the feasibility of generating photonic
graph states with inefficient quantum emitters and give a central example of
its applications to secure multi-party computation. Significantly, our schemes
offer polynomial scaling in the time to construct graph states of hundreds of
photons with high fidelity on current generation trapped ion experiments [12,
13], even when the collection efficiency of emitter photons is poor. The “emit
then add” approach requires additional resource costs for making graph states,
but we show that it is feasible with current and near-term experimental
hardware. Our scheme is a toolbox for making large entangled photonic states
for MBQC and other applications that are limited by spin decoherence rather
than photon collection efficiency. We specifically show an application to
realize distributed multi-party computation that is feasible in the near-term
with current hardware.

###### Acknowledgements.

We acknowledge helpful discussions with Kejie Fang and Vito Scarola. E.C.
thanks Christian Schaffner for some helpful explanations on multi-party
computation. This work was supported by the NSF Quantum Leap Challenge
Institute on Hybrid Quantum Architectures and Networks (NSF Award No.
2016136).

##  Appendix A  Preliminaries on graph states

For an arbitrary graph $G=(V,E)$ with vertices $V=\\{a_{1},\cdots,a_{n}\\}$
and edge set $E\subset V\times V$, consider the $n$-qubit operator obtained by
performing a controlled$-Z$ gate, $CZ_{a,b}$, between every $(a,b)\in E$. We
denote this global operator by

$U_{G}=\prod_{(a,b)\in E}CZ_{a,b}.$ (6)

The graph state associated with the graph $G$ is the $n$-qubit state

$\ket{G}=U_{G}\ket{+}^{\otimes V}.$ (7)

Note that $\ket{+}^{\otimes n}$ is stabilized by $n$ commuting operators
$\\{X_{a}\\}_{a\in V}$. Hence the stabilizer of $\ket{G}$ can be understood by
examining the how the $X_{a}$ transform under $U_{G}$. Since
$CZ_{a,b}(X_{a})CZ_{a,b}=X_{a}Z_{b}$, it follows that the stabilizer of
$\ket{G}$ is generated by the operators $\\{K_{a}\\}_{a\in V}$, where

$\displaystyle K_{a}$ $\displaystyle=U_{G}X_{a}U_{G}$ (8)
$\displaystyle=X_{a}\prod_{b\in N_{a}}Z_{b}$ $\displaystyle=X_{a}\prod_{b\in
V}Z_{b}^{\Gamma_{a,b}}\quad\quad\forall a\in V,$

and $\Gamma$ is the adjacency matrix of $G$.

For any $n$-qubit graph state $\ket{G}$, we can generate an orthonormal basis
for $\mathbb{C}_{2}^{N}$, called the associated graph basis. The basis vectors
have the form

$Z^{\mathbf{r}}\ket{G}\quad\text{where}\quad
Z^{\mathbf{r}}:=Z^{r_{1}}_{1}\otimes Z_{2}^{r_{2}}\otimes\cdots\otimes
Z_{N}^{r_{N}},$ (9)

and we will call $\mathbf{r}=(r_{1},r_{2},\cdots,r_{n})\in\mathbb{Z}_{2}^{n}$
a conditional phase vector and each bit $r_{k}$ phase information for qubit
$k$. To see that these states are orthogonal, let $\mathbf{r}$ and
$\mathbf{r}^{\prime}$ be two distinct conditional phase vectors, and suppose
their bit values differ in position $a$. Then $K_{a}$ will anti-commute with
$Z^{\mathbf{r}}Z^{\mathbf{r}^{\prime}}$, and so

$\displaystyle\bra{G}Z^{\mathbf{r}}Z^{\mathbf{r}^{\prime}}\ket{G}$
$\displaystyle=\bra{G}Z^{\mathbf{r}}Z^{\mathbf{r}^{\prime}}K_{a}\ket{G}=-\bra{G}K_{a}Z^{\mathbf{r}}Z^{\mathbf{r}^{\prime}}\ket{G}=-\bra{G}Z^{\mathbf{r}}Z^{\mathbf{r}^{\prime}}\ket{G}.$
(10)

We will be particularly interested in how the graph basis states transform
under the local Pauli measurements of $Y$ and $Z$. For a binary vector
$\mathbf{r}\in\mathbb{Z}_{2}^{n}$ and subset of nodes $S\subset V$, let
$\mathbf{r}-S$ denote the vector of length $n-|S|$ obtained from $\mathbf{r}$
by removing the coordinates in $S$. Suppose that for an initial graph basis
state $Z^{\mathbf{r}}\ket{G}$, either $Y$ or $Z$ is measured on qubit $a$ and
outcome $m_{a}\in\\{0,1\\}$ is received. The initial state transforms as
follows:

$\displaystyle Z_{a}:$ $\displaystyle\quad
Z^{\mathbf{r}}\ket{G}\mapsto\left(\prod_{b\in
N_{a}}Z_{b}^{m_{a}}\right)Z^{\mathbf{r}-a}\ket{G-a},$ (11a) $\displaystyle
Y_{a}:$ $\displaystyle\quad Z^{\mathbf{r}}\ket{G}\mapsto\left(\prod_{b\in
N_{a}}\left(-iZ_{b}\right)^{1/2}Z_{b}^{r_{a}+m_{a}}\right)Z^{\mathbf{r}-a}\ket{\tau_{a}(G)-a},$
(11b)

where $\tau_{a}(G)$ is the local complementation of $G$ at vertex $a$, i.e.
$\tau_{a}(G)$ is the graph $(V,E\Delta E(N_{a},N_{a}))$, and $\tau_{a}(G)-a$
is the graph obtained by removing $a$ from $\tau_{a}(G)$ [57]. Explicitly,

$\ket{\tau_{a}(G)}=\left(-iX_{a}\right)^{1/2}\left(\prod_{b\in
N_{a}}\left(iZ_{b}\right)^{1/2}\right)\ket{G},$ (12)

describes a set of single-qubit rotations comprising a local complementation.
Note that the $Y_{a}$ post-measurement state can always be transformed back to
the associated graph basis by performing $(iZ_{b})^{1/2}$ on each $b\in
N_{a}$. For the special case of measurement at a leaf in the graph, a vertex
with only a single neighbor such that $\tau_{a}(G)=G$, the $Y_{a}$ post-
measurement state after rotation back to the graph basis is effectively a
$Z_{a}$ post-measurement state up to the conditional phase flip
$Z_{b}^{r_{a}}$.

###  A.1  Phase transmission along a chain

Consider the effect of locally measuring along some linear chain in graph $G$.
Let $a_{1},a_{2},a_{3},\cdots,a_{n},a_{n+1}$ denote the constituent qubits,
with $a_{1}$ being the first node in the chain and $a_{n+1}$ being the final
node, which is connected to the remainder of the graph and left unmeasured in
this sub-routine. The specific measurement sequence consists of measuring $Y$
on $a_{1}$ and $(-iZ)^{1/2}Y(iZ)^{1/2}=-X$ on $a_{k}$ for all
$k=2,\cdots,n-1$. If the total state prior to measurement is a graph basis
state $Z^{\mathbf{r}}\ket{G}$ and $(m_{a_{1}},\cdots,m_{a_{n-1}})$ is the
binary sequence of outcomes from these measurements, then by Equation (11b)
the overall state evolution is

$\displaystyle Y_{a_{1}},(-X_{a_{2}}),\cdots,(-X_{a_{n-1}}):\quad
Z^{\mathbf{r}}\ket{G}$
$\displaystyle\mapsto[-iZ_{a_{n}}]^{1/2}Z_{a_{n}}^{\Omega}Z^{\mathbf{r}-\\{a_{1},\cdots,a_{n-1}\\}}\ket{G-\\{a_{1},\cdots,a_{n-1}\\}},$
(13)

where $\Omega=\sum_{i=1}^{n-1}(r_{a_{i}}+m_{a_{i}})\mod 2$. Crucially, each
$m_{a_{k}}$ is a random bit uncorrelated from $\mathbf{r}$ and any other
measurement data. Hence, we can think of each $m_{a_{k}}$ as a one-time pad
that is added to the conditional phase information $r_{a_{k}}$ when passing
from node $a_{k}$ to $a_{k+1}$.

###  A.2  Phase transmission at a fork

Consider the effect of measuring two qubits, $a$ and $b$, that are connected
to a single common node $c$. Suppose the total state prior to measurement is a
graph basis state $Z^{\mathbf{r}}\ket{G}$. If $m_{a}$ and $m_{b}$ denote the
binary outcomes when either $Y$ or $Z$ is measured on both qubits, the
respective state transformations are given by

$\displaystyle Y_{a},Y_{b}:\quad Z^{\mathbf{r}}\ket{G}$ $\displaystyle\mapsto
Z_{c}^{r_{a}+r_{b}+1}Z_{c}^{m_{a}+m_{b}}Z^{\mathbf{r}-\\{a,b\\}}\ket{G-\\{a,b\\}},$
(14a) $\displaystyle Z_{a},Z_{b}:\quad Z^{\mathbf{r}}\ket{G}$
$\displaystyle\mapsto
Z_{c}^{m_{a}+m_{b}}Z^{\mathbf{r}-\\{a,b\\}}\ket{G-\\{a,b\\}},$ (14b)

up to an overall phase. Hence, the key difference between the two measurements
is that $Y_{a},Y_{b}$ transfers the conditional phase flip
$Z_{c}^{r_{a}+r_{b}+1}$ onto the state $\ket{G-\\{a,b\\}}$ while $Z_{a},Z_{b}$
does not.

##  Appendix B  Secure multi-party computation

We verify correctness and prove security of our multi-party computation
protocol detailed in Section V, using the preliminaries of Appendix A. The
measurement sequences described in Stages 6 and 6 together accomplish the
computation of any Boolean function up to quadratic order in the parties’
inputs. We verify these sequences by tracing through the transformation of the
graph states $\ket{G_{I}}$ and $\ket{G_{II}}$ used in each part of the
protocol, and the information that is transmitted along the graph in the form
of phase flips conditioned on both the parties’ inputs and their measurements.
Subsequently, we detail how classical error correction can be utilized to
suppress a bit error on the output of the computation. We establish security
by demonstrating that the classically communicated information in the protocol
reveals no new information to any of the other parties about their input,
other than what they would learn from the final output of the computation.
Finally, we discuss how self-testing can be employed to further secure against
a possibly corrupt Source.

###  B.1  Correctness

To verify correctness for the computation of $f$, we track the evolution of
phase information as defined in Appendix A through both Stages of the
protocol. A graph state $\ket{G}$ consisting of $n$ qubits, labeled
$1,\cdots,n$, is initialized. We denote $\mathbf{m}=(m_{1},\cdots,m_{n})$ as
the binary vector of measurement outcomes for each of the qubits. In general,
measurements change the shape of the graph disconnecting the measured qubit
and applying conditional phase flips on its neighbors. As the labeling we
assigned represents a possible photon emission ordering for generating the
graph state in a quantum emitter-based experimental scheme, it is convenient
to keep this labeling for each qubit despite transformations in the graph
induced by the measurement sequence.

####  B.1.1  Stage I

Stage I details the measurement sequence performed on $\ket{G_{I}}$, requisite
for computing each $b_{i}=x_{i}y_{i}+p_{i}$. Let $x_{i}$ and $y_{i}$ be the
input for the parties $\mathbf{A}_{i}$ and $\mathbf{B}_{i}$, respectively. We
will refer to $\mathbf{A}_{i}$ and $\mathbf{B}_{i}$ as Alice and Bob, although
in general these labels change for different
$i\in\\{1,2,\cdots,\mathfrak{R}_{1}\\}$. The measurement outcome $m_{k}$
denotes the measurement $m$ of the $k^{\text{th}}$ qubit in the $8$-qubit
graph state, depicted in Figure 5. For simplicity, we suppress any additional
subscript denoting the iteration of Stage I and reset these labels with each
new copy of $\ket{G_{I}}$.

In step (1.), the Referee’s $X$ measurement on qubit $1$ decouples Bob’s qubit
$2$ from the rest of the graph. This leads to correlated outcomes
$s=m_{1}=m_{2}$ as the parties are each measuring an independent component of
the generator $X_{1}Z_{2}$ that stabilizes the state. From Equation (11a) and
Equation (13), we see this adds the conditional phase flip $Z_{4}^{s}$ to
Alice’s qubit. In step (2.), Bob’s measurement of qubit $3$ introduces a
conditional phase flip $Z_{4}^{m_{3}}$ on Alice’s qubit. Her subsequent
rotation of the qubit, using Bob’s announced $\delta_{i}=y_{i}+m_{3}$,
transforms the state such that the total conditional phase on her qubit is
described by $Z_{4}^{y_{i}+s}$. Alice then in step (3.) performs a measurement
at a fork on qubits $4$ and $5$, conditioned on her own input $x_{i}$, and
obtains $\alpha_{i}=x_{i}+m_{4}+m_{5}$. From Equation (14a) and Equation
(14b), we see that the total conditional phase applied to the Referee’s qubit
$6$ from this step is
$Z_{6}^{x_{i}(y_{i}+s+1)+m_{4}+m_{5}}=Z_{6}^{x_{i}(y_{i}+s)+\alpha_{i}}$. In
steps (4.) and (6.), the pad $s$ informs the Referee and Bob the correct basis
to measure their respective qubits, in order to obtain a correlated outcome.
In more detail, the parties each measure their independent component of the
generator $X_{6}Z_{8}$ or $Y_{6}Y_{8}$, conditioned on whether $s=0$ or $s=1$,
respectively. Note that if $s=0$ the Referee’s measurement in step (4.)
decouples the remaining two qubits, shared between Alice and Bob, and leaves
Bob’s qubit invariant under the action of step (5.) That is, the combined
action of Alice and Bob in step (5.) produces a conditional phase
$Z_{8}^{sx_{i}}$ on Bob’s qubit. Hence, step (6.) produces a correlated
outcome between the parties’ measurements and prior phase information such
that

$(x_{i}(y_{i}+s)+\alpha_{i})+b_{i}+(sx_{i})+\beta_{i}=0.$ (15)

where we denote $b_{i}=m_{6}$ belonging to the Referee and $\beta_{i}=m_{8}$
belonging to Bob, and the Referee obtains

$b_{i}=x_{i}y_{i}+p_{i}\qquad\text{(where {\hbox{p_i=\alpha_i+\beta_i}})},$
(16)

as desired.

####  B.1.2  Stage II

Correctness is proved for Stage II in the same way as before, where now each
party is labeled by a $\mathbf{P}_{k}$, for $k=1,\cdots,N$. We again let
$\mathbf{m}=(m_{1},\cdots,m_{N},m_{\text{R}})$ represent the binary vector of
measurement outcomes from each party on the $N+1$-qubit graph state, depicted
in Figure 6. We note that the ordering of the labels need not be tied to a
particular photon emission ordering, as all the measurements performed commute
with each other and all classically communicated information need only be
shared after each party’s measurement.

We first recognize that each party is measuring an independent component of
the generator, $X_{\text{R}}Z_{1}\cdots Z_{N}$, of this graph state. This
implies for the Referee’s outcome $m_{\text{R}}$ that

$m_{\text{R}}+\sum_{k=1}^{N}m_{k}=0.$ (17)

This is equivalent to the notion that the measurement of each party
$\mathbf{P}_{k}$ in step (1.) introduces a conditional phase flip $Z^{m_{k}}$
on the Referee’s qubit, such that total action on the Referee’s qubit is
$\prod_{k}Z^{m_{k}}$. The Referee can determine the value of $p$ by adding
their outcome $m_{k}$ to the sum of the party’s announced
$\nu_{k}=\mu_{k}+m_{k}$, such that

$\displaystyle p$
$\displaystyle=m_{\text{R}}+\sum_{k=1}^{N}\nu_{k}=\sum_{i=1}^{\mathfrak{R}_{1}}(\alpha_{i}+\beta_{i})+\sum_{k=0}^{\mathfrak{R}_{2}}z_{i},$
(18)

and the output of the computation is achieved:

$f=p+\sum_{i=1}^{\mathfrak{R}_{1}}b_{i}=\sum_{i=1}^{\mathfrak{R}_{1}}x_{i}y_{i}+\sum_{i=1}^{\mathfrak{R}_{2}}z_{i}.$
(19)

###  B.2  Including Error Correction

In practice, each bit conjunction computed in Stage I of the protocol as well
as the final summation computed in Stage II will have some error. In this
section we describe a basic error correction method that can be employed to
suppress the overall computational error as much as desired.

Let $\epsilon_{*}$ denote the largest probability of a bit error in each
iteration of Stage I, and let $\Xi_{i}$ be the indicator variable for the
occurrence of an error in iteration $i$. Thus, while the noiseless protocol
generates bit value $b_{i}=x_{i}y_{i}+p_{i}$ in iteration $i$, the actual
implementation generates bit values

$b_{i}=x_{i}y_{i}+p_{i}+\Xi_{i}.$ (20)

To deal with this, the Referee can employ a simple repetition code. That is,
each iteration $i$ is repeated $K_{I}$ times, from which the Referee obtains
values $b_{(i,1)}$, $b_{(i,2)},\cdots,b_{(i,K_{I})}$, where
$b_{(i,j)}=x_{i}y_{i}+p_{(i,j)}+\Xi_{(i,j)}$. Recalling that
$p_{(i,j)}=\alpha_{(i,j)}+\beta_{(i,j)}$ is the sum of Alice and Bob’s private
bits, for each $j=2,\cdots,K_{I}$, Alice and Bob announce to the Referee
messages $\alpha_{(i,1)}+\alpha_{(i,j)}$ and $\beta_{(i,1)}+\beta_{(i,j)}$,
respectively. The Referee adds these to each corresponding $b_{(i,j)}$ so that
his $K_{I}$ bit values have the form $b_{(i,j)}=x_{i}y_{i}+p_{i}+\Xi_{(i,j)}$,
where $p_{i}=\alpha_{(i,1)}+\beta_{(i,1)}$. Note that each $\alpha_{(i,j)}$
and $\beta_{(i,j)}$ is an independent private random bit for Alice and Bob, so
the announcements of $\alpha_{(i,1)}+\alpha_{(i,j)}$ and
$\beta_{(i,1)}+\beta_{(i,j)}$ do not reveal any information about
$\alpha_{(i,1)}$ and $\beta_{(i,1)}$. The Referee then performs majority
voting on the bit values $b_{(i,j)}$, accepting the value appearing the most
among the $K_{I}$ sub-iterations. By Hoeffding’s inequality, this value will
be $b_{i}=x_{i}y_{i}+p_{i}$ with a bit error rate
$\delta\leq\exp[-2K_{I}(\tfrac{1}{2}-\epsilon_{*}-\tfrac{1}{2K_{I}})^{2}]$.
Then, the combined bit error rate in computing
$\sum_{i=1}^{\mathfrak{R}_{1}}b_{i}$ is equal to the probability that an odd
number of bit errors occur among the $b_{i}$. A counting argument shows this
probability to be

$\displaystyle\epsilon_{I}$
$\displaystyle=\frac{1}{2}[1-(1-2\delta)^{\mathfrak{R}_{1}}]\leq\delta\mathfrak{R}_{1}\leq\mathfrak{R}_{1}\cdot\exp[-2K_{I}(\tfrac{1}{2}-\epsilon_{*}-\tfrac{1}{2K_{I}})^{2}].$
(21)

Note that to suppress the bit error rate, the number of repetitions $K_{I}$
needed for each iteration $i$ is exponentially smaller than the total number
of iterations $\mathfrak{R}_{1}$.

Moving to Stage II, there will be a separate bit error rate $\epsilon_{+}$ in
the Referee’s computation of $p$ using the state $\ket{G_{II}}$. Again, a
repetition code can be used by repeating this step $K_{II}$ times and
achieving an overall bit error rate on $p$ of
$\epsilon_{II}\leq\exp[-2K_{II}(\tfrac{1}{2}-\epsilon_{+}-\tfrac{1}{2K_{II}})^{2}]$.
Therefore, the total error rate in computing $f$ is
$\epsilon_{I}+\epsilon_{II}-2\epsilon_{I}\epsilon_{II}$, which is
exponentially small in the repetitions $K_{I}$ and $K_{II}$. In particular, to
obtain a bit error probability $\epsilon_{f}$ on the computation of $f$ for
fixed $\epsilon_{*}$ and $\epsilon_{+}$, it suffices to take

$\displaystyle K_{I}$
$\displaystyle=\left\lceil\frac{1}{(\frac{1}{2}-\epsilon_{*})^{2}}\ln\sqrt{\frac{\mathfrak{R}_{1}}{\epsilon_{f}}}\right\rceil\leq\left\lceil\frac{1}{(\frac{1}{2}-\epsilon_{*})^{2}}\ln\left(\frac{MN}{\sqrt{2\epsilon_{f}}}\right)\right\rceil,$
(22a) $\displaystyle K_{II}$
$\displaystyle=\left\lceil\frac{1}{(\frac{1}{2}-\epsilon_{+})^{2}}\ln\sqrt{\frac{1}{\epsilon_{f}}}\right\rceil.$
(22b)

In total, the $N$-party computation of $f$ on each party’s $M$-bit input can
be implemented with error correction in our protocol at a lower bound unit
rate of

$\frac{R}{R_{0}}\geq\frac{MN}{4M^{2}N^{2}\left\lceil\frac{\ln\left(MN/\sqrt{2\epsilon_{f}}\right)}{\left(\tfrac{1}{2}-\epsilon_{*}\right)^{2}}\right\rceil+(N+1)\left\lceil\frac{\ln\left(1/\sqrt{\epsilon_{f}}\right)}{\left(\tfrac{1}{2}-\epsilon_{+}\right)^{2}}\right\rceil},$
(23)

where $R_{0}$ is the scheme-dependent average rate to add a new photon to a
graph state. For the HoD scheme we propose, $R_{0}=\eta_{e}R_{\text{rep}}$.

###  B.3  Security

Having established correctness of the proposed protocol, we now prove that it
is secure under the requirements defined in Section V. Recall, we demand as a
security condition that playing honestly does not reveal any more information
about one’s input than what can be inferred from the final function output. We
will show that this is true under the assumption that the Referee does not
collaborate with any of the parties by supplying them with side information.

In the first phase, each state
$\ket{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}$ is a tripartite state,
held by Alice, Bob, and the Referee. Suppose that Alice is playing honestly,
and a dishonest Bob is trying to learn about her input based on his local
quantum information and whatever Alice discloses in an honest execution of the
protocol. The only information he obtains in Stage I is the public message
$\gamma_{i}=x_{i}+m_{7}$ announced by Alice. Hence, suppose that Alice’s input
is described by the random variable $\mathbf{X}_{i}$ with values $x_{i}$
having a prior distribution $p(x_{i})$, which is known to all parties. Bob’s
initial state of knowledge of variable $\mathbf{X}_{i}$ given his share of
$\ket{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}$ is described by the
density matrix

$\displaystyle\sigma^{\mathbf{X}_{i}\mathbf{B}_{i}}$
$\displaystyle=\sum_{x_{i}=0}^{1}p(x_{i})\outerproduct{x_{i}}{x_{i}}^{\mathbf{X}_{i}}\otimes\tr_{\mathbf{A}_{i}\mathbf{R}}\left(\outerproduct{G_{I}}{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}\right).$
(24)

After Alice’s measurement and Bob’s learning of the value $\gamma_{i}$, his
updated state of knowledge conditioned on this new information is

$\sigma_{\gamma_{i}}^{\mathbf{X}_{i}\mathbf{B}_{i}}=\sum_{x_{i}=0}^{1}\sum_{m_{7}=0}^{1}p(x_{i},m_{7}|\gamma_{i})\outerproduct{x_{i}}{x_{i}}^{\mathbf{X}_{i}}\otimes\tr_{\mathbf{A}_{i}\mathbf{R}}\left(\outerproduct{m_{7}}{m_{7}}_{7}\outerproduct{G_{I}}{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}\right)/p(m_{7}).$
(25)

A calculation shows that

$\displaystyle\tr_{\mathbf{A}_{i}\mathbf{R}}\left(\outerproduct{m_{7}}{m_{7}}_{7}\outerproduct{G_{I}}{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}\right)$
$\displaystyle=\frac{\mathbb{I}_{2}}{2}\otimes\frac{\mathbb{I}_{3}}{2}\otimes\tr_{7}\left(\outerproduct{m_{7}}{m_{7}}_{7}\frac{\outerproduct{+0}{+0}_{78}+\outerproduct{-1}{-1}_{78}}{2}\right)$
(26)
$\displaystyle=\frac{1}{2}\left(\frac{\mathbb{I}_{2}}{2}\otimes\frac{\mathbb{I}_{3}}{2}\otimes\frac{\mathbb{I}_{8}}{2}\right)$
$\displaystyle=\frac{1}{2}\tr_{\mathbf{A}_{i}\mathbf{R}}\left(\outerproduct{G_{I}}{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}\right).$

In other words, the post-measurement state of Bob’s subsystem is independent
of Alice’s measurement outcome. Since $m_{7}$ is a uniform random bit
independent of $x_{i}$, we have $p(m_{7})=\frac{1}{2}$ and
$p(x_{i}|\gamma_{i})=p(x_{i})$. Thus,

$\displaystyle\sigma_{\gamma_{i}}^{\mathbf{X}_{i}\mathbf{B}_{i}}$
$\displaystyle=\sum_{x_{i}=0}^{1}\sum_{m_{i}=0}^{1}p(x_{i},m_{7}|\gamma_{i})\outerproduct{x_{i}}{x_{i}}^{\mathbf{X}_{i}}\otimes\tr_{\mathbf{A}_{i}\mathbf{R}}\left(\outerproduct{G_{I}}{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}\right)$
$\displaystyle=\sum_{x_{i}=0}^{1}p(x_{i})\outerproduct{x_{i}}{x_{i}}^{\mathbf{X}_{i}}\otimes\tr_{\mathbf{A}_{i}\mathbf{R}}\left(\outerproduct{G_{I}}{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}\right)$
$\displaystyle=\sigma^{\mathbf{X}_{i}\mathbf{B}_{i}}.$ (27)

This shows that Bob’s knowledge of Alice’s input does not change throughout
the course of Stage I. The same is also clearly true for Stage II since the
$\tr_{\mathbf{R}}\outerproduct{G_{II}}{G_{II}}=\frac{1}{2}(\outerproduct{+\cdots+}{+\cdots+}+\outerproduct{-\cdots-}{-\cdots-})$,
and so the measurement outcomes $m_{k}$ of the honest parties $\mathbf{P}_{k}$
measuring $Z$ are independent of each other and of the values $\mu_{k}$.
Therefore, the only new information Bob learns about Alice’s input comes
through the announcement of $f(\mathbf{x}_{1},\cdots,\mathbf{x}_{N})$ by the
Referee at the end of the protocol. A similar conclusion is reached in the
scenario of an honest Bob and a dishonest Alice.

Now we consider the Referee. Since there is no collusion with parties
$\mathbf{P}_{1},\cdots,\mathbf{P}_{k}$, from the Referee’s perspective, either
all parties are playing fairly or some are acting maliciously; in the latter
case, it is unknown who these parties are or what attacks they are employing.
Therefore, a corrupt Referee wanting to learn the inputs of one or more honest
parties should proceed by assuming that all parties are playing honestly. Like
before, in each iteration of
$\ket{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}$, the Referee’s initial
state and description of the variables $\mathbf{X}_{i}$ and $\mathbf{Y}_{i}$
is given by

$\displaystyle\sigma^{\mathbf{X}_{i}\mathbf{Y}_{i}\mathbf{R}}=\sum_{x_{i},y_{i}=0}^{1}$
$\displaystyle
p(x_{i})p(y_{i})\outerproduct{x_{i}}{x_{i}}^{\mathbf{X}_{i}}\otimes\outerproduct{y_{i}}{y_{i}}^{\mathbf{Y}_{i}}\otimes\tr_{\mathbf{A}_{i}\mathbf{B}_{i}}\left(\outerproduct{G_{I}}{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}\right).$
(28)

Note that tracing out qubits $2$, $4$, $5$, and $8$ completely dephases all
the remaining qubits in $\ket{G_{I}}$:

$\displaystyle\tr_{2,4,5,8}\left(\outerproduct{G_{I}}{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}\right)=\frac{\mathbb{I}_{1}}{2}\otimes\frac{\mathbb{I}_{3}}{2}\otimes\frac{\mathbb{I}_{6}}{2}\otimes\frac{\mathbb{I}_{7}}{2}.$
(29)

Hence,

$\displaystyle\tr_{\mathbf{A}_{i}\mathbf{B}_{i}}\left(\outerproduct{m_{3}}{m_{3}}_{3}\otimes\outerproduct{m_{7}}{m_{7}}_{7}\outerproduct{G_{I}}{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}\right)=\tr_{\mathbf{A}_{i}\mathbf{B}_{i}}\left(\outerproduct{G_{I}}{G_{I}}^{\mathbf{A}_{i}\mathbf{B}_{i}\mathbf{R}}\right)=\frac{\mathbb{I}_{1}}{2}\otimes\frac{\mathbb{I}_{6}}{2},$
(30)

from which it follows that Alice and Bob’s announcements of
$\gamma_{i}=x_{i}+m_{7}$ and $\delta_{i}=y_{i}+m_{3}$ reveal no information to
the referee about $x_{i}$ and $y_{i}$; i.e.
$\sigma^{\mathbf{X}_{i}\mathbf{Y}_{i}\mathbf{R}}=\sigma_{\gamma_{i},\delta_{i}}^{\mathbf{X}_{i}\mathbf{Y}_{i}\mathbf{R}}$.
Likewise, it is easy to see that in Stage II, the Referee’s reduced state is
completely mixed until all $N$ messages are received, at which point it
encodes the bit value $\sum_{k=1}^{N}m_{k}$.

Now since
$f=\sum_{k=1}^{N}(m_{k}+\nu_{k})+\sum_{i=1}^{\mathfrak{R}_{1}}b_{i}$, we have
that

$\displaystyle
p\left(\mathbf{x}_{1},\cdots,\mathbf{x}_{N}\bigg{|}\sum_{k}m_{k},\\{\nu_{k}\\}_{k},\\{b_{i}\\}_{i}\right)$
$\displaystyle=p\left(\mathbf{x}_{1},\cdots,\mathbf{x}_{N}|\\{\nu_{k}\\}_{k},\\{b_{i}\\}_{i},f\right)=p\left(\mathbf{x}_{1},\cdots,\mathbf{x}_{N}|f\right),$
(31)

where the last equality follows from the fact that the $\nu_{k}$ and $b_{i}$
are independent of the $\\{\mathbf{x}_{i}\\}_{i=1}^{N}$ due to the padded bits
from the measurements. Hence, the Referee’s knowledge of the inputs
$\\{\mathbf{x}_{i}\\}_{i=1}^{N}$ given the data
$(\sum_{k}m_{k},\\{\nu_{k}\\}_{k},\\{b_{i}\\}_{i})$ is equivalent to his
knowledge of the $\\{\mathbf{x}_{i}\\}_{i=1}^{N}$ given
$f(\mathbf{x}_{1},\cdots,\mathbf{x}_{N})$.

###  B.4  Self-testing of graph states

We can further secure the computation against an untrustworthy Source, via a
self-testing procedure, which allows the parties and the Referee to validate
the state distributed by the Source. If the parties indeed have the correct
state, measuring the independent components of a uniformly randomly chosen
stabilizer of the state will lead to a correlated outcome, hence implementing
a partial test of the state’s validity. By repeating the protocol and
partitioning rounds between these stabilizer tests, discarded rounds of
computation, and a single accepted target round of computation, the parties
can upper bound the probability of receiving the incorrect state during the
target round [52]. In implementing our multi-party protocol within our HoD
scheme for generating the requisite states, we require the set of
instructions, detailing which rounds to test, compute, and ultimately accept,
be a private source of shared randomness between the parties and the Referee.
This could be generated initially from a set of GHZ states distributed to the
participants in the computation [58]. Without knowledge of which rounds are
stabilizer tests and which are computations, the Source is prevented from
modifying the state they distribute in order to fool the participants during
rounds of self-testing. Conversely, the HoS scheme allows for the requisite
graph states to be produced prior to the measurement-based computation
protocol. Hence, the instruction set directing the participants when to self-
test can be decided after the state has already been generated. In these
schemes, we therefore do not require a distinct Source and Referee, at the
cost of necessitating memory—in requiring the full set of photonic states be
generated in advance, as well as additional rounds of self-testing [53].

##  Appendix C  Constructing graph states with “emit then add”

Building graph states in either of the HoS and HoD schemes necessitates
additional experimental overhead from typical deterministic quantum emitter-
based schemes, in both the number of qubits required and entangling operations
between them. We demonstrate through an inductive argument that these
additional resource costs scale at worst linearly. Subsequently, we present a
resource-efficient set of subroutines used to produce the requisite states for
our multi-party computation protocol, described in Section II. As the whole of
our protocol is Clifford, we can employ the HoD scheme to produce and measure
these graph states efficiently in practice, without the need for a quantum
memory. We briefly discuss how phase corrections, resulting from these
construction subroutines, are handled classical in this scheme. The
subroutines we introduce are thereafter employed in Appendix D to estimate the
fidelity to make the states used in our protocol. In what follows, a
superscript $(p)$, $(s)$, or $(e)$ denotes the kind of physical qubit
associated with the relevant subspace on which an operator acts on, as a
photon, auxiliary spin, or emitter, respectively.

###  C.1  Additional overhead

Let $\ket{G}$ define an existing graph state in which there is at least a
single edge between an auxiliary spin and the set of photons previously added
to the graph. We label each of these photons by an emission order
$1,\,\cdots,m-1$. Let $V_{m}$ define the additional vector space describing
the emitter and the next photon, $m$, to be added to the graph, both of which
start in $\ket{0}$. The set of generators which stabilizes the collective
vector space $V_{G}+V_{m}$, consisting of the graph and subsequent emitter-
photon pair, has the form

$S_{V_{G}+V_{m}}=\big{\langle}\cdots,\cdots Z_{k}^{(p)}\cdots
X^{(s)},Z^{(e)},Z_{m}^{(p)}\big{\rangle},$ (32)

where $\langle\cdots\rangle$ denotes a set of generators and the notation
$\cdots Z_{k}^{(p)}\cdots$ is used to keep track of an arbitrary edge between
the auxiliary spin and a photon previously added to the graph at some emission
step $k<m$. The subcircuit depicted in Figure 8 demonstrates an example of how
to transfer entanglement (or conditional phase information) from the emitter-
photon sub-system to $\ket{G}$, with a single two-qubit spin-spin entangling
gate and local complementation. In implementing the example, we transform the
stabilizer of the combined vector space in Equation (32) as

$\displaystyle S_{V_{G}+V_{m}}^{\prime}$
$\displaystyle=\big{\langle}\cdots,(-1)^{c_{m}}\cdots Z_{k}^{(p)}\cdots
X_{m}^{(p)}X^{(s)},(-1)^{c_{m}}Z_{m}^{(p)}Z^{(s)},(-1)^{c_{m}}Z^{(e)}\big{\rangle}$
(33)

where $c_{m}\in\\{0,1\\}$ is a classical bit value conditioned on the
measurement of the emitter.

The result of these operations produces the same stabilizer we would have
arrived at had we instead pumped the auxiliary spin itself. With these
additional operations, any graph state accessible in the deterministic scheme
can be constructed in the HoS or HoD schemes. As we restrict those auxiliary
spins already entangled with any previously added photons from being pumped,
it follows that one additional spin, the emitter, and one two-qubit spin-spin
entangling gate per photon in $G$ are the minimum additional overhead in our
proposed schemes for making arbitrary graph states. Furthermore, we can define
a new vector space $V_{G}^{\prime}$, containing the existing graph state and a
newly entangled photon, with a dimension that increases by one with each new
photon. The new space $V_{G}^{\prime}$ is stabilized by a unique set of
generators that can be rotated back to a graph state basis of the same general
form as Equation (32), now defined by a new graph state $\ket{G^{\prime}}$.

Figure 8:  A subcircuit equivalent to a $CX_{s,p}$ gate, up to a conditional
phase correction, for transferring entanglement (conditional phase
information) in our proposed HoS (HoD) scheme. This example “emit then add”
procedure replaces every pumping gate in typical deterministic schemes for
generating arbitrary photonic graph states. Entanglement (conditional phase
information) between a photon (p) and a coherently pumped emitter (e)
(represented by a red $CX_{e,p}$ gate) is exchanged to an auxiliary spin (s)
via a two-qubit entangling $CZ_{e,s}$ gate and local complementation. The
emitter is measured out thereafter and reinitialized for the next iteration of
the procedure. Rotations about $X$ and $Z$ are by $\pi/2$ and $-\pi/2$,
respectively, as noted in Equation (12). The measurement of the emitter is
with respect to the $Z$ basis. All previously added photons at iterations
$k<m$ are unaffected.

###  C.2  Construction subroutines

Figure 9:  Passing-subroutine for adding new photons to an existing graph,
$G$. (a) A graph transformation of passing a new photon (green) from the
emitter (red) to an auxiliary spin (black), which is connected to one or more
previously added photons (white, denoted with a double edge for the
multiplicity). This subroutine consists of two variations: (left) leaving all
previously added photons invariant, (right) transplanting those edges to the
newly added photon. (b) An example of how local complementations on a target
qubit (magenta circle) can be used to add or remove edges. (c) A quantum
subcircuit which implements the graph transformation. The right variation of
the graph transformation above is achieved with the additional two local
complementations (blue dashed line, depicting the deviation). Rotations and
measurements follow the same notation as in Figure 8.

We also offer a pair of subroutines that simplifies the construction and
overhead for the graph states $\ket{G_{I}}$ and $\ket{G_{II}}$, described in
Section V. Representations of the graph transformations associated with the
two subroutines, along with example circuits, are depicted in Figures 9 and
10. These transformations can be performed successively with no additional
operations, transforming the previous graph $G$ built on the auxiliary spin to
a new graph $G^{\prime}$ with any new photons sharing an edge to the auxiliary
spin. Despite their intended application in our MPC protocol, we make no
assumptions about the measurement of the photons in these subroutines, such
that they can be applied generally across experimental implementations.

One “passing”-subroutine, shown in Figure 9 consists of two variations: “join”
and “extend”. The join-subroutine adds a new photon to an existing graph and
leaves all previously existing edges invariant. The extend-subroutine
transfers all edges from the auxiliary spin to the new photon. The two are
achieved without or with the additional two local complementations depicted at
the end of the example circuit, respectively. Both variations only act on
previously added photons in the neighborhood of the auxiliary spin, $N_{s}$.
Repeatedly applying the join-subroutine or extend-subroutine on a single
auxiliary spin produces a star graph or linear cluster state, respectively for
each variation.

We note briefly that in practice with each implementation of the passing-
subroutine, the newly added photon to the graph carries a conditional phase
that is a byproduct of the decoupling measurement made on the emitter, as
shown in Equation (33). This byproduct phase determines the precise basis
state of the graph and may require correction for general MBQCs. In the HoD
scheme, photons are measured before they are decoupled from the emitter and
hence any requisite phase corrections need be commuted after each measurement.
The Clifford nature of the computations employed in our MPC simplifies all of
these corrections to bit flips that can be handled classically. Furthermore,
correction of this phase is not always necessary as certain measurements made
by the parties destroy this phase information, while other measurements allow
the parties to absorb this phase information into their own pad. Conversely,
conditional measurements, such as the ones made by Alice in step (4.) of Stage
I of our protocol, couple these byproduct phases to the phase information
input into the computation. Therefore, classical communication is required
here between Alice and the Source. A simple solution is for the Source to make
public the outcomes of each of these decoupling measurements.

The other “patching”-subroutine, shown in Figure 10, serves to attach two
subgraphs $G_{1}$ and $G_{2}$ by a common edge between photons. This process
requires additional two-qubit spin-spin entangling gates from the passing-
subroutine. For further simplicity we only consider the case where $G_{1}$ and
$G_{2}$ each have a single edge to all previously added photons in their
respective subgraphs. Operations in this subroutine are restricted locally to
only the emitter, spin, and the two photons we ultimately require to share an
edge, labeled in the figure by arbitrary emission steps $j,k$ in
$1,\cdots,n_{p}$. This subroutine mirrors the one employed in the production
of large 2D cluster states in [5], and can be applied in either scheme we
propose for the same purpose.

Figure 10:  Patching-subroutine for attaching two subgraphs $G_{1}$ and
$G_{2}$ by a common edge between photons. (a) The graph transformation
depicting the patching. (b) The corresponding circuit diagram. Additional two-
qubit spin-spin entangling gates are required for this subroutine, over the
passing-subroutine. Rotations follow the same notation as in Figure 8. (c) A
2D cluster state built on an array of auxiliary spins. Edges can be generated
between photons in the layer neighboring the array of spins with this
patching.

Application of these subroutines to the construction of the graph states
discussed in Section V is straightforward. The state $\ket{G_{I}}$, consisting
of $n_{p}=8$ photons, labeled by an emission ordering depicted in Figure 5,
can be built following the sequence of steps in Build I. This procedure
requires $11$ two-qubit spin-spin entangling gates in total: $8$ from passing
operations, and $3$ from a single patching step, as we are patching between
the final two photons in each subgraph and can therefore neglect the fourth
spin-spin entangling gate in the subroutine. It is known that the sequential
nature of photon emission events imparts an ordering on the graph state,
limiting the kinds of photonic graphs accessible by construction on a single
quantum emitter [59]. The private nature of the padded AND being computed in
Stage I sets a nontrivial emission ordering, which, following the results of
[32], requires two auxiliary spins to construct. The state $\ket{G_{II}}$,
consisting of $n_{p}=N+1$ photons for an $N$ party computation, can be
constructed entirely out of the passing-subroutine on a single auxiliary spin.
This graph state can be built following Build II. Trivially, this construction
requires $N+1$ two-qubit spin-spin entangling gates.

Build I. $\ket{G_{I}}.$ Input: A photon emission order labeling photons
$(p_{1}),\cdots,(p_{8})$, corresponding to the $n_{p}=8$ photons in
$\ket{G_{I}}$, an emitting spin, and two auxiliary spins, labeled $(s_{1})$
and $(s_{2})$.

  1. 1.

Pass photon $(p_{1})$ to auxiliary spin $(s_{1})$ with join.

  2. 2.

Pass photons $(p_{2})$ and $(p_{3})$ to $(s_{1})$, utilizing extend for
$(p_{2})$ and join for $(p_{3})$.

  3. 3.

Repeat the previous step for photons $(p_{4})$ and $(p_{5})$.

  4. 4.

Pass photon $(p_{6})$ to $(s_{1})$ with extend.

  5. 5.

Pass photons $(p_{7})$ and $(p_{8})$ to auxiliary spin $(s_{2})$, utilizing
join for $(p_{7})$ and extend for $(p_{8})$.

  6. 6.

Patch subgraphs on $(s_{2})$ and $(s_{1})$.

Build II. $\ket{G_{II}}$. Input: A photon emission order labeling photons
$(p_{1}),\cdots,(p_{N}),(p_{R})$, corresponding to the $n_{p}=N+1$ photons in
$\ket{G_{II}}$, an emitting spin, and a single auxiliary spin, labeled $(s)$.

  1. 1.

Pass photons $(p_{1}),\cdots,(p_{N})$ to the auxiliary spin $(s)$ with join,
where photon $(p_{k})$ is routed to party $k$.

  2. 2.

Pass the final photon $(p_{R})$, belonging to the Referee, to $(s)$ with
extend.

##  Appendix D  Experimentally realizable fidelity calculations

We now consider an experimental realization of our schemes for constructing
the graph states utilized in our multi-party computation. While the nature of
the herald and the computation itself are device-independent, we assume here
trapped ions as our quantum emitters and auxiliary spins, due to their high-
fidelity benchmarks for two-qubit spin-spin entangling gates [12, 13] and
reasonable collection efficiency with high-NA optics [14]. We outline our
fidelity model for two schemes; the HoS scheme involving the heralding of a
Bell state between an emitter and a photon for general cases involving non-
destructive heralding of photons, and the HoD scheme where emitter photons are
measured directly in the basis required for the measurement-based computation
protocol.

###  D.1  Experimental apparatus

For the HoS scheme, heralding a Bell state between an emitter and photon is
implemented via entanglement swapping between a photon from an emitter and a
photon from a nonlinear pair source. We use spontaneous parametric down
conversion (SPDC) as our pair source for the heralding. SPDC is an optical
process based on a crystal with $\chi^{(2)}$ nonlinearity whereby a photon
from a pump is converted to a signal and idler photon pair of lower energy. It
is often used to produce entangled photon pairs in various degrees of freedom,
or as a heralded single photon source [28]. The joint measurement apparatus
required for the entanglement swapping in the heralding scheme we describe
here can be accomplished via a generalized Hong-Ou-Mandel interferometer [60]
depicted in Figure 11(a), where the emitter photon and signal photon from the
pair source are sent to a 50:50 beamsplitter. Elements from these experiments
are modeled in our estimates of the fidelity to successfully produce graph
states.

Figure 11:  Entanglement swapping in the HoS scheme. (a) Schematic of a
generalized Hong-Ou-Mandel interferometer applied as a joint measurement
apparatus. A photon entangled with an emitter is sent through port $a$ of the
beamsplitter, and a photon from a spontaneous parametric down conversion
(SPDC) photon pair source is sent through port $b$. Detection of two single-
photon orthonormal states $\ket{u}$, $\ket{v}$ in either output ports $c$ or
$d$ results in entanglement between the emitter and the idler photon from the
pair source. Various loss factors denoted by $\eta$ are modeled. Additional
elements for qubit rotations are not shown. (b) Probability tree showing the
outcomes of a Bell state measurement attempt. The “success” probability
$P_{s}$ for the Bell state measurement denotes the probability of measuring a
set of specific click patterns that indicate entanglement swapping. $P_{t}$
denotes the probability of projecting the emitter and idler onto a Bell state
per measurement attempt.

We briefly consider the set of states employed in heralding a Bell state in a
device-independent form. The internal state of an emitter $(e)$ is entangled
with a photon $(p_{e})$ in an arbitrary basis, and an entangled photon pair is
produced from the SPDC source labeled as the signal $(p_{s})$ and idler
$(p_{i})$ photons. We can express both the idealized entangled states
$\ket{\Psi_{E}}$ and $\ket{\Psi_{P}}$, respectively, as

$\displaystyle\ket{\Psi_{E}}$
$\displaystyle=\dfrac{1}{\sqrt{2}}(\ket{0}^{(e)}\ket{1;0}^{(p_{e})}-\ket{1}^{(e)}\ket{0;1}^{(p_{e})}),$
(34) $\displaystyle\ket{\Psi_{P}}$
$\displaystyle=\dfrac{1}{\sqrt{2}}(\ket{1;0}^{(p_{s})}\ket{0;1}^{(p_{i})}-\ket{0;1}^{(p_{s})}\ket{1;0}^{(p_{i})}),$
(35)

where $\ket{0}^{(e)}$ and $\ket{1}^{(e)}$ is the computational basis for the
emitter, and the notation $\ket{m;n}$ is used to denote the photonic Fock
state representation for a particular basis $\\{\ket{u},\ket{v}\\}$, such as
orthogonal polarizations, with $m$ in $\ket{u}$ and $n$ in $\ket{v}$. The
relationship between the input modes $a$ and $b$ and output modes $c$ and $d$
of the 50:50 beamsplitter can be described by the unitary transformation on
the creation operators
$\hat{a}^{\dagger}=\frac{1}{\sqrt{2}}(\hat{c}^{\dagger}+\hat{d}^{\dagger})$
and
$\hat{b}^{\dagger}=\frac{1}{\sqrt{2}}(\hat{c}^{\dagger}-\hat{d}^{\dagger})$.
With the emitter photon entering port $a$, and the signal photon entering port
$b$, the overall state after applying the transformation can be expressed in
the form

$\begin{split}\ket{\Psi_{E}}\ket{\Psi_{P}}=&\dfrac{(\hat{c}^{\dagger}_{u})^{2}-(\hat{d}^{\dagger}_{u})^{2}}{4}\ket{vac}_{c,d}\ket{0}^{(e)}\ket{0;1}^{(p_{i})}+\dfrac{\hat{d}^{\dagger}_{u}\hat{d}^{\dagger}_{v}-\hat{c}^{\dagger}_{u}\hat{c}^{\dagger}_{v}}{2\sqrt{2}}\ket{vac}_{c,d}\ket{\Psi^{+}}^{(e,p_{i})}\\\
+&\dfrac{\hat{c}^{\dagger}_{u}\hat{d}^{\dagger}_{v}-\hat{c}^{\dagger}_{v}\hat{d}^{\dagger}_{u}}{2\sqrt{2}}\ket{vac}_{c,d}\ket{\Psi^{-}}^{(e,p_{i})}+\dfrac{(\hat{c}^{\dagger}_{v})^{2}-(\hat{d}^{\dagger}_{v})^{2}}{4}\ket{vac}_{c,d}\ket{1}^{(e)}\ket{1;0}^{(p_{i})},\end{split}$
(36)

where

$\ket{\Psi^{\pm}}^{(e,p_{i})}=\dfrac{1}{\sqrt{2}}(\ket{0}^{(e)}\ket{1;0}^{(p_{i})}\pm\ket{1}^{(e)}\ket{0;1}^{(p_{i})}).$
(37)

We are interested in projecting onto either $\ket{\Psi^{+}}^{(e,p_{i})}$ or
$\ket{\Psi^{-}}^{(e,p_{i})}$ which can be realized by detecting specific click
patterns on photon counting detectors at the output ports capable of resolving
the orthonormal components. From Equation (36), we can see that detecting
orthonormal one-photon states in either ports $c$ or $d$ results in a
projection onto $\ket{\Psi^{+}}^{(e,p_{i})}$ while detection in opposite ports
results in $\ket{\Psi^{-}}^{(e,p_{i})}$. The overall probability of projection
onto either of the Bell states is $\frac{1}{2}$ for each heralded measurement
attempt. Upon the detection of $\ket{\Psi^{-}}^{(e,p_{i})}$, we can perform a
qubit rotation to produce the state $\ket{\Psi^{+}}^{(e,p_{i})}$ for phase
consistency. We can then perform a series of one- and two-qubit gates to add a
photon to a graph. Upon failure to detect the correct detection pattern, we
reinitialize the emitter and photon pair and attempt the measurement again. We
assume number-resolving detectors at the output ports of the beamsplitter
capable of detecting photons in the basis $\\{\ket{u},\ket{v}\\}$. For
example, two polarizing beamsplitters and four detectors would be used after
the output ports for photons entangled in a polarization basis.

The initial state of the emitter can be described by the state defined in
Equation (34). The output state of SPDC is a multi-mode squeezed state where
the photon pair production probability is dependent on the pump amplitude.
Assuming a classical pump, we take the Hamiltonian for the SPDC process to
approximately be of the form [33, 61]

$\hat{H}=e^{i\phi}\kappa\hat{K}^{\dagger}+e^{-i\phi}\kappa\hat{K},$ (38)

where
$\hat{K}^{\dagger}=\hat{a}_{u;s}^{\dagger}\hat{a}_{v;i}^{\dagger}-\hat{a}_{v;s}^{\dagger}\hat{a}_{u;i}^{\dagger}$
represents the creation of entangled signal and idler pairs denoted $s$ and
$i$ in the basis $\\{\ket{u},\ket{v}\\}$. The time evolution operator
$\hat{U}(t)=\exp(i\hat{H}t/\hbar)$ yields the resulting state

$\ket{\Psi_{SPDC}}=N\sum_{n=0}^{\infty}\tanh^{n}{r}\sum_{m=0}^{n}(-1)^{m}\ket{n-m;m}^{(p_{s})}\ket{m;n-m}^{(p_{i})},$
(39)

where $r=\kappa t/\hbar$ is the interaction parameter that is dependent on the
pump field amplitude, $t$ is the interaction time of the pump through the
crystal, and $N$ is the normalization constant with $N=1-\tanh^{2}{r}$. By
tuning the interaction parameter $r$, we can change the probability of
producing a single pair ($n=1$ in Equation (39) leading to Equation (35)) to
optimize the fidelity of the HoS scheme. Note that increasing the pump power
also increases the relative contribution of the higher order terms ($n>1$),
which increases the probability of detecting multiple photon pairs.

The above is applicable for polarization-entangled photon pairs directly
produced in type-II SPDC described in refs. [33, 61]; the output state and
choice of degree-of-freedom for entanglement will of course be dependent on
the specific properties of the photon pair source and pump. However, we note
that we are assuming the pump can be treated as a classical, single-mode
source, and we use a simplified Hamiltonian and output state for the photon
pairs entangled in $\\{\ket{u},\ket{v}\\}$. Moreover, factors such as the
multi-modal nature of the pump, phase differences or instabilities between the
orthonormal components in the optical path, or distinguishability between the
photons from the emitter and the SPDC source can degrade the fidelity of the
scheme.

###  D.2  Sources of infidelity

Several experimentally relevant sources of infidelity are considered in our
model. Photonic loss and detector dark counts can induce false heralding
events, leading to a failure to resolve a true Bell state and subsequent
addition of a photon to the graph. Decoherence across the emitter and any
auxiliary spins utilized in building the graph will produce errors on any
computation done on the graph state. The fidelity of each two-qubit spin-spin
entangling gate performed in the construction is considered as well. We can
also consider the fidelity of the initial entanglement between the emitter and
its photon, as well as the entanglement of the photon pair, used in the
entanglement swapping procedure.

####  D.2.1  Photonic loss

We use the standard approach to modeling photonic losses, which is to
introduce a fictitious beamsplitter with transmittance $\eta$ and reflectance
$1-\eta$ on the lossy channel. This is equivalent to applying the
transformation on the creation operator
$\hat{a}^{\dagger}=\sqrt{\eta}\hat{a}_{T}^{\dagger}+\sqrt{1-\eta}\hat{a}_{R}^{\dagger}$
[62] where $T$ and $R$ denote the transmitted and reflected paths,
respectively. The Fock state $\ket{n}$ serving as the input transforms as
$\ket{n}\rightarrow\sum_{k=0}^{n}\sqrt{\binom{n}{k}\eta^{n-k}(1-\eta)^{k}}\ket{n-k}_{T}\ket{k}_{R}$
and the reflected path is traced out. We assume, for simplicity, that $\eta$
is independent of the photonic degrees of freedom for each loss channel
modeled. Applying this to an emitter with an initial state given by Equation
(34) and performing the partial trace over the reflected path, the resulting
density matrix $\hat{\rho}_{E}$ for the emitter-photon pair incorporating
losses is

$\displaystyle\hat{\rho}_{E}=$
$\displaystyle\dfrac{1}{2}(1-\eta_{e})\outerproduct{0}{0}^{(e)}\otimes\outerproduct{vac}{vac}^{(p_{e})}+\dfrac{1}{2}(1-\eta_{e})\outerproduct{1}{1}^{(e)}\otimes\outerproduct{vac}{vac}^{(p_{e})}$
(40)
$\displaystyle\quad\quad+\dfrac{1}{2}\eta_{e}\outerproduct{0}{0}^{(e)}\otimes\outerproduct{1;0}{1;0}^{(p_{e})}+\dfrac{1}{2}\eta_{e}\outerproduct{1}{1}^{(e)}\otimes\outerproduct{0;1}{0;1}^{(p_{e})}$
$\displaystyle\quad\quad-\dfrac{1}{2}\eta_{e}\outerproduct{0}{1}^{(e)}\otimes\outerproduct{1;0}{0;1}^{(p_{e})}-\dfrac{1}{2}\eta_{e}\outerproduct{1}{0}^{(e)}\otimes\outerproduct{0;1}{1;0}^{(p_{e})}.$

Similarly, the density matrix for the SPDC source $\hat{\rho}_{SPDC}$ becomes

$\begin{split}\hat{\rho}_{SPDC}=&\sum_{n,n^{*}=0}^{\infty}\sum_{m=0}^{n}\sum_{m^{*}=0}^{n^{*}}\sum_{k_{s},k^{{}^{\prime}}_{i}=0}^{\text{min}\\{n-m,n^{*}-m^{*}\\}}\sum_{k^{{}^{\prime}}_{s},k_{i}=0}^{\text{min}\\{m,m^{*}\\}}c_{n,m,k_{s},k^{{}^{\prime}}_{s},k_{i},k^{{}^{\prime}}_{i}}c^{*}_{n^{*},m^{*},k_{s},k^{{}^{\prime}}_{s},k_{i},k^{{}^{\prime}}_{i}}\\\
&\ket{n-m-
k_{s};m-k^{{}^{\prime}}_{s}}\bra{n^{*}-m^{*}-k_{s};m^{*}-k^{{}^{\prime}}_{s}}^{(p_{s})}\\\
\otimes&\ket{m-k_{i};n-m-k^{{}^{\prime}}_{i}}\bra{m^{*}-k_{i};n^{*}-m^{*}-k^{{}^{\prime}}_{i}}^{(p_{i})},\end{split}$
(41)

where

$\begin{split}c_{n,m,k_{s},k^{{}^{\prime}}_{s},k_{i},k^{{}^{\prime}}_{i}}=(1-\xi)(\sqrt{\xi})^{n}(-1)^{m}\sqrt{\binom{n-m}{k_{s}}\binom{m}{k_{s}^{{}^{\prime}}}\binom{m}{k_{i}}\binom{n-m}{k^{{}^{\prime}}_{i}}\eta_{s}^{n-k_{s}-k^{{}^{\prime}}_{s}}(1-\eta_{s})^{k_{s}+k^{{}^{\prime}}_{s}}\eta_{i}^{n-k_{i}-k^{{}^{\prime}}_{i}}(1-\eta_{i})^{k_{i}+k^{{}^{\prime}}_{i}}},\end{split}$
(42)

and we have used $\xi=\tanh^{2}{r}$. Here, we have made the additional
substitutions $\eta_{e}=\eta^{{}^{\prime}}_{e}\eta_{det}(\lambda_{e})$ and
$\eta_{s}=\eta^{{}^{\prime}}_{s}\eta_{det}(\lambda_{s})$, where $\eta_{e}$ and
$\eta_{s}$ are the combined collection and photodetection efficiencies for the
emitter and signal photons, respectively, in the interferometry setup.
$\eta^{\prime}$ accounts for the collection efficiency of the optical path as
shown in Figure 11(a), and $\eta_{det}(\lambda)$ is the photodetection
efficiency which may be wavelength dependent (in the joint measurement, we
require $\lambda_{e}=\lambda_{s}$). $\eta_{i}=\eta_{i}^{{}^{\prime}}$ is the
collection efficiency of the idler for the SPDC setup, neglecting user-
specific losses such as transmission losses through an optical fiber network
and imperfect detection from the user. Since we are interested in retrieving
the photon from the emitter and a single pair from the SPDC source for
entanglement swapping, under the loss model the resulting probabilities for
$\ket{\Psi_{E}}$ and $\ket{\Psi_{P}}$ as defined in Equation (34) and Equation
(35) are

$\displaystyle\bra{\Psi_{E}}\hat{\rho}_{E}\ket{\Psi_{E}}$
$\displaystyle=\eta_{e},$ (43)
$\displaystyle\bra{\Psi_{P}}\hat{\rho}_{SPDC}\ket{\Psi_{P}}$
$\displaystyle=\dfrac{\eta_{s}\eta_{i}\xi(\bar{\eta}_{s}\bar{\eta}_{i}\xi+2)(1-\xi)^{2}}{(1-\bar{\eta}_{s}\bar{\eta}_{i}\xi)^{4}},$
(44)

where $\bar{\eta}_{e}=1-\eta_{e}$, $\bar{\eta}_{s}=1-\eta_{s}$, and
$\bar{\eta}_{i}=1-\eta_{i}$.

####  D.2.2  Photodetector metrics

In this work, we provide practical estimates of the fidelity achievable using
photon number-resolving detectors for entanglement swapping. We assume each
detector in the setup has some efficiency $\eta_{det}$ and also model dark
counts which arise due to inherent electronic noise in a detector. Each dark
count event is assumed to be independent and generated at a constant rate
$R_{d}$ cps, and typically dark count rates can be low ($<10^{-2}$ cps) for
single-photon detectors such as Transition Edge Sensors [63]. Furthermore, we
assume the exposure time of the detectors, $t_{\text{exp}}$ is much longer
than the time scale over which dark counts emerge. The probability for $n_{d}$
dark counts on a detector during each measurement cycle can then be
approximated by a Poisson distribution [64]

$P_{d}(n_{d})=e^{-R_{d}t_{\text{exp}}}\dfrac{(R_{d}t_{\text{exp}})^{n_{d}}}{n_{d}!}.$
(45)

The joint measurement in the heralding involves the use of detectors in output
ports $c$ and $d$ in Figure 11. Therefore, we need to consider the effect of
four detection outcomes for the herald – two detectors each with two
orthonormal results, and the probability of dark counts for each. We assume
identical dark count distributions for the detectors used in the herald.

####  D.2.3  Entanglement swapping and heralded success probability

A successful herald occurs at a probability which we define as $P_{s}$. For
the HoD scheme, $P_{s}=\eta_{e}$ as we perform additional single and two-qubit
operations on a graph only when the photon from the emitter is successfully
measured. In the HoS scheme, $P_{s}$ is the probability of detecting the set
of detector click patterns requisite for the entanglement swap.

An extra source of infidelity for the heralded Bell state measurement occurs
from the joint measurement itself. We define $P_{t}$ as the overall
probability of projecting the idler photon and emitter onto a Bell state for
each joint measurement attempt. The probabilities are indicated in Figure
11(b). This will be a function of the detection efficiencies of the photons as
well as the probability of zero dark count events detected. From Equation
(43), Equation (44), and Equation (45), $P_{t}$ is given by

$\displaystyle P_{t}(\eta_{e},\eta_{s},\eta_{i},\xi)$
$\displaystyle=\dfrac{1}{2}\bra{\Psi_{E}}\hat{\rho}_{E}\ket{\Psi_{E}}\bra{\Psi_{P}}\hat{\rho}_{SPDC}\ket{\Psi_{P}}P^{4}_{d}(0)$
(46)
$\displaystyle=\dfrac{1}{2}\dfrac{\eta_{e}\eta_{s}\eta_{i}\xi(\bar{\eta}_{s}\bar{\eta}_{i}\xi+2)}{(1-\bar{\eta}_{s}\bar{\eta}_{i}\xi)^{4}}(1-\xi)^{2}P^{4}_{d}(0).$

The heralded success probability $P_{s}$ for the joint measurement is
conditioned on a detection pattern representing the orthonormality of the
photon states after the beamsplitter. This is a source of infidelity as the
joint detection of states such as $\ket{0;0}^{(p_{e})}\ket{1;1}^{(p_{s})}$,
representing two signal photons that are orthonormal to each other from the
photon pair source and no photons from the emitter, possible due to detection
or collection losses, would not result in entanglement swapping. We can
identify the set of states that would result in a “success”:

$S=\\{\ket{1;0}^{(p_{e})}\ket{0;1}^{(p_{s})},\ket{0;1}^{(p_{e})}\ket{1;0}^{(p_{s})},\ket{0;0}^{(p_{e})}\ket{1;1}^{(p_{s})}\\}$
(47)

For each state in the set $S$, dark counts can lead to a false detection of
the state. For example, the state $\ket{1;0}^{(p_{e})}\ket{0;1}^{(p_{s})}$
with zero dark counts is indistinguishable from the state
$\ket{1;0}^{(p_{e})}\ket{0;0}^{(p_{s})}$ with one dark count falsely
attributed to the measurement of a signal photon in the state
$\ket{0;1}^{(p_{s})}$. The former has an additional associated dark count
probability of $P^{4}_{d}(0)$ and the latter $P_{d}(1)P^{3}_{d}(0)$. Thus, we
can compute $P_{s}$ by considering the probability of measuring all states in
$S$ and all dark count combinations and photon number states that reconstruct
each element of $S$. By taking the partial trace of the emitter and idler
photon from Equation (40) and Equation (41), and considering the probabilities
mentioned in the overall set of joint measurement outcomes, we arrive at the
probability $P_{s}$ for the joint measurement,

$\displaystyle P_{s}(\eta_{e},\eta_{s},\xi)=$
$\displaystyle\dfrac{3\bar{\eta}_{e}}{(1-\bar{\eta}_{s}\xi)^{2}}(1-\xi)^{2}P^{2}_{d}(1)P^{2}_{d}(0)$
$\displaystyle+$
$\displaystyle\left[\dfrac{\eta_{e}}{(1-\bar{\eta}_{s}\xi)^{2}}+\dfrac{4\bar{\eta}_{e}\eta_{s}\xi}{(1-\bar{\eta}_{s}\xi)^{3}}\right](1-\xi)^{2}P_{d}(1)P^{3}_{d}(0)$
$\displaystyle+$
$\displaystyle\left[\dfrac{\eta_{e}\eta_{s}\xi}{(1-\bar{\eta}_{s}\xi)^{3}}+\dfrac{\bar{\eta}_{e}\eta^{2}_{s}\xi^{2}}{(1-\bar{\eta}_{s}\xi)^{4}}\right](1-\xi)^{2}P^{4}_{d}(0).$
(48)

In this paper, we consider the case where heralding is repeated until a
“success” is flagged for each idler photon added to the graph. Thus, the
fidelity of the entanglement swapping procedure is
$F_{\text{swap}}=P_{t}/P_{s}$.

####  D.2.4  Decoherence

The emitter used to generate photons, as well as any auxiliary spins entangled
with an existing graph, will dephase across the duration until they are
measured and projected back onto a known state. For an emitter or auxiliary
spin represented by a density matrix $\hat{\rho}$, we model the dephasing
process via the map

$\hat{\rho}\to\mathcal{D}(\hat{\rho};t,\tau)=\frac{1}{2}(1+e^{-t/\tau})\hat{\rho}+\frac{1}{2}(1-e^{-t/\tau})Z\hat{\rho}Z,$
(49)

where $\tau$ is the coherence time of the emitter or auxiliary spin and $t$ is
a timescale for the dephasing process. Clearly this process leaves the state
invariant with probability $\tfrac{1}{2}(1+e^{-t/\tau})$, or conjugates it by
$Z$ with probability $\tfrac{1}{2}(1-e^{-t/\tau})$. It is straightforward to
verify that this map describes a Markovian process such that

$\mathcal{D}(\hat{\rho};t_{1}+t_{2},\tau)=\mathcal{D}(\hat{\rho};t_{2},\tau)\circ\mathcal{D}(\hat{\rho};t_{1},\tau).$
(50)

We assume that each attempted herald happens on a short, regular timescale
$t_{\text{rep}}=R_{\text{rep}}^{-1}$, which is simply the inverse repetition
rate of the experiment. Furthermore, we assume each qubit gate operation time
is near-instantaneous compared to $t_{\text{rep}}$, so that the dephasing
takes place during the attempted herald only. As the emitter is measured out
and reinitialized with each cycle of the experiment, it is evident that it
will only dephase for at most $t_{\text{rep}}$. This implies that for each
photon added to the graph, the contribution to the graph state fidelity from
the decoherence of the emitter is
$\tfrac{1}{2}(1+e^{-t_{\text{rep}}/\tau_{e}})$, such that

$F_{D}^{(e)}(n_{p})=\left(\frac{1}{2}\left(1+e^{-t_{\text{rep}}/\tau_{e}}\right)\right)^{n_{p}},$
(51)

is the total contribution towards building an $n_{p}$-photon graph state, and
$\tau_{e}$ is the coherence time for the emitter.

We now model the contribution to the final state fidelity from any auxiliary
spins in the system, which dephase for the entirety of their presence in the
graph. Consider a mixed state density operator
$\hat{\rho}_{n}=\sum_{\lambda}p_{\lambda}\outerproduct{\Phi_{\lambda}}{\Phi_{\lambda}}$,
described by a convex combination of $n$-qubit pure stabilizer states
$\ket{\Phi_{\lambda}}$, where $p_{\lambda}$ are the corresponding classical
probabilities. This could represent the mixture of states one expects for an
existing graph state built on a set of auxiliary spins, when under the action
of its environment—including the prior action of the dephasing map itself. The
system is initially stabilized by a set of generators
$S_{\ket{\Phi_{\lambda}}}=\langle
g_{1,\lambda},g_{2,\lambda},\cdots,g_{n,\lambda}\rangle$. Under the dephasing
map the state evolves as

$\mathcal{D}^{(s)}(\hat{\rho}_{n};t,\tau_{s})=\frac{1}{2}(1+e^{-t/\tau_{s}})\sum_{\lambda}p_{\lambda}\outerproduct{\Phi_{\lambda}}{\Phi_{\lambda}}+\frac{1}{2}(1-e^{-t/\tau_{s}})\sum_{\lambda}p_{\lambda}Z^{(s)}\outerproduct{\Phi_{\lambda}}{\Phi_{\lambda}}Z^{(s)},$
(52)

which is once again a convex combination of stabilizer states with generators

$\displaystyle S_{\ket{\Phi_{\lambda}}}$ $\displaystyle=\langle
g_{1,\lambda},g_{2,\lambda},\cdots,g_{n,\lambda}\rangle,$ $\displaystyle
S_{Z^{(s)}\ket{\Phi_{\lambda}}}$ $\displaystyle=\langle
Z^{(s)}g_{1,\lambda}Z^{(s)},Z^{(s)}g_{2,\lambda}Z^{(s)},\cdots,Z^{(s)}g_{n,\lambda}Z^{(s)}\rangle.$
(53)

$\tau_{s}$ is the coherence time of the auxiliary spins in the system, which
we treat as identical. Since we are interested in graph states,
$\hat{\rho}_{G=(V,E)}=\outerproduct{G}{G}$, whose stabilizers are generated by
the operators $\\{K_{a}\\}_{a\in V}$ defined in Equation (8), the dephasing
map only acts on the generators proportional to $X^{(s)}$, for any auxiliary
spin $(s)$ in the system. Hence, a graph state consisting of $n_{p}$ photons
and $n_{s}$ auxiliary spins would evolve under the dephasing map as the
mixture

$\mathcal{D}^{(s)}(\hat{\rho}_{G};t,\tau_{s})=\sum_{\mathbf{b}\in\mathbb{Z}_{2}^{n_{s}}}p(\mathbf{b})\outerproduct{G_{\mathbf{b}}}{G_{\mathbf{b}}},$
(54)

where $\mathbf{b}=(b_{1},b_{2},\cdots,b_{n_{s}})\in\mathbb{Z}_{2}^{n_{s}}$ and

$p(\mathbf{b})=\frac{1}{2^{n_{s}}}\prod_{i=1}^{n_{s}}(1+(-1)^{b_{i}}e^{-t/\tau_{s}}).$
(55)

This mixture is stabilized by the set of generators,

$S_{\ket{G_{\mathbf{b}}}}=\langle
K_{1}^{(p)},\cdots,K_{n_{p}}^{(p)},(-1)^{b_{1}}K_{1}^{(s)},\cdots,(-1)^{b_{n_{s}}}K_{n_{s}}^{(s)}\rangle.$
(56)

The size of the system’s stabilizer grows by one with each new photon $m$
added to the graph. For the passing-subroutines we employ in Appendix C.2, we
apply this rule, however in choosing either variation of the subroutine we
choose whether to rotate the auxiliary spin out of the basis of the dephasing
map, and consequentially project the system onto a new mixed state as
described above. That is for the $m^{\text{th}}$ photon, we generate a new
subgroup of the stabilizer as either

$\displaystyle S_{\ket{G},\text{join}-m}$
$\displaystyle=\langle(-1)^{b_{k}}\cdots Z_{k}^{(p)}\cdots
Z_{m}^{(p)}X^{(s)},X_{m}^{(p)}Z^{(s)}\rangle,$ (57a) $\displaystyle
S_{\ket{G},\text{extend}-m}$ $\displaystyle=\langle(-1)^{b_{k}}\cdots
Z_{k}^{(p)}\cdots X_{m}^{(p)}Z^{(s)},Z_{m}^{(p)}X^{(s)}\rangle.$ (57b)

Here, the bit conditioning phase $b_{k}$ is applied to the generator $K^{(s)}$
during the creation of the $k^{\text{th}}$ photon, with $k<m$. If we allow the
system to continue dephasing, these subgroups evolve, distinctly, as

$\displaystyle S_{\ket{G_{\mathbf{b}}},\text{join}-m}$
$\displaystyle=\langle(-1)^{b_{k}+b_{m}}\cdots Z_{k}^{(p)}\cdots
Z_{m}^{(p)}X^{(s)},X_{m}^{(p)}Z^{(s)}\rangle,$ (58a) $\displaystyle
S_{\ket{G_{\mathbf{b}}},\text{extend}-m}$
$\displaystyle=\langle(-1)^{b_{k}}\cdots Z_{k}^{(p)}\cdots
X_{m}^{(p)}Z^{(s)},(-1)^{b_{m}}Z_{m}^{(p)}X^{(s)}\rangle.$ (58b)

We see that in the case of executing the extend-subroutine on $m^{\text{th}}$
photon, the number of states in the mixture doubles, whereas in the case of
the join-subroutine, the symmetry between states where either $b_{k}=b_{m}$ or
$b_{k}\neq b_{m}$ leads to an effective mixture the same size as it was prior
to the $m^{\text{th}}$ photon’s addition. Furthermore, we can express the
probability for each state in the mixture in terms of $b_{k}$ and $b_{m}$ as

$P(b_{k},b_{m})=\frac{1}{4}\left(1+(-1)^{b_{k}}e^{-t_{k}/\tau_{s}}\right)\left(1+(-1)^{b_{m}}e^{-t_{m}/\tau_{s}}\right).$
(59)

where we have defined $t_{k}$ and $t_{m}$ as arbitrary times from the
probabilistic nature of the herald. For the join-subroutine, the graph state
remains unchanged when $b_{k},b_{m}=0$ or $b_{k},b_{m}=1$, whereas, for the
extend-subroutine, the graph state remains unchanged only when
$b_{k},b_{m}=0$. Hence, the fidelity under the dephasing model scales as
$\frac{1}{2}(1+e^{-(t_{k}+t_{m})/\tau_{s}})$ for the join-subroutine and
$\frac{1}{4}(1+e^{-t_{k}/\tau_{s}})(1+e^{-t_{m}/\tau_{s}})$ for the extend-
subroutine for iterations $k$ and $m$. This is a subtle distinction that
arises from the Markovian nature of the dephasing map when implementing the
join-subroutine. It implies the final state fidelity when constructing graph
states on a set of auxiliary spins will in general depend on the sequence
describing how each photon is passed into the system. In contrast, we assume
$t_{\text{rep}}\ll\tau_{s}$ in our estimates, such that this distinction is
not necessary, as
$\frac{1}{4}(1+e^{-t_{k}/\tau_{s}})(1+e^{-t_{m}/\tau_{s}})\approx\frac{1}{2}(1+e^{-(t_{k}+t_{m})/\tau_{s}})$.
We provide estimates where $t_{\text{rep}}/\tau_{s}$ is of order
$10^{-7}-10^{-9}$ [31, 10]. It is nonetheless important to discuss, when
considering auxiliary spins with shorter coherence times or constructing
exceedingly large graph states, where the time to build the graph is of order
the coherence time.

Lastly, we account for the probabilistic nature of the herald. Building graph
states using either scheme we propose can be viewed as a Bernoulli trial with
success probability $P_{s}$ occurring at regular intervals $t_{\text{rep}}$.
The cumulative probability that $m$ trials yields $r$ successes is given by
the distribution

$h(m,r,P_{s})=\binom{m-1}{r-1}P_{s}^{r}(1-P_{s})^{m-r},$ (60)

where $m=r,r+1,r+2,\cdots$. For any auxiliary spins in the graph, any failure
to herald adds an additional $t_{\text{rep}}$ to the dephasing time.
Therefore, we model the mean contribution to the state fidelity for an
auxiliary spin with $r$ photons passed to it under either passing-subroutine
as

$\displaystyle\langle F_{D}^{(s)}(r,P_{s})\rangle$
$\displaystyle=\sum_{m=r}^{\infty}h(m,r,P_{s})\left(\frac{1}{2}\left(1+e^{-mt_{\text{rep}}/\tau_{s}}\right)\right)$
(61)
$\displaystyle=\dfrac{1}{2}\left(1+\left(\dfrac{P_{s}}{P_{s}+e^{t_{\text{rep}}/\tau_{s}}-1}\right)^{r}\right)$
$\displaystyle\approx\dfrac{1}{2}\left(1+e^{-rt_{\text{rep}}/P_{s}\tau_{s}}\right),$

where $\langle\cdots\rangle$ here denotes a classical expectation value, and
$t_{\text{rep}}/P_{s}$ is the average time for a successful herald. Note in
the HoD scheme, $P_{s}=\eta_{e}$, whereas in the HoS scheme it is of the form
in Equation (48). For an $n_{p}$-photon graph state, we take $r$ up to the
number of photons that a given auxiliary spin remains a part of the graph.
Here, we consider the same coherence times for the emitter and auxiliary
spins, $\tau_{e}=\tau_{s}=\tau$. Given state-of-art of trapped ion experiments
[10], we take the dephasing timescale to be $t_{\text{rep}}/\tau=10^{-9}$ in
our best estimates.

####  D.2.5  Gates

Single-qubit gates applied to photons, the emitter and any auxiliary spins are
assumed to be perfect in our model. For all two-qubit spin-spin entangling
gates, we assume a fidelity $F_{CZ}=0.999$ in our best estimates, in line with
benchmarks from state-of-the-art trapped ion experiments [12, 13]. We assume
the time to implement any single-qubit or two-qubit gate, $t_{\text{gate}}\ll
t_{\text{rep}}$, and can therefore be treated as instantaneous.

####  D.2.6  Initial entanglement fidelity

In practice, there will be a non-unit fidelity on initializing the emitter
onto the state described in Equation (34) as well as Equation (35) for the
pair source. The additional contribution to the overall fidelity using our
schemes, as compared to schemes where an emitter is directly used to generate
graphs, is the entanglement fidelity of the nonlinear photon pair source in
our HoS scheme. For example, the main contribution to the degradation of
polarization-based entanglement fidelity for a single photon pair in SPDC
comes from the spatial-temporal profile of the pump [65] and its interaction
with the specific nonlinear medium, in which different spatial and spectral or
temporal components impart different relative phases to the entangled pair
described by Equation (35). The fidelity can be optimized by using
compensating crystals or filtering techniques; however, the latter also lowers
the collection efficiency. Nevertheless, some of the best estimated fidelities
for polarization-entangled SPDC sources range from $\sim$97% to $\sim$99.7%
for various free-space and fiber-based setups [66, 67, 68]. In terms of
overall fidelity estimations, we can introduce additional scaling terms
similar to the gate fidelity described above. We denote the initial
entanglement fidelities for the emitter photon and photon-photon pair as
$F_{e}$ and $F_{p}$, respectively. We focus primarily on the fidelity from the
SPDC source to highlight the additional infidelity from our scheme.

###  D.3  Pair generation rate optimization

Given the infidelity from false heralds, defined in Equations 46 and 48, there
exists a trade-off between the rate and fidelity at which large graph states
can be generated in the HoS scheme, as set by the dimensionless parameter
$\xi$, controlling the pair generation rate of the SPDC source. Decreasing
$\xi$ improves the probability of heralding a true Bell state, at the cost of
longer average times between successful heralds. Conversely, the effects of
decoherence on any auxiliary spins in the system, through Equation (61),
reduces the fidelity of the graph state, as the overall construction time
increases. Hence, there is an optimum rate at which HoS can run, controlled by
$\xi$ and parameterized by the relevant total collection and detection
efficiencies $\\{\eta_{e},\eta_{s},\eta_{i}\\}$, dark count rate, $R_{d}$,
dephasing timescale, $t_{\text{rep}}/\tau$, number of auxiliary spins,
$n_{s}$, and total number of photons, $n_{p}$, required by the graph. Given a
fixed set of parameters, this is a straightforward scalar maximization problem
that can be accomplished numerically. If necessary, one can optimize within
some $\epsilon$ of the optimum in order to achieve a speed-up in the rate.

###  D.4  Example applications

We briefly demonstrate how the sources of infidelity, presented in Appendix
D.2, are combined to produce the fidelity estimates discussed in Sections IV
and V. We note from the above that this fidelity is a mean estimate, optimized
over $\xi$. For the estimates discussed in our work, we assume a negligible
dark count rate, and let $\eta_{s}=\eta_{i}=1$. In practice the signal photon
collection efficiency can be near unity [31], and only makes a minor impact on
the rate and fidelity that does not affect the overall scaling of either
function, relative to the other relevant parameters. We carry out the
optimization numerically, and determine $\xi$ which achieves the optimum
fidelity, when considering estimates in our HoS scheme.

####  D.4.1  GHZ states and cluster states

In Section IV, we present the mean final state fidelity to generate arbitrary
graph states, requiring a single auxiliary spin in either of our schemes, such
as the $n_{p}$-photon star graph, which is local-unitary equivalent to a GHZ
state, or a 1D cluster state. For these graph states we optimize a function of
the form

$F_{n_{s}=1}(\xi;n_{p},\eta_{e})=\left(F_{\text{ent}}F_{\text{swap}}(\xi;\eta_{e})\right)^{n_{p}}F_{D}^{(e)}(n_{p})\langle
F_{D}^{(s)}\left(n_{p},P_{s}(\eta_{e},\xi)\right)\rangle.$ (62)

Here, we have defined $F_{\text{ent}}=F_{CZ}F_{p}$ to combine the spin-spin
entangling gate and photon pair entanglement fidelities, respectively. In
Figure 4, we compare the effects of false heralds and decoherence against the
limits imposed by imperfect spin-spin gate and initial SPDC photon pair
entanglement fidelities, and hence set $F_{\text{ent}}=1$ when computing
estimates in the false herald and decoherence limited regimes. In the
decoherence limited regime we additionally set $F_{\text{swap}}=1$ and
subsequently do not require optimization. Computing the fidelity to make these
states in our schemes with perfect spin-spin entangling gates and initial
photon pair entanglement assumes that additional error-correction or
purification is employed.

####  D.4.2  Multi-party computation

For the MPC introduced in Section V, fidelity estimates for the generation of
$\ket{G_{I}}$ and $\ket{G_{II}}$ are required to estimate the total bit error
probability in Stage I and II, respectively. We assume graph states
constructed in the HoD scheme discussed in Section III, where the computation
of $f$ happens in parallel with the construction of each state, and no pair
source or photonic memory is required. In this scheme we take
$P_{s}=\eta_{e}=0.4$, from trapped ion experiments utilizing parabolic
reflectors [17]. Additionally, we assume a dephasing timescale
$t_{\text{rep}}/\tau=10^{-9}$, following the best estimates for trapped ions
[10]. The production of arbitrarily large graph states using our scheme is
predominately limited by the spin-spin entangling gate fidelity and photon
pair entanglement fidelity, $F_{CZ}$ and $F_{p}$, respectively. However, for a
fixed number of parties $N$, the size of the required graph states for our
protocol is also fixed. For each iteration of Stage I, the Source is required
to generate a copy of the 8-qubit graph state, $\ket{G_{I}}$, depicted in
Figure 5. From Equation (51) and Equation (61), the mean fidelity to produce
each copy of the state is

$F_{G_{I}}=F_{\text{ent}}^{8}F_{CZ}^{3}F_{D}^{(e)}(8)\langle
F_{D}^{(s_{1})}(8,\eta_{e})\rangle\langle F_{D}^{(s_{2})}(2,\eta_{e})\rangle,$
(63)

where we have defined again $F_{\text{ent}}=F_{CZ}F_{p}$. We note additional
spin-spin entangling gates are required to make this graph state, as compared
to Equation (62). In Stage II, the source distributes a single copy of the
$N+1$-qubit graph state, $\ket{G_{II}}$, depicted in Figure 6, where $N$ is
number of parties involved in the computation. The mean fidelity to produce
this state is

$F_{G_{II}}(N)=F_{\text{ent}}^{N+1}F_{D}^{(e)}(N+1)\langle
F_{D}^{(s)}(N+1,\eta_{e})\rangle,$ (64)

which is equivalent to fidelity in Equation (62), upon setting $n_{p}=N+1$.

## References

  * Raussendorf and Briegel [2001] R. Raussendorf and H. J. Briegel, Phys. Rev. Lett. 86, 5188 (2001).
  * Browne and Rudolph [2005] D. E. Browne and T. Rudolph, Phys. Rev. Lett. 95, 010501 (2005).
  * Lindner and Rudolph [2009] N. H. Lindner and T. Rudolph, Phys. Rev. Lett. 103, 113602 (2009).
  * Economou  _et al._ [2010] S. E. Economou, N. Lindner, and T. Rudolph, Phys. Rev. Lett. 105, 093601 (2010).
  * Russo  _et al._ [2019] A. Russo, E. Barnes, and S. E. Economou, New Journal of Physics 21, 055002 (2019).
  * Hilaire  _et al._ [2023] P. Hilaire, L. Vidro, H. S. Eisenberg, and S. E. Economou, Quantum 7, 992 (2023).
  * Zhan and Sun [2020] Y. Zhan and S. Sun, Physical Review Letters 125, 223601 (2020).
  * Cogan  _et al._ [2023] D. Cogan, Z.-E. Su, O. Kenneth, and D. Gershoni, Nature Photonics 17, 324–329 (2023).
  * Bluvstein  _et al._ [2022] D. Bluvstein, H. Levine, G. Semeghini, T. T. Wang, S. Ebadi, M. Kalinowski, A. Keesling, N. Maskara, H. Pichler, M. Greiner, V. Vuletić, and M. D. Lukin, Nature 604, 451–456 (2022).
  * Wang  _et al._ [2021] P. Wang, C.-Y. Luan, M. Qiao, M. Um, J. Zhang, Y. Wang, X. Yuan, M. Gu, J. Zhang, and K. Kim, Nature communications 12, 1 (2021).
  * Evered  _et al._ [2023] S. J. Evered, D. Bluvstein, M. Kalinowski, S. Ebadi, T. Manovitz, H. Zhou, S. H. Li, A. A. Geim, T. T. Wang, N. Maskara, H. Levine, G. Semeghini, M. Greiner, V. Vuletić, and M. D. Lukin, Nature 622, 268–272 (2023).
  * Srinivas  _et al._ [2021] R. Srinivas, S. C. Burd, H. M. Knaack, R. T. Sutherland, A. Kwiatkowski, S. Glancy, E. Knill, D. J. Wineland, D. Leibfried, A. C. Wilson, D. T. C. Allcock, and D. H. Slichter, Nature 597, 209–213 (2021).
  * Clark  _et al._ [2021] C. R. Clark, H. N. Tinkey, B. C. Sawyer, A. M. Meier, K. A. Burkhardt, C. M. Seck, C. M. Shappert, N. D. Guise, C. E. Volin, S. D. Fallek, H. T. Hayden, W. G. Rellergert, and K. R. Brown, Physical Review Letters 127, 10.1103/physrevlett.127.130505 (2021).
  * Shu  _et al._ [2011] G. Shu, C.-K. Chou, N. Kurz, M. R. Dietrich, and B. B. Blinov, J. Opt. Soc. Am. B 28, 2865 (2011).
  * Hucul  _et al._ [2015] D. Hucul, I. V. Inlek, G. Vittorini, C. Crocker, S. Debnath, S. M. Clark, and C. Monroe, Nature Physics 11, 37 (2015).
  * Chou  _et al._ [2017] C.-K. Chou, C. Auchter, J. Lilieholm, K. Smith, and B. Blinov, Review of Scientific Instruments 88 (2017).
  * Maiwald  _et al._ [2012] R. Maiwald, A. Golla, M. Fischer, M. Bader, S. Heugel, B. Chalopin, M. Sondermann, and G. Leuchs, Physical Review A 86, 043431 (2012).
  * Kinos  _et al._ [2021] A. Kinos, D. Hunger, R. Kolesov, K. Mølmer, H. de Riedmatten, P. Goldner, A. Tallaire, L. Morvan, P. Berger, S. Welinski, _et al._ , arXiv preprint arXiv:2103.15743 (2021).
  * Yanagimoto  _et al._ [2023] R. Yanagimoto, R. Nehra, R. Hamerly, E. Ng, A. Marandi, and H. Mabuchi, PRX Quantum 4, 010333 (2023).
  * Economou  _et al._ [2006] S. E. Economou, L. J. Sham, Y. Wu, and D. G. Steel, Phys. Rev. B 74, 205415 (2006).
  * Gimeno-Segovia  _et al._ [2019] M. Gimeno-Segovia, T. Rudolph, and S. E. Economou, Phys. Rev. Lett. 123, 070501 (2019).
  * Rieländer  _et al._ [2016] D. Rieländer, A. Lenhard, M. Mazzera, and H. De Riedmatten, New Journal of Physics 18, 123013 (2016).
  * Covey  _et al._ [2023] J. P. Covey, H. Weinfurter, and H. Bernien, npj Quantum Information 9, 10.1038/s41534-023-00759-9 (2023).
  * Ward and Keller [2022] T. Ward and M. Keller, New Journal of Physics 24, 123028 (2022).
  * Krutyanskiy  _et al._ [2023] V. Krutyanskiy, M. Galli, V. Krcmarsky, S. Baier, D. A. Fioretto, Y. Pu, A. Mazloom, P. Sekatski, M. Canteri, M. Teller, J. Schupp, J. Bate, M. Meraner, N. Sangouard, B. P. Lanyon, and T. E. Northup, Phys. Rev. Lett. 130, 050803 (2023).
  * Jayakumar  _et al._ [2014] H. Jayakumar, A. Predojević, T. Kauten, T. Huber, G. S. Solomon, and G. Weihs, Nature Communications 5, 10.1038/ncomms5251 (2014).
  * Senellart  _et al._ [2017] P. Senellart, G. Solomon, and A. White, Nature Nanotechnology 12, 1026–1039 (2017).
  * Schneeloch  _et al._ [2019] J. Schneeloch, S. H. Knarr, D. F. Bogorin, M. L. Levangie, C. C. Tison, R. Frank, G. A. Howland, M. L. Fanto, and P. M. Alsing, Journal of Optics 21, 043501 (2019).
  * Zhang  _et al._ [2021] C. Zhang, Y.-F. Huang, B.-H. Liu, C.-F. Li, and G.-C. Guo, Advanced Quantum Technologies 4, 2000132 (2021).
  * Pan  _et al._ [1998] J.-W. Pan, D. Bouwmeester, H. Weinfurter, and A. Zeilinger, Physical review letters 80, 3891 (1998).
  * Ramelow  _et al._ [2013] S. Ramelow, A. Mech, M. Giustina, S. Gröblacher, W. Wieczorek, J. Beyer, A. Lita, B. Calkins, T. Gerrits, S. W. Nam, _et al._ , Optics express 21, 6707 (2013).
  * Li  _et al._ [2022] B. Li, S. E. Economou, and E. Barnes, npj Quantum Information 8, 10.1038/s41534-022-00522-6 (2022).
  * Lamas-Linares  _et al._ [2001] A. Lamas-Linares, J. C. Howell, and D. Bouwmeester, Nature 412, 887 (2001).
  * Sangouard  _et al._ [2011] N. Sangouard, B. Sanguinetti, N. Curtz, N. Gisin, R. Thew, and H. Zbinden, Physical review letters 106, 120403 (2011).
  * Vitullo  _et al._ [2018] D. L. P. Vitullo, M. G. Raymer, B. J. Smith, M. Karpiński, L. Mejling, and K. Rottwitt, Phys. Rev. A 98, 023836 (2018).
  * Zhong  _et al._ [2018] H.-S. Zhong, Y. Li, W. Li, L.-C. Peng, Z.-E. Su, Y. Hu, Y.-M. He, X. Ding, W. Zhang, H. Li, L. Zhang, Z. Wang, L. You, X.-L. Wang, X. Jiang, L. Li, Y.-A. Chen, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, Phys. Rev. Lett. 121, 250505 (2018).
  * Houshmand  _et al._ [2018] M. Houshmand, M. Houshmand, and J. F. Fitzsimons, Phys. Rev. A 98, 012318 (2018).
  * Raussendorf  _et al._ [2003] R. Raussendorf, D. E. Browne, and H. J. Briegel, Phys. Rev. A 68, 022312 (2003).
  * Browne  _et al._ [2007] D. E. Browne, E. Kashefi, M. Mhalla, and S. Perdrix, New Journal of Physics 9, 250–250 (2007).
  * Bartolucci  _et al._ [2023] S. Bartolucci, P. Birchall, H. Bombín, H. Cable, C. Dawson, M. Gimeno-Segovia, E. Johnston, K. Kieling, N. Nickerson, M. Pant, F. Pastawski, T. Rudolph, and C. Sparrow, Nature Communications 14, 10.1038/s41467-023-36493-1 (2023).
  * Löbl  _et al._ [2024] M. C. Löbl, S. Paesani, and A. S. Sørensen, Quantum 8, 1302 (2024).
  * Pant  _et al._ [2019] M. Pant, D. Towsley, D. Englund, and S. Guha, Nature communications 10, 1070 (2019).
  * Reichle  _et al._ [2006] R. Reichle, D. Leibfried, E. Knill, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland, Nature 443, 838 (2006).
  * Eisaman  _et al._ [2011] M. D. Eisaman, J. Fan, A. Migdall, and S. V. Polyakov, Review of scientific instruments 82, 071101 (2011).
  * Yao [1982] A. C. Yao, in  _23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)_ (1982) pp. 160–164.
  * Goldreich  _et al._ [1987] O. Goldreich, S. Micali, and A. Wigderson, in  _Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC ’87_, STOC ’87 (ACM Press, 1987).
  * Zhao  _et al._ [2019] C. Zhao, S. Zhao, M. Zhao, Z. Chen, C.-Z. Gao, H. Li, and Y.-a. Tan, Information Sciences 476, 357–372 (2019).
  * Beaver [1992] D. Beaver, Efficient multiparty protocols using circuit randomization, in  _Lecture Notes in Computer Science_ (Springer Berlin Heidelberg, 1992) p. 420–432.
  * Nielsen  _et al._ [2012] J. B. Nielsen, P. S. Nordholt, C. Orlandi, and S. S. Burra, A new approach to practical active-secure two-party computation, in  _Advances in Cryptology – CRYPTO 2012_ (Springer Berlin Heidelberg, 2012) p. 681–700.
  * Damgård  _et al._ [2012] I. Damgård, V. Pastro, N. Smart, and S. Zakarias, Multiparty computation from somewhat homomorphic encryption, in  _Advances in Cryptology – CRYPTO 2012_ (Springer Berlin Heidelberg, 2012) p. 643–662.
  * Choudhury and Patra [2017] A. Choudhury and A. Patra, IEEE Transactions on Information Theory 63, 428–468 (2017).
  * Takeuchi  _et al._ [2019] Y. Takeuchi, A. Mantri, T. Morimae, A. Mizutani, and J. Fitzsimons, npj Quantum Information 5, 10.1038/s41534-019-0142-2 (2019).
  * Unnikrishnan and Markham [2022] A. Unnikrishnan and D. Markham, Phys. Rev. A 105, 052420 (2022).
  * Meesala  _et al._ [2024] S. Meesala, S. Wood, D. Lake, P. Chiappina, C. Zhong, A. D. Beyer, M. D. Shaw, L. Jiang, and O. Painter, Nature Physics , 1 (2024).
  * Mittal  _et al._ [2017] S. Mittal, V. V. Orre, A. Restelli, R. Salem, E. A. Goldschmidt, and M. Hafezi, Physical Review A 96, 043807 (2017).
  * Luo  _et al._ [2015] K.-H. Luo, H. Herrmann, S. Krapick, B. Brecht, R. Ricken, V. Quiring, H. Suche, W. Sohler, and C. Silberhorn, New Journal of Physics 17, 073039 (2015).
  * Hein  _et al._ [2004] M. Hein, J. Eisert, and H. J. Briegel, Phys. Rev. A 69, 062311 (2004).
  * Baccari  _et al._ [2020] F. Baccari, R. Augusiak, I. Šupić, J. Tura, and A. Acín, Physical Review Letters 124, 10.1103/physrevlett.124.020402 (2020).
  * Schön  _et al._ [2005] C. Schön, E. Solano, F. Verstraete, J. I. Cirac, and M. M. Wolf, Physical Review Letters 95, 10.1103/physrevlett.95.110503 (2005).
  * Braunstein and Mann [1995] S. L. Braunstein and A. Mann, Phys. Rev. A 51, R1727 (1995).
  * Kok and Braunstein [2000] P. Kok and S. L. Braunstein, Phys. Rev. A 61, 042304 (2000).
  * Leonhardt and Paul [1995] U. Leonhardt and H. Paul, Progress in Quantum Electronics 19, 89 (1995).
  * Shah  _et al._ [2022] R. Shah, K.-S. Isleif, F. Januschek, A. Lindner, and M. Schott, Journal of Low Temperature Physics 209, 355–362 (2022).
  * Lee  _et al._ [2004] H. Lee, U. Yurtsever, P. Kok, G. M. Hockney, C. Adami, S. L. Braunstein, and J. P. Dowling, Journal of Modern Optics 51, 1517 (2004).
  * Rangarajan  _et al._ [2009] R. Rangarajan, M. Goggin, and P. Kwiat, Opt. Express 17, 18920 (2009).
  * Jabir and Samanta [2017] M. V. Jabir and G. K. Samanta, Scientific Reports 7, 12613 (2017).
  * Steinlechner  _et al._ [2013] F. Steinlechner, S. Ramelow, M. Jofre, M. Gilaberte, T. Jennewein, J. P. Torres, M. W. Mitchell, and V. Pruneri, Opt. Express 21, 11943 (2013).
  * Medic  _et al._ [2010] M. Medic, J. B. Altepeter, M. A. Hall, M. Patel, and P. Kumar, Opt. Lett. 35, 802 (2010).