Technical Report: Toward Applying Quantum Computing to Network Verification
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915018958700544 |
|---|---|
| author | Dozier, Kahlil Beltran, Justin Berg, Kylie Matousek, Hugo Salamatian, Loqman Katz-Bassett, Ethan Rubenstein, Dan |
| author_facet | Dozier, Kahlil Beltran, Justin Berg, Kylie Matousek, Hugo Salamatian, Loqman Katz-Bassett, Ethan Rubenstein, Dan |
| contents | Network verification (NWV), broadly defined as the verification of properties of distributed protocols used in network systems, 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 within the search space instead of individual instances. However, even these classification mechanisms have their limitations. In this paper, we consider a radically different approach: applying quantum computing to more efficiently solve NWV problems. We provide an overview of how to map variants of NWV problems into unstructured search problems that can be solved via quantum computing with quadratic speedup, making the approach feasible in theory to problems that are double in 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 NWV problems as unstructured search. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_17184 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Technical Report: Toward Applying Quantum Computing to Network Verification Dozier, Kahlil Beltran, Justin Berg, Kylie Matousek, Hugo Salamatian, Loqman Katz-Bassett, Ethan Rubenstein, Dan Quantum Physics Cryptography and Security Networking and Internet Architecture C.2.2 Network verification (NWV), broadly defined as the verification of properties of distributed protocols used in network systems, 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 within the search space instead of individual instances. However, even these classification mechanisms have their limitations. In this paper, we consider a radically different approach: applying quantum computing to more efficiently solve NWV problems. We provide an overview of how to map variants of NWV problems into unstructured search problems that can be solved via quantum computing with quadratic speedup, making the approach feasible in theory to problems that are double in 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 NWV problems as unstructured search. |
| title | Technical Report: Toward Applying Quantum Computing to Network Verification |
| topic | Quantum Physics Cryptography and Security Networking and Internet Architecture C.2.2 |
| url | https://arxiv.org/abs/2410.17184 |