¹

1 Introduction↩︎

Coordination enables efficient operation in distributed systems. An important application lies in scheduling, where incoming requests must be assigned across multiple servers [1]. Optimal scheduling and load balancing often rely on global state information, such as current server loads or queue lengths. However, acquiring this information via classical communication introduces latency. In latency-sensitive scenarios, this delay can render state information obsolete, leading to suboptimal decisions based on outdated data and consequently degrading overall system performance [2], [3]. For instance, routing incoming user requests without real-time knowledge of server availability can cause load imbalance and increase user wait times. More generally, when routing or scheduling decisions must be made on timescales that are short compared to the communication delay between routers and servers, any attempt to gather fresh state before each decision either introduces unacceptable delay or relies on information that is already stale by the time it is used. For example, in a wide-area deployment with inter-site separations of order \(100\) km, classical round-trip latencies are typically in the sub-millisecond to millisecond range, while local routing or scheduling decisions inside a high-speed service may need to be taken on timescales of tens of microseconds or less. In such regimes, global coordination based on classical communication becomes fundamentally limited.

Entanglement offers a fundamentally new approach to coordination. It provides a mechanism for establishing correlations between spatially separate systems that are stronger than any achievable classically without communication [4], [5]. This mechanism can be implemented as follows. Initially, the coordinating parties share an entangled quantum state. At a later time, upon receiving local information relevant to their coordination task, each party performs a measurement on their component of the entangled state, which can be conditioned on the local information they received. The outcomes of these local measurements will exhibit strong non-local correlations and can be used to guide the parties’ decisions, thus enabling coordination without communication.

In this work, we investigate the application of entanglement-assisted coordination to a routing problem in a distributed system with two servers. The system must process both a continuously available, preemptible baseline task and incoming customer requests. System performance is characterized by the trade-off between baseline task throughput and customer waiting time. The challenge lies in coordinating the assignment of incoming requests to the servers based only on local information, namely the processing time required by the local request, under latency constraints that preclude effective real-time communication. In this work we therefore take strictly non-communicating classical routing policies, where each server’s decision depends only on its own local information, as the baseline for comparison. We emphasize that this restriction is imposed symmetrically on quantum and classical strategies, so that any performance gap isolates the contribution of entanglement at a fixed (zero) communication budget; comparing entanglement-assisted strategies against classical protocols that use delayed or coarse-grained state information is a separate question, which we leave to future work.

We show that when the cumulative baseline output function \(T(t)\) is strictly convex, entanglement-assisted routing achieves Pareto-superior performance compared to optimal classical strategies without communication. Heralded entanglement generation between physically separated systems has been demonstrated in multiple qubit platforms [6]–[8], including over deployed fiber [9]. This makes entanglement-assisted coordination an attractive near-term application of quantum networks.

2 Related Work↩︎

This work provides a complete analytical treatment of the routing problem introduced in [10], where we first demonstrated quantum advantages in distributed scheduling. The present manuscript extends that work with full queueing-theoretic proofs, a rigorous mapping to a weighted non-local game, certified classical bounds and numerical robustness checks against the simplifying assumptions on arrival processes.

The underlying principle behind leveraging entanglement for coordination traces back to Bell’s theorem, which established that quantum mechanics predicts correlations stronger than any classical theory permits [4], [11]. This phenomenon is formalized through non-local games, where non-communicating players cooperate to maximize a payoff; for some games, quantum strategies outperform classical ones [5], [12]. Related but orthogonal to our focus, [13] extends the non-local game framework to settings where parties can communicate subject to timing constraints; our model corresponds to the zero-communication extreme.

Several works have explored translating quantum advantages in abstract non-local games into practical benefits by mapping coordination problems onto game structures. Examples include market making in high-frequency trading [14], load balancing in ad-hoc networks [15], rendezvous tasks [16]–[18], and broader networked systems [19].

From a different perspective, the problem studied in this work falls within the classical domains of load balancing, scheduling theory, and queueing theory; for foundational concepts, see [1], [2], [20]. Our work differs from classical approaches by introducing entanglement as a coordination mechanism.

Classical randomized load-balancing schemes, such as join-the-shortest-queue and the power-of-two-choices family, can dramatically improve performance compared to naive routing by using a small amount of communication to obtain partial state information [21], [22]. Our setting is different in that we explicitly target regimes where the routing decision must be made on timescales short compared to the round-trip communication delay between servers, so even this would either introduce unacceptable delay or rely on stale information. Accordingly, we take strictly non-communicating classical policies as our baseline, and compare them to entanglement-assisted strategies that achieve stronger non-local correlations without real-time communication.

3 System Description↩︎

We now introduce the distributed system we consider, depicted in Figure 1. It consists of two identical servers that process work at rate \(\mu\). Each server maintains a queue of unlimited capacity and follows a first-come, first-served (FCFS) discipline.

The system handles two distinct types of work. First, a continuously available baseline task that is always present and can be processed by either server. This baseline task is preemptible: a server working on it immediately switches to servicing a customer upon assignment. Servers are never idle, as when a server’s queue is empty, it resumes processing the baseline task.

Second, customer requests that arrive dynamically in pairs. Specifically, we assume that pairs of customers arrive simultaneously, with one customer arriving at each of two routers (depicted as circles in Figure 1). Customer pairs arrive according to a Poisson process with rate \(\lambda\). The service time \(X_i\) required by customer \(i\) is drawn independently from an exponential distribution \(\text{Exp}(\mu)\) with mean \(1/\mu\). This yields a two-server FCFS queueing system with Poisson pair arrivals and exponential service times, with per-server utilization \(\rho = \lambda/\mu < 1\) [20].

Upon arrival of a customer pair \((X_1, X_2)\), the routers must assign their respective customers to one of the two servers. Each router observes only the service time of its local customer. A key constraint is that the routers cannot communicate in real time to coordinate this assignment. This models scenarios where physical distance introduces communication latencies that are significant compared to the decision timescale, so exchanging useful real-time state is infeasible.

Each routing strategy induces a splitting probability \(p\), the long-run fraction of customer pairs sent to different servers. When customers are bunched (probability \(1-p\)), one is selected uniformly at random to precede the other in the queue.

We evaluate system performance along two dimensions. First, \(W_q\), the average time customers spend waiting in queue before service begins.

Second, baseline throughput, which measures the system’s productivity on the continuously available baseline task. Recall that servers work on this baseline task whenever their queue is empty, switching to customer service when assignments arrive. Let \(T(t)\) denote the output produced when a server works uninterrupted on the baseline task for duration \(t\). We assume \(T\) is differentiable, increasing, with \(T(0) = 0\). The long-run average baseline throughput per server, which we denote \(\mathcal{T}\), quantifies how much baseline work the system completes over time.

4 The Coordination Challenge↩︎

We show that the optimal routing policy for the routing problem we defined requires both routers to know both service times \((X_1, X_2)\), making it unattainable for routers restricted to local observations and pre-shared resources. This establishes that the routers are faced with a coordination challenge.

A rigorous queueing-theoretic analysis of the model introduced in the previous section, including proofs for statements made in this section, is given in Appendix 9. We start by noting that \(\mathcal{T}\) depends only on the overall splitting probability \(p\), not on which specific pairs are split. This is because throughput depends only on the frequency and duration of idle periods, which are determined by the splitting probability.

In contrast, customer waiting time depends on which pairs are split. Splitting pairs with high service times is disproportionately helpful in reducing waiting time. This is due to the dependence of the waiting time on the second moment of the service time distribution [20].

Given that baseline throughput depends only on \(p\), all routing strategies resulting in the same splitting probability will achieve the same throughput. Hence, among this group of strategies, we wish to find the one that minimizes waiting time. Finding the optimal routing strategy for a fixed splitting probability \(p\) is equivalent to Problem 1. By solving this for all \(p \in [0,1]\), we can characterize the optimal trade-off between the two objectives.

Here \(r(x_1, x_2)\) denotes the probability of splitting a specific pair with realized service times \((x_1, x_2)\), under load-balanced server assignment: when splitting, each server is equally likely to receive either customer; when bunching, the destination server is chosen uniformly at random.² This restriction is without loss of generality, as load-balanced policies achieve weakly lower waiting time at the same throughput (Appendix 9.8). The splitting benefit \(w(x_1,x_2)\) is given by \[w(x_1, x_2) = c_1 x_1 x_2 + c_2(x_1 + x_2),\] where \(c_1 = \frac{\lambda}{2(1-\rho)}\) and \(c_2 = \frac{1}{4}\). This function quantifies the waiting time reduction from splitting rather than bunching a pair with service times \((x_1, x_2)\); higher values indicate pairs where splitting provides greater benefit. The first term arises from the Pollaczek–Khinchine formula [20] for the \(M^X/G/1\) queue, and captures the queueing benefit of reducing workload variance by sending the two customers to different servers. The second captures the within-batch delay: when a pair is bunched behind a single server, one customer waits for the other to finish service. A full derivation is given in Appendix 9. We show in Appendix 9.5 that the solution to this optimization problem has a simple structure: it is a threshold policy that splits pairs when \(w(X_1, X_2) > \tau_p\) and bunches pairs when \(w(X_1, X_2) < \tau_p\), where threshold \(\tau_p\) is chosen such that \(\Pr[w(X_1, X_2) > \tau_p] = p\). We call this the \(w\)-threshold policy.

The strict convexity assumption on \(T(t)\) captures scenarios where longer uninterrupted processing periods yield disproportionately more output, for example, tasks with setup costs, learning curves, or context-switching penalties. Under this assumption, both baseline throughput and customer waiting time strictly decrease with \(p\), creating a trade-off between the two objectives.

The \(w\)-threshold policy requires evaluating \(w(X_1, X_2)\), which depends on both service times. Without real-time communication, however, each router observes only its local service time: router \(A\) sees \(X_1\), and router \(B\) sees \(X_2\). Neither router can directly compute \(w(X_1, X_2)\).

This establishes the coordination challenge: optimal routing decisions are determined by a global quantity \(w(X_1, X_2)\), but routers are constrained to make decisions based on local observations and any pre-shared resources.

In the quantum information literature, such coordination problems are naturally formulated as non-local games, where non-communicating players receive inputs and must produce correlated outputs to maximize a payoff. Bell’s theorem established that quantum entanglement enables stronger correlations than classically achievable without communication, suggesting entanglement might help routers better approximate the \(w\)-threshold policy.

5 Entanglement as a Coordination Resource↩︎

Having established that optimal routing requires non-local information \(w(X_1, X_2)\), we now formulate the coordination problem as a non-local game and show how entanglement enables better approximation of the \(w\)-threshold policy.

A non-local game is a cooperative game between spatially separated players who cannot communicate [5]. Each player receives an input, produces an output, and the players’ joint performance is evaluated by a payoff function depending on all inputs and outputs. Formally:

We map the routing problem to a non-local game (Figure 2) in which the routers act as players A and B. The inputs to the players are the observed service times \(X_1\) and \(X_2\). Each player’s output specifies which server to route their customer to, labelled \(\pm 1\). Note that the splitting probability from Section 4 relates to the outputs by \(r(x_1, x_2) = \Pr[o_A(x_1) \cdot o_B(x_2) = -1]\).

Unlike standard non-local games where performance is measured by winning probability, we weight decisions by \(w(X_1, X_2)\), reflecting the disproportionate impact of misrouting high-service-time pairs on waiting time [20]. The expected payoff under strategies \((o_A, o_B)\) is \(\mathbb{E}_{(X_1, X_2) \sim \pi}[V(X_1, X_2, o_A(X_1), o_B(X_2))]\); we define this as \[A(o_A, o_B) = -\mathbb{E}[o_A(X_1) o_B(X_2) \, w(X_1, X_2)],\] where \(o_A: \mathbb{R}_+ \to \{+1, -1\}\) and \(o_B: \mathbb{R}_+ \to \{+1, -1\}\) denote the decision functions mapping observed service times to output choices. Since splitting corresponds to \(o_A o_B = -1\), higher \(A\) rewards splitting high-\(w\) pairs, precisely what the optimal policy does, translating directly into reduced excess waiting time.

The \(w\)-threshold policy corresponds to \(o_A \cdot o_B = \sigma^*(X_1, X_2)\), where \(\sigma^*(x_1, x_2) = \mathrm{sign}(\tau_p - w(x_1, x_2))\).

The proof is given in Appendix 10. Since all strategies at the same splitting probability \(p\) achieve identical baseline throughput, a strategy with higher \(A\) provides a Pareto improvement in the waiting time–throughput trade-off.

We now describe how entanglement serves as a coordination resource. The routers pre-share an entangled state, e.g., \(\ket{\psi^-} = (\ket{01} - \ket{10})/\sqrt{2}\). Upon observing local service times \(X_1\) and \(X_2\), router A performs a measurement on its qubit in a basis determined by angle \(\theta_A(X_1)\), obtaining outcome \(o_A \in \{+1, -1\}\); router B acts analogously with angle \(\theta_B(X_2)\). The routers then route to server \(o_A\) and \(o_B\) respectively, resulting in bunching when \(o_A \cdot o_B = +1\) and splitting when \(o_A \cdot o_B = -1\).

The quantum advantage question is now precise: can entanglement-assisted strategies achieve \(A_{\text{quantum}} > A_{\text{classical}}\) for this weighted non-local game? In the next section, we establish this affirmatively for a range of system parameters.

6 Main Results↩︎

We now present the main results of this work. First, we establish that quantum advantage in the routing game implies superior routing performance. Second, we prove that optimal classical strategies take a simple threshold form. Third, we demonstrate that quantum advantage manifests across a substantial range of system parameters.

Theorem 2 reduces the question of whether entanglement improves routing performance to determining the advantage region \(\mathcal{P}\). To establish that \(\mathcal{P}\) is nonempty, we need lower bounds on quantum performance and upper bounds on classical performance. Lower bounds are straightforward: we construct explicit quantum strategies and evaluate their payoffs. Upper bounds are in principle more challenging, since we must optimize over all possible local decision functions, i.e., an infinite-dimensional space.

The following theorem provides the structural result that makes classical certification tractable.

The proof is given in Appendix 11. This result reduces classical certification to a tractable finite-dimensional optimization over threshold pairs \((\theta_A, \theta_B)\). Classical players may also use shared randomness to correlate their strategies; the optimal shared-randomness payoff is \(A_{\mathrm{cl,SR}}^*(p) = \mathrm{conc}(A_{\mathrm{cl}}^*)(p)\), the concave envelope of the deterministic value. Our certified bounds compare against this benchmark; see Appendix 11 for details.

The specific values reported here correspond to a stylized parameter regime; they should be interpreted as a certified existence proof of quantum advantage rather than as a quantitative prediction for any deployed system. The dependence of the magnitude of the advantage on the arrival process is explored numerically in Section 6.2.

Both the quantum and classical bounds are obtained numerically. Quantum lower bounds come from explicit strategies parametrised by polynomial measurement angles, optimised by a Gauss-Laguerre quadrature scheme. Classical upper bounds, on the other hand, exploit Theorem 3 to reduce the certification problem to a grid search over threshold pairs \((\theta_A, \theta_B)\), with the residual gap between grid points controlled by an explicit Lipschitz bound on the payoff. Full details are given in Appendix 12.

6.1 Illustrative Example: Warm-up Costs↩︎

Theorem 2 establishes quantum advantage under the assumption that cumulative baseline output \(T(t)\) is strictly convex. We now construct a physically motivated example satisfying this condition and derive the resulting throughput–splitting probability relationship.

For tasks with warm-up dynamics, such as cache population, JIT compilation, or context acquisition, instantaneous productivity \(\phi(t)\) increases over uninterrupted work periods [23]. A natural model is exponential saturation: \[\phi(t) = \phi_{\max}(1 - e^{-\alpha t}),\] corresponding to first-order relaxation toward steady-state productivity \(\phi_{\max}\), with warm-up rate \(\alpha\). Integrating with \(T(0) = 0\) yields \[T(t) = \phi_{\max}\left[t - \frac{1}{\alpha}(1 - e^{-\alpha t})\right],\] which is strictly convex since \(T''(t) = \phi_{\max}\alpha e^{-\alpha t} > 0\).

To obtain long-run average throughput, recall that each server alternates between idle periods \(I \sim \mathrm{Exp}(\Lambda)\), during which it processes baseline work, and busy periods \(B\) serving customers. The batch arrival rate is \(\Lambda = \lambda(1+p)/2\). By the renewal reward theorem [24], \[\mathcal{T}(p) = \frac{\mathbb{E}[T(I)]}{\mathbb{E}[I + B]}.\] Evaluating the numerator using integration by parts (Appendix 9.6) and substituting the mean cycle length gives \[\label{eq:throughput95model} \mathcal{T}(p) = \phi_{\max}(1-\rho) \cdot \frac{2\alpha}{\lambda(1+p) + 2\alpha}.\tag{1}\] This expression decreases in \(p\), as required: more frequent splitting interrupts baseline work before reaching high-productivity steady state. Normalizing by the maximum achievable throughput \(\phi_{\max}(1-\rho)\), corresponding to instantaneous warm-up (\(\alpha \to \infty\)), yields the dimensionless throughput \(\mathcal{T}(p)/[\phi_{\max}(1-\rho)] \in (0,1]\).

Figure 3 shows the waiting time–throughput trade-off using this model. Quantum strategies achieve lower waiting time than classical strategies throughout the certified advantage region, with a maximum reduction in the waiting time gap (relative to the \(w\)-threshold policy) of approximately 21% near \(p \approx 0.20\).

6.2 Independent arrivals and other arrival processes↩︎

Our analytical results rely on two simplifying assumptions: customers arrive in pairs (one at each router simultaneously), and according to a Poisson process. We now show numerically that the quantum advantage persists when both assumptions are relaxed.

When customers arrive independently at the two routers, there is no longer a shared arrival event to align the consumption of entangled pairs. We therefore introduce a clock at rate \(\nu\): at each tick, both routers measure their half of the next entangled pair regardless of buffer state, so pair indices stay synchronised. If a buffer is empty the local outcome is discarded; if both have a customer at the head, the joint outcome routes them.

The clock rate \(\nu\) trades coordination against latency. Stability requires \(\nu > \lambda\). Low \(\nu\) lets buffers fill, raising the probability both routers have a customer at a tick (so entanglement is consumed productively), at the cost of longer in-buffer waits. As \(\nu \to \infty\), ticks almost always find at least one buffer empty and the coordination advantage vanishes. Together with the splitting probability \(p\), this defines a two-dimensional operating space \((\nu, p)\), which we sweep numerically. At each operating point, we simulate the quantum strategy (degree-2 polynomial Bell-measurement angles, optimised on Poisson arrivals and Exp service) and a classical-threshold-clock rule tuned to the same target \(p\), using a purpose-built discrete-event simulator. Classical strategies do not strictly require a clock, as a classical router can decide on arrival, but introducing one lets us trace the same \((\mathcal{T}, W_q)\) trade-off curve as the quantum strategy, enabling a like-for-like comparison.

Beyond independent Poisson, we consider two arrival processes chosen to span very different arrival statistics: at one extreme, fully regular arrivals; at the other, bursty traffic. Under deterministic arrivals, customers arrive at fixed intervals of \(1/\lambda\), with no randomness in the inter-arrival times. For the bursty regime we use a two-state Markov-Modulated Poisson Process (MMPP-2) [25], [26], a standard model for correlated traffic in communication networks. The process alternates between an active state, in which customers arrive as a Poisson process of rate \(2\lambda\), and a silent state, in which no customers arrive. Transitions between the two states happen at a symmetric rate \(q\), so each state has mean duration \(1/q\); smaller \(q\) corresponds to longer bursts and longer silences. The two states are equiprobable in steady-state, so the long-run mean arrival rate is \(\lambda\), matching the Poisson and deterministic processes. Note that the quantum strategies used in this sweep are the same Poisson + Exp-optimised angles applied unchanged: this is a robustness check, not a per-distribution re-optimisation.

Figure 4 summarises the results. The advantage holds with independent rather than paired arrivals, across the full range of \(\lambda\) tested, and broadly grows with load (Figure 4 (a)). Further, it is largest for bursty arrivals, which we expect are more representative of real network traffic (Figure 4 (b)).

7 Discussion and Outlook↩︎

Advantages in non-local games are typically modest in magnitude. The canonical example is the CHSH game, where quantum strategies achieve a winning probability of approximately \(85\%\) versus \(75\%\) for classical strategies, a relative improvement of roughly \(13\%\) [12]. In our weighted routing game, the maximum payoff gap represents a comparable relative advantage. Such gaps might suggest that quantum coordination offers only marginal practical benefit.

However, the relevant metric for system performance is not the probability of the players’ decisions agreeing with the winning condition, but rather operational quantities, such as waiting time and throughput, that may depend non-linearly on coordination quality. This non-linearity can amplify modest coordination improvements into substantial operational gains. In our model, this happens through two distinct mechanisms.

First, the waiting time depends on the second moment of the service time distribution, making misrouting of high-service-time pairs disproportionately costly. Our routing game captures this directly: unlike standard non-local games where all disagreements with the winning condition contribute equally, the payoff weights each routing decision by its operational impact \(w(x_1, x_2)\).

Second, when the baseline throughput function \(T(t)\) is strictly convex, throughput grows super-linearly with uninterrupted processing time. Better coordination at fixed waiting time enables operation at lower splitting probability, with the curvature of \(T(t)\) amplifying small reductions in \(p\) into larger throughput gains. The magnitude of this amplification depends on how severely the baseline task penalizes interruption.

This suggests a general principle: quantum coordination may offer meaningful practical advantage in settings where operational metrics depend super-linearly on coordination quality. In queueing and scheduling contexts, this corresponds to tasks with significant warm-up costs, batch processing requirements, or context-switching penalties.

The quantum resources required to demonstrate this advantage are modest. The protocol uses bipartite entanglement shared between the two decision makers and local measurements conditioned on the observed service times. Each routing decision consumes at most one shared entangled pair, so in steady state the entanglement consumption rate is of the same order as the routing decision rate in the target system. Heralded entanglement generation and storage have been demonstrated in several physical platforms [6]–[8], including over deployed metropolitan fiber [9]. Our analysis relies on two assumptions: (i) an entangled pair is present when a routing decision is made, and (ii) memory readout is deterministic. Both hold for heralded entanglement with near-unit efficiency memory. Unheralded schemes (e.g., SPDC-based) do not guarantee (i), and low-efficiency memories do not guarantee (ii).

In this work we assumed perfect, always-available entanglement. In practice, non-unit fidelity reduces the achievable quantum payoff, while limited entanglement availability (due to generation rate or memory lifetime) causes the effective policy to interpolate between quantum and classical performance. Quantifying the fidelity and availability thresholds required to retain meaningful advantage is an important direction for future work.

For our proofs, we assumed paired simultaneous Poisson arrivals for ease of analysis. Our numerical results indicate that quantum advantage persists for independent arrivals, and is larger for burstier arrivals, which are more representative of network traffic.

Our analysis targets settings where routing decisions must be taken faster than classical round-trip communication allows, so our baseline explicitly rules out real-time state exchange. Comparing against latency-constrained classical protocols that use delayed or coarse-grained state information would require separate analysis. Promising application domains include wide-area content-delivery networks and wireless medium-access control, where uninterrupted background processing is disproportionately valuable.

8 Conclusion↩︎

We have shown that entanglement-assisted coordination yields rigorously certified performance gains in a concrete distributed routing model. Specifically, we characterized the optimal full-information routing policy as a weighted threshold rule, formulated the coordination problem as a weighted non-local game with payoff directly determining waiting time, proved that optimal classical strategies take a threshold form enabling efficient certification, and demonstrated quantum advantage across a substantial parameter range.

These results suggest distributed scheduling and load balancing as a candidate application domain for near-term quantum networks, offering a starting point for translating non-local correlations into operational improvements in latency-constrained distributed systems.

Code Availability↩︎

The code used to perform the numerical optimizations and generate the figures in this paper is available at https://gitlab.com/FranciscoHS/entanglement-routing-advantage.

Acknowledgements↩︎

We thank Jeroen Grimbergen and John Gardiner for useful discussions on the mathematical analysis. We thank Conor E. Bradley, Janice van Dam and Scarlett Gauthier for critical reading of earlier versions of the manuscript. We acknowledge funding from the Dutch Research Council (NWO) through the project “QuTech Part III Application based research - Demonstrators” (project number 601.QT.001), and from the European Union under project InQubate-101213305. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Innovation Council. Neither the European Union nor the granting authority can be held responsible for them.

Competing Interests↩︎

The authors declare no competing financial or non-financial interests.

Author Contributions↩︎

F.F.S. and S.W. conceptualized the project. F.F.S. developed the queueing-theoretic analysis, proved the theoretical results, performed the numerical analysis, and wrote the manuscript. All authors revised the manuscript.

9 The \(w\)-threshold policy is Pareto optimal↩︎

In this appendix we present a rigorous analysis of the queueing model introduced in the main text, culminating in a proof that the \(w\)-threshold policy achieves Pareto optimality: no other policy can improve one objective (reduce waiting time or increase throughput) without worsening the other.

A central quantity in our analysis is the splitting benefit function \[w(x_1, x_2) = c_1 x_1 x_2 + c_2(x_1 + x_2),\] where \(c_1 = \frac{\lambda}{2(1-\rho)}\) and \(c_2 = \frac{1}{4}\). This function quantifies the reduction in expected customer waiting time achieved by splitting a pair with service times \((x_1, x_2)\) rather than bunching them. The term \(c_1 x_1 x_2\) captures the queueing benefit from reducing workload variance, while \(c_2(x_1 + x_2)\) captures the delay avoided when customers are sent to separate servers rather than queued behind one another. The optimal routing policy, as we shall prove, takes a simple threshold form: split pairs for which \(w(x_1, x_2)\) exceeds a threshold \(\tau\), and bunch pairs for which it falls below.

We structure the appendix as follows. First, we formalize the system model and establish key symmetry properties. We then reduce the system to a single-server perspective, define the core quantities and decompose customer waiting time into interpretable components. With this foundation, we formulate the routing problem as a constrained optimization over splitting decisions and prove that the \(w\)-threshold policy is optimal at any fixed splitting probability.

9.1 Model↩︎

We consider a distributed system consisting of two identical servers and two routers. Each server has a queue of unlimited capacity to hold incoming requests and follows a first-come, first-served (FCFS) discipline. The system handles two types of work. First, a continuously available, preemptible baseline task. Second, servicing customers. When a customer is assigned to a server processing the baseline task, the server immediately preempts the baseline work and begins servicing the customer. Customers arrive in pairs, one at each router, according to a Poisson process with rate \(\lambda\). Each customer’s service time is drawn independently from an exponential distribution Exp(\(\mu\)) (rate \(\mu\), mean \(1/\mu\)). We denote a customer pair’s service times as \((X_1,X_2)\).

Servers are never idle. When a server completes service for all customers in its queue and finds the queue empty, it immediately resumes processing the baseline task until the next customer arrival. Note that baseline work does not affect customer waiting-time calculations. It only fills customer-less periods. However, the baseline throughput depends on the distribution of the lengths of these ‘idle’ periods (e.g., due to setup costs or non-linear returns on uninterrupted baseline time), creating a trade-off with customer waiting times.

Upon arrival of a customer pair, each router decides to which server to route its incoming customer. We assume each router observes the service time of its customer, but has no other information. They do not know the service time of the other customer in the pair, nor do they have information about the state of the server and its queue. Under these constraints, an implementable routing policy is a map from a single observed service time to a choice of server. To provide a fundamental bound on performance, we analyze oracle routing policies that have access to both service times \((X_1, X_2)\) when making routing decisions. These policies provide a lower bound on waiting time achievable by any implementable policy, which observes only a single service time. An oracle policy maps each pair \((x_1, x_2)\) to a distribution over four routing actions: split with \(\min(x_1,x_2)\) to Server 1, split with \(\max(x_1,x_2)\) to Server 1, bunch to Server 1, or bunch to Server 2. We parameterize policies by the splitting probability \(r(x_1, x_2) \in [0,1]\), the probability that a pair with service times \((x_1, x_2)\) is split. The overall splitting probability is \(p := \mathbb{E}[r(X_1,X_2)]\). When writing expectations involving the routing policy, we use the shorthand \(\mathbb{E}[r \cdot f(X_1, X_2)]\) to denote \(\mathbb{E}[r(X_1, X_2) \cdot f(X_1, X_2)]\).

When two customers are sent to the same server, one customer is selected uniformly at random to precede the other. Both are then processed FCFS.

We restrict attention to load-balanced policies, which treat the two servers identically: when splitting, each server is equally likely to receive the larger job; when bunching, the destination server is chosen uniformly at random. This restriction is without loss of generality.

We prove this in Appendix 9.8. The key insight is that baseline throughput depends only on the splitting probability \(p\), not on the server assignment when splitting or bunching (Proposition 2), while load imbalance strictly increases waiting time. Thus load-balanced policies weakly dominate all other policies in the joint (waiting time, throughput) space, and restricting attention to them is without loss of generality for characterizing the Pareto frontier.

Under load-balanced policies, both servers see statistically identical arrival processes: each receives customers at rate \(\lambda\), with identical batch size distributions and identical conditional service time distributions. We may therefore analyze the system from the perspective of a single server. This yields per-server utilization \(\rho = \lambda/\mu\), independent of the splitting probability. We assume \(\rho < 1\) throughout, ensuring stability.

From this single-server perspective, customers arrive according to a compound Poisson process with batch arrival rate \[\Lambda = \lambda\frac{1+p}{2}\] and batch size distribution (for \(K\in\{1,2\}\)) \[\Pr\{K=1\} = \frac{2p}{1+p}, \qquad \Pr\{K=2\} = \frac{1-p}{1+p}.\] These expressions follow from the splitting/bunching structure. The batch arrival rate \(\Lambda = \lambda(1+p)/2\) is obtained by averaging \(\lambda(1+r(x_1,x_2))/2\) (the rate at which batches are generated at this server) over \((X_1, X_2)\). The batch size probabilities are then obtained by normalizing the rates of size-1 arrivals (from split pairs, rate \(\lambda p\)) and size-2 arrivals (from bunched pairs sent here, rate \(\lambda(1-p)/2\)). Note that the customer arrival rate at a single server is \(\Lambda \mathbb{E}[K] = \lambda\), as required by symmetry. Because the routing policy depends on \((X_1,X_2)\), the per-customer service time distribution at a server is generally non-exponential; hence the single-server model is \(M^X/G/1\) (compound Poisson arrivals with general service times). Note that for batches of size \(K=2\), the service times \((X_1, X_2)\) are generally not independent, as their presence in the same batch is conditioned on the routing policy \(r(x_1, x_2)\).

9.2 Single-server primitives and batch workload↩︎

We now derive the second moment of the batch workload seen by a single server, which is the key input to the Pollaczek–Khinchine formula [20] for computing expected waiting time.

