Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2410.17184 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |