Fault-Tolerant Consensus in Quantum Networks

We consider a quantum synchronous message-passing model (c.f., [7]), consisting of $n$ synchronous processes (also called players), each with common clock (a clock tick is called a round or a step) and unique id from the known set $\mathcal{P}=[n]=\{1,\ldots,n\}$.

Between any pair of processes we assume the existence of a quantum channel being able to transmit reliable^***Messages are not lost nor corrupted while in transit. messages caring quantum bits, qubits. For the sake of completeness, we also augment the model by classic point-to-point channels between any pair of processes. In each round, a process can send (personalized) quantum and classic messages to any selected subset of other processes. After multicasting messages, in the same round a process receives messages that were just sent to it by other processes, and performs local computation, which involves both quantum and classic bits.^†††Local computation also decides what messages to send in the next round and to whom.

Processes are prone to crash failures, also called fail-stops. A crashed process permanently stops any activity, including sending and receiving messages.

We model crashes as incurred by a full-information adversary (the same as in [8, 10]) that knows the algorithm, the exact pure quantum state (see Section 3) and the classic state of the system at any point of an execution, and has an unbounded computational power. The adversary decides which processes to fail and when. The adversary is also adaptive – it can make a decision on-line based on its current full-knowledge of the system. However, the adversary does not know the future computation, which means that it does not know future random bits drawn by processes.

As for the quantum part, the adversary can apply no quantum operation to the system, but it is aware of all quantum and classic changes of state that the network undergoes. If a process is crashed by the adversary, we assume that its quantum bits are not destroyed (in particular, entangled qubits in other processes do not collapse but maintain their entanglement), however they cannot be used in further computation.

Failures are not clean – when a process crashes when attempting to multicast a message, then some of the recipients may receive the message and some may not; this aspect is controlled by the adversary. A $t$-adversary is additionally restricted by the the number of crashed processes being smaller than $t$; if $t=n$ then the $n$-adversary is also called an unbounded adversary (note that even in such case, at least one process must survive for consensus to make sense). Throughout the paper, we will be calling the adversary described above “adaptive”, for short.

each process $p$ has its own initial value $input_{p}$ and has to output a (common) decision value, so that the following conditions hold: validity – decision must be on an input value of some process; agreement – no two processes decide on different values; and termination – each process eventually decides on some value, unless it is faulty. All those three requirements must hold with probability 1. We focus on binary consensus, in which initial values are in $\{0,1\}$.

Correctness and complexity – in terms of time (the number of rounds needed for all processes to terminate) and the number of quantum bits (qubits) and communication bits – are analyzed and maximized (worst-case) against an adaptive adversary.

We say that a random event occurs with high probability (whp for short), if its probability could be made $1-O(n^{-c})$ for any sufficiently large positive constant $c$ by linear scaling of parameters.

We focus on quantum properties relevant to our algorithms. A quantum system operates on qubits. Single qubit can be either in a pure or a mixed state. A pure state is a vector in a $2$-dimensional Hilbert space $\mathcal{H}$, while a mixed state is modelled as a probabilistic distribution over pure states. Similarly, a register consisting of $d$ qubits can also be in a pure or a mixed state. A pure quantum state, denoted $\ket{x}$, is a vector of $2^{d}$-dimensional Hilbert space $\mathcal{H}^{\otimes d}=\mathcal{H}\otimes\ldots\otimes\mathcal{H}$. Again, a mixed state of larger dimension is viewed a probabilistic distribution over pure states. In our paper, we will operate only on pure states, and we will use only the standard computational basis of the Hilbert space, which consists of vectors $\{\ket{b_{1}\ldots b_{d}}:b_{1}\ldots,b_{d}\in\{0,1\}^{d}\}$, to describe the system. Therefore, any state $\ket{x}$ can be expressed as $\ket{x}=\sum_{i=0}^{2^{d}-1}\alpha_{i}\ket{i}$, with the condition that $\sum_{i}|\alpha_{i}|^{2}=1$, since quantum states can be only normalized vectors.