We apply the Pollaczek–Khinchine (PK) formula for an \(M^X/G/1\) queue, which expresses the expected virtual waiting time, i.e., the time until a batch begins service, as: \[\mathbb{E}[W_q^{\text{virtual}}] = \frac{\Lambda \mathbb{E}[B_s^2]}{2(1-\rho)},\] where \(\Lambda\) is the batch arrival rate and \(\mathbb{E}[B_s^2]\) is the second moment of the batch workload. The full customer waiting time additionally includes within-batch delay, i.e., the time one customer spends waiting for its partner in a batch, which we derive in Appendix 9.3. We have already established that \(\Lambda = \lambda (1+p)/2\). In this section, we derive the product \(\Lambda \mathbb{E}[B_s^2]\).

For a customer pair with service times \((X_1, X_2)\), define the total service time \(S = X_1 + X_2.\) We require only that \(S\) has finite first and second moments, which is satisfied under individual customer service times Exp(\(\mu\)).

Rather than computing \(\mathbb{E}[B_s^2]\) directly (which would require conditioning on a batch arriving at this server), we compute the expected squared-workload contribution from each arriving pair. For a pair \((x_1, x_2)\) with splitting probability \(r = r(x_1, x_2)\), define \(Y\) to be the squared workload contributed to this server. The possible outcomes are:

• With probability \((1-r)/2\), the pair is bunched to this server, contributing \((x_1 + x_2)^2\).

• With probability \(r/2\), the pair is split and \(x_1\) is routed here, contributing \(x_1^2\).

• With probability \(r/2\), the pair is split and \(x_2\) is routed here, contributing \(x_2^2\).

• With probability \((1-r)/2\), the pair is bunched to the other server, contributing \(0\).

Thus \[\mathbb{E}[Y | x_1, x_2] = \frac{1-r}{2}(x_1+x_2)^2 + \frac{r}{2}x_1^2 + \frac{r}{2}x_2^2 = \frac{1}{2}\left[(1-r)(x_1+x_2)^2 + r(x_1^2+x_2^2)\right].\] Since pairs arrive at rate \(\lambda\), the expected sum of squared batch workloads per unit time is \(\lambda \mathbb{E}[Y]\), which equals \(\Lambda \mathbb{E}[B_s^2]\). Therefore \[\Lambda\,\mathbb{E}[B_s^2] = \frac{\lambda}{2}\,\mathbb{E}\!\left[(1-r)(X_1+X_2)^2+r\,(X_1^2+X_2^2)\right].\] Rearranging, \[\begin{align} \Lambda\,\mathbb{E}[B_s^2] &=\frac{\lambda}{2}\,\mathbb{E}\!\left[(X_1+X_2)^2 - r\left((X_1+X_2)^2 - X_1^2-X_2^2\right)\right]\\ &=\frac{\lambda}{2}\Big(\mathbb{E}[S^2]-2\mathbb{E}[r\,X_1X_2]\Big). \end{align}\]

9.3 Waiting time decomposition↩︎

We now characterize the mean customer waiting time under a given routing policy. From the single-server perspective established in Appendix 9.1, we have an \(M^X/G/1\) queue with batch arrival rate \(\Lambda = \lambda(1+p)/2\) and utilization \(\rho = \lambda/\mu\).

The customer waiting time can be decomposed into two components. First, the virtual wait: the time a customer waits for work already in the system when its batch arrives. Second, the within-batch delay: the additional time a customer waits if it is the second customer in a size-2 batch, in which case it must wait for its partner’s service to complete.

The virtual wait component is given by the Pollaczek–Khinchin formula for \(M^X/G/1\) queues: \[\mathbb{E}[W_q^{\text{virtual}}] = \frac{\Lambda \mathbb{E}[B_s^2]}{2(1-\rho)}.\] From Appendix 9.2, we have \(\Lambda \mathbb{E}[B_s^2] = \frac{\lambda}{2}(\mathbb{E}[S^2] - 2\mathbb{E}[rX_1X_2])\), so \[\mathbb{E}[W_q^{\text{virtual}}] = \frac{\lambda(\mathbb{E}[S^2] - 2\mathbb{E}[rX_1X_2])}{4(1-\rho)}.\] Note that \(\rho = \lambda/\mu\) does not depend on the policy.

For the within-batch delay, consider a given pair \((x_1, x_2)\). If the pair is bunched (probability \(1-r\)), one of the two customers waits for the other’s service. The expected within-batch delay for a randomly selected customer from this pair is \((x_1 + x_2)/4\): with probability \(1/2\) the customer is second and waits for an expected time of \((x_1 + x_2)/2\). Therefore, the expected within-batch delay contribution from a pair \((x_1, x_2)\) is \((1-r)(x_1+x_2)/4\). Averaging over all pairs yields \[\mathbb{E}[\text{within-batch delay}] = \tfrac{1}{4}\,\mathbb{E}[(1-r)S],\] where \(S = X_1 + X_2\).

The total mean waiting time is therefore \[\mathbb{E}[W_q] = \mathbb{E}[W_q^{\text{virtual}}] + \mathbb{E}[\text{within-batch delay}] = \frac{\lambda(\mathbb{E}[S^2] - 2\mathbb{E}[rX_1X_2])}{4(1-\rho)} + \frac{1}{4}\mathbb{E}[(1-r)S].\]

9.4 Optimization formulation at fixed splitting probability↩︎

We now formulate the routing problem as a constrained optimization. Recall from Appendix 9.3 that \[\mathbb{E}[W_q] = \frac{\lambda(\mathbb{E}[S^2] - 2\mathbb{E}[rX_1X_2])}{4(1-\rho)} + \frac{1}{4}\mathbb{E}[(1-r)S].\] Expanding the within-batch term as \(\mathbb{E}[(1-r)S] = \mathbb{E}[S] - \mathbb{E}[rS]\), we obtain \[\mathbb{E}[W_q] = \frac{\lambda\mathbb{E}[S^2]}{4(1-\rho)} + \frac{\mathbb{E}[S]}{4} - \frac{\lambda}{2(1-\rho)}\mathbb{E}[rX_1X_2] - \frac{1}{4}\mathbb{E}[rS].\]

Define constants \[c_1 = \frac{\lambda}{2(1-\rho)}, \qquad c_2 = \frac{1}{4}.\] Then we can write \[\mathbb{E}[W_q] = \text{const} - \big(c_1\,\mathbb{E}[r X_1 X_2] + c_2\,\mathbb{E}[rS]\big),\] where \(\text{const} = \frac{\lambda\mathbb{E}[S^2]}{4(1-\rho)} + \frac{\mathbb{E}[S]}{4}\) is independent of the routing policy.

Since minimizing \(\mathbb{E}[W_q]\) is equivalent to maximizing the term in parentheses, we can formulate the routing problem at fixed splitting probability \(p \in [0,1]\) as:

9.5 Optimal policy↩︎

We now characterize the solution to Problem 2. Recall the splitting benefit function \(w: \mathbb{R}_+^2 \to \mathbb{R}_+\) defined at the beginning of this appendix: \[w(x_1, x_2) = c_1 x_1 x_2 + c_2(x_1 + x_2),\] where \(c_1 = \frac{\lambda}{2(1-\rho)}\) and \(c_2 = \frac{1}{4}\). The objective function can thus be written compactly as \(\mathbb{E}[r \cdot w(X_1, X_2)]\). Since \(X_1, X_2 \sim \text{Exp}(\mu)\), all moments exist, and \(w(X_1, X_2)\) is integrable, i.e., \(w \in L^1\).

The threshold structure arises because the constraint \(\mathbb{E}[r] = p\) acts like a budget: we may split at most a fraction \(p\) of pairs on average. Optimality requires allocating this budget to pairs with highest marginal benefit \(w\).

As the target splitting probability \(p\) increases, the threshold \(\tau_p\) decreases, allowing more pairs to be split. This family of policies, indexed by \(p\), will be shown to trace the Pareto frontier between customer waiting time and the baseline throughput (which is a function of \(p\)).

