Entanglement improves coordination in distributed systems Preprint: APS/123-QED Francisco Ferreira da Silva, Stephanie Wehner Abstract Coordination in distributed systems is often hampered by communication latency, which degrades performance. Quantum entanglement offers fundamentally stronger correlations than classically achievable without communication. Crucially, these correlations manifest instantaneously upon measurement, irrespective of the physical distance separating the systems. We investigate the application of shared entanglement to a dual-work optimization problem in a distributed system comprising two servers. The system must process both a continuously available, preemptible baseline task and incoming customer requests arriving in pairs. System performance is characterized by the trade-off between baseline task throughput and customer waiting time. We present a rigorous analytical model demonstrating that when the baseline task throughput function is strictly convex, rewarding longer uninterrupted processing periods, entanglement-assisted routing strategies achieve Pareto-superior performance compared to optimal communication-free classical strategies. We prove this advantage through queueing-theoretic analysis, non-local game formulation, and computational certification of classical bounds. Our results identify distributed scheduling and coordination as a novel application domain for near-term entanglement-based quantum networks. I Introduction Coordination enables efficient operation in distributed systems. An important application lies in scheduling, where incoming requests must be assigned across multiple servers Casavant and Kuhl 1988 . 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 Wang et al. 1985 ; Jiang 2015 . 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 10^{2} 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 Bell 1964 ; Brunner et al. 2014 . 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 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 Covey et al. 2023 ; Ruf et al. 2021 ; Krutyanskiy et al. 2023 , including over deployed fiber Stolk et al. 2024 . This makes entanglement-assisted coordination an attractive near-term application of quantum networks. II Related Work This work provides a complete analytical treatment of the routing problem introduced in Da Silva and Wehner 2025 , 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, and certified classical bounds. 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 Bell 1964 ; Hensen et al. 2015 . 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 Clauser et al. 1969 ; Brunner et al. 2014 . Related but orthogonal to our focus, Ding et al. 2025 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 Ding and Jiang 2024 , load balancing in ad-hoc networks Hasanpour et al. 2017 , rendezvous tasks Mironowicz 2023 ; Viola and Mironowicz 2024 ; Tucker et al. 2024 , and broader networked systems Arun et al. 2025 . 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 Wang et al. 1985 ; Casavant and Kuhl 1988 ; Gross et al. 2011 . 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 Mitzenmacher 2002 ; Gupta et al. 2007 . 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. III 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. Figure 1: Distributed system studied in this work. Two servers, depicted by squares, handle two distinct types of work. On the right, a baseline task that is preemptible and always available. On the left, customer requests that dynamically arrive at the system via the routers, depicted as circles. The servers are endowed with queues of unlimited size in which customers wait. The routers may share entanglement with each other, which they can use to better coordinate their routing decisions. Entanglement is depicted here by wavy lines connecting the two routers. 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 Gross et al. 2011 . 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. IV 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 A . 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 Gross et al. 2011 . 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. Problem 1 (Optimal routing at fixed splitting probability) . Given a target splitting probability p\in[0,1] , find a routing policy r:\mathbb{R}_{+}^{2}\to[0,1] that solves \displaystyle\text{maximize} \displaystyle\mathbb{E}[r(X_{1},X_{2})\cdot w(X_{1},X_{2})] (1) \displaystyle\text{subject to} \displaystyle\mathbb{E}[r(X_{1},X_{2})]=p, \displaystyle 0\leq r(x_{1},x_{2})\leq 1\text{ for all }(x_{1},x_{2}). 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. 1 1 1 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. This restriction is without loss of generality, as load-balanced policies achieve weakly lower waiting time at the same throughput (Appendix A.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}), (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. We show in Appendix A.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. Definition 1 (Pareto Optimality) . A routing policy is Pareto optimal with respect to customer waiting time W_{q} and baseline throughput \mathcal{T} if there exists no other feasible policy that can strictly improve one objective (decrease W_{q} or increase \mathcal{T} ) without worsening the other. The set of all such policies constitutes the Pareto frontier. Theorem 1 (Pareto Optimality) . Assume the baseline throughput function T(t) is strictly convex. Then the family of w -threshold policies, parametrized by p\in[0,1] , traces out the complete Pareto frontier between customer waiting time and baseline throughput. 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. V 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 Brunner et al. 2014 . 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: Definition 2 (Non-local game) . A non-local game G=(\mathcal{X},\mathcal{Y},\mathcal{A},\mathcal{B},\pi,V) consists of input sets \mathcal{X},\mathcal{Y} , output sets \mathcal{A},\mathcal{B} , a probability distribution \pi over \mathcal{X}\times\mathcal{Y} , and a payoff function V:\mathcal{X}\times\mathcal{Y}\times\mathcal{A}\times\mathcal{B}\to\mathbb{R} . The game proceeds as follows: inputs (x,y)\sim\pi are distributed to players A and B respectively; each player produces an output ( a\in\mathcal{A} , b\in\mathcal{B} ) without communication; the payoff V(x,y,a,b) is evaluated. Players may share pre-distributed resources (classical shared randomness or quantum entanglement) but cannot communicate during the game. Router A Router B X_{1} X_{2} o_{A} o_{B} o_{A}\cdot o_{B}=-1\Rightarrow split o_{A}\cdot o_{B}=+1\Rightarrow bunch Figure 2: The routing problem as a non-local game. Routers A and B receive inputs (service times X_{1} , X_{2} ) and produce outputs ( o_{A},o_{B}\in\{+1,-1\} ) without communication. The product o_{A}\cdot o_{B} determines whether the customer pair is split across servers or bunched to the same server. 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 IV 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 Gross et al. 2011 . 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})], (3) 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})) . Lemma 1 (Payoff \leftrightarrow Waiting Time Gap) . For any routing strategy with game payoff A , the excess customer waiting time relative to the w -threshold policy satisfies \Delta W_{q}=\frac{A^{*}-A}{2}, (4) where A^{*}=-\mathbb{E}[\sigma^{*}(X_{1},X_{2})\,w(X_{1},X_{2})] is the w -threshold policy’s payoff. The proof is given in Appendix B . 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. VI 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 (Quantum Advantage in Routing) . Assume the baseline throughput function T(t) is strictly convex. Let \mathcal{P}=\{p\in[0,1]:A_{\mathrm{qu}}(p)>A_{\mathrm{cl,SR}}^{*}(p)\} denote the set of splitting probabilities at which quantum strategies achieve higher game payoff than classical strategies with shared randomness. Then quantum strategies Pareto-dominate classical strategies over \mathcal{P} : for all p\in\mathcal{P} , \Delta W_{q}^{\mathrm{qu}}(p)<\Delta W_{q}^{\mathrm{cl}}(p) (5) at identical baseline throughput \mathcal{T}(p) . Proof. Under strict convexity, baseline throughput \mathcal{T}(p) is strictly monotonic in p (Proposition 2 ). Equal throughput therefore implies equal splitting probability. By Lemma 1 , \Delta W_{q}=(A^{*}-A)/2 . Hence A_{\mathrm{qu}}>A_{\mathrm{cl,SR}}^{*} implies \Delta W_{q}^{\mathrm{qu}}<\Delta W_{q}^{\mathrm{cl}} at the same p , and thus at the same throughput \mathcal{T}(p) . ∎ 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. Theorem 3 (Classical Strategies are Threshold Strategies) . For the routing game, any optimal deterministic classical strategy (o_{A}^{*},o_{B}^{*}) consists of threshold functions: there exist \theta_{A},\theta_{B}\geq 0 such that o_{A}^{*}(x)=\begin{cases}+1&x<\theta_{A}\\ -1&x\geq\theta_{A}\end{cases},\qquad o_{B}^{*}(x)=\begin{cases}+1&x<\theta_{B}\\ -1&x\geq\theta_{B}\end{cases}. (6) The proof is given in Appendix C . 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 C for details. Theorem 4 (Quantum Advantage Region) . For exponential service times with \mu=1 and arrival rate \lambda=0.8 , quantum strategies achieve certified advantage over classical strategies with shared randomness for splitting probabilities p\in[0.075,0.325] . The maximum reduction in waiting time gap ( \Delta W_{q}^{\mathrm{cl}}-\Delta W_{q}^{\mathrm{qu}} ) is approximately 0.073 (in units of 1/\mu ), occurring near p\approx 0.20 . The proof constructs explicit quantum strategies via polynomial measurement angles and certifies classical bounds via Theorem 3 , with full details given in Appendix D . VI.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 Hennessy and Patterson 2011 . A natural model is exponential saturation: \phi(t)=\phi_{\max}(1-e^{-\alpha t}), (7) 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], (8) which is strictly convex since T^{\prime\prime}(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 Grimmett and Stirzaker 2020 , \mathcal{T}(p)=\frac{\mathbb{E}[T(I)]}{\mathbb{E}[I+B]}. (9) Evaluating the numerator using integration by parts (Appendix A.6 ) and substituting the mean cycle length gives \mathcal{T}(p)=\phi_{\max}(1-\rho)\cdot\frac{2\alpha}{\lambda(1+p)+2\alpha}. (10) 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 . Figure 3: Waiting time gap \Delta W_{q}=(A^{*}-A)/2 versus normalized throughput for quantum and classical strategies. Classical values are certified upper bounds; quantum values are achieved payoffs. Bottom axis: normalized throughput \mathcal{T}/[\phi_{\max}(1-\rho)] ; top axis: corresponding splitting probability p . System parameters: \lambda=0.8 , \mu=1 , \alpha=0.5 . VII 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\% Clauser et al. 1969 . 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 Covey et al. 2023 ; Ruf et al. 2021 ; Krutyanskiy et al. 2023 , including over deployed metropolitan fiber Stolk et al. 2024 . 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. The assumption of paired simultaneous arrivals isolates a single bipartite decision for analytical clarity, targeting regimes where offered load is roughly balanced across entry points. Extensions to general traffic patterns, other service-time distributions, and richer objective functions (e.g., fairness or variability penalties) are expected to preserve quantum advantages, since the core benefit derives from non-local correlations. 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. VIII 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 establish distributed scheduling and load balancing as a promising application domain for near-term quantum networks, providing a template 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 . 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. * Appendix A 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}), (11) 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. A.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. Proposition 1 (Load Balancing) . For any oracle routing policy, there exists a load-balanced policy achieving weakly lower waiting time at the same baseline throughput. We prove this in Appendix A.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} (12) 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}. (13) 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}) . A.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 Gross et al. 2011 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)}, (14) 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 A.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]. (15) 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]. (16) Rearranging, \displaystyle\Lambda\,\mathbb{E}[B_{s}^{2}] \displaystyle=\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] (17) \displaystyle=\frac{\lambda}{2}\Big(\mathbb{E}[S^{2}]-2\mathbb{E}[r\,X_{1}X_{2}]\Big). (18) A.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 A.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)}. (19) From Appendix A.2 , we have \Lambda\mathbb{E}[B_{s}^{2}]=\frac{\lambda}{2}(\mathbb{E}[S^{2}]-2\mathbb{E}[rX_{1}X_{2}]) , so \mathbb{E}[W_{q}^{\text{virtual}}]=\frac{\lambda(\mathbb{E}[S^{2}]-2\mathbb{E}[rX_{1}X_{2}])}{4(1-\rho)}. (20) 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], (21) 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_{1}X_{2}])}{4(1-\rho)}+\frac{1}{4}\mathbb{E}[(1-r)S]. (22) A.4 Optimization formulation at fixed splitting probability We now formulate the routing problem as a constrained optimization. Recall from Appendix A.3 that \mathbb{E}[W_{q}]=\frac{\lambda(\mathbb{E}[S^{2}]-2\mathbb{E}[rX_{1}X_{2}])}{4(1-\rho)}+\frac{1}{4}\mathbb{E}[(1-r)S]. (23) 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_{1}X_{2}]-\frac{1}{4}\mathbb{E}[rS]. (24) Define constants c_{1}=\frac{\lambda}{2(1-\rho)},\qquad c_{2}=\frac{1}{4}. (25) Then we can write \mathbb{E}[W_{q}]=\text{const}-\big(c_{1}\,\mathbb{E}[rX_{1}X_{2}]+c_{2}\,\mathbb{E}[rS]\big), (26) 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: Problem 2 (Optimal routing at fixed splitting probability; restates Problem 1 ) . Given a target splitting probability p\in[0,1] , find a routing policy r:\mathbb{R}_{+}^{2}\to[0,1] that solves \displaystyle\text{maximize} \displaystyle c_{1}\,\mathbb{E}[rX_{1}X_{2}]+c_{2}\,\mathbb{E}[rS] (27) \displaystyle\text{subject to} \displaystyle\mathbb{E}[r]=p, \displaystyle 0\leq r(x_{1},x_{2})\leq 1\text{ for all }(x_{1},x_{2}). A.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}), (28) 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} . Theorem 5 (Optimal threshold policy) . For any target splitting probability p\in[0,1] , the optimal routing policy for Problem 2 is a threshold policy: r^{*}(x_{1},x_{2})=\begin{cases}1&\text{if }w(x_{1},x_{2})>\tau_{p},\\ 0&\text{if }w(x_{1},x_{2})<\tau_{p},\end{cases} (29) where the threshold \tau_{p} is chosen such that \mathbb{E}[r^{*}]=p . Under the exponential service time distribution, the random variable W=w(X_{1},X_{2}) is continuously distributed; thus \mathbb{P}(w=\tau_{p})=0 , and the threshold \tau_{p} uniquely determines p . Proof. Let r^{*} be the threshold policy defined above, and let r be any other feasible policy such that \mathbb{E}[r]=p . We wish to show \mathbb{E}[r^{*}w]\geq\mathbb{E}[rw] . For any realization (x_{1},x_{2}) , consider the expression (r^{*}(x_{1},x_{2})-r(x_{1},x_{2}))(w(x_{1},x_{2})-\tau_{p}) . We observe the following: • If w(x_{1},x_{2})>\tau_{p} , then r^{*}=1 . Since r\in[0,1] , (1-r)\geq 0 and (w-\tau_{p})>0 . Their product is \geq 0 . • If w(x_{1},x_{2})<\tau_{p} , then r^{*}=0 . Since r\in[0,1] , (0-r)\leq 0 and (w-\tau_{p})<0 . Their product is \geq 0 . • If w(x_{1},x_{2})=\tau_{p} , the product is 0 . Thus, (r^{*}-r)(w-\tau_{p})\geq 0 holds pointwise for all (x_{1},x_{2}) . Taking expectations: \mathbb{E}[(r^{*}-r)(w-\tau_{p})]\geq 0. (30) Expanding the expectation: \mathbb{E}[r^{*}w]-\mathbb{E}[rw]-\tau_{p}(\mathbb{E}[r^{*}]-\mathbb{E}[r])\geq 0. (31) By the constraint \mathbb{E}[r^{*}]=\mathbb{E}[r]=p , the last term is zero. Therefore, \mathbb{E}[r^{*}w]\geq\mathbb{E}[rw] , proving that the threshold policy r^{*} is optimal. ∎ 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 ). A.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 A.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)}. (32) For the busy period, we derive the mean duration using a rate-balance argument. By PASTA (Poisson Arrivals See Time Averages) Wolff 1982 , 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)}, (33) 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). (34) 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^{\prime} . To compute the long-run average baseline throughput, we apply the renewal reward theorem Grimmett and Stirzaker 2020 : 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]}, (35) where \mathbb{E}[T(I)]=\int_{0}^{\infty}T(t)\Lambda e^{-\Lambda t}\,dt. (36) Note that baseline throughput depends only on the splitting probability p , not on which specific pairs are split. Proposition 2 (Monotonicity of baseline throughput in p ) . Let \Lambda=\lambda(1+p)/2 and assume T is differentiable with derivative \phi=T^{\prime} and T(0)=0 , with T increasing. Then: 1. If T is strictly convex (so \phi is increasing), then \mathcal{T}(p) strictly decreases in p . 2. If T is linear (so \phi is constant), then \mathcal{T}(p) is independent of p . 3. If T is strictly concave (so \phi is decreasing), then \mathcal{T}(p) strictly increases in p . Proof. Write \mathcal{T}(p)=\frac{\mathbb{E}[T(I)]}{\mathbb{E}[I+B]}=\frac{1+p}{C}\,\mathbb{E}[T(I)],\qquad C=2\left(\frac{1}{\lambda}+\frac{1}{\mu-\lambda}\right). Set f(\Lambda):=\mathbb{E}[T(I)] so that \mathcal{T}(p)=\frac{1+p}{C}\,f(\Lambda). Differentiate with respect to p : \frac{d\mathcal{T}}{dp}=\frac{1}{C}\Big(f(\Lambda)+(1+p)\,f^{\prime}(\Lambda)\,\frac{d\Lambda}{dp}\Big). Since \frac{d\Lambda}{dp}=\frac{\lambda}{2} and \Lambda=\frac{\lambda}{2}(1+p) , we have (1+p)\,\frac{d\Lambda}{dp}=\Lambda . Hence \frac{d\mathcal{T}}{dp}=\frac{1}{C}\big(f(\Lambda)+\Lambda f^{\prime}(\Lambda)\big)=\frac{1}{C}\,\frac{d}{d\Lambda}\big(\Lambda f(\Lambda)\big)=\frac{1}{C}\,\frac{d}{d\Lambda}\big(\Lambda\,\mathbb{E}[T(I)]\big). Because C>0 , the sign of \frac{d\mathcal{T}}{dp} equals the sign of \frac{d}{d\Lambda}\big(\Lambda\,\mathbb{E}[T(I)]\big) . With I\sim\mathrm{Exp}(\Lambda) , we use integration by parts. Since T(0)=0 and T is differentiable, \mathbb{E}[T(I)]=\int_{0}^{\infty}T(t)\,\Lambda e^{-\Lambda t}\,dt=\left[T(t)(-e^{-\Lambda t})\right]_{0}^{\infty}+\int_{0}^{\infty}\phi(t)e^{-\Lambda t}\,dt=\int_{0}^{\infty}\phi(t)\,e^{-\Lambda t}\,dt, hence g(\Lambda):=\Lambda\,\mathbb{E}[T(I)]=\Lambda\int_{0}^{\infty}\phi(t)e^{-\Lambda t}\,dt,\quad g^{\prime}(\Lambda)=\int_{0}^{\infty}\phi(t)e^{-\Lambda t}(1-\Lambda t)\,dt. Let U\sim\mathrm{Exp}(\Lambda) , so \mathbb{E}[U]=1/\Lambda . Rewriting the integrals in terms of expectations with respect to U : \int_{0}^{\infty}\phi(t)e^{-\Lambda t}\,dt=\frac{1}{\Lambda}\int_{0}^{\infty}\phi(t)\Lambda e^{-\Lambda t}\,dt=\frac{1}{\Lambda}\,\mathbb{E}[\phi(U)], and \int_{0}^{\infty}\phi(t)\,t\,\Lambda e^{-\Lambda t}\,dt=\mathbb{E}[U\,\phi(U)]. Therefore, g^{\prime}(\Lambda)=\frac{1}{\Lambda}\,\mathbb{E}[\phi(U)]-\mathbb{E}[U\,\phi(U)]=\mathbb{E}[U]\,\mathbb{E}[\phi(U)]-\mathbb{E}[U\,\phi(U)]=-\mathrm{Cov}(U,\phi(U)). Since \Lambda>0 , the sign of d\mathcal{T}/dp equals the sign of -\mathrm{Cov}(U,\phi(U)) . When \phi is monotonic, U and \phi(U) are co-monotonic, so the covariance has the same sign as \phi^{\prime} . Thus: (i) \phi increasing (convex T ) implies \mathrm{Cov}(U,\phi(U))>0 , hence \mathcal{T} is strictly decreasing in p ; (ii) \phi constant implies \mathrm{Cov}(U,\phi(U))=0 , hence \mathcal{T} is independent of p ; (iii) \phi decreasing implies \mathrm{Cov}(U,\phi(U))<0 , hence \mathcal{T} is strictly increasing in p . ∎ 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. A.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 (Pareto optimality; restates Theorem 1 ) . Assume T is strictly convex (so baseline throughput strictly decreases in p by Proposition 2 ). Then the family of threshold policies \{r^{*}_{p}:p\in[0,1]\} , where r^{*}_{p} solves Problem 2 for splitting probability p , achieves the Pareto frontier between baseline throughput and customer waiting time. Proof. Consider any feasible routing policy r with induced splitting probability p_{r}=\mathbb{E}[r] . We show that r is weakly dominated by the threshold policy r^{*}_{p_{r}} achieving the same splitting probability. By Proposition 2 , baseline throughput depends only on the splitting probability: \mathcal{T}(r)=\mathcal{T}(p_{r})=\mathcal{T}(r^{*}_{p_{r}}). (37) By Theorem 5 , among all policies with splitting probability p_{r} , the threshold policy r^{*}_{p_{r}} minimizes customer waiting time: \mathbb{E}[W_{q}](r^{*}_{p_{r}})\leq\mathbb{E}[W_{q}](r). (38) Thus r^{*}_{p_{r}} achieves the same baseline throughput as r with no greater customer waiting time, so r is weakly dominated by r^{*}_{p_{r}} . This establishes that every point on the Pareto frontier corresponds to a threshold policy. Conversely, every threshold policy r^{*}_{p} is Pareto optimal. Any policy with the same splitting probability p has the same throughput (Proposition 2 ) and weakly higher waiting time (Theorem 5 ), so cannot strictly dominate r^{*}_{p} . Any policy with different splitting probability has different throughput, so cannot improve both objectives simultaneously. It remains to show that increasing p strictly reduces waiting time under the threshold policy. Recall from Appendix A.4 that \mathbb{E}[W_{q}]=\text{const}-\mathbb{E}[r\cdot w] , where the constant is independent of the routing policy. For the threshold policy r^{*}_{p} , we have \mathbb{E}[r^{*}_{p}\cdot w]=\mathbb{E}[w\cdot\mathbf{1}\{w>\tau_{p}\}] . As p increases, the threshold \tau_{p} decreases (since p=\Pr[w>\tau_{p}] and the distribution of w is continuous). Since w\geq 0 , decreasing \tau_{p} strictly increases \mathbb{E}[w\cdot\mathbf{1}\{w>\tau_{p}\}] , and hence strictly decreases \mathbb{E}[W_{q}](r^{*}_{p}) . Since T is strictly convex, by Proposition 2 , \mathcal{T} strictly decreases in p . Therefore increasing p strictly reduces waiting time while strictly decreasing throughput, and decreasing p strictly increases waiting time while strictly increasing throughput. Thus no feasible policy strictly dominates r^{*}_{p} . ∎ Remark 1 . The endpoints p=1 and p=0 are attained by taking \tau=0 and \tau=\infty , respectively. 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. A.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. Proposition 3 (Load-Balanced Dominance) . For any oracle routing policy \pi with splitting probability p , there exists a load-balanced policy \pi^{\text{bal}} with the same splitting probability that achieves weakly lower average customer waiting time and identical baseline throughput. A policy is load-balanced if, when splitting, each server is equally likely to receive the larger job, and when bunching, the destination server is chosen uniformly at random. Proof. Consider an arriving pair (X_{1},X_{2}) with X_{i}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\text{Exp}(\mu) . For each pair, an oracle policy \pi selects from four possible routing actions: • A_{\min} (Split): Send \min(X_{1},X_{2}) to Server 1 and \max(X_{1},X_{2}) to Server 2. • A_{\max} (Split): Send \max(X_{1},X_{2}) to Server 1 and \min(X_{1},X_{2}) to Server 2. • B_{1} (Bunch): Send X_{1}+X_{2} to Server 1 and 0 to Server 2. • B_{2} (Bunch): Send 0 to Server 1 and X_{1}+X_{2} to Server 2. Let (\alpha,\beta,\gamma,\delta) be the probabilities that the oracle selects actions A_{\min},A_{\max},B_{1},B_{2} respectively. The induced splitting probability is p=\alpha+\beta . Lemma 2 (Moments of exponential order statistics) . For X_{1},X_{2}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\text{Exp}(\mu) : \mathbb{E}[\min]=\frac{1}{2\mu},\quad\mathbb{E}[\min{}^{2}]=\frac{1}{2\mu^{2}},\quad\mathbb{E}[\max]=\frac{3}{2\mu},\quad\mathbb{E}[\max{}^{2}]=\frac{7}{2\mu^{2}}. (39) Proof. Since \min(X_{1},X_{2})\sim\text{Exp}(2\mu) , we have \mathbb{E}[\min]=1/(2\mu) and \mathbb{E}[\min^{2}]=2/(2\mu)^{2}=1/(2\mu^{2}) . For the maximum, the density is f_{\max}(t)=2\mu(e^{-\mu t}-e^{-2\mu t}) . Using \int_{0}^{\infty}t^{n}e^{-at}\,dt=n!/a^{n+1} , direct calculation yields \mathbb{E}[\max]=3/(2\mu) and \mathbb{E}[\max^{2}]=7/(2\mu^{2}) . ∎ Let Z_{1} denote the workload contributed to Server 1 by a single arriving pair. Using Lemma 2 and the sum moments ( \mathbb{E}[X_{1}+X_{2}]=2/\mu , \mathbb{E}[(X_{1}+X_{2})^{2}]=6/\mu^{2} ), the load \rho_{1} and second-moment flux K_{1}=\lambda\mathbb{E}[Z_{1}^{2}] at Server 1 are: \displaystyle\rho_{1} \displaystyle=\lambda(\alpha\cdot\tfrac{1}{2\mu}+\beta\cdot\tfrac{3}{2\mu}+\gamma\cdot\tfrac{2}{\mu}), (40) \displaystyle K_{1} \displaystyle=\lambda(\alpha\cdot\tfrac{1}{2\mu^{2}}+\beta\cdot\tfrac{7}{2\mu^{2}}+\gamma\cdot\tfrac{6}{\mu^{2}}). (41) Step 1: Work conservation. Every arriving pair contributes total expected work \mathbb{E}[X_{1}+X_{2}]=2/\mu to the system, regardless of the routing action. Thus \rho_{1}+\rho_{2}=2\lambda/\mu=2\bar{\rho} for all policies, where \bar{\rho}=\lambda/\mu . Step 2: Load-balanced policies exist and achieve \rho_{1}=\rho_{2} . Define a policy to be load-balanced if \alpha=\beta and \gamma=\delta , i.e., when splitting, each server is equally likely to receive the larger job, and when bunching, each server is equally likely to receive the pair. For a target splitting probability p , the load-balanced policy sets \alpha=\beta=p/2 and \gamma=\delta=(1-p)/2 . Substituting into ( 40 ): \rho_{1}=\lambda\left(\frac{p}{2}\cdot\frac{1}{2\mu}+\frac{p}{2}\cdot\frac{3}{2\mu}+\frac{1-p}{2}\cdot\frac{2}{\mu}\right)=\frac{\lambda}{2\mu}(p+(1-p)\cdot 2)=\frac{\lambda}{\mu}=\bar{\rho}. (42) By an analogous calculation, \rho_{2}=\bar{\rho} . Thus load-balanced policies achieve \rho_{1}=\rho_{2}=\bar{\rho} for any splitting probability p\in[0,1] . In contrast, policies violating \alpha=\beta or \gamma=\delta can induce load imbalance. For example, with p=1 , the policy \alpha=1,\beta=0 (always send the smaller job to Server 1) yields \rho_{1}=\lambda/(2\mu)=\bar{\rho}/2\neq\bar{\rho} . Step 3: Load imbalance increases waiting time. Since the map (\alpha,\beta,\gamma,\delta)\mapsto(\rho_{1},K_{1}) is linear and the domain is a simplex, the set of achievable pairs (\rho_{1},K_{1}) is a convex polytope. Define the efficient frontier K^{*}(\rho) as the minimum K_{1} achievable for a given load \rho_{1}=\rho . Lemma 3 (Convexity of efficient frontier) . The efficient frontier K^{*}(\rho) is piecewise linear and convex, with K^{*\prime}(\rho)\geq 1/\mu>0 . Proof. The lower boundary of the polytope is traced through vertices V_{0} (load 0 ), V_{1} (load \lambda/2\mu ), V_{2} (load 3\lambda/2\mu ), and V_{3} (load 2\lambda/\mu ), with slopes: \frac{dK^{*}}{d\rho}\bigg|_{V_{0}\to V_{1}}=\frac{1}{\mu},\quad\frac{dK^{*}}{d\rho}\bigg|_{V_{1}\to V_{2}}=\frac{3}{\mu},\quad\frac{dK^{*}}{d\rho}\bigg|_{V_{2}\to V_{3}}=\frac{5}{\mu}. (43) Since the slopes are strictly increasing and bounded below by 1/\mu , K^{*}(\rho) is piecewise linear and convex. ∎ The system-average waiting time is W=\frac{1}{2}(g(\rho_{1})+g(\rho_{2})) , where g(\rho)=K^{*}(\rho)/[2(1-\rho)] . The curvature of g is: g^{\prime\prime}(\rho)=\frac{K^{*\prime\prime}(\rho)(1-\rho)^{2}+2K^{*\prime}(\rho)(1-\rho)+2K^{*}(\rho)}{2(1-\rho)^{3}}. (44) For stable systems ( 1-\rho>0 ), we have K^{*\prime\prime}(\rho)\geq 0 , K^{*\prime}(\rho)\geq 1/\mu>0 (Lemma 3 ), and K^{*}(\rho)>0 for \rho>0 . Thus g^{\prime\prime}(\rho)>0 , so g is strictly convex. Parametrize load imbalance by \epsilon=\rho_{1}-\bar{\rho} , so \rho_{1}=\bar{\rho}+\epsilon and \rho_{2}=\bar{\rho}-\epsilon by work conservation. The waiting time W(\epsilon)=\frac{1}{2}[g(\bar{\rho}+\epsilon)+g(\bar{\rho}-\epsilon)] is symmetric in \epsilon and strictly convex. Therefore W is uniquely minimized at \epsilon=0 , i.e., at balanced load \rho_{1}=\rho_{2}=\bar{\rho} . Step 4: Load-balanced policies are optimal for any fixed p . Fix a splitting probability p . Among all policies with this p , non-load-balanced policies can induce load imbalance \epsilon\neq 0 , while load-balanced policies achieve \epsilon=0 (Step 2). Since load imbalance strictly increases waiting time (Step 3), load-balanced policies achieve weakly lower waiting time. ∎ Corollary 1 (Servers see identical arrivals) . Under load-balanced policies, both servers experience statistically identical M^{X}/G/1 arrival processes. All analysis may therefore be conducted from the perspective of a single server without loss of generality. This completes the technical foundations for the coordination challenge established in Section IV of the main text. Appendix B 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 A 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. B.1 Local Strategies The analysis in Appendix A 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. B.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})), (45) 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 A : 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 A denotes a splitting probability. We restrict attention to strategies achieving splitting probability p : \Pr[o_{A}(X_{1})o_{B}(X_{2})=-1]=p. (46) This constraint is natural because, as established in Appendix A.6 , baseline throughput depends only on the splitting probability p . Comparing strategies at fixed p therefore isolates the waiting time objective. Remark 2 (Load-balanced server assignment) . The waiting time analysis in Appendix A assumes load-balanced server assignment: when splitting, each server is equally likely to receive either job; when bunching, the destination server is chosen uniformly at random. For local strategies, load balancing is achievable via shared randomness: players share a random bit b\in\{0,1\} , and if b=1 , both flip their outputs (i.e., output -o_{A}(X_{1}) and -o_{B}(X_{2}) instead of o_{A}(X_{1}) and o_{B}(X_{2}) ). This transformation preserves the product o_{A}o_{B} (hence the split/bunch decision and game payoff) while ensuring symmetric server assignment. Throughout this appendix, we assume all strategies employ load-balanced server assignment, so that the waiting time results from Appendix A apply. B.3 The Queueing–Game Correspondence Lemma 4 (Waiting time gap) . Let (o_{A},o_{B}) be any local routing strategy with splitting probability p , employing load-balanced server assignment. The excess waiting time relative to the w -threshold policy is \Delta W_{q}:=\mathbb{E}[W_{q}](o_{A},o_{B})-\mathbb{E}[W_{q}]^{*}=\frac{1}{2}\,\mathbb{E}\bigl[(o_{A}(X_{1})o_{B}(X_{2})-\sigma^{*}(X_{1},X_{2}))\,w(X_{1},X_{2})\bigr]. (47) Proof. From Appendix A.4 , under load-balanced server assignment the expected waiting time under any routing policy with split indicator s:\mathbb{R}_{+}^{2}\to\{0,1\} is \mathbb{E}[W_{q}]=C-\mathbb{E}[s\cdot w], (48) where C=\frac{\lambda\mathbb{E}[S^{2}]}{4(1-\rho)}+\frac{\mathbb{E}[S]}{4} is independent of the routing policy and w(x_{1},x_{2})=c_{1}x_{1}x_{2}+c_{2}(x_{1}+x_{2}) is the splitting benefit function. The w -threshold policy achieves s^{*}(x_{1},x_{2})=\mathbf{1}\{w(x_{1},x_{2})>\tau_{p}\} , which can be written as s^{*}=\frac{1-\sigma^{*}}{2} (49) since \sigma^{*}=+1 when w<\tau_{p} (bunch, s^{*}=0 ) and \sigma^{*}=-1 when w>\tau_{p} (split, s^{*}=1 ). Similarly, for a local strategy (o_{A},o_{B}) with split indicator s=(1-o_{A}o_{B})/2 , we have s^{*}-s=\frac{1-\sigma^{*}}{2}-\frac{1-o_{A}o_{B}}{2}=\frac{o_{A}o_{B}-\sigma^{*}}{2}. (50) The waiting time gap is therefore \displaystyle\Delta W_{q} \displaystyle=\mathbb{E}[W_{q}](o_{A},o_{B})-\mathbb{E}[W_{q}]^{*} (51) \displaystyle=\bigl(C-\mathbb{E}[s\cdot w]\bigr)-\bigl(C-\mathbb{E}[s^{*}w]\bigr) (52) \displaystyle=\mathbb{E}[s^{*}w]-\mathbb{E}[s\cdot w] (53) \displaystyle=\mathbb{E}[(s^{*}-s)\cdot w] (54) \displaystyle=\frac{1}{2}\,\mathbb{E}[(o_{A}o_{B}-\sigma^{*})\cdot w].\qed (55) Remark 3 (Interpretation) . The waiting time gap decomposes into contributions from two types of disagreement with \sigma^{*} : • Under-splitting : bunching when \sigma^{*}=-1 (i.e., o_{A}o_{B}=+1 ), contributing +w to \Delta W_{q} . • Over-splitting : splitting when \sigma^{*}=+1 (i.e., o_{A}o_{B}=-1 ), contributing -w to \Delta W_{q} . Since strategies are constrained to the same splitting probability p , any over-splitting must be compensated by under-splitting elsewhere. However, under-splitting occurs in the high- w region (above threshold) while over-splitting occurs in the low- w region (below threshold), so under-splitting is more costly. This asymmetry ensures \Delta W_{q}\geq 0 with equality if and only if o_{A}o_{B}=\sigma^{*} almost surely. B.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 A(o_{A},o_{B})=-\mathbb{E}[o_{A}(X_{1})o_{B}(X_{2})\cdot w(X_{1},X_{2})], (56) 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. Proposition 4 (Game–queueing equivalence; restates Lemma 1 ) . Let A^{*}=-\mathbb{E}[\sigma^{*}\cdot w] denote the w -threshold payoff. For any local strategy (o_{A},o_{B}) with splitting probability p and load-balanced server assignment: \Delta W_{q}=\frac{A^{*}-A(o_{A},o_{B})}{2}. (57) Consequently, maximizing the game payoff A(o_{A},o_{B}) is equivalent to minimizing the excess waiting time \Delta W_{q} . Proof. From Lemma 4 : \displaystyle\Delta W_{q} \displaystyle=\frac{1}{2}\,\mathbb{E}[(o_{A}o_{B}-\sigma^{*})\cdot w] (58) \displaystyle=\frac{1}{2}\bigl(\mathbb{E}[o_{A}o_{B}\cdot w]-\mathbb{E}[\sigma^{*}\cdot w]\bigr) (59) \displaystyle=\frac{1}{2}\bigl(-A(o_{A},o_{B})-(-A^{*})\bigr) (60) \displaystyle=\frac{A^{*}-A(o_{A},o_{B})}{2}.\qed (61) Corollary 2 (Quantum advantage implies waiting time reduction) . Let A_{\mathrm{cl}}^{*}(p) denote the maximum payoff achievable by a classical strategy at splitting probability p , and let A_{\mathrm{qu}}(p) denote the payoff achievable by a quantum strategy at the same splitting probability. If A_{\mathrm{qu}}(p)>A_{\mathrm{cl}}^{*}(p) , then \Delta W_{q}^{\mathrm{qu}}(p)<\Delta W_{q}^{\mathrm{cl}}(p), (62) i.e., the quantum strategy achieves strictly lower excess waiting time at splitting probability p . The following theorem extends this pointwise comparison to Pareto dominance across a range of splitting probabilities. Theorem 7 (Pareto dominance; restates Theorem 2 ) . Let \mathcal{P}\subseteq[0,1] be the set of splitting probabilities for which A_{\mathrm{qu}}(p)>A_{\mathrm{cl}}^{*}(p) . Then quantum strategies Pareto dominate classical strategies over \mathcal{P} : for all p\in\mathcal{P} , \Delta W_{q}^{\mathrm{qu}}(p)<\Delta W_{q}^{\mathrm{cl}}(p) (63) at identical baseline throughput \mathcal{T}(p) . Proof. Fix p\in\mathcal{P} . By Proposition 4 , the excess waiting times satisfy \Delta W_{q}^{\mathrm{qu}}(p)=\frac{A^{*}-A_{\mathrm{qu}}(p)}{2}<\frac{A^{*}-A_{\mathrm{cl}}^{*}(p)}{2}=\Delta W_{q}^{\mathrm{cl}}(p), (64) where the inequality follows from A_{\mathrm{qu}}(p)>A_{\mathrm{cl}}^{*}(p) . By Proposition 2 in Appendix A.6 , baseline throughput depends only on the splitting probability p , not on which specific pairs are split. Therefore both strategies achieve the same baseline throughput \mathcal{T}(p) . Since quantum strategies achieve strictly lower waiting time at identical throughput for all p\in\mathcal{P} , they Pareto dominate classical strategies over this range. ∎ Remark 4 . Theorem 7 establishes that demonstrating quantum advantage in the non-local game immediately implies Pareto dominance in the waiting time–throughput trade-off. It remains to characterize what classical strategies can achieve (Appendix C ) and compute classical and quantum performance numerically (Appendix D ). Appendix C Classical Strategies This appendix characterizes what classical strategies can achieve in the routing game defined in Appendix B . We first show that optimal deterministic strategies take a threshold form, then establish the correct classical benchmark when shared randomness is allowed. C.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. Definition 3 (Threshold strategy) . A strategy f:\mathbb{R}_{+}\to\{+1,-1\} is a threshold strategy with threshold \theta\geq 0 if f(x)=\begin{cases}+1&x<\theta,\\ -1&x\geq\theta.\end{cases} (65) We write f_{\theta} to denote the threshold strategy with threshold \theta . The main result of this section is the following. Theorem 8 (Optimal deterministic strategies are threshold strategies; restates Theorem 3 ) . For the routing game at any splitting probability p\in(0,1) , there exists an optimal deterministic strategy (o_{A}^{*},o_{B}^{*}) where both o_{A}^{*} and o_{B}^{*} are threshold strategies. More precisely, the optimal strategy takes the form of a threshold pair up to a global sign flip (o_{A},o_{B})\mapsto(-o_{A},-o_{B}) , which preserves the payoff and splitting constraint; we may therefore always choose the standard orientation of Definition 3 . The proof proceeds by showing that, for any fixed strategy of one player, the optimal response of the other player is a threshold strategy. Lemma 5 (Optimal response is a threshold) . Fix a strategy o_{B}:\mathbb{R}_{+}\to\{+1,-1\} with E_{0}:=\mathbb{E}[o_{B}(X)]\in(-1,1) , E_{0}\neq 0 , and E_{1}:=\mathbb{E}[o_{B}(X)\cdot X] . Among all strategies o_{A} satisfying the splitting constraint \Pr[o_{A}(X_{1})o_{B}(X_{2})=-1]=p , the payoff A(o_{A},o_{B}) is uniquely maximized by a threshold strategy. The case E_{0}=0 is handled in Remark 5 . Proof. We first rewrite the payoff in terms of o_{A} alone. Using independence of X_{1} and X_{2} : \displaystyle A(o_{A},o_{B}) \displaystyle=-\mathbb{E}[o_{A}(X_{1})o_{B}(X_{2})\cdot w(X_{1},X_{2})] (66) \displaystyle=-\mathbb{E}_{X_{1}}\bigl[o_{A}(X_{1})\cdot\mathbb{E}_{X_{2}}[o_{B}(X_{2})\cdot w(X_{1},X_{2})]\bigr]. (67) Computing the inner expectation with w(x_{1},x_{2})=c_{1}x_{1}x_{2}+c_{2}(x_{1}+x_{2}) : \displaystyle\mathbb{E}_{X_{2}}[o_{B}(X_{2})\cdot w(x_{1},X_{2})] \displaystyle=c_{1}x_{1}\mathbb{E}[o_{B}(X)\cdot X]+c_{2}x_{1}\mathbb{E}[o_{B}(X)]+c_{2}\mathbb{E}[o_{B}(X)\cdot X] (68) \displaystyle=(c_{1}E_{1}+c_{2}E_{0})\,x_{1}+c_{2}E_{1}. (69) Define the effective weight function \tilde{w}:\mathbb{R}_{+}\to\mathbb{R} by \tilde{w}(x):=(c_{1}E_{1}+c_{2}E_{0})\,x+c_{2}E_{1}. (70) Then the payoff becomes A(o_{A},o_{B})=-\mathbb{E}[o_{A}(X)\cdot\tilde{w}(X)]. (71) The splitting constraint \Pr[o_{A}(X_{1})o_{B}(X_{2})=-1]=p can be rewritten using independence: p=\Pr[o_{A}o_{B}=-1]=\frac{1-\mathbb{E}[o_{A}(X)]\mathbb{E}[o_{B}(X)]}{2}=\frac{1-D_{0}E_{0}}{2}, (72) where D_{0}:=\mathbb{E}[o_{A}(X)] . This yields the constraint D_{0}=\frac{1-2p}{E_{0}}. (73) The optimization over o_{A} is therefore: \displaystyle\text{maximize} \displaystyle-\mathbb{E}[o_{A}(X)\cdot\tilde{w}(X)] (74) \displaystyle\text{subject to} \displaystyle\mathbb{E}[o_{A}(X)]=D_{0}^{\mathrm{target}}:=\frac{1-2p}{E_{0}}, \displaystyle o_{A}(x)\in\{+1,-1\}\text{ for all }x\geq 0. This is a linear functional optimization with a linear constraint. We solve it via Lagrangian relaxation. The Lagrangian is \mathcal{L}(o_{A},\lambda)=-\mathbb{E}[o_{A}(X)\cdot\tilde{w}(X)]-\lambda\bigl(\mathbb{E}[o_{A}(X)]-D_{0}^{\mathrm{target}}\bigr)=-\mathbb{E}[o_{A}(X)\cdot(\tilde{w}(X)+\lambda)]+\lambda D_{0}^{\mathrm{target}}. (75) For any fixed \lambda , the Lagrangian is maximized pointwise by choosing o_{A}(x)=\begin{cases}+1&\text{if }\tilde{w}(x)+\lambda<0,\\ -1&\text{if }\tilde{w}(x)+\lambda>0.\end{cases} (76) Since \tilde{w}(x)=(c_{1}E_{1}+c_{2}E_{0})\,x+c_{2}E_{1} is affine in x , the condition \tilde{w}(x)+\lambda\lessgtr 0 defines a half-line whenever the slope c_{1}E_{1}+c_{2}E_{0} is nonzero. If c_{1}E_{1}+c_{2}E_{0}>0 , then \tilde{w} is strictly increasing, so \tilde{w}(x)+\lambda<0 if and only if x<\theta for some threshold \theta . The optimal response satisfies o_{A}(x)=+1 for x<\theta and o_{A}(x)=-1 for x\geq\theta . If c_{1}E_{1}+c_{2}E_{0}<0 , then \tilde{w} is strictly decreasing, so \tilde{w}(x)+\lambda<0 if and only if x>\theta for some threshold \theta . The optimal response satisfies o_{A}(x)=-1 for x<\theta and o_{A}(x)=+1 for x\geq\theta , which is the negation of a threshold strategy: o_{A}=-f_{\theta} . In both cases, the optimal o_{A} is a threshold strategy up to a global sign flip. Since the game payoff depends on the product o_{A}o_{B} , replacing (o_{A},o_{B}) with (-o_{A},-o_{B}) leaves the payoff and splitting constraint unchanged. Thus any optimum with reversed-orientation strategies corresponds to an equivalent optimum with standard-orientation strategies. In the degenerate case c_{1}E_{1}+c_{2}E_{0}=0 , the effective weight is constant and the optimal response is o_{A}\equiv\pm 1 , which can be viewed as a limiting threshold strategy with \theta\in\{0,\infty\} . For the numerical optimization, we verify that optimal threshold pairs (\theta_{A},\theta_{B}) lie in the interior of the feasible region where the non-degeneracy condition holds. The threshold \theta is determined by the constraint \mathbb{E}[o_{A}(X)]=D_{0}^{\mathrm{target}} ; since \mathbb{E}[f_{\theta}(X)] is continuous and strictly monotonic in \theta , a unique such \theta exists for any feasible D_{0}^{\mathrm{target}}\in(-1,1) . ∎ Remark 5 (The case E_{0}=0 ) . When E_{0}=0 , the splitting constraint D_{0}E_{0}=1-2p forces p=1/2 , and the constraint on D_{0}=\mathbb{E}[o_{A}(X)] becomes vacuous. The optimization over o_{A} reduces to the unconstrained pointwise problem \max_{o_{A}}-\mathbb{E}[o_{A}(X)\cdot\tilde{w}(X)] , solved by o_{A}(x)=-\operatorname{sign}(\tilde{w}(x)) . With E_{0}=0 , the effective weight simplifies to \tilde{w}(x)=E_{1}(c_{1}x+c_{2}) , which has constant sign on \mathbb{R}_{+} (since c_{1},c_{2}>0 ). The optimal response is therefore a constant function o_{A}\equiv-\operatorname{sign}(E_{1}) , corresponding to a limiting threshold strategy with \theta=0 or \theta=\infty . In the fully degenerate case E_{0}=E_{1}=0 , \tilde{w}\equiv 0 and any strategy o_{A} is optimal; a threshold strategy may again be chosen. Thus the conclusion of Lemma 5 extends to E_{0}=0 . Proof of Theorem 8 . Suppose (o_{A}^{*},o_{B}^{*}) is a globally optimal deterministic strategy. We show both o_{A}^{*} and o_{B}^{*} must be threshold strategies (up to global sign flip). Suppose o_{A}^{*} is not a threshold strategy (in either orientation). By Lemma 5 (or Remark 5 when E_{0}=0 ), there exists a threshold strategy \tilde{o}_{A} (up to sign flip) such that A(\tilde{o}_{A},o_{B}^{*})>A(o_{A}^{*},o_{B}^{*}) , contradicting global optimality of (o_{A}^{*},o_{B}^{*}) . Therefore o_{A}^{*} is a threshold strategy up to sign flip. By an identical argument with the roles of o_{A} and o_{B} exchanged (the problem is symmetric under player exchange), o_{B}^{*} is also a threshold strategy up to sign flip. By the (o_{A},o_{B})\mapsto(-o_{A},-o_{B}) symmetry, the pair can always be taken to have standard orientation. ∎ Remark 6 (Reduction to finite-dimensional optimization) . Theorem 8 reduces the search for optimal deterministic strategies from an infinite-dimensional space of function pairs (o_{A},o_{B}) to a two-dimensional optimization over threshold pairs (\theta_{A},\theta_{B})\in\mathbb{R}_{+}^{2} . The explicit parameterization and certified computation procedure are given in Appendix D . C.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] . Proposition 5 (Fixed- p mixtures) . Since the payoff A(o_{A},o_{B}) is linear in the strategy, shared randomness provides no advantage at fixed splitting probability: any convex mixture of deterministic strategies all achieving splitting probability p has payoff at most A_{\mathrm{cl}}^{*}(p) . Proof. Let (o_{A,i},o_{B,i}) for i=1,\ldots,n be deterministic strategies each achieving splitting probability p , and let q_{i}\geq 0 with \sum_{i}q_{i}=1 . The mixture achieves payoff A_{\mathrm{SR}}=\sum_{i}q_{i}A(o_{A,i},o_{B,i})\leq\max_{i}A(o_{A,i},o_{B,i})\leq A_{\mathrm{cl}}^{*}(p).\qed (77) 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. Definition 4 (Shared-randomness classical value) . The shared-randomness classical value at splitting probability p is A_{\mathrm{cl,SR}}^{*}(p):=\sup\bigl\{\mathbb{E}_{\kappa}[A(o_{A,\kappa},o_{B,\kappa})]:\mathbb{E}_{\kappa}[p_{\kappa}]=p\bigr\}, (78) the supremum over all shared-randomness strategies with mean splitting probability p . Proposition 6 (Concavity) . The shared-randomness classical value A_{\mathrm{cl,SR}}^{*}(p) is concave in p . Proof. Fix p_{1},p_{2}\in[0,1] , \alpha\in(0,1) , and let p=\alpha p_{1}+(1-\alpha)p_{2} . For any \epsilon>0 , let S_{1},S_{2} be strategies achieving payoffs within \epsilon of A_{\mathrm{cl,SR}}^{*}(p_{1}) and A_{\mathrm{cl,SR}}^{*}(p_{2}) respectively. Consider the strategy that selects S_{1} with probability \alpha and S_{2} with probability 1-\alpha via an independent Bernoulli (\alpha) coin flip. This strategy has mean splitting probability \alpha p_{1}+(1-\alpha)p_{2}=p and achieves expected payoff at least \alpha(A_{\mathrm{cl,SR}}^{*}(p_{1})-\epsilon)+(1-\alpha)(A_{\mathrm{cl,SR}}^{*}(p_{2})-\epsilon) . Taking \epsilon\to 0 yields A_{\mathrm{cl,SR}}^{*}(p)\geq\alpha A_{\mathrm{cl,SR}}^{*}(p_{1})+(1-\alpha)A_{\mathrm{cl,SR}}^{*}(p_{2}) . ∎ The key result is that A_{\mathrm{cl,SR}}^{*}(p) equals the concave envelope of the deterministic value. Theorem 9 (Concavification) . The shared-randomness classical value equals the concave envelope of the deterministic classical value: A_{\mathrm{cl,SR}}^{*}(p)=\mathrm{conc}(A_{\mathrm{cl}}^{*})(p), (79) where \mathrm{conc}(f) denotes the upper concave envelope of f . Proof. Upper bound. Any shared-randomness strategy is a convex mixture of deterministic strategies. Each deterministic component with splitting probability p_{i} achieves payoff at most A_{\mathrm{cl}}^{*}(p_{i}) . The mixture therefore achieves payoff at most the corresponding convex combination of A_{\mathrm{cl}}^{*}(p_{i}) values, which lies on or below the concave envelope. Lower bound. By Proposition 6 , A_{\mathrm{cl,SR}}^{*} is concave. Since deterministic strategies are a special case of shared-randomness strategies, A_{\mathrm{cl,SR}}^{*}(p)\geq A_{\mathrm{cl}}^{*}(p) for all p . A concave function that dominates A_{\mathrm{cl}}^{*} pointwise must dominate \mathrm{conc}(A_{\mathrm{cl}}^{*}) . ∎ Remark 7 (The correct classical benchmark) . For certifying quantum advantage, the correct classical benchmark is A_{\mathrm{cl,SR}}^{*}(p) , not A_{\mathrm{cl}}^{*}(p) . If A_{\mathrm{cl}}^{*}(p) happens to be concave (so the concave envelope coincides with the original function), then shared randomness provides no advantage at any splitting probability. This completes the characterization of classical strategies. The numerical methods for computing A_{\mathrm{cl}}^{*}(p) and its concave envelope are presented in Appendix D . Appendix D 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. D.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}, (80) where A(p) is the payoff achieved by either the classical or quantum strategy. D.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. D.2.1 Explicit Parameterization For X\sim\mathrm{Exp}(\mu) and threshold strategy f_{\theta} , the relevant moments are: \displaystyle D_{0}(\theta) \displaystyle:=\mathbb{E}[f_{\theta}(X)]=\Pr[X<\theta]-\Pr[X\geq\theta]=1-2e^{-\mu\theta}, (81) \displaystyle D_{1}(\theta) \displaystyle:=\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. (82) Evaluating the integrals: \displaystyle\int_{0}^{\theta}x\mu e^{-\mu x}\,dx \displaystyle=\frac{1}{\mu}\bigl(1-e^{-\mu\theta}(1+\mu\theta)\bigr), (83) \displaystyle\int_{\theta}^{\infty}x\mu e^{-\mu x}\,dx \displaystyle=\frac{1}{\mu}e^{-\mu\theta}(1+\mu\theta). (84) 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}. (85) For threshold strategies with thresholds \theta_{A} and \theta_{B} , the game payoff becomes: 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), (86) and the splitting constraint becomes: D_{0}(\theta_{A})\cdot D_{0}(\theta_{B})=1-2p. (87) The optimal classical value at splitting probability p is: A_{\mathrm{cl}}^{*}(p)=\max_{\begin{subarray}{c}\theta_{A},\theta_{B}\geq 0\\ D_{0}(\theta_{A})D_{0}(\theta_{B})=1-2p\end{subarray}}A(\theta_{A},\theta_{B}). (88) D.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})}. (89) 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. (90) 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}. (91) 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). (92) 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})). (93) The optimal classical value is A_{\mathrm{cl}}^{*}(p)=\sup_{\theta_{A}>\theta_{\min}}\tilde{A}(\theta_{A}). (94) D.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) . Definition 5 (Grid approximation) . For grid spacing \delta>0 , define the grid points \theta_{A}^{(k)}=\theta_{\min}+\epsilon+k\delta,\quad k=0,1,\ldots,K, (95) where K=\lfloor(\theta_{\max}-\theta_{\min}-\epsilon)/\delta\rfloor . The grid approximation to the optimal value is A_{\mathrm{grid}}:=\max_{k\in\{0,\ldots,K\}}\tilde{A}(\theta_{A}^{(k)}). (96) Lipschitz Bound. To control the discretization error, we bound the derivative of \tilde{A} . Lemma 6 (Lipschitz bound) . On any compact interval [\theta_{a},\theta_{b}]\subset(\theta_{\min},\infty) , the reduced objective \tilde{A} is Lipschitz continuous with constant L=\sup_{\theta_{A}\in[\theta_{a},\theta_{b}]}\left|\frac{d\tilde{A}}{d\theta_{A}}\right|. (97) Proof. The functions D_{0}(\theta) and D_{1}(\theta) are smooth (in fact, analytic) on (0,\infty) . The constraint mapping \theta_{A}\mapsto\theta_{B}(\theta_{A}) is smooth on (\theta_{\min},\infty) . The payoff A(\theta_{A},\theta_{B}) is a polynomial in D_{0},D_{1} values, hence smooth. By the chain rule, \tilde{A}(\theta_{A})=A(\theta_{A},\theta_{B}(\theta_{A})) is smooth, and in particular Lipschitz on compact subintervals. ∎ 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}}. (98) The partial derivatives are: \displaystyle\frac{\partial A}{\partial\theta_{A}} \displaystyle=-c_{1}D_{1}^{\prime}(\theta_{A})D_{1}(\theta_{B})-c_{2}\bigl(D_{1}^{\prime}(\theta_{A})D_{0}(\theta_{B})+D_{0}^{\prime}(\theta_{A})D_{1}(\theta_{B})\bigr), (99) \displaystyle\frac{\partial A}{\partial\theta_{B}} \displaystyle=-c_{1}D_{1}(\theta_{A})D_{1}^{\prime}(\theta_{B})-c_{2}\bigl(D_{1}(\theta_{A})D_{0}^{\prime}(\theta_{B})+D_{0}(\theta_{A})D_{1}^{\prime}(\theta_{B})\bigr), (100) where \displaystyle D_{0}^{\prime}(\theta) \displaystyle=2\mu e^{-\mu\theta}, (101) \displaystyle D_{1}^{\prime}(\theta) \displaystyle=2\mu\theta e^{-\mu\theta}. (102) 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}^{\prime}(\theta_{A})D_{0}(\theta_{B})}{D_{0}(\theta_{A})D_{0}^{\prime}(\theta_{B})}=-\frac{D_{0}(\theta_{B})}{D_{0}(\theta_{A})}\cdot\frac{e^{-\mu\theta_{A}}}{e^{-\mu\theta_{B}}}. (103) On a compact interval [\theta_{a},\theta_{b}] , all quantities D_{0},D_{1},D_{0}^{\prime},D_{1}^{\prime},\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. Boundary Contributions. We must also bound the objective on the excluded regions. Lemma 7 (Boundary bounds) . The reduced objective \tilde{A}(\theta_{A}) extends continuously to finite limits at the boundaries: \displaystyle\lim_{\theta_{A}\to\theta_{\min}^{+}}\tilde{A}(\theta_{A}) \displaystyle=A_{\min}(p), (104) \displaystyle\lim_{\theta_{A}\to\infty}\tilde{A}(\theta_{A}) \displaystyle=A_{\infty}(p), (105) where A_{\min}(p) and A_{\infty}(p) are finite values. Proof. As \theta_{A}\to\theta_{\min}^{+} , we have D_{0}(\theta_{A})\to(1-2p)^{+} , so D_{0}(\theta_{B})\to 1^{-} , which requires \theta_{B}\to\infty . In this limit: • D_{0}(\theta_{A})\to 1-2p (finite), • D_{1}(\theta_{A})\to D_{1}(\theta_{\min}) (finite), • D_{0}(\theta_{B})\to 1 (finite), • D_{1}(\theta_{B})\to 1/\mu (finite). Since the payoff A(\theta_{A},\theta_{B}) is a polynomial in D_{0},D_{1} values, the limit A_{\min}(p) is finite. As \theta_{A}\to\infty , we have D_{0}(\theta_{A})\to 1 , so D_{0}(\theta_{B})\to 1-2p , giving \theta_{B}\to\theta_{\min} . By a symmetric argument, all quantities remain finite and A_{\infty}(p) is finite. By symmetry of the problem under \theta_{A}\leftrightarrow\theta_{B} , we have A_{\min}(p)=A_{\infty}(p) . ∎ Remark 8 . Although the boundary limits are finite, numerical evaluation confirms that for p in the range of interest, these limits lie below the interior maximum. The derivative |d\tilde{A}/d\theta_{A}| diverges as \theta_{A}\to\theta_{\min}^{+} (since d\theta_{B}/d\theta_{A} grows like e^{\mu\theta_{B}} ), indicating that the payoff changes rapidly near the boundary, but this does not imply the limit is -\infty . Certified Upper Bound. Combining the above, we obtain: Proposition 7 (Certified classical bound) . Let [\theta_{\min}+\epsilon,\theta_{\max}] be a compact interval such that \tilde{A}(\theta_{\min}+\epsilon)A_{\mathrm{grid}}+L\delta/2 . D.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. D.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). (109) 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}. (110) The game payoff and splitting probability become \displaystyle A(a,b) \displaystyle=-\mathbb{E}\bigl[\cos\bigl(2(\theta_{A}(X_{1})-\theta_{B}(X_{2}))\bigr)\cdot w(X_{1},X_{2})\bigr], (111) \displaystyle p(a,b) \displaystyle=\mathbb{E}\left[\frac{1-\cos\bigl(2(\theta_{A}(X_{1})-\theta_{B}(X_{2}))\bigr)}{2}\right]. (112) 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}). (113) We precompute the weight matrices W_{ij}=w(x_{i},x_{j})\cdot w_{i}w_{j},\qquad\pi_{ij}=w_{i}w_{j}, (114) 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. D.4 Threshold Payoff Computation The w -threshold payoff A^{*}(p) corresponds to the optimal policy established in Appendix A : 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)} . D.5 Throughput Model The throughput \mathcal{T}(p) as a function of splitting probability is determined by the baseline task model described in Appendix A.6 . For the numerical results presented in the main text, we use the exponential saturation warm-up model from Section VI.1 , giving \mathcal{T}(p)=\phi_{\max}(1-\rho)\cdot\frac{2\alpha}{\lambda(1+p)+2\alpha} (115) with \phi_{\max}=1 and \alpha=0.5 . D.6 Numerical Parameters Table 1 summarizes the numerical parameters used to generate the results in the main text. Parameter Value Description \lambda 0.8 Customer pair arrival rate \mu 1.0 Service rate \alpha 0.5 Warm-up rate \phi_{\max} 1.0 Steady-state productivity Classical optimization Grid points 500 Number of \theta_{A} grid points \theta_{\max} 12.0 Maximum threshold considered Quantum optimization Polynomial degree 2 Degree of measurement angle polynomials Quadrature points 60 Gauss–Laguerre quadrature points Restarts 20 Random restarts for optimization Seed 1 Random seed for reproducibility w -threshold computation Monte Carlo samples 10^{5} Samples for payoff estimation Table 1: Numerical parameters used for computing classical and quantum performance.