Papers for
quantum network engineers
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Reducing provers simplifies distributed quantum verification tasks
Reducing Provers in Distributed Quantum Verification
Abstract: In the distributed quantum Merlin-Arthur ($\mathsf{dQMA}$) model introduced by Fraigniaud, Le Gall, Nishimura, and Paz (ITCS 2021), a network of quantum computers verifies a global property with the aid of a quantum proof supplied by an untrusted prover. While the nodes are computationally unbounded, the challenge is to limit proof size and the communication required for verification. In this paper, we consider the model of Hasegawa, Kundu, and Nishimura (PODC 2024), where the proof must be unentangled across nodes, and define its extension to $k$ unentangled provers, denoted by $\mathsf{dQMAS}(k)$. In this setting, we investigate the proof size per node and the communication costs of reducing the number of provers. Our first result reduces the number of provers from $k$ to two, doubling the proof size without additional communication. Moreover, with four additional rounds, we can reduce the number of provers from $k$ to one, using at most three times the original local proof size plus a logarithmic term in the number of nodes. Finally, we establish amplification for perfectly complete protocols. In this regime, a single prover suffices with a constant-factor overhead in our reductions, yielding $\mathsf{dQMAS} = \mathsf{dQMAS}(k)$.
Quantum phenomena shape network functions beyond message transport
Beyond Quantum Messages: Toward Quantum-Native Network Functioning
Abstract: The Quantum Internet is commonly envisioned as a network that transports quantum states and distributes entanglement as the key resource underpinning distributed quantum applications. This view is necessary but incomplete if quantum phenomena are confined to what the network carries or manages, while network functionalities remain grounded predominantly in classical abstractions. This Perspective advances a broader thesis: quantum phenomena can also participate directly in the realization of network functionalities. We first establish the architectural baseline by introducing entanglement as a stateful network resource whose operational condition is non-locally distributed across remote nodes, evolves through manipulation or consumption, and degrades over time through decoherence. Its evolving state must therefore remain visible to the functionalities acting on it. We then move beyond resource visibility and use two mechanisms as proof points of a broader quantum-native functional design space: entanglement generation during propagation through coherent spatial-path superposition, and operational connectivity induced by shared entanglement that can depart from the physical graph. These examples show that paths, neighbors, or participating nodes may become operationally relevant in ways determined by quantum coherence and shared entanglement, rather than by physical connectivity alone. We identify Quantum Addressing as a transversal abstraction capable of representing such relations while complementing, rather than replacing, classical addressing and signaling. The resulting perspective broadens the Quantum Internet from transporting quantum information and distributing entanglement to exploiting quantum phenomena in network functioning, opening a coupled frontier spanning routing, forwarding, control, and functionality placement.
Efficiently finding structured subgraphs in labeled tour graphs
Finding full immersions is fixed-parameter tractable in labeled tour graphs
Abstract: We give an $O_H(n^5)$-time algorithm to test whether an $n$-vertex labeled tour graph has a full immersion isomorphic to a labeled tour graph $H$. A labeled tour graph is a connected $4$-regular graph whose edges are labeled by binary vectors of fixed length. To obtain a full immersion, a vertex may be removed only by pairing up its four incident edges and "splitting off" both pairs, summing the labels within each pair. Even for one-bit labels, no polynomial-time algorithm was previously known for arbitrary fixed $H$. Our main tool is of independent interest: we give an algorithmic min-max theorem that, in particular, characterizes the maximum number of odd-length circuits in a rooted circuit decomposition of an Eulerian graph. Our results have implications for vertex-minors, whose study is motivated by applications in quantum networking, connections with graph minor theory, and the goal of developing an irrelevant vertex technique for dense graphs. For vertex-minors, circle graphs play the same role as planar graphs do for graph minors. As a corollary of our main theorem, we obtain a fixed-parameter tractable algorithm for apex-vertex-minor testing in $k$-apex circle graphs. We also prove an irrelevant vertex theorem for such graphs of large rank-width. More broadly, our results are essential to forthcoming work of three of the authors proving a structure theorem for graphs with a forbidden vertex-minor. There, our min-max theorem plays the role of both the algorithmic $A$-paths and Two Paths Theorems.
Quantum communication enhanced by spatial path superposition technique
Spatial Path Superposition: A No-Cloning Perspective on MIMO-Inspired Spatial Diversity
Abstract: Spatial diversity is a key mechanism in classical Multi-Input Multi-Output (MIMO) communications, where multiple propagation alternatives provide redundant observations that improve reliability in noisy environments. A direct translation of this principle to quantum communications is forbidden by the no-cloning theorem, since an unknown quantum state cannot be copied and transmitted through independent links. In this Perspective article, we argue that spatial path superposition provides a no-cloning-compatible analogue of the spatial-diversity principle of MIMO. Rather than duplicating the transmitted quantum state, a quantum carrier is coherently delocalized over multiple communication links, so that alternative spatial evolutions are experienced in quantum superposition. In this framework, classical redundancy is replaced by spatial coherence, and the communication link itself becomes part of the quantum dynamics. Indeed, spatial coherence can enhance the fidelity of the received quantum state, providing the quantum counterpart of the classical diversity gain, and can be converted into bipartite and multipartite entanglement during propagation. This implies that, under suitable coherent path control, noisy channel evolutions can contribute constructively to entanglement generation. This Perspective identifies spatial path superposition as a quantum-native primitive for the Quantum Internet, linking no-cloning-compatible spatial diversity, fidelity enhancement, entanglement generation, and coherent path control.
Quantum base stations dynamically share entanglement for sensing and communication
Entanglement Allocation for Quantum Integrated Sensing and Communication
Abstract: Jointly supporting communication and distributed sensing over a shared, limited pool of entanglement resources is an attractive prospect for future quantum networks. We develop a network-level quantum integrated sensing and communication (Q-ISAC) framework in which a quantum base station dynamically allocates elementary Bell pairs between communication users and distributed sensing. Sensing resources are adaptively partitioned among multiple GHZ probes with dynamically selected sizes and sensing-node assignments. We derive an effective quantum Fisher information model accounting for probabilistic fusion, transmission loss, and memory decoherence, and formulate a finite-horizon allocation problem subject to communication QoS, expected sensing-information, sensing-reliability, and hardware constraints. A hierarchical constrained proximal policy optimization (HC-PPO) framework combines learned discrete sensing allocation with analytical continuous communication allocation. Numerical results show that GHZ probing requires approximately $27$--30% fewer sensing qubits than separable probing under modest probe-size caps and 65-67% fewer at the highest considered target under the same sensing requirements. Adaptive multi-GHZ partitioning provides greater robustness than single-GHZ sensing, while adaptive communication--sensing sharing outperforms the evaluated fixed splits. The proposed HC-PPO framework satisfies the joint requirements in at least 99.9% of test instances across the considered sensing targets and fusion probabilities. Monte Carlo evaluation separately shows that realized terminal information reached its target in 96-98% of realizations, distinguishing expected-information satisfaction from realized sensing performance.
Quantum method improves private data retrieval on forest graphs
Quantum Private Information Retrieval on Forests
Abstract: We consider the problem of graph private information retrieval (PIR) in the quantum setting. We focus on a specific type of graphs, namely the forest graphs. A forest graph is a union of disjoint trees. We consider the quantum setting where all the servers share an entangled state. Each server is allowed to send only one qudit per retrieval round. We design a scheme for the forest graphs that achieves the rate of $\frac{3}{N}$. The scheme uses a GHZ state as the initial entangled state between the servers prior to the scheme initiation. We compare our scheme with the only work done in the literature that considered the quantum setting of graph PIR. We show that our scheme is more efficient in this setting. We derive the quantum capacity for the case of $G=3K_2$, which is equal to $4/6$. $G=3K_2$ is a special case of the forest graph. We design a scheme that is specialized for this graph, achieving a rate equal to $4/6$ and provide the corresponding matching upper bound, establishing it as the capacity.
Entanglement does not boost classical communication in many quantum channels
Classical communication over quantum channels: does entanglement help in nature?
Abstract: Can entangling codewords across independent uses of a quantum channel improve the rate of classical communication? An old conjecture states that there is no such entanglement advantage for all channels. Although Hastings's result and follow-up works disproved this conjecture, it turns out that enormous dimension is required to construct a channel where entanglement enhances classical communication. This indicates that there might be no entanglement advantage for many physical channels, or for all low dimensional channels. Motivated by recent progress on (generalized) amplitude damping channels, we propose a general Schur-weighted block entropy inequality, and show that there is no entanglement advantage for all phase-covariant channels including multi-level amplitude damping channels, generalized dephasing channels, and damping-dephasing channels. As a by-product, we also recover the recently established result that there is no entanglement advantage for all qubit channels.
Quantum communication improves error rates with new decoding method
Quantum communication: a discrimination approach
Abstract: We develop a state discrimination approach to unassisted quantum communication through a noisy quantum channel. Starting from the operational duality between entanglement recovery and state discrimination, we construct entanglement-generation codes with explicit decoders constructed from Petz recovery maps. The resulting error bounds hold for every number of channel uses and are expressed in terms of Petz-Rényi coherent information. For product sources, they yield exponential error decay at rates below coherent information.
Quantum switch protocol minimizes memory for entanglement distribution
Entanglement Distribution in Quantum Switch Networks: Memory Limits and Achievability
Abstract: We study the minimum persistent memory required to distribute a graph state through a quantum switch. Specifically, consider a central switch that assists $n$ remote users in distributing a graph state, using independently generated user-switch Bell pairs. Since Bell-pair generation is probabilistic, different links generally succeed at different times. When a Bell-pair is generated, the qubits may need to be stored in memory while waiting for other links to succeed. Recently, new protocols have been proposed to reduce this storage overhead by processing and releasing some switch qubits before all Bell links are available. However, these protocols do not characterize the minimum persistent switch memory required at each stage. Moreover, the local-cover method in the state-of-the-art Piecemaker protocol is computationally expensive for general target graphs. In this work, we characterize the minimum persistent switch memory required after any subset of users' Bell links are generated and processed. We then develop an online stabilizer-transition protocol that attains this limit, which can be implemented in polynomial time in the number of qubits $n$. Remarkably, this optimal protocol can provide substantial memory reductions over existing heuristic approaches. In particular, for the path graph $P_n$ over $n$ users, Piecemaker protocol requires at least $\lfloor n/2\rfloor$ qubits of peak persistent memory for \textit{every Bell-links generation order}, whereas under the order $(1,2,\ldots,n)$, our protocol requires only one persistent switch qubit. Finally, the same stabilizer-transition framework also provides a direct forward construction for sequential graph-state generation using the minimum number of quantum emitters, equal to the maximum of the height function.
Quantum method improves decoding multiple senders messages jointly
Quantum simultaneous decoding via pretty-good measurements of tilted states
Abstract: A multiple-access channel transmits messages from several senders to one receiver. For quantum outputs, the receiver must distinguish states depending on all messages, while tests for different decoding errors may not commute. In this paper, we give a self-contained account of simultaneous decoding, in which one joint measurement recovers the messages at the established achievable rates using independent codebooks. The proof combines Sen's tilted-subspace method with Cheng's analysis of the pretty-good measurement, a standard measurement for distinguishing quantum states. Auxiliary labels close to a common reference state separate the geometric directions associated with different errors. A Gram-matrix bound then allows separately chosen binary tests to certify the performance of one measurement. The labels are removed from the completed decoder, leading to a deterministic packing theorem that applies to finite state ensembles, including unequal priors. We develop the two-sender case first, with worked examples and figures, before treating any fixed number of senders. Sharper finite-error guarantees for the same decoder are developed separately, with sharp bounds for two specified steps of the analysis rather than a claim of globally optimal decoding. Applications recover known achievable rates for unassisted and entanglement-assisted classical communication, distributed classical compression with quantum side information, and coherent-state communication through a beamsplitter or passive multiport device. The common proof makes the geometric mechanism and its quantitative consequences available without repeating the construction for each application.
Quantum handshake verifies real quantum devices on networks
Secure Quantum Handshakes: Quantum Network Verification Via Simon's Algorithm
Abstract: Quantum networking represents the future of secure communication, enabling fundamentally new capabilities through quantum information exchange. However, these networks require secure, high-fidelity quantum communication channels, and they require every participating node to be a genuine quantum device. Currently, there is no reliable method to verify whether clients entering a quantum network truly possess quantum computational capability and are connecting over robust channels. In this work, we introduce a client-validation protocol that functions as a proof-of-quantum-capability handshake. Our protocol secures a quantum network against classical spoofers, noisy quantum computers, and genuine quantum devices connecting with the network over noisy or insecure channels. We validate the efficacy of this protocol through numerical simulations under erasure, dephasing, and depolarizing noise models.
Pauli error composition controls key rate in multiparty quantum networks
Pauli Error Composition Determines the Multipartite Advantage in Conference Key Agreement
Abstract: GHZ-based conference key agreement distributes a shared key to $N$ parties in one network use, whereas pairwise BB84 needs $N-1$. The survival of that advantage has been studied against party number, loss, and topology, but almost always with the channel fixed at depolarizing. Simulating both protocols exactly for $N = 3, 4, 5$ under dephasing, amplitude damping, and depolarizing noise, we find the crossover is set by the channel's Pauli error composition, not its identity: normalized to average infidelity, amplitude damping and depolarizing agree to within about 1\% at each group size, while dephasing can tolerate roughly $2.4\times$ more at $N = 3$. We derive a closed-form rate for arbitrary per-party Pauli noise and use it to prove that concentrating a fixed noise budget on one arm is strictly worse than spreading it, and that giving the dealer role to the cleanest arm improves the rate by roughly 18\%. One structural fact drives every result: the phase-error term is a product over all $N$ arms, while the bit-error term stays local to a pair.
Quantum network routing method detects cheating with minimal calls
A Cheat-Sensitive Primitive for Destination-Private Quantum Routing
Abstract: Quantum networks will rely on intermediate nodes to distribute entanglement, but the same nodes may learn which users are being connected. We introduce a minimal two-call routing primitive in which a user, Alice, establishes an entangled link with one of several clients while testing whether the provider, Bob, has disturbed a coherently encoded request. The construction adapts the hidden-order mechanism of quantum private queries: one call contains a direct request, the other a coherent superposition of the desired and null addresses, and Alice keeps their order secret. A private matching qubit held by the selected client restores the coherent test state after a favorable Bell-measurement outcome, so that Alice can test the returned query without any further operation by Bob. The claim is deliberately limited. The protocol shows that a routing request can carry a physical cheating test, and it detects an explicit destination-reading attack with nonzero probability. It does not yet provide a quantitative information-disturbance tradeoff, composable security, or certification of an unmeasured output against arbitrary attacks. We also characterize the exact perfect-pass limit, in which Bob's residual state, averaged over the private matching states, is independent of the destination.
Quantum routers eliminate signal loss for perfect state transfers
Quantum State Routing and Perfect State Transfer on Signed Graphs under Environmental Noise
Abstract: Routing unknown quantum information across distributed communication networks requires autonomous, measurement-free mechanisms to prevent wave-function collapse. Szegedy quantum walks provide a mechanism for spatial state transport. The conventional walks on unweighted graphs suffer from severe back-reflection, spatial dispersion, and channel crosstalk. In this paper, we introduce a deterministic topological quantum routing architecture based on coined Szegedy quantum walks on edge-duplicated signed graphs. By treating edge signs as localized phase shifts within a balanced coin reflection, we enforce an exact zero back-scattering condition across routing nodes. We demonstrate deterministic Perfect State Transfer (PST) with unit fidelity at exact arrival times across fundamental archetypes, including the signed dumbbell switch $D_{2m,0,2n}$ and scalable glued binary trees. Furthermore, we analyse routing performance under realistic open-system amplitude and phase damping noise channels.
Quantum position verification secured against large entanglement attacks
Breaking the Bounded Entanglement Barrier for Quantum Position Verification
Abstract: Position verification, introduced by Chandran et al. (SIAM J. Computing 2014), allows verifiers to test a prover's claimed position by an interactive protocol. Classical position verification is impossible. Even for Quantum Position Verification (QPV), there always exists an LOCC (Local Operations and Classical Communication) attack if the adversary can hold an exponentially large amount of preshared entanglement. Somewhat surprisingly, we show that we can circumvent this barrier in the idealized continuous-time model, where time is represented by a real-valued parameter and challenge messages can be sent at a time sampled uniformly from a real interval. In this model, we give a BB84-based protocol that remains secure against any finite coalition of LOCC adversaries with arbitrary finite (possibly exponential) quantum storage and entanglement. Our construction can also be instantiated in the discrete-time model. Even though the previous impossibility results apply, we are able to obtain an information-theoretic QPV protocol in which the honest parties' total resources (communication and storage) can be significantly smaller than the adversarial resource bound. In fact, we can achieve any desired polynomial gap between honest parties and adversarial resources. To our knowledge, all previous protocols in the literature required resources of the honest parties to be at least as large as the adversarial entanglement. Interestingly, the resource gap between the honest and adversarial party resources in our protocol depends on how precisely time can be measured. As the precision of the best-known clock improves with further research, the resource gap in our protocol keeps increasing. In particular, the adversarial resource bound keeps increasing while the honest parties' resources remain largely the same. We call this the "I sleep, you work" paradigm.
Quantum networks improve data quality by routing with priority delays
Priority-Aware Routing for Quantum Networks:Integrating Coherence-Time Constraints into Scheduling
Abstract: Quantum networks face a fundamental challenge absent in classical networks; finite memory coherence times mean that queuing delay directly degrades information quality, causing decoherence that has no classical analog. Existing routing protocols optimize for hop count or channel fidelity while treating scheduling delays as a secondary concern, leaving fidelity vulnerable to congestion-induced decoherence. We present a coherence-aware routing protocol that integrates decoherence constraints into path selection via a priority-modulated aging model derived analytically from Weighted Fair Queueing theory, where high-priority traffic receives compressed effective queue delay. We build a custom discrete-event simulator verified against NetSquid (across 104 states), and evaluate across two structurally diverse topology classes under identical physical parameters, isolating topology structure as the sole independent variable. In all experiments, our protocol is benchmarked against loss-only Dijkstra routing and FIFO scheduling as baselines. On topologies, P2 traffic achieves 96.08% fidelity under a 9x load increase with only 0.04 percentage point degradation, versus a 13.51 percentage point collapse for the loss-only baseline; P2 tail latency holds stable at 0.055 ms while Dijkstra degrades 5.5x. On Barabasi-Albert scale-free topologies, our protocol delivers a +4.12 percentage point fidelity advantage with 97.8% higher aggregate throughput at operational loads over the baseline, with a clearly characterized hub-saturation boundary at 160k QPS. FIFO scheduling provides negligible priority differentiation on both topology classes, providing strong evidence that coherence-aware routing-not scheduling alone is responsible for the observed QoS gains.
Quantum entanglement routing improves fidelity and throughput in repeater chains
Optimal Entanglement Routing in Quantum Repeater Chains: Beyond Fixed Operation Order and Purification Schedule
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.
Quantum networks enable information-free proof verification among many parties
Zero Knowledge Proofs in Quantum Networks
Abstract: Zero-knowledge proofs (ZKPs) enable the verification of a statement without revealing any information beyond its validity and constitute a fundamental primitive in cryptography and information theory. However, existing constructions rely on computational assumptions and are predominantly confined to bipartite settings, leaving their information-theoretic realization in bipartite or network scenarios largely unexplored. Here we develop a framework for zero-knowledge verification based on the indistinguishability of quantum states under operational constraints. Exploiting the fundamental limitations imposed by local operations, we show that a verifier is inherently restricted from extracting information about the underlying state while retaining the ability to verify correctness. We construct explicit protocols for multiparty quantum networks that achieve information-theoretic security, ensuring that no subset of collaborating parties can gain knowledge beyond the validity of the statement, independent of their joint computational power.
Quantum algorithm colors cycle graphs in constant time
Quantum Advantage for Distributed Symmetry Breaking
Abstract: We present a distributed quantum algorithm that $3$-colors cycles in $O(1)$ rounds, with high probability. It follows that all locally checkable labeling problems (LCLs) that have round complexity $O(\log^* n)$ in the classical LOCAL model can be solved in $O(1)$ rounds in the quantum-LOCAL model, with high probability; this includes problems such as maximal independent set and maximal matching in bounded-degree graphs. This presents the first natural examples of graph problems with an asymptotic distributed quantum advantage for the LOCAL model; all prior examples that separate LOCAL and quantum-LOCAL are artificial problems constructed merely for the sake of demonstrating quantum advantage.
Quantum Markov blankets improve efficiency and security in quantum networks
QCMI-Based Quantum Markov Blanket Discovery for Semantic Quantum Networks
Abstract: Quantum-enabled semantic communication networks (QESCs) leverage quantum technologies to transmit data meaning efficiently, yet face challenges from costly resources and noise. This letter introduces Quantum Markov Blankets (QMBs) to QESCs, a novel framework to isolate essential quantum information for semantic transmission. We prove QMBs' validity using quantum conditional mutual information, showing that they shield semantic content from irrelevant subsystems. An implementation strategy optimises QMB detection, reducing resource use. Simulations suggest that QMB-based QESCs cut qubit consumption by 50\%-75\% while enhancing fidelity compared with non-optimised quantum semantic schemes. Unlike classical approaches, QMBs offer inherent security by limiting an eavesdropper's access to classical data outside the blanket. We outline future directions, including real-time QMB adaptation. This work bridges quantum information theory and semantic communication, advancing resource-efficient and secure quantum networks.
Holevo barycenter does not multiply under combined quantum channels
Non-Multiplicativity of the Holevo Barycenter of Quantum Channels
Abstract: The Holevo barycenter of a quantum channel is the unique output state obtained as the average output of any ensemble achieving the Holevo capacity. Given two quantum channels, the multiplicativity problem asks whether this barycenter tensorizes under parallel composition, namely whether the barycenter of the product channel coincides with the tensor product of the individual barycenters. This question is closely related to the additivity problem for the Holevo capacity: additivity implies tensorization of the Holevo barycenter, while tensorization alone is not sufficient for additivity. Although a construction is known that demonstrates the existence of channels with non-additive Holevo capacity, their corresponding Holevo barycenters still tensorize, leaving open whether multiplicativity might ultimately hold universally. Here, we answer this question in the negative by exhibiting channels for which the Holevo barycenter is not multiplicative under the tensor product of the channel with itself. Moreover, we show that the entropy of the Holevo barycenter is neither universally subadditive nor universally superadditive under tensor product.
Quantum channel capacity strictly limits reliable information transfer
No information transmission through quantum channels above capacity
Abstract: We show that the capacity of a quantum channel demarcates a phase transition: while reliable transmission below capacity is always possible, any attempt to transmit information above it fails catastrophically. Specifically, we prove exponential strong converse theorems for unassisted quantum and classical communication over arbitrary finite-dimensional memoryless quantum channels. At rates beyond the respective capacity, the entanglement-generation fidelity and the success probability for classical communication decay exponentially with the number of channel uses. This rules out transmission above capacity even when one tolerates arbitrarily large errors. Our proof follows the classical Arimoto strategy, augmented by a crucial new ingredient: integral representations of Rényi information measures that lead to asymptotic continuity bounds for Rényi capacities.