Entanglement improves coordination in distributed systems

Francisco Ferreira da Silva; Stephanie Wehner

REVIEW 3 major objections 3 minor 61 references

In a two-server scheduling model, shared entanglement lets routers coordinate better than any classical strategy that cannot communicate, reducing customer waiting time at identical throughput.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 04:33 UTC pith:ZQRWBA7K

load-bearing objection There is a real analytical result here — the queueing-to-weighted-Bell-game equivalence is genuinely nice — but the classical bound is less certified than advertised because Theorem 8's sign-flip argument does not close off mixed-orientation strategies. the 3 major comments →

arxiv 2602.04588 v2 pith:ZQRWBA7K submitted 2026-02-04 quant-ph cs.DC

Entanglement improves coordination in distributed systems

Francisco Ferreira da Silva , Stephanie Wehner This is my paper

classification quant-ph cs.DC PACS 03.67.-a03.65.Ud

keywords entanglement-assisted coordinationnon-local gamesdistributed schedulingqueueing theoryPareto optimalityquantum networksroutingwaiting time

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper tries to establish that quantum entanglement can deliver concrete operational gains in distributed coordination, not just abstract Bell-inequality violations. It analyzes two servers that process a preemptible baseline task plus customer pairs arriving at two routers that cannot exchange real-time information. The paper proves that when the baseline task's cumulative output is a strictly convex function of uninterrupted processing time, entanglement-assisted routing achieves lower customer waiting time at the same baseline throughput than any classical strategy restricted to local observations and shared randomness. The proof works by showing the optimal full-information policy is a weighted threshold rule, mapping the routing decision to a weighted non-local game whose payoff is exactly proportional to waiting time, and certifying classical upper bounds via a threshold-structure theorem. For exponential service times (μ=1, λ=0.8), the certified quantum advantage holds for splitting probabilities p∈[0.075,0.325], with a maximum waiting-time gap reduction of about 0.073 mean service times near p≈0.20.

Core claim

The central claim: in a two-server routing system with no real-time communication, shared entanglement yields strictly lower customer waiting time at identical baseline throughput than any classical strategy, provided the baseline task's cumulative output T(t) is strictly convex. The proof has three load-bearing steps. First, with full information the optimal policy is a threshold rule on the splitting benefit w(x1,x2)=c1 x1 x2 + c2(x1+x2). Second, mapping the routing decision to a weighted non-local game with payoff A=-E[o_A o_B w] gives the exact identity ΔW_q=(A*-A)/2, so game payoff is waiting time. Third, optimal classical strategies are threshold functions, making a certified classical

What carries the argument

The splitting-benefit function w(x1,x2)=c1 x1 x2 + c2(x1+x2) (c1=λ/(2(1-ρ)), c2=1/4) quantifies how much waiting time is saved by splitting a pair rather than bunching it; the optimal full-information policy is a w-threshold policy. The non-local game maps each router's observed service time to a ±1 output with payoff A=-E[o_A o_B w], and the identity ΔW_q=(A*-A)/2 makes the game payoff exactly proportional to excess waiting time. Theorem 3 reduces classical optimization to threshold pairs (θ_A, θ_B), enabling certification; quantum strategies use a shared Bell pair with measurement angles conditioned on local service times, evaluated numerically via a polynomial angle ansatz and Gauss–Lague

Load-bearing premise

The argument collapses if the baseline task's output is not strictly convex in uninterrupted processing time; the headline numerical advantage region also rests on the quadrature and optimization being accurate enough to certify the reported gap.

What would settle it

Run a high-accuracy optimization of classical threshold strategies with rigorous interval arithmetic for the exponential μ=1, λ=0.8 case; if the classical payoff upper bound rises above the reported quantum payoff for every p∈[0.075,0.325], the certified advantage region is false.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

Wherever the baseline task has strictly convex returns and routers cannot communicate in real time, quantum strategies achieve strictly lower customer waiting time than any classical strategy at the same baseline throughput.
A modest Bell-type coordination advantage (comparable to CHSH) translates into meaningful operational gains because waiting time depends on the second moment of service times and convex throughput amplifies small changes in splitting probability.
The waiting-time reduction is certified for a concrete parameter range: p∈[0.075,0.325] for μ=1, λ=0.8, with maximum gap reduction ≈0.073 mean service times near p≈0.20.
The protocol consumes at most one shared entangled pair per routing decision, so the entanglement generation rate needed is the same order as the routing decision rate—within reach of heralded entanglement demonstrations.
Distributed scheduling and load balancing become a viable near-term application domain for quantum networks, not just abstract non-local games.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The payoff-to-waiting-time identity should carry over to other service-time distributions because the core mechanism is the second-moment dependence, though the threshold structure and certified region would change.
A natural next step would be to compute the minimum entanglement fidelity and pair-generation rate needed to preserve the advantage, since the paper assumes perfect, always-available entanglement.
One could extend the model to more than two servers or non-paired arrivals; the non-local correlation benefit should persist, but the game formulation becomes multi-party and harder to certify.
The strict convexity assumption is exactly the condition that a latency-constrained classical scheme with stale state information would also violate; comparing against such schemes might reveal where the quantum advantage persists once classical communication is allowed but delayed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

There is a real analytical result here — the queueing-to-weighted-Bell-game equivalence is genuinely nice — but the classical bound is less certified than advertised because Theorem 8's sign-flip argument does not close off mixed-orientation strategies.

read the letter

Two things you should know. First, the mapping from a two-server routing queue to a weighted Bell-type game is genuinely nice. The waiting-time gap equals half the payoff gap, and the w-threshold policy is Pareto optimal under strictly convex baseline throughput. That part of the paper is coherent; I did not find a serious problem in the queueing derivation.

Second, the numerical certification of the classical bound has a proof gap that the authors' "global sign flip" does not close. Lemma 5's optimal response can be the negation of a threshold when the effective slope is negative. The flip (o_A,o_B) -> (-o_A,-o_B) only maps (-f_a,f_b) to (f_a,-f_b), not to (f_a,f_b). Theorem 8 asserts all optimal deterministic strategies are standard threshold pairs, but the proof as written does not rule out mixed-orientation pairs. The numerical search in Appendix D considers only standard thresholds, so A*_cl,SR(p) could be understated if any mixed-orientation strategy beats the best standard pair. My quick checks suggest standard pairs dominate, but that is not proved, and the paper calls the bound "certified." That is a real soft spot.

