{'fraction_non_alphanumeric': 0.04309551561253911, 'fraction_numerical': 0.019538678608674316, 'mean_word_length': 4.161890436985434, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Resource analysis for quantum-aided Byzantine agreement with the four-qubit singlet state

In distributed computing, a Byzantine fault is a condition where a component behaves inconsistently, showing different symptoms to different components of the system. Consensus among the correct components can be reached by appropriately crafted communication protocols even in the presence of byzantine faults. Quantum-aided protocols built upon distributed entangled quantum states are worth considering, as they are more resilient than traditional ones. Based on earlier ideas, here we establish a parameter-dependent family of quantum-aided weak broadcast protocols. We compute upper bounds on the failure probability of the protocol, and define and illustrate a procedure that minimizes the quantum resource requirements. Following earlier work demonstrating the suitability of noisy intermediate scale quantum (NISQ) devices for the study of quantum networks, we experimentally create our resource quantum state on publicly available quantum computers. Our work highlights important engineering aspects of the future deployment of quantum communication protocols with multi-qubit entangled states.

In distributed computing, a Byzantine fault is a condition where a component behaves inconsistently, showing different symptoms to different components of the system. Consensus among the correct components can be reached by appropriately crafted communication protocols even in the presence of byzantine faults. Quantum-aided protocols built upon distributed entangled quantum states are worth considering, as they are more resilient than traditional ones. Based on earlier ideas, here we establish a parameter-dependent family of quantum-aided weak broadcast protocols. We compute upper bounds on the failure probability of the protocol, and define and illustrate a procedure that minimizes the quantum resource requirements. Following earlier work demonstrating the suitability of noisy intermediate scale quantum (NISQ) devices for the study of quantum networks, we experimentally create our resource quantum state on publicly available quantum computers. Our work highlights important engineering aspects of the future deployment of quantum communication protocols with multi-qubit entangled states.

Introduction
In distributed computing, a Byzantine fault is a condition where a component behaves inconsistently, show-ing different symptoms to different components of the system. To reach consensus among the correctly functioning components, communication protocols resilient to such faults must be used. An early example of such protocols was developed by Pease et al. [1]. That protocol provides consensus if t < n/3, where n is the number of components in the distributed system, and t is the maximum number of components exhibiting Byzantine fault. For example, if the maximum number of faulty components is 1, then at least 4 components are needed to reach consensus. We will refer to this property of the protocol as resilience. The efficiency of early protocols [1,2] has since been improved [3][4][5][6].
Quantum-aided 'weak broadcast' protocols developed in the past two decades, built upon distributed entangled quantum states [7] such as the four-qubit singlet state [8,9], are worth considering, as they offer a higher resilience: t faulty components are tolerated as long as t < n/2. For example, to be resilient against t = 1 faulty component, having n = 3 components is sufficient.
In this work, we build on those earlier ideas, and introduce a parameter-dependent family of quantumaided weak broadcast protocols that relies on an entangled four-qubit singlet state [8]. Our main contributions are as follows.
(1) Proof. We prove the weak broadcast functionality of the protocol in a certain range of protocol parameters. The proof relies on considering the failure probability p f (m) as the function of the number m of resource states, and upper bounding this failure probability exponentially, that is, proving p f ≤ e −bm with a certain b > 0 as m → ∞.
(2) Tight upper bound for failure probability. We compute a tight upper bound to the failure probability of the protocol, as function of the number of quantum states used to broadcast a single classical bit.
(3) Resource optimisation. We use the tight upper bound to perform a resource optimisation, i.e., compute the answer to these questions: (i) For a given allowed failure probability, how to set the protocol parameters to minimise the number of resource states? (ii) What is the number of required resources states?
(4) Preparation of the four-qubit singlet state. Following earlier work demonstrating the suitability of noisy intermediate-scale quantum (NISQ) devices for the study of quantum networks [10], we experimentally create our resource quantum state on the public quantum-computer prototypes of IBM and IonQ, and characterise its state fidelity.
In a spirit similar to a recent study [11] of an alternative quantum-aided protocol [12], our analysis illustrates multiple engineering aspects of future deployment of such protocols in practice.
The rest of the paper is structured as follows. In Sec. 2, we define a two-parameter weak broadcast protocol based on the four-qubit singlet state. In Sec. 3, we prove the functionality of the protocol. In Sec. 4, we outline how to compute the tight upper bound for the failure probability, and discuss the resource optimisation protocol. In Sec. 5, we construct two four-qubit quantum circuits that can be used to generate the singlet state, and implement those circuits on IBM's quantum computer devices. We discuss our results and follow-up ideas, and draw conclusions, in Sec. 6.

A two-parameter Weak Broadcast protocol
Multi-party communication protocols exist for various functionalities. Two examples are broadcast and weak broadcast [13]. An important building block for more complex protocols is a weak broadcast protocol that is resilient up to one faulty component in the presence of 3 components. Following Ref. [13], we will denote such protocols as WBC(3,1). A key result of Ref. [13] is that WBC(3,1) can be used as a primitive, to efficiently build a broadcast protocol with n ≥ 3 components, resilient against any t < n/2 faulty components. This motivates us to define and study a protocol achieving WBC(3,1). In a distributed system with 3 components, the WBC(3,1) protocol has the following goal: the sender (S) wants to distribute a single bit x S ∈ {0, 1} of classical information to the two receivers R 0 and R 1 , in such a way that there is a consensus about the bit value even if one of the three components is an active adversary. More formally, in a WBC(3,1) protocol, the output of the receivers can take a value ⊥ (often called 'abort') besides 0 and 1, and the protocol should fulfill the conditions of 'Validity' and 'Consistency'. Validity means that if the Sender S is correct (i.e., exactly follows the prescribed protocol), then the output bit values of all correct components are equal to x S . Consistency means that if any correct component has an output y ∈ {0, 1}, then all other correct components should have an output from {y, ⊥}. (See a more detailed description in Appendix A.) The two-parameter WBC(3,1) protocol we define here is derived from similar protocols in earlier works [7][8][9]. It prescribes communication between three components (S, R 0 , R 1 ) to achieve consensus in the sense of WBC(3,1) described above. The quantum resource of this protocol is a four-qubit singlet state [8]: In fact, we assume that to achieve WBC(3,1) with a single data bit, the parties have distributed m ∈ Z + four-qubit singlet states through public quantum channels such that the first two qubits are distributed to S, the third qubit is distributed to R 0 , and the last qubit is distributed to R 1 , as shown in Fig. 1a.
In rough terms, the more four-qubit singlet states are used to broadcast one bit, the higher the probability of success; hence the integer m is a key quantity in assessing the performance of the protocol.
Having m singlet states distributed, the components perform measurements in the computational basis, each obtaining its own random list of bit values: S obtains m bit-pairs, while R 0 and R 1 obtain m bits each. An example for such a collection of random correlated bitstrings for m = 12 is shown in Fig. 1b, and the probability density function of the six possible outcomes of four-bit strings, derived straightforwardly from Eq. (1), is shown in Fig. 1c. We will refer to the six possible four-long bitstring outcomes as Elementary Events, and we will refer to a particular instance of this collection of random data, as shown in Fig. 1b, as an Event. In what follows, we will use Q j [α] to denote the measurement result of component j in its row α, where j ∈ (S, R 0 , R 1 ) ≡ (S, 0, 1) and α ∈ (1, 2, . . . , m) ≡ (a, b . . . ). For example, in Fig. 1c, The Weak Broadcast protocol presented below has two real-valued parameters: 0 < µ < 1/3 and 1/2 < λ < 1. We anticipate that the protocol works well if µ and λ are close to their upper bound.
The Weak Broadcast protocol we propose is as follows. In all steps, the classical channels are assumed to be authenticated, and all the channels, the source of quantum states, and the measurements, are assumed to be perfect.
1. Invocation Phase. S sends the data bit (x S ) to be broadcasted to the other components. We denote the bits of the components R 0 and R 1 received as x 0 = x S and x 1 = x S . Now the Sender measures all its qubits (2 qubits in each distributed state) in the computational basis. For each qubit pair of S, if both measurements corresponding to state index α (see Fig. 1b) yielded x S , then S adds index α to its check set σ S . After assembling σ S , this check set is sent to both receivers. At this point, both receivers hold a bit value x j and a set σ j from the Sender. The Sender also sets its output to y S = x S . In the example of Fig. 1b We also provide a more compact and more formal definition of the protocol: then y 1 := y 01 else y 1 =ỹ 1 fi In what follows, we will use the label 'Weak Broadcast protocol' or simply 'Weak Broadcast' to denote the above protocol. The description above shows how the correct components behave. Our goal is to show that this protocol is secure for at most one faulty component in a certain range of the values of the parameters µ and λ. Roughly speaking (see below for the theorem), by security [13] we mean that the failure probability of the protocol, that is, the probability of not achieving weak broadcast, converges to zero as the number m of four-qubit singlet states is increased to infinity. Even though the Weak Broadcast protocol itself follows straightforwardly from earlier works [8,9], the security theorem and its proof has not been published before, to our knowledge.
We point out an important property of the above Weak Broadcast protocol, which is shared with similar earlier protocols [7,9,13,14]. There is an asymmetry between the two Receivers R 0 and R 1 . In contrast to R 0 , R 1 never sends messages, thus it has no impact on the output of the other components. In particular, if R 1 is the faulty component, then the other two components will reach consensus and hence weak broadcast is guaranteed. Therefore, from now on we do not consider the case when R 1 is faulty; we restrict our attention to three other adversary configurations, which we will refer to as 'no faulty', 'S faulty', and 'R 0 faulty'.

Security of Weak Broadcast
The Weak Broadcast protocol defined in Sec. 2 is based on Refs. [7][8][9]13]. Reference [13] provides a security proof of the weak broadcast protocol proposed therein. That protocol uses entangled three-qutrit states. In this work, we apply elements from there to construct a security proof for the above-defined Weak Broadcast protocol, which is based on four-qubit singlet states. Preliminaries and the theorem are presented in this section; for the proof we refer to Appendix E.
We start by specifying our framework. We assume that there is a complete network of pairwise authenticated classical channels among the three components, S, R 0 and R 1 . We also assume that this classical network is synchronous. In particular, (1) before the protocol, the components have already agreed on a common point in time when the protocol is to be started, and (2) all components operate according to a global clock and every message sent during a clock cycle (our protocol consists of 2 clock cycles) will arrive to the receiver by the end of the cycle. Recall also that we consider three adversary configurations: 'no faulty', 'S faulty', and 'R 0 faulty'.
Here, adversary or faulty component means an active adversary, which might act as a properly functioning component, but it might try to undermine the protocol by sending confusing information to the other components. In fact, we assume a conscious adversary following a rational strategy. We also assume that the adversary has only local information. In other words, each random bit generated from the four-qubit singlet states by a local measurement, see Fig. 1b, is known only for the component that has performed the measurement.
We also assume that there is a quantum source that distributes the four-qubit singlet states to the components as shown in Fig. 1. This distribution happens before the measurements required for the communication steps of the Weak Broadcast protocol are performed.
After these preliminaries, we state the theorem claiming the security of Weak Broadcast: Theorem: For any parameter pairs (µ, λ) fulfilling 2/9 < µ < 1/3, and (2a) the failure probability p f (m) of the Weak Broadcast protocol, defined as Protocol 1 above, converges to zero as m → ∞. In particular, in all three adversary configurations, the failure probability is upperbounded as with a, b > 0. The proof is found in Appendix E. The parameter range where our proof guarantees security is shown in Fig. 2.
In the spirit of Refs. [7,13], we make a remark on the complexity of the protocol: Let R q and B q be the round and bit complexities of distributing and measuring a four-qubit singlet state. Then, the Weak Broadcast protocol with a failure probability of at most 0 < 1 requires a round complexity of R = R q + 2, and a bit complexitiy of B = O(log(1/ ))B q . A natural question is if using secure classical channels instead of authenticated ones brings any advantage. Here we reason that the answer is no. If the Sender is the faulty component, then even if it can eavesdrop on the communication between R 0 and R 1 , that has no effect on the outcome of the protocol. Furthermore, if R 0 is the faulty component, then S is correct, hence S sends the very same information to both receivers. Therefore, R 0 eavesdropping on the communication between S and R 1 does not gain extra information for R 0 . These imply that authenticated classical channels where eavesdropping is possible are just as useful in this case as secure channels.