Transitions, or equivalently – changes of states of a quantum system, are given by unitary transformations on the Hilbert space of $d$ qubits. These unitary transformations are called quantum gates. These operations are exhaustive in the sense that any quantum computation can be expressed as a unitary operator on some Hilbert space. There are small-size sets of quantum gates working on two-dimensional space that are universal – any unitary transformation on a $2^{d}$-dimensional quantum space can be approximated by a finite collection of these universal gates. In our applications, any quantum algorithm computation run by a process requires polynomial (in $n$) number of universal gates.

Finally, an important part of quantum computation is also a quantum measurement. Measurements are performed with respect to a basis of the Hilbert space – in our case this is always the computational basis. A complete measurement in the computational basis executed on a state $\ket{x}=\sum_{i=0}^{2^{d}-1}\alpha_{i}\ket{i}$ leaves the state in one of the basis vectors, $\ket{i}$, for $i\in\{0,1\}^{d}$, with probability $\alpha_{i}^{2}$. The outcome of the measurement is a classic register of $d$ bits, informing to which vector the state has been transformed. It is also possible to measure only some qubits of the system, which is called a partial measurement. If $A$ describes the subset of qubits that we want to measure and $B$ is the remaining part of the system, then the partial measurement is defined by the set of projectors $\{\Pi_{i}=\ket{i}_{A}\bra{i}_{A}\otimes I_{B}\ \,|\ \,\mbox{for }i\in\{0,1\}^{d}\}$.^‡‡‡Whenever it could be irrelevant, from the context, we may follow the standard notation in quantum computing and skip writing normalizing factors. In the former, a subscript refers to the part of the system on which the object exists, $I$ denotes the identity function, while $\bra{i}$ is a functional of the dual space to the original Hilbert space (its matrix representation is the conjugate transpose of the matrix representation of $\ket{i}$). If before the measurement the system was in a state $\ket{x}_{AB}$ then, after the measurement, it is in one of the states $\{\Pi_{i}\ket{x}_{AB}\ \,|\ \,\mbox{for }i\in\{0,1\}^{d}\}$, where state $\Pi_{i}\ket{x}_{AB}$ is achieved with probability $\bra{x}_{AB}\Pi_{i}\ket{x}_{AB}$.^§§§$\Pi_{i}\ket{x}_{AB}$ and $\bra{x}_{AB}\Pi_{i}\ket{x}_{AB}$ are simply linear operations on matrices and vectors. The reader can find a comprehensive introduction to quantum computing in [29].

Let $G=(V,E)$ denote an undirected graph. Let $W\subseteq V$ be a set of nodes of $G$. We say that an edge $(v,w)$ of $G$ is internal for $W$ if $v$ and $w$ are both in $W$. We say that an edge $(v,w)$ of $G$ connects the sets $W_{1}$ and $W_{2}$, or is between $W_{1}$ and $W_{2}$, for any disjoint subsets $W_{1}$ and $W_{2}$ of $V$, if one of its ends is in $W_{1}$ and the other in $W_{2}$. The subgraph of $G$ induced by $W$, denoted $G|_{W}$, is the subgraph of $G$ containing the nodes in $W$ and all the edges internal for $W$ in $G$. A node adjacent to a node $v$ is a neighbor of $v$ and the set of all the neighbors of a node $v$ is the neighborhood of $v$. $N^{i}_{G}(W)$ denotes the set of all the nodes in $V$ that are of distance at most $i$ from some node in $W$ in graph $G$. In particular, the (direct) neighborhood of $v$ is denoted $N_{G}(v)=N^{1}_{G}(v)$.

The following combinatorial properties are of utter importance in the analysis of our algorithms. Graph $G$ is said to be $\ell$-expanding, or to be an $\ell$-expander, if any two subsets of $\ell$ nodes each are connected by an edge. Graph $G$ is said to be $(\ell,\alpha,\beta)$-edge-dense if, for any set $X\subseteq V$ of at least $\ell$ nodes, there are at least $\alpha|X|$ edges internal for $X$, and for any set $Y\subseteq V$ of at most $\ell$ nodes, there are at most $\beta|Y|$ edges internal for $Y$. Graph $G$ is said to be $(\ell,\varepsilon,\delta)$-compact if, for any set $B\subseteq V$ of at least $\ell$ nodes, there is a subset $C\subseteq B$ of at least $\varepsilon\ell$ nodes such that each node’s degree in $G|_{C}$ is at least $\delta$. We call any such set $C$ a survival set for $B$.