The second soft spot is the numerical certification itself. The classical upper bound uses a numerically computed Lipschitz constant, not a formal interval certificate; the quantum "achieved" payoff uses Gauss-Laguerre quadrature and SLSQP with no error bounds. The reported margin — about 0.073 in waiting-time gap — is probably robust to quadrature error, but "certified" overstates the support. The authors flag the perfect-entanglement and no-communication assumptions; they should also flag that the advantage region rests on numerical optimization without rigorous error control.

What is actually new: the w-threshold Pareto optimality, the exact waiting-time/payoff correspondence, and the weighted continuous-input game with threshold classical structure. The analytical results are solid; the numerical claims are the weak part. This paper deserves a serious referee, but the referee should require a fix to the sign-flip argument and a more honest description of the numerical bounds — either interval arithmetic or a clear statement that the advantage region is numerically observed, not formally certified. I would send it out and ask for revisions before trusting the quantitative claims.

Referee Report

3 major / 3 minor

Summary. The paper studies a two-server FCFS queue in which pairs of customers arrive at two routers, each router observes only its local service time, and the routers must decide whether to send their customers to the same server (bunch) or to different servers (split) without real-time communication. A continuously available, preemptible baseline task is processed during idle periods. The authors prove that the optimal full-information policy is a threshold on the splitting benefit w(x1,x2)=c1 x1 x2 + c2(x1+x2), that the local-decision problem is exactly a weighted non-local game whose payoff determines the waiting-time gap, that optimal classical strategies are threshold pairs, and that for exponential service times with μ=1, λ=0.8, entanglement-assisted quantum strategies achieve strictly lower waiting time at identical baseline throughput for p∈[0.075,0.325], with a maximum reduction in the waiting-time gap of approximately 0.073 (in units of 1/μ).

Significance. If the technical gaps are repaired, this is a valuable contribution: it translates abstract quantum non-local correlations into an operational queueing-theoretic performance metric, with an explicit protocol, a clear analytical correspondence between the game payoff and the waiting-time gap, and public code. The queueing reduction to a w-threshold policy and the game–queueing equivalence are elegant and are the strongest parts of the paper. A correct version would provide a concrete template for assessing entanglement-assisted coordination in latency-constrained distributed systems.

major comments (3)

[Appendix C, Theorem 8 / Lemma 5] Lemma 5 identifies that when c1E1+c2E0<0, the optimal response is a negated threshold -f_θ. The subsequent global sign flip (o_A,o_B)->(-o_A,-o_B) maps (-f_a,f_b) to (f_a,-f_b), not to a standard threshold pair; one player remains negated. Such one-sided pairs are valid classical strategies with splitting probability p=(1+E[f_a]E[f_b])/2 and are not covered by the optimization in Appendix D.2, which restricts to standard thresholds satisfying D0(θ_A)D0(θ_B)=1-2p. The proof of Theorem 8 therefore does not establish that optimal deterministic classical strategies are standard threshold pairs. Consequently A*_cl,SR(p) may be underestimated, and the advantage region P in Theorem 4 is not rigorously supported.
[Appendix D.2, Proposition 7] Proposition 7 is presented as a certified upper bound, but the Lipschitz constant L is obtained numerically by sampling |dA~/dθ_A| on a fine grid (Remark 9), and the boundary conditions A~(θ_min+ε)<A_grid and A~(θ_max)<A_grid are only numerically verified. A numerical maximum of a derivative is not a mathematical upper bound; without interval-arithmetic or analytical estimates, the inequality A_cl(p)≤A_grid+Lδ/2 is not guaranteed. Similarly, the restriction to [θ_min+ε,θ_max] is not rigorously justified for excluding the boundary regions. Thus the 'certified' classical benchmark in Theorem 4 exceeds what is actually proved.
[Appendix D.3, Eq. (D32)] The quantum payoff A_qu is evaluated with 60-point Gauss-Laguerre quadrature and optimized with SLSQP. The quadrature error is not bounded; if the quadrature overestimates the expectation in Eq. (D32), the reported A_qu may exceed the true payoff of the constructed strategy, so A_qu is not a guaranteed lower bound. SLSQP convergence itself is not an issue for a lower bound, but the final evaluation must be certified. Consequently the numerical gap of 0.073 and the interval [0.075,0.325] in Theorem 4 are not certified against numerical error.

minor comments (3)

[Section VI.A] The text says the maximum reduction in the waiting-time gap is 'approximately 21%' near p≈0.20, while the abstract quotes the absolute value 0.073. Make explicit that 21% is the relative reduction of the gap with respect to the classical gap, to avoid apparent inconsistency.
[Appendix D.4] A* is estimated by Monte Carlo with 10^5 samples but no confidence interval is reported. While A* cancels in the A_qu-A_cl comparison, the plotted ΔW values inherit the sampling noise; report standard errors or evaluate A* with the same quadrature as A_qu.
[Definition 3] Definition 3 defines only the standard orientation of a threshold strategy. The text repeatedly uses 'up to a global sign flip' but never defines a reversed-orientation threshold -f_θ. Defining this explicitly would make the proof of Theorem 8 and the discussion of Lemma 5 easier to follow.

Circularity Check

0 steps flagged

No significant circularity: derivation chain is self-contained; self-citation [10] is contextual and not load-bearing.

full rationale

The paper's derivation is self-contained. Appendix A derives the w-threshold policy and throughput T(p) from the M^X/G/1 queueing model, and Lemma 1/Proposition 4 prove the waiting-time gap equals (A* - A)/2 rather than assuming that equivalence as a definition. Quantum advantage at fixed p therefore implies lower waiting time at equal throughput by algebraic consequence of the queueing model, not by construction. The classical benchmark is obtained from a structural threshold theorem plus a certified grid search, while the quantum values are explicit polynomial-angle strategies evaluated by Gauss-Laguerre quadrature; neither is fitted to the claimed conclusion. The only self-citation, [10], describes the earlier workshop version and is not the basis of any theorem. The reviewer-raised concerns about possibly omitted sign-flipped threshold strategies and about the lack of formal interval certificates are correctness risks affecting the numerical certification, not circularity: if they were valid, the reported p-range could fail, but the derivation would still not reduce to its inputs.