Resource optimization of the Weak Broadcast protocol
In this section, our first goal is to calculate a tight upper bound for the failure probability p f (m) of the Weak Broadcast protocol. This tight upper bound will be used to estimate the resource requirements of the protocol. In particular, we will estimate the number m of singlet states that are required to achieve weak broadcast with a small failure probability, say, 5%. This analysis is similar in spirit to Ref. [11], which was carried out for a different quantum-aided multi-party communication protocol [12].
First, we derive the tight upper bound of the failure probability of the Weak Broadcast protocol as function of µ and λ. We obtain analytical results, and cross-check those against Monte-Carlo simulations. Then, we optimize the protocol in the µ-λ parameter plane. That is, we identify the parameter values that require the least resources, i.e., the smallest number of four-qubit singlet states such that the failure probability is guaranteed to be below the desired failure probability threshold.

Tight upper bound for the failure probability -analytical results
We analyse the resource requirement of the Weak Broadcast protocol is as follows. We can fix the parameter values µ and λ, and the target failure threshold p f,t ; e.g., µ = 0.272, λ = 0.94, and p f,t = 0.05. The target failure threshold p t,f = 0.05 means that the user can tolerate at most 5% failure probability. Then, the resource requirement of the protocol is characterized by the minimal number m min (µ, λ, p f,t ) ∈ Z + of four-qubit singlet states required to suppress the failure probability p f below the threshold p f,t .
A natural way to compute m min would be to identify the optimal adversary strategies for the S faulty and R 0 faulty configurations, i.e. those strategies that maximize the failure probability. We do not complete this task here. Instead, we identify optimal incomplete strategies, which are incomplete in the sense that they provide a description of the adversary's behavior for certain Events but not for others. Using these optimal incomplete strategies, we can compute tight upper bounds on the failure probabilities p f (m), and can use those upper bounds to compute an upper bound m min,↑ of the minimal resource requirement.
For the no faulty configuration, we derive the exact result p To evaluate these analytical formulas, we carry out numerical summation. The results, for a fixed value of protocol parameters, are shown in the three panels of Fig. 3, corresponding to the three adversary configurations. See caption for parameter values. All three panels show that the failure probability p f exhibits a decreasing trend as we increase the number of fourqubit singlet states, as expected. From the data, we can read off the minimum number of states required to suppress the upper bound of the failure probability below p f,t = 0.05: these are 143, 246 and 280, respectively, for the three adversary configurations. Our upper bound m min,↑ of the minimal resource requirement of this protocol for p f,t = 0.05 is the maximum of those three integers, that is, m min,↑ = 280.