Consider $O(\log{n})$ repetitions of the main loop (phases) of the CheapQuantumConsensus algorithm. If during these phases, the processes with value $b_{p}=1$ become a large majority (at least $\frac{6}{10}$ fraction of alive processes), then, as discussed before, every process will decide within the next two rounds. The same holds if processes with value $b_{p}=0$ start to overpopulate by a ratio of $\frac{6}{10}$ all non-faulty processes. On the other hand, if the cardinalities of the two groups with different values $b_{p}$ are close to each other, then the processes execute the CheapQuantumCoin algorithm. It outputs a random bit (the same in every participating process), under the assumption that at least a $\frac{2}{3}$ fraction of processes that started this phase as non-faulty have not crashed during this phase. However, in these $O(\log{n})$ phases there must be at least one phase in which the property of a $\frac{2}{3}$ fraction of processes survive holds. In what follows, we argue that if the adversary can crash arbitrarily many processes, but smaller than $n$, then the expected number of phases should still be $O(\log{n})$. Now, to obtain the algorithm stated in Theorem 2, we make two more adjustments of the original CheapQuantumConsensus algorithm. In lines 1 and 1, processes execute the algorithms FastCounting and CheapQuantumCoin, respectively, with parameters $x,d,\alpha$ set as follows: $x=2,d=\log{n},\alpha=\log{n}$. This corresponds to a use of sparse graph for communication (of degree roughly $O(\log{n})$). In consequence, the time complexity of the FastCounting algorithm increases to $O(\log^{4}{n})$, but the communication complexity decreases to $O(\log^{8}{n})$ amortized per process. The details are presented in Section 6, and performance follows from putting the abovementioned parameters to the formulas in Theorem 5). Similarly, the time complexity of the CheapQuantumCoin algorithm increases to $O(\log^{3}{n})$, but the communication complexity (both quantum and classical) decreases to $O(\log^{7}{n})$ amortized per process. The details are presented in Section 5, and performance follows from putting the abovementioned parameters to the formulas in Theorem 3).

We now describe the CheapQuantumCoin algorithm. Its pseudocode is presented in Figure 2. It takes as an input: a process name $p$ and two integers, $d$ and $\alpha$. The two latter parameters are used to determine communication pattern between non-faulty processes, and their choice determines complexity of the algorithm.

As mentioned before, processes use quantum equivalent of a procedure in which processes draw random names from the range $[1,\ldots,n^{3}]$ and decide on a random bit proposed by the process with the largest name.^¶¶¶Note that the latter procedure cannot be used against an adaptive adversary, as it could crash such a leader. We view the quantum part of the algorithm as a quantum circuit on the joint space of all qubits ever used by different processes. Due to the distributed nature of the system, not all quantum operations are allowed by the quantum circuit. That is, (i) any process can perform arbitrary unitary gates on its part of the system, (ii) unitary gates on qubits of different processes might be performed, but must be preceded by quantum communication that send qubits involved in the operation to a single process. The communication can be either direct or via relays. We next explain what unitary gates can be used to simulate the classic algorithm of the leader election in the quantum distributed setting. For the purpose of explanation, we assume that the qubits needed to execute each of the following gates have been delivered to proper processes. The pattern of communication assuring this delivery is described in the next paragraph.