Axiom & Free-Parameter Ledger

6 free parameters · 7 axioms · 0 invented entities

The central claim rests on an analytical queueing/non-local-game correspondence that is internally derived, plus a numerical certification. The free parameters are the illustrative system parameters and the optimized quantum strategy coefficients; no new physical entities are postulated. The main untested premise is the accuracy of the numerical pipeline underpinning the advantage region.

free parameters (6)

λ (pair arrival rate) = 0.8
Chosen for the numerical example; the certified advantage region is computed at this value and may not hold for other loads.
μ (service rate) = 1.0
Scales time; set to 1 in the numerical certification.
α (warm-up rate) = 0.5
Hand-chosen curvature parameter in the exponential-saturation baseline model; the magnitude of the operational advantage depends on it.
φ_max (steady-state productivity) = 1.0
Normalization in the throughput model; does not affect the qualitative trade-off.
Quantum measurement-angle polynomial coefficients = optimized in code; not reported in text
The quantum strategy is constructed by optimizing degree-2 polynomial coefficients (a0..a2, b0..b2) to maximize payoff at each p; the reported advantage is a lower bound for this specific family.
Numerical hyperparameters (grid=500, quadrature=60, restarts=20, seed=1)
Choices in the certification pipeline; no sensitivity analysis is reported.

axioms (7)

domain assumption Routing decisions must be made on timescales shorter than classical round-trip latency, so communication-free classical strategies are the relevant baseline.
Sections I and III; if delayed or coarse-grained classical state were allowed, the comparison could change (the authors flag this in Section VII).
domain assumption Customer pairs arrive as a Poisson process with rate λ and service times are i.i.d. Exp(μ).
Section III; underlies the M^X/G/1 reduction and all numerical results.
domain assumption Baseline output T(t) is differentiable, increasing, T(0)=0, and strictly convex.
Section III and Proposition 2; strict convexity is required for the Pareto trade-off and monotonicity of throughput in p.
standard math Servers alternate between idle and busy periods as a renewal process; PASTA and renewal reward theorem apply.
Appendix A.6, using standard queueing results [24,25].
domain assumption Quantum measurements on a shared singlet yield correlation cos(2(θ_A−θ_B)) and any real polynomial angle functions are physically implementable.
Appendix D.3; standard two-qubit measurement formalism.
domain assumption Perfect, always-available entanglement and deterministic memory readout.
Section VII discussion; explicitly flagged as an assumption, with near-term devices only approximating it.
ad hoc to paper Numerical accuracy of Gauss-Laguerre quadrature and SLSQP convergence for the quantum lower bound.
Appendix D.3; no error bounds are provided for these steps, so the reported quantum payoff values are not formally certified.

pith-pipeline@v1.3.0-alltime-deepseek · 25880 in / 26022 out tokens · 266742 ms · 2026-08-03T04:33:39.230685+00:00 · methodology

0 comments

read the original 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.

Figures

Figures reproduced from arXiv: 2602.04588 by Francisco Ferreira da Silva, Stephanie Wehner.