Tight upper bound for the failure probability -Monte-Carlo simulations
To test our analytical calculations described in the previous subsection, here we use Monte-Carlo simulations to compute the failure probability p For the S faulty and R 0 faulty adversary configurations, our simulation corresponds to the upper-bound calculation described in the previous subsection. For example, for the S faulty configuration, we use the optimal incomplete strategy described in App. B, and do the following steps. (1) We generate a random Event.
(2) We check if the random Event is in the domain of the optimal incomplete strategy. (3a) If the Event is not in the domain, then we assume failure. (3b) If the Event is in the domain, then we evaluate the protocol such that S is acting according to its adversary strategy; this leads to either failure or weak broadcast.
(4) After repeating these steps for N different random Events, we express the failure-probability upper bound as the ratio N f /N of the number N f of failures and the number N of random Events. These results are shown as the red crosses in Fig. 3b and c, for the S faulty and R 0 faulty configurations, respectively. Data corresponds to N = 10, 000 random Events.
In Fig. 3a, b, and c, the results of the Monte-Carlo simulations (red crosses) are in excellent agreement with the exact results (green circles). We interpret the small differences between the Monte-Carlo result and the exact result as statistical fluctuations of the Monte-Carlo result. For example, estimating the failure probability p = 0.2 from N = 10, 000 samples has a statistical error of p(1 − p)/N ≈ 0.4 %.

Optimization in the parameter space
In the previous subsections, we computed the resource requirements of the Weak Broadcast protocol for fixed values of the parameters µ and λ, and for a fixed value of the target failure threshold p f,t . A natural next step is the optimisation of the protocol: finding the optimal parameter values λ and µ, which minimize the resource requirements, such that it is guaranteed that the failure probability is kept below the target failure threshold p f,t . Even though we do not know the failure probabilities of the best adversary strategies, we do know tight upper bounds for the failure probability, using which we can carry out the optimization. In particular, we will minimize the function m min,↑ (µ, λ, p f,t ) in the (µ, λ) parameter plane, with the specific value of the target failure threshold p f,t = 0.05. We expect that future deployment of such communication protocols will require similar optimization procedures.
We perform this optimization in two steps, as follows. We use the analytical formulas discussed in section 4.1. For a rough optimization in the (µ, λ) parameter space, we consider the rectangle in Fig. 4a, and the grid of parameter pairs shown there. For each point (box) of the grid, we evaluate the failureprobability upper bound p ↑ (m) for m = 290, 300, and color the box as blue or green, respectively, according to the minimal m within this set where p f,↑ < p f,t = 0.05. This procedure results in the pattern in Fig. 4a, which suggest a finer optimization focusing on the area of the dark blue rectangle of Fig. 4a. Note that grey boxes correspond to parameter values µ, λ lying outside the green zone of Fig. 2.
The results of this finer optimization are shown in Fig. 4b. The procedure is analogous to the rough optimization, with the difference that here the set of m values is m = 270, 271, . . . , 300. Figure 4b reveals a 'sweet rectangle', a rectangle of points where using 280 four-qubit singlet states is sufficient to achieve weak broadcast with at most 5 % error. We emphasize that for an error threshold different from 5 %, this optimization must be repeated, and might yield different optimal values for the parameters µ and λ.
To summarize, in this section we have outlined and implemented resource optimization procedures for the Weak Broadcast protocol. This illustrates the engineering aspects of the deployment of future quantumaided distributed systems.

Four-qubit singlet state on IBM Q and IonQ devices
An important goal in the field of quantum communication is to advance the hardware technology and thereby to enable the practical deployment of quantum-aided multi-party communication [9,15,16]. With this goal in mind, we studied the preparation of the resource states of the Weak Broadcast pro-tocol, i.e., four-qubit singlet states, on NISQ hardware [17], namely using superconducting qubits of IBM Q [18] and trapped ion qubits of IonQ [19].
Both superconducting and trapped ion qubits have already been shown to be promising candidates for implementing quantum networks [10]. Quantum network functionalities using superconducting qubits housed in spatially separated cryogenic systems have been experimentally demonstrated recently [20], while scalable remote entanglement between trapped ions has been achieved via photon and phonon interactions [21], raising the hope that entangled states prepared on-chip on quantum processors can be used as resources in quantum networks.
In the rest of this section we identify two quantum circuits that prepare the four-qubit singlet state.
To characterize the quality of our experimental state preparation, we use two quantities. The first one is the classical fidelity F c , that is the fidelity between (i) the probability distribution P exp of bitstrings obtained experimentally by doing computational-basis measurements, and (ii) the ideal probability distribution P id of measured bitstrings, following from Eq. (1) and shown in Fig. 1c: (4) The second figure of merit for state preparation is the quantum state fidelity F q . We obtain this by performing quantum state tomography at the end of the circuit, reconstructing the density matrix ρ exp from the experimental data, and evaluating the fidelity between this state and the ideal four-qubit singlet state ρ id = |ψ ψ|: (5)

Circuit A
First, we need to identify a quantum circuit that prepares the four-qubit singlet state. We rely on CNOT as the two-qubit gate. On today's noisy devices, CNOT is 'expensive' in the sense that its gate error is greater than the single-qubit gate errors. Therefore, a second target for our circuit search is to minimize the number of CNOTs. A third aspect is related to the incomplete connectivity of IBM Q devices: in this subsection we will pay special attention to devices that host a chain of four qubits with linear connectivity. On linear qubit chains, we performed our measurements using Circuit A, shown in Fig. 5, which is based on the results of Ref. [22]. The construction of Ref.
[22] provides a circuit with 18 CNOTs. This we have further simplified, partly by hand, partly by Qiskit's transpiler, to a circuit containing 14 CNOTs. In the circuit we use general single-particle U gates, with the parametrization We have run Circuit A in all four-qubit linear chains in all IBM Q devices with Quantum Volume 32 (available in 2021 April). This yields 32 qubit configurations, and the corresponding results are listed in Table 3. In Table 3, we characterize the quality of state preparation using classical and quantum fidelities introduced in Eqs. 4 and 5.
Without readout error mitigation, our best experiment was the one using the qubit chain 0-1-2-3 on ibmq_santiago, yielding F c = 0.8510. When we correct for the readout errors using the built-in readout error mitigation procedure of Qiskit (see Refs. [23,24] for theoretical details), then the best result is found on the same qubit chain, with F c = 0.9021. For reference, the classical fidelity between a uniform bitstring distribution and the ideal bitstring distribution is 1/ √ 3 ≈ 0.58. Hence we conclude that the bitstring distribution provided by IBM Q hardware is much closer to the ideal one than to random noise. The data in Table 3 show that the bestperforming arrangement is the 0-1-2-3 qubit chain on ibmq_santiago. Without readout error mitigation, the fidelity is F q = 0.7435, whereas readout error mitigation improves this to F mitig q = 0.8116. As a  Figure 6: Circuit B, a 5-CNOT circuit that prepares the four-qubit singlet state of Eq. (1). reference, the quantum state fidelity of the ideal fourqubit singlet state and the fully mixed four-qubit state is ≈ 0.0625.