1. 1.

   Hadamard gate. This unitary operation on a single qubit is given by the matrix $H=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\ 1&-1\end{bmatrix}$. When applied to every qubit of an $m$-qubit state $\ket{0\ldots 0}$, it produces a uniform superposition of vectors of the computational basis, i.e.,

   $$H^{\otimes m}\ket{0\ldots 0}=\frac{1}{\sqrt{2}\cdot n^{3/2}}\sum_{\ell_{1},\ldots,\ell_{m-1}\in\{0,1\}^{m-1},b\in\{0,1\}}\ket{\ell_{1}\ldots\ell_{m}b}=\frac{1}{2^{m/2}}\sum_{i=0}^{2^{m}-1}\ket{i}\ .$$

   In the beginning, every process applies this gate to its main register $\ket{Leader}\ket{Coin}$ consisting of $3\log+1$ qubits, (line 2). This way the entire system is in the following state:

   $$\left(\frac{1}{\sqrt{2}\cdot n^{3/2}}\sum_{i=0}^{2n^{3}-1}\ket{i}\right)^{\otimes n}=\left(\frac{1}{\sqrt{2}\cdot n^{3/2}}\sum_{i=0}^{2n^{3}-1}\ket{i}\right)\otimes\ldots\otimes\left(\frac{1}{\sqrt{2}\cdot n^{3/2}}\sum_{i=0}^{2n^{3}-1}\ket{i}\right).$$

   Observe, that if all processes measure the main registers in the computational basis, they the outcome has the same probability distribution as a random experiment in which every process draws a number from uniform distribution over $[1,\ldots,n^{3}]$ (first $3\log{n}$ qubits of each register) and a uniform random bit (the last qubit of each register).

2. 2.

   CNOT and Pairwise_CNOT. The $CNOT$ is a 2-qubit gate given by the following unitary transform

   $$CNOT\left(\alpha\ket{00}+\beta\ket{01}+\gamma\ket{10}+\delta\ket{11}\right)=\alpha\ket{00}+\beta\ket{01}+\gamma\ket{11}+\delta\ket{10}.$$

   The Pairwise_CNOT gate works on a register of $2\cdot m$ qubits. Let $A$ be the first half of the register while $B$ is the second. The gate applies the $CNOT$ gate qubit-wisely to corresponding pairs of qubits of $A$ and $B$. We only use this gate when the part $B$ of the entire register is in the state $\ket{0\ldots 0}$. If the part $A$ of the enitre register is in a state $\sum_{i=0}^{2^{m}-1}\alpha_{i}\ket{i}_{A}$ then the unitary gate results in

   $$\texttt{Pairwise\_CNOT}\left(\sum_{i=0}^{2^{m}-1}\alpha_{i}\ket{i}_{A},\ket{0\ldots 0}_{B}\right)=\sum_{i=0}^{2^{m}-1}\alpha_{i}\ket{i}_{A}\ket{i}_{B}\ .$$

   Whenever a process decides to send its qubits to another process, it performs the Pairwise_CNOT gate on its qubits and the new block of $3\log{n}+1$ qubits initialized to $\ket{0\ldots 0}$. Since, as a result, the information needed to be propagated is now also encoded on another $3\log{n}+1$ qubits, the processes can send the new block to another part keeping the original qubits for itself. Observe, however, that this is not a universal copy gate (which is not possible in quantum model of computation), since it does not copy the part $A$ to the part $B$, but rather achieves a specific form of entanglement that encodes the same information if described in the computational basis.

3. 3.

   F_CNOT and Controlled_Swap. Let $f:\{0,1\}^{m}\rightarrow\{0,1\}$ be a Boolean function. Let $A$ be a register of $m$ qubits and $C$ be an additional single qubit register. The gate $\texttt{F\_CNOT}_{f}$ performs $NOT$ operation on the last qubit iff $f(A)=1$. If $C=\ket{0}$, then we get

   $$\texttt{F\_CNOT}_{f}\left(\sum_{i=0}^{2^{m}-1}\alpha_{i}\ket{i}_{A},\ket{0}_{C}\right)=\sum_{i=0}^{2^{m}-1}\alpha_{i}\ket{i}_{A}\ket{f(i)}_{C}\ .$$

   The gate can be implemented using $2^{m}$ unitary transforms. For each vector $x$ from the computational basis such that $f(x)=1$, we apply $NOT$ on the last qubit and then compose at most $2^{m}$ such gates. We note here that we never use the F_CNOT gate on registers of more than $3\log{n}+1$ qubits, therefore the F_CNOT has polynomial size.

   The Controlled_Swap operates on a control register $C$ and two registers of the same size, $A$ and $B$. It swaps the content of two registers of the same size if the control register is $\ket{1}$. Formally, the gate works as follows:

   $$\texttt{Controlled\_Swap}\left(\ket{i}_{A},\ket{j}_{B},\alpha\ket{0}+\beta\ket{1}\right)=\alpha\cdot\ket{i}_{A}\ket{j}_{B}\ket{0}+\beta\cdot\ket{j}_{A}\ket{i}_{B}\ket{1}\ .$$

   We use these two gates whenever a process receives qubits of another process. First, a control qubit $\ket{S}$ is prepared by comparing the content of the received register and the main register of the process. The condition function used in the gate is the following:

   $$f:\{0,1\}^{3\log{n}+1}\times\{0,1\}^{3\log{n}+1}\rightarrow\{0,1\}\ \ ,\ \ f(i,j)\iff i>j\ .$$

   Next, the qubit $\ket{S}$ is passed to the Controlled_Swap gate, operating again on the main register and the newly received qubits. For the $\ket{1}$ part of the control qubit, which corresponds to the fact that the received register has larger values in the computational basis, the gate switches the content of the two registers.

