CS Paper Radar

Optimal Entanglement Routing in Quantum Repeater Chains: Beyond Fixed Operation Order and Purification Schedule

Aikaterini Mandilara, Antonia Tsili, Dimitris Syvridis, Konstantinos Christodoulopoulos

cs.NI quant-ph ·submitted 2026-09-29 10:25 UTC · v1
theory

Abstract

Entanglement routing establishes entangled pairs between distant nodes of a quantum network by purifying and swapping pairs generated on elementary links. Existing methods typically restrict the decision space along two axes: the operation order, often fixed to purify-then-swap (PtS), and the purification schedule of each link, often restricted to pumping. Focusing on linear repeater chains with finite link capacities, we relax both restrictions and study the maximization of the expected end-to-end throughput subject to a fidelity threshold under two quantum-noise models. We develop a unified capacity-aware optimization framework comprising an exact mixed-integer linear program (MILP) under PtS, instantiated with either pumping or general tree purification schedules, and an exact dynamic program (DP) over arbitrary operation orders. Under symmetric Pauli noise, we prove that pumping converges to a fidelity strictly below unity, imposing a capacity-independent feasibility bound and a maximum chain length on every pumping-based PtS method, whereas general tree schedules yield a capacity-dependent bound. We further prove that post-swap purification never increases the throughput, so a free operation order can only increase feasibility. Numerical evaluations confirm the bounds: tree schedules serve over 90\% of the requests that pumping cannot at moderate fidelity thresholds; within the pumping class, a free operation order recovers much of this advantage; but once links use tree schedules, the tree-based MILP and the order-exact DP serve identical request sets throughout. Operation order and purification schedule are thus substitutes, with the purification schedule the dominant factor governing feasibility under symmetric Pauli noise.

Comment
21 pages, 9 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Utility-Based Path Selection and Configuration in Quantum Networks via Layered Shortest Paths

cs.NI quant-ph ·2026-09-14 ·Leonardo Bacciottini, Subhransu Maji, Don Towsley, Gayane Vardoyan
theory similarity 0.74
Abstract · 13 pages

A path in a quantum network is a chain of repeaters that distributes entanglement between two users. Selecting a path requires balancing the rate and quality (e.g., fidelity) of the delivered entanglement, but these quantities, unlike standard routing metrics, compose non-additively. The problem is compounded by link-level configuration choices (e.g., distillation rounds or emitter brightness tuning), each trading rate against fidelity, so that a path's performance depends jointly on its route and its per-link settings. We cast this joint path selection and configuration problem as a shortest path computation on a layered graph whose layers track discretized end-to-end fidelity. A single run returns the full rate fidelity Pareto frontier, from which the path maximizing any nondecreasing utility function of rate and fidelity can be selected. We prove that for certain utility functions (including the secret key rate of BB84), the method is a fully polynomial time approximation scheme, returning a near-optimal path within a specified tolerance. We further characterize exactly when cheaper scalarization-based routing suffices: it is optimal for utility functions with convex fidelity profiles, but can be arbitrarily suboptimal otherwise (e.g., for step-like, sigmoidal utilities), whereas the layered method remains reliable in all cases.

0.23

Multi-Pair Fidelity-Aware Rate Allocation in a Quantum Network: Approximation Schemes

cs.NI ·2026-08-11 ·Zunzheng Zhang, Xuanli Lin, Zhaofeng Zhang, Nageswara S. V. Rao, Guoliang Xue
theory similarity 0.72
Abstract

Entanglement distribution in quantum networks must jointly account for limited link capacities, probabilistic entanglement swapping, and heterogeneous link fidelities. In this paper, we study multi-pair fidelity-aware rate allocation in quantum networks. We formulate three rate-allocation problems: rate sum, rate sum subject to minimum-rate constraints, and max-min fairness. Prior work has studied a special case of the rate sum problem, where all links have identical fidelity. This special case admits a polynomial-time algorithm. We prove that all three problems are NP-hard. We then study optimization versions of these problems which maximize the minimum end-to-end fidelity subject to throughput or fairness requirements. We present fully polynomial-time approximation schemes (FPTAS) for solving these optimization problems. Experiments on randomly generated networks demonstrate the computational effectiveness of the proposed schemes.

0.04

Distributing Quantum Circuits Using Pre-Distributed Entanglement Pairs over Quantum Networks

cs.ET quant-ph ·2026-10-19 ·Yukun Yang, Ranjani G. Sundaram, Himanshu Gupta
publishedbenchmark similarity 0.66
Abstract · 9 pages, 4 figures. Full author version revised after acceptance; includes the cost-aware entanglement consumption section omitted from the …

Distributing quantum circuits across a network of quantum devices is a recent approach to improve the scalability of quantum computation. Entangled pairs of qubits distributed across network nodes are used as a communication resource for executing inter-node (remote) gates. However, establishing these entanglement pairs incurs significant latency, and doing so during the circuit's execution may lead to the decoherence of logical qubits. Instead, it may be beneficial to distribute certain entanglement pairs before the circuit is executed. Thus, we consider the problem of distributing a quantum circuit across a quantum network containing some pre-distributed entanglement pairs and seek to minimize the execution time of the circuit. We address this problem in three steps. First, given the quantum network and (optionally) a probability distribution over training circuits, we determine a set of pre-distributed entanglement pairs under a specified budget. Second, we compute a qubit-to-memory allocation that minimizes the expected execution time given these pre-distributed resources. Finally, we identify any additional entanglement pairs required during execution, generate them concurrently, and execute the circuit gates. We evaluate our methods on a broad range of benchmark circuits.