Circuit B
Another four-qubit circuit that prepares the fourqubit singlet state |ψ , is Circuit B depicted in Fig. 6, which includes only 5 CNOT gates. We found Circuit B using a combination of random circuit search and gradient descent: We assembled random circuits using CNOTs and single-qubit gates from the set {I, X, T, S, H}; searching through approximately 10 7 such instances, we selected the one whose output state had the maximal overlap with the four-qubit singlet state. Then, for the selected instance, we replaced all the one-qubit gates with generic three-parameter single-qubit gates, and performed gradient descent in this multi-dimensional parameter space, with the goal of maximizing the fidelity between the output state of the circuit and the four-qubit singlet state.
Although the decrease in the number of CNOTs with respect to Circuit A is spectacular (5 instead of 14), Circuit B did not produce better results than Circuit A in our state-preparation experiments with the IBM Q quantum processors. The reason is that Circuit B does not suit the linear qubit chain arrangements of the QV32 backends of IBM Q, hence it can only be run without qubit rearrangement on lowerquality hardware (e.g,. ibmq_16_melbourne), which has the loop-type connectivity of Circuit B.
However, we also implemented Circuit B on IonQ's trapped ion quantum computer, which has full connectivity. Beside the better connectivity, these devices have also smaller readout and gate error rates. The experiments were run through the AWS Braket cloud service [25]. As we expected, the results were better; we achieved classical fidelities ≥ 95% in all bases and a quantum fidelity (without readout error mitigation) of 88.5%, both being considerably higher than the fidelities obtained using the IBM Q quantum processors.
To conclude, we have identified two circuits, Circuit A and Circuit B, that can be used to prepare the four-qubit singlet state on IBM Q and IonQ hard-ware. According to our best data, the circuit on IBM Q produces the desired bitstring probability distribution with classical fidelity F mitig c = 0.9002, and it produces the desired state with quantum state fidelity F mitig q = 0.8116. Correspondingly, our single run of the experiment on IonQ achieved classical fidelities ≥ 95% in all bases and a quantum fidelity without readout error mitigation of 88.5%.

Conclusion and outlook
In this work, we introduced a two-parameter family of quantum-aided weak broadcast protocols, and proved their security in a certain range of its parameters. We computed a tight upper bound m min,↑ on the number of resource quantum states required to suppress the failure probability of the protocol below a given target failure probability threshold. We optimized the protocol, that is, we located the parameter range where the resource requirements, as indicated by m min,↑ , are minimal. We have experimentally implemented the preparation and characterization of our four-qubit resource state on real qubits: in the superconducting quantum processors of IBM and the ion-trap quantum processors of IonQ. Our work illustrates the engineering aspects of future deployments of such protocols in practice. The methods and results of this work can be utilized in future research toward multi-party quantum communication in distributed systems.
Let us note that throughout the theoretical part of this work, we assumed that the four-qubit singlet state |ψ of Eq. (1) is prepared and distributed through public quantum channels to the three components of the distributed system. The role of these entangled states is to provide random bits that are correlated among the different components. The same functionality cannot be substituted by a source of correlated classical random bits, distributed through public channels. In this case, the adversary can eavesdrop on the classical channel transmitting the random bits from the source to the components, and hence the criterion that each component knows only its own measurement outcomes can be violated. In the quantum case, considered in this work, the eavesdropping can be detected by sacrificing a fraction of the fourqubit singlet state in a distribute-and-test procedure of the protocol, similar to the procedures described in preceding work [8,9,14]. We leave it for future work to elaborate the quantitative details of such a distribute-and-test procedure.
The above observation points toward further important follow-up tasks to this work. For example, an attack against the protocol could be based on the adversary gaining control over the source, or over the measurement devices generating the correlated random bits. A further difficulty is posed by physical errors of the source, the quantum channels, and the measurement devices, as highlighted by our experiments presented in Sec. 5. We anticipate that the effect of these imperfections on the protocol will be studied in a framework similar to that of device-independent quantum key distribution [26,27]. Some of these issues have already been discussed [7][8][9], but a quantitative study is, to our knowledge, still missing.

Acknowledgments
We   Consistency: all correct components decide on the same output.
The truth table of the broadcast functionality is shown in Table 1, for the special case when the number of components is n = 3, and resilience is expected up to t = 1 faulty component.
In the definition of the second functionality, weak broadcast, the conditions of broadcast are relaxed to some extent, and in addition to 0 and 1, a third output value called 'abort' (⊥) is also allowed. As discussed in the main text, the weak broadcast functionality is important because it can be used as a building block to achieve broadcast [13]. The truth table of the weak broadcast functionality is shown in Table 1, for the special case when the number of components is n = 3, and resilience is expected up to t = 1 faulty component. In the main text, this special case is denoted by WBC(3,1).

B Adversary strategies against the Weak Broadcast protocol
In this section, we define adversary strategies, and propose an S faulty strategy and an R 0 faulty strategy. We prove that the strategies proposed here are optimal, i.e., they maximise the failure probability, in App. D.
As a preliminary for this section, recall that in Sec. 2, we defined the Elementary Events as the possible correlated random outcomes of the measurement of the four-qubit singlet state |ψ of Eq. (1). There are six such outcomes, 0011, 1100, 1010, 0101, 1001, and 0110. It follows from Eq. (1) that the probabilities of 0011 and 1100 are 1/3, whereas the probabilities of the remaining four bitstrings are 1/12.
Furthermore, we have denoted the number of four-qubit singlet states, available for the weak broadcast of a single bit from S, as m. In Sec. 2, we defined an Event as the random configuration of the m bitstrings measured on the m distributed four-qubit singlet states by the three components. Fig. 7a shows an example of an Event for m = 12 (actually, this is the same Event as in Fig. 1b). The first column is the index of the singlet state, and columns 2-4 show the qubit measurement outcomes (Elementary Events) obtained by the three components. Note that the number of possible different Events is 6 m , and for a given m, it is straightforward to calculate the occurence probability of each possible Event. For example, the Event in Fig. 7 occurs with probability (1/3) 8 (1/12) 4 .