Let us now explain how all the gates listed above work together. As mentioned in the description of the Hadamard gate, after line 2 ends, the main registers of the system are in the state being a uniform superposition of all vectors of the computational basis. Starting from this point, the composition of all gates applied to different registers along the execution can be viewed as a single unitary gate on the entire system, consisting of the qubits that any processes ever created. Note that the unitary transformation might be different depending on the failure in communication, i.e., a failure in delivery of some block of qubits between two processes may result in abandoning gates involving these qubits, but for a moment let us assume that the links are reliable. Since the unitary transformation is linear, it is enough to consider how it affects the vectors of the computational basis. However, all the gates described above behave in the computational basis as their classic equivalents. More precisely, let $\ket{x}$ be a vector from the computational basis spanning the whole circuit. Let $p$ be the process whose main register has the largest^∥∥∥The probability of a tie is polynomially small value in the state $\ket{x}$. From the point of view of this register, the following happens in the algorithm. In each round, $p$ creates an entangled state on $6\log{n}+2$ qubits (see point $(2)$) that has the same qubits on its new block of $3\log{n}+1$ qubits as it has on the main register. Then, it propagates the new block to its neighbors (line 2). The neighbors compare the content of received qubits and exchange them with their main register if their content is smaller (gates F_CNOT and Controlled_Swap in lines 1). This operation is then repeated $(k+2)^{2}(\gamma_{\alpha}+1)$ on the set of links defined by some random evolving graphs, see the later paragraph about adaptive communication pattern. In the end, the processes who, either directly or via relays, received the content of the largest main register, have the same value in their main register. Therefore, the result of the measurement in line 2 must be the same in all these processes.

Assume now that we are able to achieve bidirectional quantum communication between any pair of processes of an $\alpha$-fraction of the entire system, regardless of the (dynamic) actions of the adversary. From the above, the algorithm transforms any vector whose largest main register is one of the registers of the $\alpha$-fraction to a vector such that processes from the $\alpha$-fraction have the same values in main registers. Connecting the above discussion with the fact the algorithm is a $1-$to$-1$ transformation on the linear space of states, we get that the probability of measuring the same values in the processes of the $\alpha$-fraction is at least the probability of measuring the largest value in one of the processes belonging to the $\alpha$-fraction, if the measurement was done before the quantum communication. Since the state is a uniform superposition at that time, the probability is at least $\alpha-o(1)$ and we can claim the following lemma.^******The $o(1)$ part contributes to the unlikely event that there are ties between largest values.

As explained, we not only need that the communication should be efficient in terms of the number of qubits and classic bits, but also it should be such that any two correct processes of a large fraction of the entire system are connected by a short path of correct process so that quantum registers can be relayed. Let $d,\alpha$ be two integers parameters. We define $k=\left\lceil\frac{\log(n/d)}{\log{\alpha}}\right\rceil$, $\gamma_{\alpha}=\frac{\log{n}}{\log{\alpha}}$, and $\delta_{\alpha}=\frac{2}{3}\alpha$. Initially, each process $p$ draws independently $k+1$ sets $\mathcal{N}_{p}(d),\mathcal{N}_{p}(d\alpha^{1}),\ldots,\mathcal{N}_{p}(d\alpha^{k})$, where a set $\mathcal{N}_{p}(d\alpha^{i})$, for $0\leq i\leq k$, includes each process from $\mathcal{P}$ with probability $\frac{d\alpha^{i}}{n}$.

