Jul 2026· International Conference on Computer Communications and Networks· pp. 1-6· 0 citations· 22 references
Abstract
Wireless multi-hop networks rely on a subset of nodes to relay traffic, broadcast control messages, and maintain global connectivity without requiring every device to forward packets. A virtual backbone formalizes this idea by selecting a sparse set of representative nodes that can cover the network and serve as a routing substrate. In graph terms, given a general communication graph G = (V,E), the backbone is often modeled as a connected dominating set (CDS): a subset S ⊆ V such that every node in V \S has a neighbor in S, and the subgraph induced by S is connected. CDS-based backbones reduce routing overhead but are NP-hard to compute and must balance sparsity, coverage, and connectivity. Here we introduce a quantum approach to solving the CDS problem based on the cyclic quantum annealing algorithm, suitable for current digital quantum computers, which we call Digitized Cyclic Annealing. We explore the dependence of the obtained solutions on the algorithm hyperparameters and show how transfer learning allows us to find their values for large-scale problems. We demonstrate the complete algorithm on a network optimization problem using N = 73 qubits on an IBM Kingston quantum processor.
A new proof that the multiple-unicast conjecture holds for networks with at most six coding nodes, without computer-aided search, is given, and it is shown that if the conjecture holds on $\Gamma_{3,3}$, then it holds whenever no three sessions have six distinct terminal locations.
Sirui Liu, Linfeng Que, Zongpeng Li et al.· 0 citations
Entanglement-based networks provide a scalable framework for multiuser quantum communication by passively routing spectrally correlated photon pairs across interconnected nodes. Several wavelength-allocation schemes have been demonstrated experimentally, but these designs do not yet give a general way to determine how spectral use, receiver load, repeated connections, and fan-out constrain one another. We address this problem through the network's connectivity graph, where the wavelength assignment becomes a resource-optimization problem. For one-sided fan-out, assigning each link to a center and grouping links with the same center gives an exact optimization for arbitrary networks and fan-out limits. We solve this for complete networks and for complete networks in which every user has one excluded partner. Allowing both conjugate wavelengths to fan out changes the resource landscape: a balanced binary hierarchy attains the minimum spectral-layer count for a complete network while reducing the maximum receiver load to logarithmic in the number of users. An eight-user complete network then makes explicit the competing roles of spectral efficiency, receiver load, redundancy, and fan-out. We include the passive-splitter loss and the dependence of the key rate on the delivered pair flux to determine the minimum total pair-generation rate required to meet the prescribed targets. Finally, we formulate the corresponding BBM92 quantum key distribution (QKD) secret-key-rate analysis for a continuous-wave-pumped broadband source, with true and accidental coincidences evaluated between detector channels at the two endpoint users and relative layer pair-generation rates fixed by the source spectrum. This framework, therefore, provides a direct route from exact network resource laws to the design and comparison of passive entanglement architectures under experimentally specified hardware constraints.
Ekta Panwar, Gilberto Borges, Saeide Salari et al.· 0 citations
Broadcasting in graphs refers to the information dissemination problem in which a source node has an atomic piece of information to be distributed to all the nodes of a graph. In the standard telephone model, broadcasting proceeds as a sequence of synchronous rounds, where, at each round, every informed node can transfer the information to at most one of its neighbors. The broadcast time of a graph $G$ is the maximum, taken over every node $v\in V(G)$, of the minimum number of rounds required for broadcasting from $v$ in $G$. We study the network design problem that, for every $\epsilon>0$, asks for the minimum number of edges of $n$-node graphs with broadcast time close to optimal, i.e., at most $(1+\epsilon)\log_2n$. Let $\phi=(1+\sqrt{5})/2$ be the golden ratio, and let $\alpha=1/\log_2\phi-1\simeq 0.44$. We show that, for every $n\geq 1$, and for every $\epsilon\in(0,\alpha)$, it suffices to add $O(n^{1-\epsilon/\alpha})$ edges to a well chosen $n$-node tree for designing an $n$-node graph with broadcast time $(1+\epsilon)\log_2n$. This asymptotic bound on the additional number of edges improves the previsouly known bound $O(n^{1-\epsilon})$, and has implications to the design of graphs with minimum broadcast cost, defined as number of edges times broadcast time. Moreover, we show that, for infinitely many values of $n$, $\Omega(n)$ edges must be added to some tree for designing an $n$-node graph with broadcast time $\lceil\log_2 n\rceil+1$. Therefore, our bound $O(n^{1-\epsilon/\alpha})$ on the additional number of edges for $0<\epsilon<\alpha$ is asymptotically tight at the two extremities of the interval $(0,\alpha]$, as it is $O(n)$ when $\epsilon\to 0$, and $O(1)$ when $\epsilon=\alpha$. Finally, we show that, for every $n$, there exists an $n$-node graph with broadcast time $\lceil\log_2 n\rceil+1$ and at most $2n-4\lceil\log_2n\rceil+O(1)$ edges.
Pierre Fraigniaud, Hovhannes A. Harutyunyan· 0 citations
We introduce a constraint-preserving hybrid quantum-classical greedy framework for the minimum vertex cover problem, which extends directly to maximum independent set by bitwise complementation. The framework uses projected Pauli-X terms whose sum preserves the feasible subspace and acts within it exactly as the adjacency matrix of a layered graph of feasible covers. This graph is connected, so every feasible cover is linked to the configuration containing all vertices by a sequence of allowed single-vertex flips. Starting from this configuration, the corresponding continuous-time quantum walk propagates amplitude into layers containing progressively smaller covers. We rank vertices using either their marginal cover probabilities or the expected cover size obtained after fixing each candidate vertex in the cover, and use these rankings to guide recursive greedy reductions. Across several random-graph families, with walk times fixed using independent calibration ensembles, the quantum-informed algorithms achieve lower mean approximation ratios and solve a larger fraction of instances optimally than their corresponding classical greedy baselines. The conditioned-energy strategy performs best on the tested instances and retains algorithmic performance close to the exact continuous-time limit under low-depth Trotterisation. For bounded-degree graphs, each Trotter layer has circuit depth independent of system size, and the framework requires neither penalty terms nor variational training.
R. P. Bassa, F. A. Quinton, Franz G. Fuchs et al.· 0 citations
As practical quantum networks approach large-scale deployment, the need for efficient user-to-user frequency allocation is increasing, yet current approaches only provide partial solutions to the routing and spectrum allocation problem for an arbitrary quantum network. We address this challenge for repeater-less flex-grid quantum networks based on hyperentangled photons using an efficient three-stage pipeline combining leading tools in classical networking with recent advances in numerical optimization. First, double instantiations of Yen's algorithm obtain low-loss route candidates between each pair of users and the entanglement sources. Second, the advanced process optimizer (APOPT) obtains frequency channel allocations that maximize distribution rates under fidelity constraints. Finally, the constraint programming solver using satisfiability methods (CP-SAT) assigns specific frequency bins to each link, ensuring that there is no contention between frequencies from different sources. We numerically demonstrate this approach on a representative ring network and a Manhattan incumbent local exchange carrier topology, realizing significant improvements over prior genetic algorithm approaches in speed, accuracy, and scalability. Overall, this pipeline provides an efficient heuristic workflow for optimizing broadband entanglement distribution, applicable to arbitrarily connected quantum networks integrated within the existing lightwave infrastructure.
Zachary Goisman, M. L. Stevens, Maxwell Goisman et al.· 0 citations
It is proved that any optimal backbone configuration must correspond to a capacity-maximizing Voronoi tessellation of the network region, and this can be efficiently approximated by a centroidal Voronoi tessellation via Lloyd's algorithm, with backbone nodes connected according to a Delaunay triangulation.
A. Fletcher, Ignazio Pedone, S. Pirandola· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
