Solving Virtual Backbone Problems with Digitized Cyclic Annealing on Near-Term Quantum Computers

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.