9.6 Baseline task throughput↩︎

Having characterized the policy minimizing waiting time at fixed splitting probability, we now analyze the second objective—baseline throughput—to establish the Pareto trade-off.

Following the single-server perspective established in Appendix 9.1, we analyze one server’s baseline throughput. Recall that each server processes a continuously available baseline task when it has no customers to service, switching between customer and baseline work instantly with no overhead.

The server alternates between idle periods, when no customers are present, and busy periods, when at least one is. Let \(I\) denote the duration of an idle period and \(B\) denote the duration of a busy period.

During an idle period, the server processes baseline work until the next batch arrival. Since batches arrive according to a Poisson process with rate \(\Lambda = \lambda(1+p)/2\), the duration of an idle period is exponentially distributed: \[I \sim \text{Exp}(\Lambda), \qquad \mathbb{E}[I] = \frac{1}{\Lambda} = \frac{2}{\lambda(1+p)}.\]

For the busy period, we derive the mean duration using a rate-balance argument. By PASTA (Poisson Arrivals See Time Averages) [27], a batch arriving according to a Poisson process finds the system in steady state: idle with probability \(1-\rho\) and busy with probability \(\rho\). Busy periods are therefore initiated at rate \(\Lambda(1-\rho)\)—the batch arrival rate times the probability of finding an idle server. Since the long-run fraction of time spent busy equals the rate of entering the busy state times the mean time spent there, we have \(\rho = \Lambda(1-\rho) \cdot \mathbb{E}[B]\), giving \(\mathbb{E}[B] = \rho / [\Lambda(1-\rho)]\). Substituting \(\rho=\lambda/\mu\) and \(\Lambda=\lambda(1+p)/2\), \[\mathbb{E}[B] = \frac{\rho}{\Lambda(1-\rho)} = \frac{2}{(1+p)(\mu-\lambda)},\] which decreases with \(p\), implying that higher splitting probability leads to shorter busy periods.

The system forms a renewal process: since the system returns to the same empty state at the end of each busy period, and Poisson arrivals are memoryless, successive cycles are independent. The mean cycle length is \[\mathbb{E}[I+B] = \frac{2}{\lambda(1+p)} + \frac{2}{(1+p)(\mu-\lambda)} = \frac{2}{1+p}\left(\frac{1}{\lambda} + \frac{1}{\mu-\lambda}\right).\]