B.1 S faulty
For concreteness, and without the loss of generality, here we assume that the faulty S is a conscious adversary, which wants to reach failure of Weak Broadcast such that receiver R 0 outputs y 0 = 0 and receiver R 1 outputs y 1 = 1. Hence, the message sent by S to R 0 is x 0 = 0, whereas the message sent by S to R 1 is x 1 = 1.
Let us first formalize what we mean by an adversary strategy (of S). To this end, we introduce two natural classifications of the Events; a finer, global classification, and a coarser, local one. Here, the term 'local' refers to the property that the classification is based only on the information available to the adversary sender S.
We define the global count list of an Event as the list of the six non-negative integers that count the frequencies of the six different measurement outcomes of the Event. The set of the global count lists will be denoted as GCL. That is, an element of GCL is g = (g 1 , g 2 , g 3 , g 4 , g 5 , g 6 ) = (m 0011 , m 0101 , m 0110 , m 1001 , m 1010 , m 1100 ).
Note that for a certain Event, the adversary S does not know the corresponding global count list g, as S knows only the first two bit values of each row of the Event. Clearly, for any g ∈ GCL it holds that 6 i=1 g i = m. Furthermore, we will denote the counting function that associates an element of GCL to an Event as G : Events → GCL. (8) Note that this function is not injective, since in general, multiple Events are mapped to a single global count list g ∈ GCL. In fact, for any g ∈ GCL, the number of Events that are mapped to g via G is |G −1 (g)| = m g 1 , g 2 , g 3 , g 4 , g 5 , g 6 , where the bracket on the right hand side denotes the multinomial coefficient. An adversary strategy of the sender S describes how S uses its own local information to act during the protocol. More precisely, the strategy is a procedure, according to which the adversary S selects the check sets σ 0 and σ 1 , to be sent to R 0 and R 1 , respectively, in the Invocation Phase. Locally, the sender S cannot distinguish between the outcomes 0101 and 0110, as S knows only the first two bits of these bitstrings. Similarly, S cannot distinguish between the outcomes 1010 and 1001. These imply that the basis of an adversary strategy of S is provided by the four non-negative integers (g 1 , g 2 +g 3 , g 4 +g 5 , g 6 ) = (m 0011 , m 0101 +m 0110 , m 1001 +m 1010 , m 1100 ).
For our purposes, it is sufficient to use an even coarser local classification, which does not distinguish between the local bit pairs 01 and 10 of the sender S. This coarser classification is defined by the map L S : GCL → LCL S , g → ≡ ( 1 , 2 , 3 ) ≡ (g 1 , g 2 + g 3 + g 4 + g 5 , g 6 ). (10) Here, LCL S is the set of local count lists for the S faulty scenario, which is implicitly defined as the range of L S , containing triplets of non-negative integers, such that 1 + 2 + 3 = m. The term local count list hence refers to the integer triplets ∈ LCL S . Because of the sum rule 1 + 2 + 3 = m, a local count list is represented by two of its elements, e.g., 1 and 3 , and hence the set LCL S can be visualised in a two-dimensional plot. This is illustrated for the case m = 12 in Fig. 8, where each non-grey square (i.e., orange and blue squares) represents a local count list.
The adversary strategy of S describes how the behavior of S is derived from the local information S has. For our purposes, it is sufficent to regard the local count list associated to the Event as the local information possessed by S. We define an adversary strategy of S as a function ζ S that maps the local count list of S to a list of 6 non-negative integers, Here, k mixed ≤ 2 indicates the number of mixed-outcome (01XX and 10XX) indices to be included in σ 0 , and k (1) 1100 ≤ 3 indicates the number of 1100 indices to be included in σ 1 , etc. Our purpose in this work is to analyse the failure probability of certain strategies. For this purpose, it is sufficient to define a strategy by the numbers above: how many indices from each class are included in each check set. It is not necessary to specify which indices are included from each class, because the failure probability is independent of the specific choice. Nevertheless, in the examples considered in this work, we assume that S includes the 'smallest' indices from each class, in alphabetical order of the indices (see Fig. 7).  (17), depicted as the blue, black, and red lines, respectively. Blue region depicts those local count lists where the incomplete strategy ζ is not defined.
We call a strategy, as defined in Eq. (11), a complete strategy, if its domain is the complete LCL S ; otherwise, we call it an incomplete strategy. For a complete strategy, the failure probability p f is a well-defined real number p f ∈ [0, 1]. From now on, we will deal with incomplete strategies, and hence we will not be able to compute the specific failure probability; however, we can derive a relatively tight upper bound for the failure probability.
In what follows, we will often consider sequences of strategies: such a strategy sequence is a function that specifies a strategy for each m. A natural notation for a strategy in such a sequence ζ S,m ; note that we will often suppress the m, and call such a sequence of strategies simply as a strategy. In general, for different strategies in a given sequence, the domain and the failure probability (or the failure-probability upper bound, for incomplete strategies) are different.
In this work, we focus on a sequence of optimal incomplete adversary strategies of S. This is given as where with . denoting the ceiling function.
Second, the adversary S can include Q indices of mixed outcomes in its check set σ 0 only if the number 2 of mixed outcomes is sufficient, that is, if Besides these two restrictions, we further restrict the domain of ζ by requiring The above 3 conditions define the domain D(ζ) of the strategy ζ. With this extra condition, the incomplete strategy ζ of Eq. (12) is optimal in its domain D(ζ), which will be proven in App. D.1. The domain D(ζ) is shown as the orange region in Fig. 8, and the conditions Eqs. (15), (16), and (17) are depicted as the blue, black, and red lines in Fig. 8, respectively. How can the strategy ζ in Eq. (12) lead to failure? This is exemplified by a specific instance of the Weak Broadcast protocol in Fig. 7, for m = 12. To be specific, we consider a Weak Broadcast protocol with parameter values µ = 0.26 and λ = 0.94. The adversary strategy derived from the optimal strategy of Eq. (12) using these values of µ, λ and m can be written as ζ = (3, 1, 0; 0, 0, 3 ), (18) since T = 4 and Q = 1.
The table in Fig. 7a shows an Event for m = 12. The local information of S, i.e., the information S possesses, is denoted by boldface characters in Fig. 7a: S knows the indices of the four-qubit singlet states used in the protocol, it knows its own measurement outcomes (bit-pairs), and it also knows the measurement outcomes of R 0 and R 1 for those rows where S measured 00 or 11. The information S does not possess is denoted by italic characters in Fig. 7a.  = (4, 4, 4) is in the domain, defined by Eqs. (15), (16), (17), of the incomplete strategy ζ in Eq. (18). Hence S can follow the incomplete strategy ζ S , which results in the communication and decision steps depicted in Fig. 7b. There, the receivers R 0 and R 1 follow the Weak Broadcast protocol, and their output bit values are y 0 = 0 and y 1 = 0, respectively, implying failure of the Weak Broadcast protocol.
The above example sheds light on why the strategy ζ S in Eq. (12) is efficient (in fact, optimal in its domain) in achieving failure. In more general terms, its efficiency is reasoned as follows. According to this strategy, the adversary sender S tries to send a check set σ 0 such that R 0 finds it convincingly long (that is, the Length Condition of the Check Phase is satisfied) and consistent (that is, the Consistency Condition of the Check Phase is satisfied); but when sent over to R 1 as ρ 01 , then R 1 finds it inconsistent (Consistency Condition of the Cross-Check Phase is violated), resulting in failure via y 0 = 0 and y 1 = 1. This is achieved by the strategy ζ S of Eq. (12), if each of the Q rows chosen from the mixed class by S contain bit 1 at R 0 and bit 0 at R 1 . If at least a single one of these rows contains bit 0 at R 0 and bit 1 at R 1 , then R 0 finds the check set σ 0 inconsistent with the data bit x 0 = 0 and hence produces an output y 0 =⊥, leading to Weak Broadcast (see Table 2, row 8 or row 17).