0.46

ReFINE: Scheduling of Distillation and Coding for Rate-Fidelity Tradeoff in Quantum Networks

cs.ET quant-ph ·2026-09-17 ·Narges Alavisamani, Matthieu Bloch, Moinuddin Qureshi
similarity 0.65
Abstract

In quantum networks, nodes are connected via sharing of Einstein-Podolsky-Rosen (EPR) pairs, ideally with high fidelity and high rate. However, the fidelity of EPR pairs degrades due to imperfect generation and decoherence errors. Entanglement Distillation is a method that increases the fidelity but operates probabilistically and may destroy all involved EPR pairs upon failure. This failure reduces available EPR pairs for application use, thereby decreasing the service rate. Quantum Error Correction (QEC) is another mechanism to protect EPR pairs against error by forming what we term as Coding-Enhanced Memory (CEM). While effective, CEM requires extra time and resources to form the code, which also reduces the service rate. Existing methods often use static combinations of distillation and CEM, ignoring demand variations. This results in a low service rate without significant fidelity gain. Limited resources together with this rate-fidelity tradeoff make it essential to schedule when to run distillation, form CEM, or serve requests. We propose ReFINE, a demand-aware preemptive scheduler that based on application requirements either serves an available EPR pair immediately or preserves it in CEM. This selective use of CEM, only when needed, enables a better balance for rate-fidelity tradeoff than always using CEM. Between request arrivals, ReFINE either schedules distilling EPR pairs or forming CEM to protect distilled pairs, following one of the three priority policies: ReFINE-D (Distillation-First) first generates EPR pairs for distillation and then forms the CEM, prioritizing service rate. ReFINE-M (Memory-First) first forms the CEM, then generates the EPR pairs for distillation, prioritizing fidelity. ReFINE-C (Concurrent) performs both distillation and CEM formation concurrently, balancing between fidelity and service rate.

0.11

Complexity Barriers to State Preparation in Quantum Approximate Optimization

cs.CC quant-ph ·2026-09-25 ·Stuart Hadfield
theory similarity 0.64
Abstract

For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

0.39

Compiling Together: High-Throughput Distributed Quantum Computing via Multi-Compilation

cs.AR quant-pheess.SY ·2026-10-02 ·Yipei Liu, Sen Zhang, Zebo Yang, Lei Yang
similarity 0.64
Abstract

Quantum computing is a promising paradigm for problems that are challenging for classical machines, but realizing that promise requires far more qubits than a single processor can offer. Distributed quantum computing (DQC) scales out by connecting multiple quantum processing units (QPUs), at the cost of making entanglement the scarce resource: every remote gate consumes a Bell pair, and inter-QPU links generate Bell pairs at finite rates orders of magnitude slower than local gates. Since quantum programs are executed repeatedly, this rate bounds how fast shots complete and thus how fast results are obtained. Existing DQC compilers emit a single implementation per circuit, so throughput is capped by its busiest link while other links stay idle. We observe that alternative compilations of the same circuit are logically equivalent yet stress different links; executing them concurrently and pooling their samples converts idle Bell pairs into additional shots. We formulate the joint selection of compilations and allocation of shots under per-link Bell-pair capacities as Candidate-Constrained Max-Shot Allocation (CMA), prove it NP-hard, and solve it with a dynamic program and its approximate variant AppDP, a compact MILP, and a greedy heuristic Effi. In simulation on six-QPU networks, multi-compilation raises throughput by 2-4.5* over the single compilation and correspondingly improves output fidelity under equal Bell-pair budgets. On hardware, it increases measured fidelity by up to 93% and reaches the single-compilation fidelity in up to 10* less time. Scaling to 36 QPUs and 144-qubit circuits, MILP improves throughput over the single compilation by 76.8% on average across 48 configurations while Effi allocates in milliseconds.

0.16

Complexity Amplification from Compression in Quantum Random Access Optimization

cs.CC quant-ph ·2026-09-07 ·Stuart Hadfield
similarity 0.64
Abstract · Abstract shortened for arxiv submission

Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli $X$, $Y$, and $Z$ observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, with bipartite restrictions in BQP $\cap$ StoqMA. We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.

0.43

Practical wavelength selection for quantum-augmented networks over shared optical fiber

cs.CR quant-phcs.NI ·2026-10-14 ·Nitin Jha, Prateek Paudel, Abhishek Parakh
theory similarity 0.63
Abstract

In a quantum augmented network, sharing optical fiber with classical traffic requires quantum wavelength selection to balance logical fidelity, block acceptance, and classical data reception. Here we develop a wavelength-selection framework for an error-corrected three-stage quantum communication protocol. Under a thermal-background model with independent errors, an ideal one-photon receiver, and ideal recovery, we derive an accepted qubit channel and a key-independent lower bound on logical entanglement fidelity. Combining this bound with block acceptance gives an entanglement-fidelity yield bound, which we maximize over evaluated wavelengths subject to fidelity and classical link-budget requirements. For the Steane [[7,1,3]] code at 5 km per traversal and -10 dBm per classical channel, the largest fidelity certificate occurs near 1537 nm, whereas the largest yield bound occurs near 1551 nm. Along the 1.25 Gb/s classical link budget with 0.2% base error, the optimized yield bound falls below 10^-6 near 10 km per traversal, while fidelity remains certified at 0.99 or higher at longer spans. These results distinguish fidelity and yield constraints and identify certified operating regions for quantum-augmented networks sharing optical fiber.

0.18