Communication is structured into $(k+2)^{2}$ epochs, see line 2. Each epoch consists of $2(\gamma_{\alpha}+1)$ communication rounds, also called testing rounds. They are scheduled in $\gamma_{\alpha}+1$ iterations within the loop “for” in line 2, each iteration containing two communication rounds (underlined in the pseudocode): sending/receiving inquiries in line 2 and sending/receiving responses in line 2. In the testing rounds of the first epoch, a process $p$ sends inquiries to processes in set $\mathcal{N}_{p}(d)$. The inquired processes respond by sending in the next round (line 2) their current classic state and specially prepared, in line 2, quantum register. However, if in a result of crashes $p$ starts receiving less than $\delta_{\alpha}$ responses per round, it switches its communication neighborhood from $\mathcal{N}_{p}(d)$ to the next, larger set, $\mathcal{N}_{p}(d\cdot\alpha)$. A similar adaptation to a crash pattern is continued in the remaining epochs.

Process $p$ stores the cardinally of the set being inquired in an epoch in the variable $\texttt{degree}_{p}$ (initialized to $d$ in line 2). For the purpose of testing rounds, $p$ copies the value $\texttt{degree}_{p}$ to a variable $\texttt{adaptive\_degree}_{p}$ (line 2). In every testing round, $p$ adapts its variable $\texttt{adaptive\_degree}_{p}$ to the largest value $x\leq\texttt{adaptive\_degree}_{p}$ such that it received at least $\delta_{a}$ responses from processes that have their variable adaptive_degree at least $x$ (loop “while” in line 2). If $p$ had to decrease the value $\texttt{adaptive\_degree}_{p}$ in testing rounds of an epoch, it then increases the main variable $\texttt{degree}_{p}$ by the factor $\alpha$ before the next epoch, see line 2. The latter operation formally encodes the intuition that the process $p$ expected to have $\delta_{\alpha}$ non-faulty neighbors with their values of degree at least as big as its own, but due to crashes it did not happen; Therefore, $p$ increases the number of inquired processes, by adopting the next, larger neighborhood set $\mathcal{N}_{p}(\cdot)$, randomly selected, in order to increase the chance of communication with the majority of non-faulty processes in the next epoch. On the other hand, the adaptive procedure of reducing adaptive_degree in testing rounds of a single epoch helps neighbors of $p$ to estimate correctly the size of the neighborhood that process $p$ is using in the current testing round, which might be much smaller than the value $\texttt{degree}_{p}$ from the beginning of the epoch. This, in turn, calibrates the value of adaptive_degree of the neighbors of $p$, and this calibration can propagate to other processes of distance up to $\gamma_{\alpha}$ from $p$ in the next iterations of testing rounds.

Let us define graphs $\mathcal{G}(d\alpha^{i})$, for $0\leq i\leq k$, as the union of random sets $\cup_{p\in\mathcal{P}}\mathcal{N}_{p}(d\alpha^{i})$. The probability distribution of the graph $\mathcal{G}(d\alpha^{i})$ is the same as the random graph $G(n,y)$ for $y=\frac{d\alpha^{i}}{n}$. Chlebus, Kowalski and Strojnowski [13] showed in their Theorem 2, applied for $k=\frac{64n}{d\alpha^{i-1}}$, that the graph $\mathcal{G}(d\alpha^{i})$ has the following properties, whp:
(i) it is $(\frac{n}{d\alpha^{i-1}})$-expanding, which follows from $(\frac{n}{d\alpha^{i-1}},\frac{2}{3}\frac{n}{d\alpha^{i-2}},\frac{4}{3}\frac{n}{d\alpha^{i-2}})$-edge-expanding property,
(ii) it is $(\frac{n}{d\alpha^{i-1}},\frac{1}{3}\alpha,\frac{2}{3}\alpha)$-edge-dense,                 (iii) it is $(16\frac{n}{d\alpha^{i-1}},3/4,\frac{2}{3}\alpha)$-compact,
(iv) the degree of each node is at most $\frac{21}{20}d\alpha^{i}$.