B.2 R 0 faulty
For concreteness, and without the loss of generality, here we assume that the correct sender S sends the message x S = x 0 = x 1 = 0 to the receivers. Furthermore, we assume that the faulty R 0 is a conscious adversary, which wants to reach failure of Weak Broadcast such that the correct R 1 has an output bit value y 1 = 1 that conflicts with the output bit value of x S = 0 of S.
We start by formalizing what we mean by an adversary strategy of R 0 . Similarly to the S faulty configuration, our starting point is the set GCL of global count lists, see Eq. (7). The adversary strategy of the receiver R 0 describes how R 0 uses its own local information to act during the protocol. Then, locally, the receiver R 0 can distinguish between three types of outcomes. First, if the third bit of the outcome, i.e., the bit R 0 has measured, carries the value '1', and the index of the outcome is sent from S to R 0 in the check set σ 0 , then R 0 can identify the outcome as 0011. Second, if the third bit of the outcome carries the value '1', and the index of the outcome is not included in σ 0 , then R 0 identifies the outcome as 'either 0110 or 1010'. In any other case, i.e., if the third bit of the outcome carries the value of '0', then R 0 identifies the outcome as 'either 0101, or 1001, or 1100'. It is natural to denote the frequency of each type of outcome in a given Events as m 0011 , m XX10 , and m XX0X .
This threefold classification of the Events according to R 0 's local information is therefore defined by the map Here, LCL R is the set of local count lists for the R 0 faulty scenario, which is implicitly defined as the range of L R , containing triplets of non-negative integers, such that 1 + 2 + 3 = m. The term local count list hence refers to the integer triplets ∈ LCL R . Because of the sum rule 1 + 2 + 3 = m, a local count list is represented by two of its elements, e.g., 1 and 2 , and hence the set LCL R can be visualised in a two-dimensional plot. This is illustrated for the case m = 12 in Fig. 9, where each non-grey square represents a local count list.
The adversary strategy of R 0 describes the procedure to assemble the check set ρ 01 , based on the local information R 0 has. Hence, we define an adversary strategy of R 0 as a function ζ R that maps the local count list of R 0 to a list of 3 non-negative integers: Here, k 0011 ≤ 1 indicates how many of the 0011 indices does R 0 include in the check set ρ 01 sent to R 1 in the Cross-calling Phase. Similarly, k XX10 ≤ 2 indicates the number of XX10 indices to be included in ρ 01 , and k XX0X ≤ 3 indicates the number of XX0X indices to be included in ρ 01 .
Similarly to the case of the S adversary strategy discussed above, here it is also sufficient to define a strategy by the 'k' numbers above in Eq. (20): how many indices from each class are included in each check set. It is not necessary to specify which indices are included from each class, because the failure probability is independent of the specific choice. Nevertheless, in the examples considered in this work, we assume that R 0 includes the 'smallest' indices from each class, in alphabetical order of the indices (see Fig. 10).
We call a strategy, as defined in Eq. (20), a complete strategy, if its domain is the complete LCL R ; otherwise, we call it an incomplete strategy. From now on, we deal with incomplete strategies, and hence we will not be able to compute the specific failure probability; however, we will derive an upper bound for the failure probability.
We consider the incomplete strategy defined as where n min is the smallest non-negative integer such that 2 + n min ≥ T . That is, The above definition of ζ R contains an implicit assumption on the domain of ζ R : the strategy can be followed only if the value of n min , as defined in Eq. (22), is not greater than 3 . More precisely, if 2 < T , then T − 2 ≤ 3 must hold. Formulating this in terms of 1 and 2 : if 2 < T , then 1 ≤ m − T must hold. As 2 ≥ T implies 1 ≤ m − T , we conclude that the domain of the above strategy is defined by In Fig. 9, this domain D(ζ R ) is illustrated for a specific choice of parameters (see caption). There, the domain D(ζ R ) of the strategy is shown as the union of the orange, blue and pink regions, whereas the green region is the complementD(ζ R ) of the domain. Furthermore, the condition (23) is depicted as the red line. We claim that the incomplete strategy ζ R is optimal on its domain. This will be proven in App. D.2. How can the strategy ζ R of Eq. (21) lead to failure? This is exemplified by a specific instance of the Weak Broadcast protocol in Fig. 10, for m = 12. To be specific, we consider a Weak Broadcast protocol with parameter values µ = 0.26 and λ = 0.94. The table in Fig. 10a shows an Event for m = 12. The local information possessed by R 0 is denoted by boldface characters in Fig. 10a (cf. the second paragraph of this section); the information hidden from R 0 is denoted as italic.
Based on the local information R 0 has, it classifies the indices α ∈ {1, . . . , m} ≡ {a, b, . . . , l} of the Event into the three classes defined above: 0011, XX10, XX0X. In the example of Fig. 10a, these classes can be identified as the corresponding check sets: 0011 = {b, e, f, i}, XX10 = {d, g}, and XX0X = {a, c, h, j, k, l}. This implies m 0011 ≡ 1 = 4, m XX10 ≡ 2 = 2, and m XX0X ≡ 3 = 6. This local count list = (4, 2, 6) is in the domain D(ζ R ) of the incomplete strategy ζ R ; in fact, it is in the orange region of Fig. 9. Hence R 0 can follow the incomplete strategy ζ R , which results in the communication and decision steps depicted in Fig. 10b. There, the sender S and the receiver R 1 follow the Weak Broadcast protocol, and their output bit values are x S = 0 and y 1 = 1, respectively, implying failure of the Weak Broadcast protocol.
The above example sheds light on why the strategy ζ R in Eq. (20) is efficient (in fact, optimal in its domain) in achieving failure. In more general terms, its efficiency is reasoned as follows. According to this strategy, the adversary receiver R 0 sends a false data bit value (y 01 = 1 = 0 = x S ) and tries to 'back it up' by a check set ρ 01 that is convincingly long (that is, the Length Condition of the Cross-Check Phase is satisfied) and consistent (that is, to achieve that the Consistency Condition of the Cross-Check Phase is satisfied). This is achieved by the strategy ζ R of Eq. (20), if the number of consistent indices is large enough; hence it is reasonable for R 0 to include all indices that are certainly consistent with the bit value y 01 = 1 (red indices in Fig. 10), and include the minimal amount of indices which are only potentially consistent with the bit value y 01 = 1 (these are the two blue indices in Fig. 10b), such that the Length Condition is satisfied.

C Failure probabilities
In this section, we compute the exact failure probability for the 'no faulty' adversary configuration, and compute tight upper bounds of the failure probabilities for the adversary configurations 'S faulty' and 'R 0 faulty'. These results allow future users of the protocol to allocate resources sparingly. In fact, these results are analysed, and are used to optimize the protocol, in the main text.