Let \(T(t)\) denote the amount of baseline work completed during an idle period of length \(t\). We assume \(T\) is increasing (longer idle periods complete more work), differentiable with \(T(0) = 0\), and denote its derivative by \(\phi = T'\).

To compute the long-run average baseline throughput, we apply the renewal reward theorem [24]: the long-run average reward per unit time equals the expected reward per cycle divided by the expected cycle length. Here, the “reward” in each cycle is the baseline work \(T(I)\) completed during the idle period. Therefore, the long-run average baseline throughput per server is: \[\mathcal{T}(p) = \frac{\mathbb{E}[T(I)]}{\mathbb{E}[I + B]},\] where \[\mathbb{E}[T(I)] = \int_0^\infty T(t) \Lambda e^{-\Lambda t}\,dt.\]

Note that baseline throughput depends only on the splitting probability \(p\), not on which specific pairs are split.

For tasks with setup costs, learning curves, or context-switching penalties, the function \(T\) is convex and baseline throughput strictly decreases with splitting probability. In what follows, we focus on the strictly convex case, which yields a nontrivial Pareto trade-off between the two objectives.

9.7 Pareto optimality of the threshold policy↩︎

We now establish that the \(w\)-threshold policy characterized in Theorem 5 achieves the Pareto frontier between customer waiting time and baseline task throughput.

Recall that any routing policy induces a splitting probability \(p = \mathbb{E}[r] \in [0,1]\). From Proposition 2, the baseline throughput \(\mathcal{T}(p)\) depends only on this splitting probability, not on which specific pairs are split. Thus characterizing the Pareto frontier reduces to minimizing customer waiting time at each fixed splitting probability.

For a fixed splitting probability \(p \in [0,1]\), Theorem 5 establishes that the threshold policy \(r^*_p\) minimizes customer waiting time among all policies achieving splitting probability \(p\). We now show that as \(p\) varies over \([0,1]\), these optimal policies trace out the complete Pareto frontier.

Theorem 6 establishes that the \(w\)-threshold policy achieves the complete Pareto frontier. The operating point can be selected by choosing an appropriate splitting probability \(p\) (or, equivalently, threshold \(\tau\)): higher splitting probability reduces customer waiting time at the expense of baseline throughput.

9.8 Optimality of Load-Balanced Server Assignment↩︎

We now prove Proposition 1, justifying the restriction to load-balanced policies. For any routing policy that induces a splitting probability \(p\), we show that load-balanced server assignment minimizes the average customer waiting time.

This completes the technical foundations for the coordination challenge established in Section 4 of the main text.

10 Mapping to a Non-Local Game↩︎

In this appendix, we show that the distributed routing problem introduced in the main text and analyzed in detail in Appendix 9 can be formulated as a non-local game. With this formulation, we establish an exact correspondence between performance in the non-local game and excess waiting time relative to the \(w\)-threshold policy.

10.1 Local Strategies↩︎

The analysis in Appendix 9 characterized the \(w\)-threshold policy, which is optimal when both service times \((X_1, X_2)\) are available for routing decisions. This policy splits pairs with high splitting benefit \(w(x_1, x_2)\) and bunches pairs with low splitting benefit, achieving the minimum waiting time at any given splitting probability.

In practice, each router observes only its local customer’s service time. Router A (B) observes \(x_1\) (\(x_2\)) and must choose an output based solely on this value. This is precisely the setting of a non-local game, where non-communicating players receive local inputs and must produce outputs.

The key question becomes: how well can local strategies approximate the \(w\)-threshold policy? Classical strategies (with shared randomness) and quantum strategies (with shared entanglement) may achieve different performance levels. The non-local game formulation allows us to quantify this gap precisely.

10.2 Setup↩︎

Fix a splitting probability \(p \in [0,1]\) and let \(\tau_p\) be the unique threshold satisfying \(\Pr[w(X_1,X_2) > \tau_p] = p\). Define the decision function \[\sigma^*(x_1,x_2) = \mathrm{sign}(\tau_p - w(x_1,x_2)),\] which takes value \(+1\) (bunch) when \(w < \tau_p\) and \(-1\) (split) when \(w > \tau_p\). This is the \(w\)-threshold policy established in Appendix 9: split when the splitting benefit exceeds the threshold, and bunch otherwise.

A local routing strategy is specified by output functions \(o_A: \mathbb{R}_+ \to \{+1, -1\}\) and \(o_B: \mathbb{R}_+ \to \{+1, -1\}\), where router A observes \(X_1\) and outputs \(o_A(X_1)\), and router B observes \(X_2\) and outputs \(o_B(X_2)\). The product \(o_A(X_1) o_B(X_2) = +1\) indicates bunching (both routers choose the same server) and \(o_A(X_1) o_B(X_2) = -1\) indicates splitting (routers choose different servers). We define the split indicator \(s = (1 - o_A o_B)/2 \in \{0,1\}\), which equals \(1\) when the pair is split and \(0\) when bunched. Note that \(s \in \{0,1\}\) is a realized outcome for each pair, whereas \(r(x_1, x_2) \in [0,1]\) in Appendix 9 denotes a splitting probability.

We restrict attention to strategies achieving splitting probability \(p\): \[\Pr[o_A(X_1) o_B(X_2) = -1] = p.\] This constraint is natural because, as established in Appendix 9.6, baseline throughput depends only on the splitting probability \(p\). Comparing strategies at fixed \(p\) therefore isolates the waiting time objective.

10.3 The Queueing–Game Correspondence↩︎

10.4 Non-Local Game Formulation↩︎

We cast the routing problem as a non-local game (Definition 2). Players A and B receive service times \(X_1, X_2 \sim \mathrm{Exp}(\mu)\) independently and produce outputs \(o_A(X_1), o_B(X_2) \in \{+1, -1\}\) without communication. The game payoff is \[\label{eq:game-payoff} A(o_A, o_B) = -\mathbb{E}[o_A(X_1) o_B(X_2) \cdot w(X_1,X_2)],\tag{4}\] subject to the constraint \(\Pr[o_A(X_1) o_B(X_2) = -1] = p\). The payoff \(A\) rewards splitting (which corresponds to \(o_A o_B = -1\)) in proportion to the splitting benefit \(w\), directly encoding the queueing objective \(\mathbb{E}[s \cdot w]\) that determines waiting time.

The following theorem extends this pointwise comparison to Pareto dominance across a range of splitting probabilities.

11 Classical Strategies↩︎

This appendix characterizes what classical strategies can achieve in the routing game defined in Appendix 10. We first show that optimal deterministic strategies take a threshold form, then establish the correct classical benchmark when shared randomness is allowed.

11.1 Optimal Deterministic Strategies↩︎

We show that optimal deterministic strategies take a simple threshold form, reducing the infinite-dimensional optimization to a two-dimensional problem.

The main result of this section is the following.

The proof proceeds by showing that, for any fixed strategy of one player, the optimal response of the other player is a threshold strategy.

11.2 Shared Randomness and the Classical Benchmark↩︎

We now consider classical strategies augmented with shared randomness. A shared-randomness strategy uses a common random variable \(\kappa\) (independent of the inputs \(X_1, X_2\)) to select a deterministic local strategy \((o_{A,\kappa}, o_{B,\kappa})\) for each arriving pair. The resulting payoff is \(\mathbb{E}_\kappa[A(o_{A,\kappa}, o_{B,\kappa})]\), and the splitting constraint requires \(\mathbb{E}_\kappa[p_\kappa] = p\), where \(p_\kappa = \Pr[o_{A,\kappa}(X_1) o_{B,\kappa}(X_2) = -1]\).

However, shared randomness can improve performance by mixing strategies at different splitting probabilities \(p_1, \ldots, p_n\) with \(\sum_i q_i p_i = p\). This motivates the following definition.

The key result is that \(A_{\mathrm{cl,SR}}^*(p)\) equals the concave envelope of the deterministic value.

This completes the characterization of classical strategies. The numerical methods for computing \(A_{\mathrm{cl}}^*(p)\) and its concave envelope are presented in Appendix 12.

12 Numerical Methods↩︎

This appendix describes the numerical methods used to compute the waiting time–throughput trade-off curves for classical and quantum strategies presented in the main text.

12.1 Overview↩︎

To construct the Pareto frontier comparison between classical and quantum strategies, we compute three quantities at each splitting probability \(p \in (0, 1/2)\):

1. The \(w\)-threshold payoff \(A^*(p)\), achieved by the optimal policy with full access to both service times;

2. The optimal classical payoff \(A_{\mathrm{cl}}^*(p)\), achieved by the best local threshold strategy;

3. The quantum payoff \(A_{\mathrm{qu}}(p)\), achieved by a numerically optimized quantum strategy.

The waiting time gap relative to the \(w\)-threshold policy is then obtained via the game–queueing correspondence (Proposition 4): \[\Delta W_q = \frac{A^*(p) - A(p)}{2},\] where \(A(p)\) is the payoff achieved by either the classical or quantum strategy.

12.2 Classical Upper Bound via Threshold Strategies↩︎

By Theorem 8, optimal deterministic classical strategies take the form of threshold strategies. This section provides the explicit parameterization and certified computation procedure.

12.2.1 Explicit Parameterization↩︎

For \(X \sim \mathrm{Exp}(\mu)\) and threshold strategy \(f_\theta\), the relevant moments are: \[\begin{align} D_0(\theta) &:= \mathbb{E}[f_\theta(X)] = \Pr[X < \theta] - \Pr[X \geq \theta] = 1 - 2e^{-\mu\theta}, \\ D_1(\theta) &:= \mathbb{E}[f_\theta(X) \cdot X] = \int_0^\theta x \mu e^{-\mu x}\, dx - \int_\theta^\infty x \mu e^{-\mu x}\, dx. \end{align}\]

Evaluating the integrals: \[\begin{align} \int_0^\theta x \mu e^{-\mu x}\, dx &= \frac{1}{\mu}\bigl(1 - e^{-\mu\theta}(1 + \mu\theta)\bigr), \\ \int_\theta^\infty x \mu e^{-\mu x}\, dx &= \frac{1}{\mu}e^{-\mu\theta}(1 + \mu\theta). \end{align}\]

Therefore: \[D_1(\theta) = \frac{1}{\mu}\bigl(1 - 2e^{-\mu\theta}(1 + \mu\theta)\bigr) = \frac{1}{\mu}D_0(\theta) - 2\theta e^{-\mu\theta}.\]

For threshold strategies with thresholds \(\theta_A\) and \(\theta_B\), the game payoff becomes: \[\label{eq:payoff-thresholds} A(\theta_A, \theta_B) = -c_1 D_1(\theta_A) D_1(\theta_B) - c_2\bigl(D_1(\theta_A) D_0(\theta_B) + D_0(\theta_A) D_1(\theta_B)\bigr),\tag{5}\] and the splitting constraint becomes: \[\label{eq:constraint-thresholds} D_0(\theta_A) \cdot D_0(\theta_B) = 1 - 2p.\tag{6}\]

The optimal classical value at splitting probability \(p\) is: \[A_{\mathrm{cl}}^*(p) = \max_{\substack{\theta_A, \theta_B \geq 0 \\ D_0(\theta_A) D_0(\theta_B) = 1 - 2p}} A(\theta_A, \theta_B).\]

12.2.2 Reduction to One-Dimensional Optimization↩︎

The constraint \(D_0(\theta_A) \cdot D_0(\theta_B) = 1 - 2p\) defines a one-dimensional curve in \((\theta_A, \theta_B)\) space. We parameterize this curve by \(\theta_A\) and solve for \(\theta_B\).

Recall that \(D_0(\theta) = 1 - 2e^{-\mu\theta}\) is strictly increasing in \(\theta\), with \(D_0(0) = -1\) and \(\lim_{\theta \to \infty} D_0(\theta) = 1\). Given \(\theta_A\), the constraint requires \[D_0(\theta_B) = \frac{1 - 2p}{D_0(\theta_A)}.\] For \(\theta_B\) to exist (i.e., for the right-hand side to lie in \((-1, 1)\)), we need \[-1 < \frac{1 - 2p}{D_0(\theta_A)} < 1.\]

For \(p \in (0, 1/2)\), we have \(1 - 2p > 0\). The constraint \(\frac{1-2p}{D_0(\theta_A)} < 1\) requires \(D_0(\theta_A) > 1 - 2p\), i.e., \(\theta_A > \theta_{\min}\) where \[\theta_{\min} = -\frac{\ln p}{\mu}.\] The constraint \(\frac{1-2p}{D_0(\theta_A)} > -1\) imposes no additional restriction beyond \(\theta_A > \theta_{\min}\): once \(D_0(\theta_A) > 1-2p > 0\), the lower bound is automatically satisfied since \(\frac{1-2p}{D_0(\theta_A)} > 0 > -1\).

For \(p \in (1/2, 1)\), we have \(1 - 2p < 0\), and a symmetric analysis applies with the roles of upper and lower bounds exchanged.

Henceforth, we focus on \(p \in (0, 1/2)\); the case \(p > 1/2\) is analogous. The feasible range is \(\theta_A \in (\theta_{\min}, \infty)\), and by symmetry of the problem, we may restrict to \(\theta_A \in (\theta_{\min}, \theta_{\mathrm{sym}}]\) where \(\theta_{\mathrm{sym}}\) is the symmetric point satisfying \(\theta_A = \theta_B\).

Given feasible \(\theta_A\), we compute \[\theta_B(\theta_A) = -\frac{1}{\mu} \ln\left(\frac{1}{2}\left(1 - \frac{1 - 2p}{D_0(\theta_A)}\right)\right).\]

Define the reduced objective function \(\tilde{A}: (\theta_{\min}, \infty) \to \mathbb{R}\) by \[\tilde{A}(\theta_A) := A(\theta_A, \theta_B(\theta_A)).\]

The optimal classical value is \[A_{\mathrm{cl}}^*(p) = \sup_{\theta_A > \theta_{\min}} \tilde{A}(\theta_A).\]

12.2.3 Certified Grid Search↩︎

To compute \(A_{\mathrm{cl}}^*(p)\) with certified error bounds, we discretize the feasible interval and bound the error due to discretization.

Fix a compact search interval \([\theta_{\min} + \epsilon, \theta_{\max}]\) for some small \(\epsilon > 0\) and large \(\theta_{\max}\). We separately bound the contribution from the excluded regions \((\theta_{\min}, \theta_{\min} + \epsilon)\) and \((\theta_{\max}, \infty)\).

12.2.3.1 Lipschitz Bound.

To control the discretization error, we bound the derivative of \(\tilde{A}\).

To compute \(L\) explicitly, we use the chain rule: \[\frac{d\tilde{A}}{d\theta_A} = \frac{\partial A}{\partial \theta_A} + \frac{\partial A}{\partial \theta_B} \cdot \frac{d\theta_B}{d\theta_A}.\]

The partial derivatives are: \[\begin{align} \frac{\partial A}{\partial \theta_A} &= -c_1 D_1'(\theta_A) D_1(\theta_B) - c_2 \bigl( D_1'(\theta_A) D_0(\theta_B) + D_0'(\theta_A) D_1(\theta_B) \bigr), \\ \frac{\partial A}{\partial \theta_B} &= -c_1 D_1(\theta_A) D_1'(\theta_B) - c_2 \bigl( D_1(\theta_A) D_0'(\theta_B) + D_0(\theta_A) D_1'(\theta_B) \bigr), \end{align}\] where \[\begin{align} D_0'(\theta) &= 2\mu e^{-\mu\theta}, \\ D_1'(\theta) &= 2\mu \theta e^{-\mu\theta}. \end{align}\]

The derivative of the constraint mapping is obtained by implicit differentiation of \(D_0(\theta_A) D_0(\theta_B) = 1 - 2p\): \[\frac{d\theta_B}{d\theta_A} = -\frac{D_0'(\theta_A) D_0(\theta_B)}{D_0(\theta_A) D_0'(\theta_B)} = -\frac{D_0(\theta_B)}{D_0(\theta_A)} \cdot \frac{e^{-\mu\theta_A}}{e^{-\mu\theta_B}}.\]

On a compact interval \([\theta_a, \theta_b]\), all quantities \(D_0, D_1, D_0', D_1', \theta_B, \frac{d\theta_B}{d\theta_A}\) are bounded. The Lipschitz constant \(L\) can be computed numerically by evaluating \(|d\tilde{A}/d\theta_A|\) on a fine grid and taking the maximum, or bounded analytically by bounding each factor.

12.2.3.2 Boundary Contributions.

We must also bound the objective on the excluded regions.

12.2.3.3 Certified Upper Bound.

Combining the above, we obtain:

12.2.4 Concavification↩︎

By Theorem 9, the correct classical benchmark is \(A_{\mathrm{cl,SR}}^*(p) = \mathrm{conc}(A_{\mathrm{cl}}^*)(p)\). The concave envelope is computed via the upper hull algorithm in \(O(n)\) time for sorted input.

12.3 Quantum Lower Bound via Polynomial Measurement Angles↩︎

For quantum strategies, we consider players sharing a maximally entangled two-qubit state and performing local measurements parameterized by angles \(\theta_A(x_1)\) and \(\theta_B(x_2)\). We are free to choose any Bell state and measurement angle convention; our numerical implementation uses a convention such that the resulting correlation is \[\mathbb{E}[o_A(X_1) o_B(X_2) \mid X_1 = x_1, X_2 = x_2] = \cos\bigl(2(\theta_A(x_1) - \theta_B(x_2))\bigr).\]

We parameterize the measurement angles as polynomials of degree \(n\): \[\theta_A(x) = \sum_{k=0}^{n} a_k x^k, \qquad \theta_B(x) = \sum_{k=0}^{n} b_k x^k.\] The game payoff and splitting probability become \[\begin{align} A(a, b) &= -\mathbb{E}\bigl[\cos\bigl(2(\theta_A(X_1) - \theta_B(X_2))\bigr) \cdot w(X_1, X_2)\bigr], \\ p(a, b) &= \mathbb{E}\left[\frac{1 - \cos\bigl(2(\theta_A(X_1) - \theta_B(X_2))\bigr)}{2}\right]. \end{align}\]

For computational efficiency, we evaluate these expectations using Gauss–Laguerre quadrature. For \(X \sim \mathrm{Exp}(\mu)\), we use the substitution \(y = \mu x\) to obtain quadrature points \(\{x_i\}\) and weights \(\{w_i\}\) such that \[\mathbb{E}[f(X)] \approx \sum_{i=1}^{m} w_i f(x_i).\] We precompute the weight matrices \[W_{ij} = w(x_i, x_j) \cdot w_i w_j, \qquad \pi_{ij} = w_i w_j,\] enabling rapid evaluation of the payoff and constraint for any polynomial coefficients via array operations.

We maximize the payoff subject to the splitting probability constraint using sequential least-squares programming (SLSQP), with multiple random restarts to avoid local optima. The result is a lower bound on the quantum value, as we are exhibiting a specific (polynomial) quantum strategy.

12.4 Threshold Payoff Computation↩︎

The \(w\)-threshold payoff \(A^*(p)\) corresponds to the optimal policy established in Appendix 9: split when \(w(X_1, X_2) > \tau_p\) and bunch otherwise, where \(\tau_p\) is chosen such that \(\Pr[w(X_1, X_2) > \tau_p] = p\).

We compute \(A^*(p)\) via Monte Carlo estimation:

1. Sample \(N\) independent pairs \((X_1^{(i)}, X_2^{(i)}) \sim \mathrm{Exp}(\mu)^{\otimes 2}\).

2. Compute \(w^{(i)} = w(X_1^{(i)}, X_2^{(i)})\) for each sample.

3. Determine \(\tau_p\) as the \((1-p)\)-quantile of \(\{w^{(i)}\}\).

4. Compute the \(w\)-threshold decision \(\sigma^{*(i)} = \mathrm{sign}(\tau_p - w^{(i)})\).

5. Estimate the payoff as \(A^*(p) \approx -\frac{1}{N}\sum_{i=1}^{N} \sigma^{*(i)} w^{(i)}\).

12.5 Throughput Model↩︎

The throughput \(\mathcal{T}(p)\) as a function of splitting probability is determined by the baseline task model described in Appendix 9.6. For the numerical results presented in the main text, we use the exponential saturation warm-up model from Section 6.1, giving \[\mathcal{T}(p) = \phi_{\max}(1-\rho) \cdot \frac{2\alpha}{\lambda(1+p) + 2\alpha}\] with \(\phi_{\max} = 1\) and \(\alpha = 0.5\).

12.6 Numerical Parameters↩︎

Table 1 summarizes the numerical parameters used to generate the results in the main text.

References↩︎

---

1. Corresponding author: francisco@delftnetworks.com↩︎

2. Throughout this manuscript, we use uppercase letters (e.g., \(X_1\)) to denote random variables and lowercase letters (e.g., \(x_1\)) to denote their realizations or dummy variables in function definitions.↩︎