arXiv:2410.17184 · ACM Workshop on Hot Topics in Networks (HotNets)

Toward Applying Quantum Computing to Network Verification

Kahlil Dozier, Justin Beltran, K. Jordan Berg, Hugo Matousek, Loqman Salamatian, Ethan Katz-Bassett, Dan Rubenstein

Published Nov 11, 2024• 1 citation

Abstract

Network verification, broadly defined as proving the correctness of certain properties resulting from a network's configuration, cannot be efficiently solved on classical hardware via brute force. Prior work has developed a variety of methods that scale by observing a structure in the search space and then evaluating classes induced by that structure. However, even these classification mechanisms have their limitations. In this paper, we consider a radically different approach: applying quantum computing to more efficiently solve network verification problems. We provide an overview of how to map variants of verification problems into unstructured search problems that can be solved via quantum computing with quadratic speedup, making the approach feasible in theory to problems that twice as big in the size of the input. Emerging quantum systems cannot yet tackle problems of practical interest, but rapid advances in hardware and algorithm development make now a great time to start thinking about their application. With this in mind, we explore the limits of scale of the problem for which quantum computing can solve network verification problems as unstructured search.

DOI: 10.1145/3696348.3696891

Related papers

Applications and verification of quantum computers

Shih-Han Hung

Quantum computing devices can solve problems that are infeasible for classical computers. While rigorously proving speedups over existing classical algorithms demonstrates the usefulness of quantum computers, analyzing the limits on efficient processes for computational tasks allows us to better understand the power of quantum computation. Indeed, hard problems for quantum computers also enable useful cryptographic applications. In this dissertation, we aim to understand the limits on efficient quantum computation and base applications on hard problems for quantum computers. We consider models in which a classical machine can leverage the power of a quantum device, which may be affected by noise or behave adversarially. We present protocols and tools for detecting errors in a quantum machine and estimate how serious the deviation is. We construct a non-interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In the setting of error-prone quantum hardware, we employ formal methods to construct a logical system for reasoning about the robustness of a quantum algorithm design. We also study the limits of ideal quantum computers for computational tasks and give asymptotically optimal algorithms. In particular, we give quantum algorithms which provide speedups for the polynomial interpolation problem and show their optimality. Finally, we study the performance of quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. In particular, we show that for various linear algebra problems, there is no quantum speedup, while for some problems, exponential speedups can be achieved.

Jan 1, 20210 citations

A Hybrid Classical/Quantum Algorithm to Estimate Network Violation Probabilities

Kahlil Dozier, Justin Beltran, Hugo Matousek +1 more

The emergence of Quantum Computing has resulted in a slate of quantum algorithms that can solve a wide variety of algorithmic and computational problems faster than any classical computer. How we can apply these various quantum algorithms to practical problems in computing is still an ongoing area of research. In this work, we present a ''hybrid classical/quantum'' algorithm that uses quantum counting to solve a network verification problem involving the estimation of probabilities. We present a detailed cost analysis of our algorithm, showing that under certain assumptions it outperforms standard verification methods.

ACM SIGMETRICS Performance Evaluation ReviewSep 22, 20260 citations

Quantum Algorithmic Frameworks for Graph-Based Optimization and Network Analysis in Large-Scale Computational Systems

Beyza Altan

The increasing scale and interconnectedness of modern computational systems have intensified the demand for efficient algorithms capable of analyzing complex networks and solving graph-based optimization problems. Classical optimization techniques, while effective for moderate-sized datasets, often encounter exponential computational growth when applied to large-scale graph structures characterized by high dimensionality and dynamic topology. This paper explores quantum algorithmic frameworks for graph-based optimization and network analysis in large-scale computational systems, emphasizing the potential of quantum computing paradigms to address combinatorial complexity and enhance computational scalability. By synthesizing developments in quantum search algorithms, variational quantum circuits, and hybrid quantum–classical optimization methods, the study evaluates their applicability to tasks such as shortest-path discovery, clustering, community detection, and network resilience assessment. The findings suggest that quantum-enabled frameworks may provide complementary advantages in exploring vast solution spaces and improving optimization efficiency, particularly when integrated with classical preprocessing and orchestration strategies.

Next generation.Feb 20, 20260 citations

Quantum computation: Efficient network partitioning for large scale critical infrastructures

Saikat Ray Majumder, Annarita Giani, Shen, Weiwei +3 more

Quantum computers are emerging as a viable alternative to tackle certain computational problems that are challenging for classical computers. With the rapid development of quantum hardware such as those based on trapped ions, there is practical motivation for identifying risk management problems that are efficiently solvable with these systems. Here we focus on network partitioning as a means for analyzing risk in critical infrastructures and present a quantum approach for its implementation. It is based on the potential speedup quantum computers can provide in the identification of eigenvalues and eigenvectors of sparse graph Laplacians, a procedure which is constrained by time and memory on classical computers.

arXiv:2302.02074Feb 4, 20231 citation

Verification of Quantum Computation: An Overview of Existing Approaches

Alexandru Gheorghiu, Theodoros Kapourniotis, Elham Kashefi

Quantum computers promise to efficiently solve not only problems believed to be intractable for classical computers, but also problems for which verifying the solution is also considered intractable. This raises the question of how one can check whether quantum computers are indeed producing correct results. This task, known as quantum verification , has been highlighted as a significant challenge on the road to scalable quantum computing technology. We review the most significant approaches to quantum verification and compare them in terms of structure, complexity and required resources. We also comment on the use of cryptographic techniques which, for many of the presented protocols, has proven extremely useful in performing verification. Finally, we discuss issues related to fault tolerance, experimental implementations and the outlook for future protocols.

arXiv:1709.06984Theory of Computing SystemsJul 6, 2018175 citations

Risk Analysis of Information Security Violations and Vulnerabilities in Information Processing Systems: Grover's Algorithm

Mikhail Pavlov

Abstract In computer science, the Church–Turing thesis has long defined the conceptual boundary of classical computation, asserting that any effectively computable function can be executed by a universal Turing machine. While quantum computing does not invalidate this thesis in terms of computability, it challenges classical assumptions regarding computational efficiency and complexity. With the emergence of quantum computation, the circuit model — built upon logical primitives such as NOT and AND in classical systems — finds its quantum counterpart in reversible and unitary gate structures. Within this framework, Grover’s algorithm represents a fundamental advancement: a quantum algorithm capable of solving unstructured search problems with quadratic speedup compared to classical approaches. This work analyzes the implications of Grover’s algorithm for information security risk assessment, particularly in the context of brute-force attacks and search-based cryptanalysis.

Mar 3, 20260 citations