C.1 No faulty
In this subsection, we consider the no faulty configuration. Without the loss of generality, assume that the data bit sent by S is x S = 0. Then, we have the following exact result for the failure probability p f , which we denote as p (24) Recall the definition T = µm , introduced in the Weak Broadcast protocol, Sec. 2. Recall also that T is the minimal check set length that satisfies the Length Conditions.
To derive this result, it is sufficient to note that the protocol leads to failure only if the Length Condition of the Check Phase evaluates as False, that is, if the number of 0011 outcomes is less than the minimal check set length that satisfies the Length Conditions; i.e. if the following condition holds: Since the Elementary Event 0011 is generated with a probability of 1/3, the probability of Eq. (25) holding true can be expressed by the binomial formula Eq. (24). This concludes the proof. Note that the analysis generalises straightforwardly to the case when the message of the sender S is x S = 1, and yields the same result for p

C.2 S faulty
Here, we provide an upper bound p (S) f,↑ for the failure probability in the S faulty configuration. To express this upper bound, recall that T = µm is the minimal check set length that satisfies the Length Conditions, which was introduced in Eq. (13). Also recall that the integer Q was defined in Eq. (14). Here we use its exact definition, that is, Q = T − T λ + 1. With these notations, the upper bound p with In the derivation of this upper bound, first we express the upper bound formally for a general incomplete strategy, and then we apply it to the S faulty strategy defined above.
Assume that we have identified an incomplete strategy ζ that is optimal in its domain D(ζ) ⊂ LCL S . An upper bound of the failure probability of this strategy can be expressed as Here, P ( ) is the probability that a random Event produces the local count list . Furthermore, P ζ (failure| ) is the conditional probability of failure, given the random Event produces the local count list . Finally,D(ζ) is the complement of D(ζ), that is,D(ζ) = LCL S \ D(ζ).
In words, the formula (28) for the upper bound is interpreted as follows: the random Event either produces a local count list that is in the domain of the strategy ζ, and then we compute the corresponding failure probability exactly (first sum); or, the Event produces a local count list that is outside the domain of the strategy ζ, and then we assume a worst-case scenario, i.e., that failure happens with unit probability (second sum).
Using the normalization condition we see that Eq. (28) can be reformulated as Note that these considerations suggest that for a given incomplete strategy, a lower bound p (S) f,↓ of failure probability can also be expressed, by assuming a best-case scenario, i.e., zero failure probability, for Events that produce local count lists that are outside of the domain of the strategy. Formally, this lower bound is expressed as p To evaluate the upper bound p (S) f,↑ of the failure probability for this optimal partial strategy ζ via Eq. (30), we first express (32) Recall that = ( 1 , 2 , 3 ) is determined by two of its components, e.g., 1 and 3 , because 1 + 2 + 3 = m. Equation (32) is a straighforward consequence of the fact that the probability of a 0011 outcome, the probability of a mixed outcome (0101 or 0110 or 1001 or 1010), and the probability of a 1100 outcome, are all equal to 1/3. Finally, we express the failure probability of ζ on its domain, which is This follows from the fact that S includes Q mixed indices in its check set σ 0 , and this leads to failure only if all the Q corresponding mixed outcomes contain a '1' at R 0 . Inserting Eqs.