**Figure 2.** Figure 2: FIG. 2. The routing problem as a non-local game. Routers [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: FIG. 3. Waiting time gap ∆ [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

discussion (0)

Reference graph

Works this paper leans on

61 extracted references · 3 linked inside Pith

[1]

T. L. Casavant and J. G. Kuhl, A taxonomy of scheduling in general-purpose distributed computing systems, IEEE Transactions on software engineering14, 141 (1988)

1988
[2]

QuTech Part III Application based research - Demonstrators

Upon observing local service timesX 1 andX 2, router A performs a measure- ment on its qubit in a basis determined by angleθ A(X1), obtaining outcomeo A ∈ {+1,−1}; router B acts anal- ogously with angleθ B(X2). The routers then route to servero A ando B respectively, resulting in bunching when oA ·o B = +1 and splitting wheno A ·o B =−1. The quantum advan...
[3]

Wanget al., Load sharing in distributed systems, IEEE Transactions on computers100, 204 (1985)

Y.-T. Wanget al., Load sharing in distributed systems, IEEE Transactions on computers100, 204 (1985)

1985
[4]

Jiang, A survey of task allocation and load balanc- ing in distributed systems, IEEE Transactions on Parallel and Distributed Systems27, 585 (2015)

Y. Jiang, A survey of task allocation and load balanc- ing in distributed systems, IEEE Transactions on Parallel and Distributed Systems27, 585 (2015)

2015
[5]

J. S. Bell, On the einstein podolsky rosen paradox, Physics Physique Fizika1, 195 (1964)

1964
[6]

Brunner, D

N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Bell nonlocality, Reviews of modern physics 86, 419 (2014)

2014
[7]

J. P. Covey, H. Weinfurter, and H. Bernien, Quantum networks with neutral atom processing nodes, npj Quan- tum Information9, 90 (2023)

2023
[8]

M. Ruf, N. H. Wan, H. Choi, D. Englund, and R. Hanson, Quantum networks based on color centers in diamond, Journal of Applied Physics130(2021)

2021
[9]

Krutyanskiy, M

V. Krutyanskiy, M. Galli, V. Krcmarsky, S. Baier, D. Fioretto, Y. Pu, A. Mazloom, P. Sekatski, M. Can- teri, M. Teller,et al., Entanglement of trapped-ion qubits separated by 230 meters, Physical Review Letters130, 050803 (2023)

2023
[10]

A. J. Stolk, K. L. van der Enden, M.-C. Slater, I. te Raa- Derckx, P. Botma, J. van Rantwijk, J. B. Biemond, R. A. Hagen, R. W. Herfst, W. D. Koek,et al., Metropolitan- scale heralded entanglement of solid-state qubits, Science advances10, eadp6442 (2024)

2024
[11]

F. F. Da Silva and S. Wehner, Entanglement improves coordination in distributed systems, inProceedings of the 2nd Workshop on Quantum Networks and Distributed Quantum Computing(2025) pp. 14–20

2025
[12]

Hensen, H

B. Hensen, H. Bernien, A. E. Dr´ eau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. Vermeulen, R. N. Schouten, C. Abell´ an,et al., Loophole-free bell inequality violation using electron spins separated by 1.3 kilometres, Nature526, 682 (2015)

2015
[13]

J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Proposed experiment to test local hidden-variable theo- ries, Physical review letters23, 880 (1969)

1969
[14]

D. Ding, Z. Ji, P. Pocreau, M. Xu, and X. Xu, Quan- tum nonlocality under latency constraints, arXiv preprint arXiv:2510.26349 (2025)

Pith/arXiv arXiv 2025
[15]

Ding and L

D. Ding and L. Jiang, Coordinating decisions via quan- tum telepathy, arXiv preprint arXiv:2407.21723 (2024)

Pith/arXiv arXiv 2024
[16]

Hasanpour, S

M. Hasanpour, S. Shariat, P. Barnaghi, S. A. Hoseinita- batabaei, S. Vahid, and R. Tafazolli, Quantum load bal- ancing in ad hoc networks, Quantum Information Pro- cessing16, 1 (2017)

2017
[17]

Mironowicz, Entangled rendezvous: a possible appli- cation of bell non-locality for mobile agents on networks, New Journal of Physics25, 013023 (2023)

P. Mironowicz, Entangled rendezvous: a possible appli- cation of bell non-locality for mobile agents on networks, New Journal of Physics25, 013023 (2023)

2023
[18]

Viola and P

G. Viola and P. Mironowicz, Quantum strategies for ren- dezvous and domination tasks on graphs with mobile agents, Physical Review A109, 042201 (2024)

2024
[19]

Tucker, P

J. Tucker, P. Strange, P. Mironowicz, and J. Quin- tanilla, Quantum-assisted rendezvous on graphs: Explicit algorithms and quantum computer simulations, arXiv preprint arXiv:2405.14951 (2024)

Pith/arXiv arXiv 2024
[20]

V. Arun, V. Chidambaram, and S. Aaronson, Faster- than-light coordination for networked systems with quan- tum non-local games, inProceedings of the 24th ACM Workshop on Hot Topics in Networks (HotNets ’25) (College Park, MD, USA, 2025) to appear

2025
[21]

Gross, J

D. Gross, J. F. Shortle, J. M. Thompson, and C. M. Harris,Fundamentals of queueing theory, Vol. 627 (John wiley & sons, 2011)

2011
[22]

Mitzenmacher, The power of two choices in random- ized load balancing, IEEE Transactions on Parallel and Distributed Systems12, 1094 (2002)

M. Mitzenmacher, The power of two choices in random- ized load balancing, IEEE Transactions on Parallel and Distributed Systems12, 1094 (2002). 8

2002
[23]

Gupta, M

V. Gupta, M. H. Balter, K. Sigman, and W. Whitt, Analysis of join-the-shortest-queue routing for web server farms, Performance Evaluation64, 1062 (2007)

2007
[24]

J. L. Hennessy and D. A. Patterson,Computer architec- ture: a quantitative approach(Elsevier, 2011)

2011
[25]

Grimmett and D

G. Grimmett and D. Stirzaker,Probability and random processes(Oxford university press, 2020)

2020
[26]

R. W. Wolff, Poisson arrivals see time averages, Opera- tions Research30, 223 (1982). Appendix A: Thew-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 thew-threshold policy achieves Pareto optimality: no other policy can improve one objective ...

1982
[27]

Each server has a queue of unlimited capacity to hold incoming requests and follows a first-come, first-served (FCFS) discipline

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 c...
[28]

Single-server primitives and batch workload We now derive the second moment of the batch workload seen by a single server, which is the key input to the Pollaczek–Khinchine formula [20] for computing expected waiting time. We apply the Pollaczek–Khinchine (PK) formula for anM X /G/1 queue, which expresses the expected virtual waiting time, i.e., the time ...
[29]

From the single-server perspec- tive established in Appendix A 1, we have anM X /G/1 queue with batch arrival rate Λ =λ(1 +p)/2 and utilization ρ=λ/µ

W aiting time decomposition We now characterize the mean customer waiting time under a given routing policy. From the single-server perspec- tive established in Appendix A 1, we have anM X /G/1 queue with batch arrival rate Λ =λ(1 +p)/2 and utilization ρ=λ/µ. The customer waiting time can be decomposed into two components. First, the virtual wait: the tim...
[30]

Optimization formulation at fixed splitting probability We now formulate the routing problem as a constrained optimization. Recall from Appendix A 3 that E[Wq] = λ(E[S2]−2E[rX 1X2]) 4(1−ρ) + 1 4 E[(1−r)S].(A13) 11 Expanding the within-batch term asE[(1−r)S] =E[S]−E[rS], we obtain E[Wq] = λE[S2] 4(1−ρ) + E[S] 4 − λ 2(1−ρ) E[rX1X2]− 1 4 E[rS].(A14) Define c...
[31]

Recall the splitting benefit functionw:R 2 + →R + defined at the beginning of this appendix: w(x1, x2) =c 1x1x2 +c 2(x1 +x 2),(A18) wherec 1 = λ 2(1−ρ) andc 2 = 1 4

Optimal policy We now characterize the solution to Problem 2. Recall the splitting benefit functionw:R 2 + →R + defined at the beginning of this appendix: w(x1, x2) =c 1x1x2 +c 2(x1 +x 2),(A18) wherec 1 = λ 2(1−ρ) andc 2 = 1 4 . The objective function can thus be written compactly asE[r·w(X 1, X2)]. Since X1, X2 ∼Exp(µ), all moments exist, andw(X 1, X2) i...
[32]

Following the single-server perspective established in Appendix A 1, we analyze one server’s baseline throughput

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 con...
[33]

IfTis strictly convex (soϕis increasing), thenT(p)strictly decreases inp. 13
[34]

IfTis linear (soϕis constant), thenT(p)is independent ofp
[35]

Proof.Write T(p) = E[T(I)] E[I+B] = 1 +p C E[T(I)], C= 2 1 λ + 1 µ−λ

IfTis strictly concave (soϕis decreasing), thenT(p)strictly increases inp. Proof.Write T(p) = E[T(I)] E[I+B] = 1 +p C E[T(I)], C= 2 1 λ + 1 µ−λ . Setf(Λ) :=E[T(I)] so that T(p) = 1 +p C f(Λ). Differentiate with respect top: dT dp = 1 C f(Λ) + (1 +p)f ′(Λ) dΛ dp . Since dΛ dp = λ 2 and Λ = λ 2 (1 +p), we have (1 +p) dΛ dp = Λ. Hence dT dp = 1 C f(Λ) + Λf ′...
[36]

Recall that any routing policy induces a splitting probabilityp=E[r]∈[0,1]

Pareto optimality of the threshold policy We now establish that thew-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 probabilityp=E[r]∈[0,1]. From Proposition 2, the baseline throughputT(p) depends only on this splitting ...
[37]

For any routing policy that induces a splitting probabilityp, we show that load-balanced server assignment minimizes the average customer waiting time

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 probabilityp, we show that load-balanced server assignment minimizes the average customer waiting time. Proposition 3(Load-Balanced Dominance).For any oracle routing policyπwith spl...
[38]

This policy splits pairs with high splitting benefitw(x 1, x2) and bunches pairs with low splitting benefit, achieving the minimum waiting time at any given splitting probability

Local Strategies The analysis in Appendix A characterized thew-threshold policy, which is optimal when both service times (X1, X2) are available for routing decisions. This policy splits pairs with high splitting benefitw(x 1, x2) and bunches pairs with low splitting benefit, achieving the minimum waiting time at any given splitting probability. In practi...
[39]

Define the decision function σ∗(x1, x2) = sign(τp −w(x 1, x2)),(B1) which takes value +1 (bunch) whenw < τp and−1 (split) whenw > τ p

Setup Fix a splitting probabilityp∈[0,1] and letτ p be the unique threshold satisfying Pr[w(X 1, X2)> τp] =p. Define the decision function σ∗(x1, x2) = sign(τp −w(x 1, x2)),(B1) which takes value +1 (bunch) whenw < τp and−1 (split) whenw > τ p. This is thew-threshold policy established in Appendix A: split when the splitting benefit exceeds the threshold,...
[40]

The Queueing–Game Correspondence Lemma 4(Waiting time gap).Let(o A, oB)be any local routing strategy with splitting probabilityp, employing load-balanced server assignment. The excess waiting time relative to thew-threshold policy is ∆Wq :=E[W q](oA, oB)−E[W q]∗ = 1 2 E (oA(X1)oB(X2)−σ ∗(X1, X2))w(X 1, X2) .(B3) Proof.From Appendix A 4, under load-balance...
[41]

Players A and B receive service timesX 1, X2 ∼ Exp(µ) independently and produce outputso A(X1), oB(X2)∈ {+1,−1}without communication

Non-Local Game F ormulation We cast the routing problem as a non-local game (Definition 2). Players A and B receive service timesX 1, X2 ∼ Exp(µ) independently and produce outputso A(X1), oB(X2)∈ {+1,−1}without communication. The game payoff is A(oA, oB) =−E[o A(X1)oB(X2)·w(X 1, X2)],(B11) subject to the constraint Pr[o A(X1)oB(X2) =−1] =p. The payoffArew...
[42]

Definition 3(Threshold strategy).A strategyf:R + → {+1,−1}is athreshold strategywith thresholdθ≥0if f(x) = ( +1x < θ, −1x≥θ

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 strategyf:R + → {+1,−1}is athreshold strategywith thresholdθ≥0if f(x) = ( +1x < θ, −1x≥θ. (C1) We writef θ to denote the threshold strat...
[43]

A shared-randomness strategy uses a common random variableκ(independent of the inputsX 1, X2) to select a deterministic local strategy (o A,κ, oB,κ) for each arriving pair

Shared Randomness and the Classical Benchmark We now consider classical strategies augmented with shared randomness. A shared-randomness strategy uses a common random variableκ(independent of the inputsX 1, X2) to select a deterministic local strategy (o A,κ, oB,κ) for each arriving pair. The resulting payoff isE κ[A(oA,κ, oB,κ)], and the splitting constr...
[44]

Overview To construct the Pareto frontier comparison between classical and quantum strategies, we compute three quantities at each splitting probabilityp∈(0,1/2):
[45]

Thew-threshold payoffA ∗(p), achieved by the optimal policy with full access to both service times
[46]

The optimal classical payoffA ∗ cl(p), achieved by the best local threshold strategy; 22
[47]

The quantum payoffA qu(p), achieved by a numerically optimized quantum strategy. The waiting time gap relative to thew-threshold policy is then obtained via the game–queueing correspondence (Proposition 4): ∆Wq = A∗(p)−A(p) 2 ,(D1) whereA(p) is the payoff achieved by either the classical or quantum strategy
[48]

This section provides the explicit parameterization and certified computation procedure

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. a. Explicit Parameterization ForX∼Exp(µ) and threshold strategyf θ, the relevant moments are: D0(θ) :=E[f θ(X)] = Pr[X < θ]−P...
[49]

Chooseϵsmall enough andθ max large enough that the boundary conditions in Proposition 7 are satisfied (verified numerically)
[50]

ComputeA grid on a grid with spacingδ
[51]

Compute the Lipschitz constantLnumerically by evaluating|d ˜A/dθA|on a finer grid
[52]

For demonstrating quantum advantage, it suffices to showA qu(p)> Agrid +Lδ/2

Report the certified upper boundA ∗ cl(p)≤A grid +Lδ/2. For demonstrating quantum advantage, it suffices to showA qu(p)> Agrid +Lδ/2. d. Concavification By Theorem 9, the correct classical benchmark isA ∗ cl,SR(p) = conc(A∗ cl)(p). The concave envelope is computed via the upper hull algorithm inO(n) time for sorted input
[53]

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θ A(x1) andθ B(x2). We are free to choose any Bell state and measurement angle convention; our numerical implementation uses a convention such that the resu...
[54]

We computeA ∗(p) via Monte Carlo estimation:

Threshold Payoff Computation Thew-threshold payoffA ∗(p) corresponds to the optimal policy established in Appendix A: split whenw(X 1, X2)> τp and bunch otherwise, whereτ p is chosen such that Pr[w(X 1, X2)> τp] =p. We computeA ∗(p) via Monte Carlo estimation:
[55]

SampleNindependent pairs (X (i) 1 , X(i) 2 )∼Exp(µ) ⊗2
[56]

Computew (i) =w(X (i) 1 , X(i) 2 ) for each sample
[57]

Determineτ p as the (1−p)-quantile of{w (i)}
[58]

Compute thew-threshold decisionσ ∗(i) = sign(τp −w (i))
[59]

Estimate the payoff asA ∗(p)≈ −1 N PN i=1 σ∗(i)w(i)
[60]

Throughput Model The throughputT(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 A, giving T(p) =ϕ max(1−ρ)· 2α λ(1 +p) + 2α (D36) withϕ max = 1 andα= 0.5
[61]

Numerical Parameters Table I summarizes the numerical parameters used to generate the results in the main text. Parameter V alue Description λ0.8 Customer pair arrival rate µ1.0 Service rate α0.5 Warm-up rate ϕmax 1.0 Steady-state productivity Classical optimization Grid points 500 Number ofθ A grid points θmax 12.0 Maximum threshold considered Quantum op...

[1] [1]

T. L. Casavant and J. G. Kuhl, A taxonomy of scheduling in general-purpose distributed computing systems, IEEE Transactions on software engineering14, 141 (1988)

1988

[2] [2]

QuTech Part III Application based research - Demonstrators

Upon observing local service timesX 1 andX 2, router A performs a measure- ment on its qubit in a basis determined by angleθ A(X1), obtaining outcomeo A ∈ {+1,−1}; router B acts anal- ogously with angleθ B(X2). The routers then route to servero A ando B respectively, resulting in bunching when oA ·o B = +1 and splitting wheno A ·o B =−1. The quantum advan...

[3] [3]

Wanget al., Load sharing in distributed systems, IEEE Transactions on computers100, 204 (1985)

Y.-T. Wanget al., Load sharing in distributed systems, IEEE Transactions on computers100, 204 (1985)

1985

[4] [4]

Jiang, A survey of task allocation and load balanc- ing in distributed systems, IEEE Transactions on Parallel and Distributed Systems27, 585 (2015)

Y. Jiang, A survey of task allocation and load balanc- ing in distributed systems, IEEE Transactions on Parallel and Distributed Systems27, 585 (2015)

2015

[5] [5]

J. S. Bell, On the einstein podolsky rosen paradox, Physics Physique Fizika1, 195 (1964)

1964

[6] [6]

Brunner, D

N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Bell nonlocality, Reviews of modern physics 86, 419 (2014)

2014

[7] [7]

J. P. Covey, H. Weinfurter, and H. Bernien, Quantum networks with neutral atom processing nodes, npj Quan- tum Information9, 90 (2023)

2023

[8] [8]

M. Ruf, N. H. Wan, H. Choi, D. Englund, and R. Hanson, Quantum networks based on color centers in diamond, Journal of Applied Physics130(2021)

2021

[9] [9]

Krutyanskiy, M

V. Krutyanskiy, M. Galli, V. Krcmarsky, S. Baier, D. Fioretto, Y. Pu, A. Mazloom, P. Sekatski, M. Can- teri, M. Teller,et al., Entanglement of trapped-ion qubits separated by 230 meters, Physical Review Letters130, 050803 (2023)

2023

[10] [10]

A. J. Stolk, K. L. van der Enden, M.-C. Slater, I. te Raa- Derckx, P. Botma, J. van Rantwijk, J. B. Biemond, R. A. Hagen, R. W. Herfst, W. D. Koek,et al., Metropolitan- scale heralded entanglement of solid-state qubits, Science advances10, eadp6442 (2024)

2024

[11] [11]

F. F. Da Silva and S. Wehner, Entanglement improves coordination in distributed systems, inProceedings of the 2nd Workshop on Quantum Networks and Distributed Quantum Computing(2025) pp. 14–20

2025

[12] [12]

Hensen, H

B. Hensen, H. Bernien, A. E. Dr´ eau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. Vermeulen, R. N. Schouten, C. Abell´ an,et al., Loophole-free bell inequality violation using electron spins separated by 1.3 kilometres, Nature526, 682 (2015)

2015

[13] [13]

J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Proposed experiment to test local hidden-variable theo- ries, Physical review letters23, 880 (1969)

1969

[14] [14]

D. Ding, Z. Ji, P. Pocreau, M. Xu, and X. Xu, Quan- tum nonlocality under latency constraints, arXiv preprint arXiv:2510.26349 (2025)

Pith/arXiv arXiv 2025

[15] [15]

Ding and L

D. Ding and L. Jiang, Coordinating decisions via quan- tum telepathy, arXiv preprint arXiv:2407.21723 (2024)

Pith/arXiv arXiv 2024

[16] [16]

Hasanpour, S

M. Hasanpour, S. Shariat, P. Barnaghi, S. A. Hoseinita- batabaei, S. Vahid, and R. Tafazolli, Quantum load bal- ancing in ad hoc networks, Quantum Information Pro- cessing16, 1 (2017)

2017

[17] [17]

Mironowicz, Entangled rendezvous: a possible appli- cation of bell non-locality for mobile agents on networks, New Journal of Physics25, 013023 (2023)

P. Mironowicz, Entangled rendezvous: a possible appli- cation of bell non-locality for mobile agents on networks, New Journal of Physics25, 013023 (2023)

2023

[18] [18]

Viola and P

G. Viola and P. Mironowicz, Quantum strategies for ren- dezvous and domination tasks on graphs with mobile agents, Physical Review A109, 042201 (2024)

2024

[19] [19]

Tucker, P

J. Tucker, P. Strange, P. Mironowicz, and J. Quin- tanilla, Quantum-assisted rendezvous on graphs: Explicit algorithms and quantum computer simulations, arXiv preprint arXiv:2405.14951 (2024)

Pith/arXiv arXiv 2024

[20] [20]

V. Arun, V. Chidambaram, and S. Aaronson, Faster- than-light coordination for networked systems with quan- tum non-local games, inProceedings of the 24th ACM Workshop on Hot Topics in Networks (HotNets ’25) (College Park, MD, USA, 2025) to appear

2025

[21] [21]

Gross, J

D. Gross, J. F. Shortle, J. M. Thompson, and C. M. Harris,Fundamentals of queueing theory, Vol. 627 (John wiley & sons, 2011)

2011

[22] [22]

Mitzenmacher, The power of two choices in random- ized load balancing, IEEE Transactions on Parallel and Distributed Systems12, 1094 (2002)

M. Mitzenmacher, The power of two choices in random- ized load balancing, IEEE Transactions on Parallel and Distributed Systems12, 1094 (2002). 8

2002

[23] [23]

Gupta, M

V. Gupta, M. H. Balter, K. Sigman, and W. Whitt, Analysis of join-the-shortest-queue routing for web server farms, Performance Evaluation64, 1062 (2007)

2007

[24] [24]

J. L. Hennessy and D. A. Patterson,Computer architec- ture: a quantitative approach(Elsevier, 2011)

2011

[25] [25]

Grimmett and D

G. Grimmett and D. Stirzaker,Probability and random processes(Oxford university press, 2020)

2020

[26] [26]

R. W. Wolff, Poisson arrivals see time averages, Opera- tions Research30, 223 (1982). Appendix A: Thew-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 thew-threshold policy achieves Pareto optimality: no other policy can improve one objective ...

1982

[27] [27]

Each server has a queue of unlimited capacity to hold incoming requests and follows a first-come, first-served (FCFS) discipline

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 c...

[28] [28]

Single-server primitives and batch workload We now derive the second moment of the batch workload seen by a single server, which is the key input to the Pollaczek–Khinchine formula [20] for computing expected waiting time. We apply the Pollaczek–Khinchine (PK) formula for anM X /G/1 queue, which expresses the expected virtual waiting time, i.e., the time ...

[29] [29]

From the single-server perspec- tive established in Appendix A 1, we have anM X /G/1 queue with batch arrival rate Λ =λ(1 +p)/2 and utilization ρ=λ/µ

W aiting time decomposition We now characterize the mean customer waiting time under a given routing policy. From the single-server perspec- tive established in Appendix A 1, we have anM X /G/1 queue with batch arrival rate Λ =λ(1 +p)/2 and utilization ρ=λ/µ. The customer waiting time can be decomposed into two components. First, the virtual wait: the tim...

[30] [30]

Optimization formulation at fixed splitting probability We now formulate the routing problem as a constrained optimization. Recall from Appendix A 3 that E[Wq] = λ(E[S2]−2E[rX 1X2]) 4(1−ρ) + 1 4 E[(1−r)S].(A13) 11 Expanding the within-batch term asE[(1−r)S] =E[S]−E[rS], we obtain E[Wq] = λE[S2] 4(1−ρ) + E[S] 4 − λ 2(1−ρ) E[rX1X2]− 1 4 E[rS].(A14) Define c...

[31] [31]

Recall the splitting benefit functionw:R 2 + →R + defined at the beginning of this appendix: w(x1, x2) =c 1x1x2 +c 2(x1 +x 2),(A18) wherec 1 = λ 2(1−ρ) andc 2 = 1 4

Optimal policy We now characterize the solution to Problem 2. Recall the splitting benefit functionw:R 2 + →R + defined at the beginning of this appendix: w(x1, x2) =c 1x1x2 +c 2(x1 +x 2),(A18) wherec 1 = λ 2(1−ρ) andc 2 = 1 4 . The objective function can thus be written compactly asE[r·w(X 1, X2)]. Since X1, X2 ∼Exp(µ), all moments exist, andw(X 1, X2) i...

[32] [32]

Following the single-server perspective established in Appendix A 1, we analyze one server’s baseline throughput

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 con...

[33] [33]

IfTis strictly convex (soϕis increasing), thenT(p)strictly decreases inp. 13

[34] [34]

IfTis linear (soϕis constant), thenT(p)is independent ofp

[35] [35]

Proof.Write T(p) = E[T(I)] E[I+B] = 1 +p C E[T(I)], C= 2 1 λ + 1 µ−λ

IfTis strictly concave (soϕis decreasing), thenT(p)strictly increases inp. Proof.Write T(p) = E[T(I)] E[I+B] = 1 +p C E[T(I)], C= 2 1 λ + 1 µ−λ . Setf(Λ) :=E[T(I)] so that T(p) = 1 +p C f(Λ). Differentiate with respect top: dT dp = 1 C f(Λ) + (1 +p)f ′(Λ) dΛ dp . Since dΛ dp = λ 2 and Λ = λ 2 (1 +p), we have (1 +p) dΛ dp = Λ. Hence dT dp = 1 C f(Λ) + Λf ′...

[36] [36]

Recall that any routing policy induces a splitting probabilityp=E[r]∈[0,1]

Pareto optimality of the threshold policy We now establish that thew-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 probabilityp=E[r]∈[0,1]. From Proposition 2, the baseline throughputT(p) depends only on this splitting ...

[37] [37]

For any routing policy that induces a splitting probabilityp, we show that load-balanced server assignment minimizes the average customer waiting time

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 probabilityp, we show that load-balanced server assignment minimizes the average customer waiting time. Proposition 3(Load-Balanced Dominance).For any oracle routing policyπwith spl...

[38] [38]

This policy splits pairs with high splitting benefitw(x 1, x2) and bunches pairs with low splitting benefit, achieving the minimum waiting time at any given splitting probability

Local Strategies The analysis in Appendix A characterized thew-threshold policy, which is optimal when both service times (X1, X2) are available for routing decisions. This policy splits pairs with high splitting benefitw(x 1, x2) and bunches pairs with low splitting benefit, achieving the minimum waiting time at any given splitting probability. In practi...

[39] [39]

Define the decision function σ∗(x1, x2) = sign(τp −w(x 1, x2)),(B1) which takes value +1 (bunch) whenw < τp and−1 (split) whenw > τ p

Setup Fix a splitting probabilityp∈[0,1] and letτ p be the unique threshold satisfying Pr[w(X 1, X2)> τp] =p. Define the decision function σ∗(x1, x2) = sign(τp −w(x 1, x2)),(B1) which takes value +1 (bunch) whenw < τp and−1 (split) whenw > τ p. This is thew-threshold policy established in Appendix A: split when the splitting benefit exceeds the threshold,...

[40] [40]

The Queueing–Game Correspondence Lemma 4(Waiting time gap).Let(o A, oB)be any local routing strategy with splitting probabilityp, employing load-balanced server assignment. The excess waiting time relative to thew-threshold policy is ∆Wq :=E[W q](oA, oB)−E[W q]∗ = 1 2 E (oA(X1)oB(X2)−σ ∗(X1, X2))w(X 1, X2) .(B3) Proof.From Appendix A 4, under load-balance...

[41] [41]

Players A and B receive service timesX 1, X2 ∼ Exp(µ) independently and produce outputso A(X1), oB(X2)∈ {+1,−1}without communication

Non-Local Game F ormulation We cast the routing problem as a non-local game (Definition 2). Players A and B receive service timesX 1, X2 ∼ Exp(µ) independently and produce outputso A(X1), oB(X2)∈ {+1,−1}without communication. The game payoff is A(oA, oB) =−E[o A(X1)oB(X2)·w(X 1, X2)],(B11) subject to the constraint Pr[o A(X1)oB(X2) =−1] =p. The payoffArew...

[42] [42]

Definition 3(Threshold strategy).A strategyf:R + → {+1,−1}is athreshold strategywith thresholdθ≥0if f(x) = ( +1x < θ, −1x≥θ

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 strategyf:R + → {+1,−1}is athreshold strategywith thresholdθ≥0if f(x) = ( +1x < θ, −1x≥θ. (C1) We writef θ to denote the threshold strat...

[43] [43]

A shared-randomness strategy uses a common random variableκ(independent of the inputsX 1, X2) to select a deterministic local strategy (o A,κ, oB,κ) for each arriving pair

Shared Randomness and the Classical Benchmark We now consider classical strategies augmented with shared randomness. A shared-randomness strategy uses a common random variableκ(independent of the inputsX 1, X2) to select a deterministic local strategy (o A,κ, oB,κ) for each arriving pair. The resulting payoff isE κ[A(oA,κ, oB,κ)], and the splitting constr...

[44] [44]

Overview To construct the Pareto frontier comparison between classical and quantum strategies, we compute three quantities at each splitting probabilityp∈(0,1/2):

[45] [45]

Thew-threshold payoffA ∗(p), achieved by the optimal policy with full access to both service times

[46] [46]

The optimal classical payoffA ∗ cl(p), achieved by the best local threshold strategy; 22

[47] [47]

The quantum payoffA qu(p), achieved by a numerically optimized quantum strategy. The waiting time gap relative to thew-threshold policy is then obtained via the game–queueing correspondence (Proposition 4): ∆Wq = A∗(p)−A(p) 2 ,(D1) whereA(p) is the payoff achieved by either the classical or quantum strategy

[48] [48]

This section provides the explicit parameterization and certified computation procedure

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. a. Explicit Parameterization ForX∼Exp(µ) and threshold strategyf θ, the relevant moments are: D0(θ) :=E[f θ(X)] = Pr[X < θ]−P...

[49] [49]

Chooseϵsmall enough andθ max large enough that the boundary conditions in Proposition 7 are satisfied (verified numerically)

[50] [50]

ComputeA grid on a grid with spacingδ

[51] [51]

Compute the Lipschitz constantLnumerically by evaluating|d ˜A/dθA|on a finer grid

[52] [52]

For demonstrating quantum advantage, it suffices to showA qu(p)> Agrid +Lδ/2

Report the certified upper boundA ∗ cl(p)≤A grid +Lδ/2. For demonstrating quantum advantage, it suffices to showA qu(p)> Agrid +Lδ/2. d. Concavification By Theorem 9, the correct classical benchmark isA ∗ cl,SR(p) = conc(A∗ cl)(p). The concave envelope is computed via the upper hull algorithm inO(n) time for sorted input

[53] [53]

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θ A(x1) andθ B(x2). We are free to choose any Bell state and measurement angle convention; our numerical implementation uses a convention such that the resu...

[54] [54]

We computeA ∗(p) via Monte Carlo estimation:

Threshold Payoff Computation Thew-threshold payoffA ∗(p) corresponds to the optimal policy established in Appendix A: split whenw(X 1, X2)> τp and bunch otherwise, whereτ p is chosen such that Pr[w(X 1, X2)> τp] =p. We computeA ∗(p) via Monte Carlo estimation:

[55] [55]

SampleNindependent pairs (X (i) 1 , X(i) 2 )∼Exp(µ) ⊗2

[56] [56]

Computew (i) =w(X (i) 1 , X(i) 2 ) for each sample

[57] [57]

Determineτ p as the (1−p)-quantile of{w (i)}

[58] [58]

Compute thew-threshold decisionσ ∗(i) = sign(τp −w (i))

[59] [59]

Estimate the payoff asA ∗(p)≈ −1 N PN i=1 σ∗(i)w(i)

[60] [60]

Throughput Model The throughputT(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 A, giving T(p) =ϕ max(1−ρ)· 2α λ(1 +p) + 2α (D36) withϕ max = 1 andα= 0.5

[61] [61]

Numerical Parameters Table I summarizes the numerical parameters used to generate the results in the main text. Parameter V alue Description λ0.8 Customer pair arrival rate µ1.0 Service rate α0.5 Warm-up rate ϕmax 1.0 Steady-state productivity Classical optimization Grid points 500 Number ofθ A grid points θmax 12.0 Maximum threshold considered Quantum op...