Since the variable $\texttt{degree}_{p}$ takes values in the set $\{d,d\alpha^{1},\ldots,d\alpha^{k}\}$, the pigeonhole principle assures that eventually $p$ will participate in an epoch in which $\texttt{degree}_{p}$ has not been increased (in the most severe scenario, $p$ will use the set $\mathcal{N}_{p}(d\alpha^{k})$, which consists of all other processes – because it contains each process, as a neighbor of $p$, with probability $1$). The $(\gamma_{\alpha},\delta_{\alpha})$-dense-neighborhood property of random graphs composed from neighborhoods $\mathcal{N}(\texttt{degree}_{p})$ implies that $p$ will then contact a majority of other non-faulty processes via at most $\gamma_{\alpha}+1$ intermediate processes (during testing rounds). Formally, the following holds:

On the other hand, $(16n/d\alpha^{i-1},3/4,2\alpha/3)$-compactness of the (random) graph composed of processes that have the variable degree at least $d\alpha^{i}$, guarantees that the total number of processes that use sets $\mathcal{N}(d\alpha^{i})$ during the epoch $i$ is at most $\frac{n}{\alpha^{i-2}}$, which amortizes communication complexity.

The above discussion yields the following result.

Obviously, the constant-time is achieved in Theorem 5 when $x,\alpha=n^{\epsilon}$, for a constant $\epsilon\in(0,1)$. In this case, the number of rounds is $O\Big{(}\big{(}\frac{1}{\epsilon}\big{)}^{4}\Big{)}$, while the communication complexity is $O(n^{3\epsilon}\log^{2}{n})$ (amortized) per process. In our approach, we generalize the method of Hajiaghayi et al. [25] to denser communication graphs of certain properties, which allows us to achieve constant running time. The constant running time is the key feature of the algorithm, since it is used in the implementation of (expected) constant-round quantum consensus protocol CheapQuantumConsensus. The main difference between ours and the state-of-art approach is a different Gossip protocol used in the divide-and-conquer method.

The FastCounting algorithm is recurrent. It takes as an input the following values: $\mathcal{P}$ is the set of processes on which the algorithm is executed; $p$ is the name of a process which executes the algorithm; $a_{p}\in\{0,1\}$ denotes if $p$ is active ($a_{p}=1$) or not; and parameters $x,d,\alpha$, where $x$ is the branching factor and $d,\alpha$ steer the density of the communication graph in the execution. Knowing the set $\mathcal{P}$ of $n$ processes, FastCounting splits the set into $x$ disjoint groups of processes, each of size between $\left\lfloor\frac{n}{x}\right\rfloor$ and $\left\lceil\frac{n}{x}\right\rceil$. Name these groups $\mathcal{P}_{1},\ldots,\mathcal{P}_{x}$. The groups are known to each participating process. The algorithm then makes $x$ parallel recursive calls on each of these groups. As a result, a process $p$ from a group $\mathcal{P}_{i}$, for $1\leq i\leq x$, gets the number of the active processes in its group $\mathcal{P}_{i}$. In the merging step, all processes execute Gossip algorithm, proposed in Theorem 4, with parameters $d,\alpha$, where the input rumors are the numbers calculated in the recursive calls. To keep the communication small, when processes learn new rumors they always store at most one rumor corresponding to each of the $x$ groups. This way, the number of bits needed to encode all rumors is $O(x\log{n})$. Let $r_{1},\ldots,r_{\ell}$ be the rumors learned by process $p$ from the execution of the Gossip algorithm. The final output of $p$ is the sum $\sum_{i=1}^{\ell}r_{i}$. We provide the pseudocode of the algorithm in Figure 3. Note that all processes run the algorithm to help counting and Gossip, not only those with $a_{p}=1$, but only the latter are counted (see lines 2, 5, 7). For detail analysis of the round and communication bit complexity we refer to Section C.