C.3 R 0 faulty
Here, we provide an upper bound p f,↑ for the failure probability in the R 0 faulty configuration. Again, recall that T = µm (original definition in Eq. (13)) and Q = T − T λ + 1 (original definition in Eq. (14). With these notations, the failure-probability upper bound reads: where The result (34) is valid both for the x S = 0 and the x S = 1 scenario. In what follows, we derive this result. The derivation follows the 3-step scheme outlined in the S faulty case below Eq. (27). Assume that we have identified an incomplete strategy ζ that is optimal on its domain D(ζ) ⊂ LCL R . An upper bound of the failure probability of this strategy can be expressed as shown in Eqs. (28). A lower bound can also be expressed as Eq. (31).
For our optimal incomplete strategy ζ, the formula for the failure-probability upper bound, Eq. (28), can be structured further, according to the three regions (orange, pink, blue) in Fig. 9: In the pink region, failure is guaranteed, in fact, for any R 0 adversary strategy, since 1 < T implies that the check list σ 0 = σ 1 sent by S violates the Length Condition of the Check Phase. In the blue region, however, failure is guaranteed because the adversary R 0 was lucky to find enough outcomes XX10, that is, 2 ≥ T −Q+1, such that its check set ρ 01 automatically satisfies the Consistency Condition of the Cross-check Phase. The last three terms of Eq. (37) can be readily expressed by binomial and trinomial distributions. The blue, pink, and green regions correspond to, respectively, to the second term of Eq. (35), to the third term of Eq. (35), and to the second term of Eq. (34).
To complete the derivation of the failure-probability upper bound, we express P ζ (failure| ) for ∈ orange: To interpret this formula, let us first recall that in the orange region of D(ζ), it holds that n min = T − 2 . Furthermore, note also that the probability that the number of XX10 outcomes in the check set ρ 01 of length n min = T − 2 is k is given by the binomial distribution. Hence, Eq. Here, we show that the S faulty adversary strategy defined above is an optimal incomplete strategy, i.e., it is optimal on its domain. Consider therefore an arbitrary strategy 1100 .
It is straightforward to see that the strategy derived from S B , has a higher or equal failure probability than the initial Bad Strategy S B : The reason is as follows. On the one hand, deviating from k 1100 = (0, 0, m 1100 ) either decreases the failure probability, or does not change that. In words: from the viewpoint of an adversary S, it is useless to deviate from the correct communication toward R 1 . On the other hand, k (0) 1100 > 0 leads to weak broadcast, implying p f = 0.
To analyze the failure probability of the 'improved' strategy ζ B further, we introduce Q = k (0) mixed and T = k (0) 0011 + Q . We address the question: are any strategies defined by (T , Q ) = (T, Q) better than the strategy the strategy ζ? No, as we argue now.
(i) If T < T , then the strategy ζ B is dysfunctional, p f = 0, since there are not enough indices in σ 0 and σ 1 to convince the receivers; that is, the Length Condition of the Check Phase evaluates is violated, implying weak broadcast. These strategies are depicted as red circles in Fig. 11a.
(ii) If T ≥ T and Q < Q, then the strategy ζ B is dysfunctional, since this excludes the possibility that ρ 01 contains enough inconsistent indices that compromise R 0 . These strategies are depicted as purple circles in Fig. 11.
(iii) The failure probability of the strategy ζ B along the 'line' (T , Q ) = (T + n, Q + n) decreases as n ≥ 0 is increased. I.e., along this line, depicted as the line of diagonal arrows in Fig. 11a, the filled green circle depicting n = 0 represents the optimal strategy. The reason is that by increasing T from T to T + n, the number of mixed outcomes in σ 0 for which R 0 needs to measure a '1' to cause failure is increased to Q + n, as demanded by the Consistency Condition of the Cross-Check Phase. This reduces the corresponding failure probability from (1/2) Q to (1/2) Q+n . This trend is depicted in Fig. 11a by the diagonal arrows.
(iv) The strategy ζ B is dysfunctional 'below the line' defined in (iii), see the blue circles in Fig. 11a. There, even if all Q mixed outcomes included in σ 0 have '1' at R 0 , that is insufficient to violate the Consistency Condition of the Cross-Check phase. (v) The failure probability of the strategies ζ B 'above the line' defined in (iii), that is, strategies with (T , Q ) = (T + n, Q + n ) (where n ≥ 0 and n ≥ n), decrease as n is increased. Indeed, as n is increased, the check set size remains unchanged (T + n), but the number of 'guessed' indices (Q + n ) is increased, and hence the failure probability (1/2) Q+n decreases. This trend is depicted in Fig. 11a by the vertical arrows.
This concludes the proof that the strategy ζ = (T − Q, Q, 0; 0, 0, m 1100 ) is indeed optimal on its domain.

D.2 R 0 faulty
Here, we prove that the R 0 adversary strategy ζ = (0, m XX10 , n min ) defined above is optimal on its domain. (i) Increasing the first strategy parameter k 0011 from zero decreases the failure probability, as it lowers the chance of the Consistency Condition of the Cross-check Phase evaluating as True.
(ii) Consider the alternative strategies ζ = (0, k XX10 , k XX0X ), with k XX10 = m XX10 −n and k XX0X = n min +n , with n, n ≥ 0. The alternative strategies are dysfunctional (p f = 0) 'below the line' of the (k XX10 , k XX0X ) plane defined by n = n , i.e., for n > n . This is because for such a strategy, the check set size |ρ 01 | is below the minimum size T required to satisfy the Length Conditions. These dysfunctional strategies are shown as the red circles in Fig. 11b.
(iii) The alternative strategies along the line n = n , shown in Fig. 11b as the line of diagonal arrows, have a decreasing failure probability as n is increased. Along this line, the check set size |ρ 01 | is fixed to the minimum size T , but the number n min + n of guessed indices increases, and hence the probability of satisfying the Consistency Condition of the Cross-check Phase decreases. This trend is depicted in Fig. 11b by the diagonal arrows.
(iv) Consider the alternative strategies 'above the line' of the (k XX10 , k XX0X ) plane defined by n = n , i.e., above the line of diagonal arrows in Fig. 11b. These are the strategies of the form ζ = (0, m XX10 − n, n min + n ) with n ≥ n. For a fixed n, the failure probability of these strategies decreases as n is increased. This is because increasing n by 1 increases the check set size |ρ 01 | by 1, and hence the right hand side of the Consistency Condition of the Check Phase by 1, and at the same time, increases the minimum number of lucky indices needed to satisfy that Consistency Condition, leading to a decrease of the failure probability. This trend is depicted in Fig. 11b by the horizontal arrows.
This concludes the proof that the strategy ζ = (0, m XX10 , n min ) is indeed optimal on its domain

E Security proof
In this Appendix, we derive asymptotic (m → ∞) upper bounds for the failure probability for generic adversary strategies.

E.1 No faulty
Without the loss of generality, we assume that S sends the message x S = 0.
The protocol will achieve consensus, y 0 = y 1 = x S = 0, if the number of 0011 outcomes in the event is at least T , cf. the exact failure-probability result of Eq. (24). The probability of achieving consensus, i.e., that a random event contains the outcome 0011 with frequency m 0011 is where X j are binary (Bernoulli) random variables, taking values 0 or 1, with probability p = 1/3 for the latter. This implies that Recall that µ < 1/3; hence, the failure probability p f can be upper bounded by the Chernoff bound as That is, in the absence of an adversary, the failure probability of the Weak Broadcast protocol is subject to an upper bound that decreases exponentially as m increases.
Recall that the general form of the Chernoff bound used to derive this result is whereX is the expectation value of the sum variable X.

E.2 S faulty
The security proof for the S faulty adversary configuration will be based on the tight failure-probability upper bound calculation presented in App. C.2.
Our goal is here is to derive an exponentially decaying upper bound for the failure probability. To this end, we restrict the domain of the S faulty adversary strategy ζ, defined in C.2. The restricted strategy is denoted as ζ r . In particular, we restrict the domain of ζ for 'regular' or 'typical' local count lists, where 1 and 3 are approximately equal to their expected values m/3. Formally, we define D(ζ r ) as formed by those ( 1 , 3 ) pairs where µm < 1 , 3 < 2m/3 − µm.
Since D(ζ r ) ⊂ D(ζ), and D(ζ) is optimal on its domain, the restricted strategy ζ r is also optimal on its domain.

E.3 R 0 faulty
Here, we describe the security proof for the R 0 faulty adversary configuration. This proof is based on the tight failure-probability upper bound calculation presented in App. C.3. We restrict the domain of the R 0 faulty optimal incomplete adversary strategy ζ, defined in B.2. The restricted strategy is denoted as ζ r . In particular, we restrict the domain of ζ for 'regular' local count lists, where 1 and 2 are close to their expected values, m/3 and m/6, respectively. Formally, we define the domain D(ζ r ) of the restricted strategy as formed by those ( 1 , 2 ) pairs which satisfy µm/2 < 2 < 2m/6 − µm/2.
Note that ζ r is indeed a restriction of ζ, since the upper bound in Eq. (52) is a stricter condition than (23). Furthermore, since D(ζ r ) ⊂ D(ζ), and ζ is optimal on its domain, the restricted strategy ζ r is also optimal on its domain.
In the spirit of Eq. (28), the failure-probability upper bound can be expressed using the restricted strategy ζ r as follows: In the last step, we used the Chernoff bound in Eq. (51). Finally, we provide an upper bound for the first term of Eq. (54). Within the restricted strategy domain D(ζ r ), the adversary R 0 has the greatest chance to cause failure if the number of 'safe' indices, 2 , is maximal, 2 = 2,max ≡ 2m/6 − µm/2 . For a local count list containing 2,max , Eq. (38) specifies P ζ (failure| 1 , 2,max ) as a sum of the upper part of a binomial distribution, between k = T − Q + 1 − 2,max to k = T − 2,max . In fact, the quantity P ζr (failure| 1 , 2,max ) is independent of 1 . The Chernoff bound P (X ≥ (1 + δ)X) ≤ e −Xδ 2 /3 , for 0 ≤ δ, can be used to upper bound this sum, if the the latter is an upper tail sum, that is, the lower end of the k sum is above the expectation valueX = 2 3 (T − 2,max ) of k: The latter condition is readily transformed as where we disregarded ceiling and floor functions for simplicity. Note that since λ < 1, the condition of Eq. (59) can be satisfied only if µ > 2/9 ≈ 0.222.
If the condition (59) holds, then the Chernoff bound of Eq. (57) is applied with the substitution Note that Eq. (60) implies that the coefficient of m on the right hand side is positive, i.e., the upper bound in Eq. (66) is exponentially decreasing with increasing m.

F Preparation and benchmarking of the four-qubit singlet state on IBM Q
This appendix exhibits the data we obtained by conducting experiments on IBM Q quantum computer prototypes. We aimed these experiments to prepare the four-qubit singlet state |ψ of Eq. (1) using Circuit A of Fig. 5, and to quantify how close the experiment resembles the preparation of an ideal four-qubit singlet state. Further details are in the table caption. backend