2024-07-17

# Quantum algorithms for vertex sparsification

## Publication

### Publication

The goal of graph sparsification is to compress large graphs into smaller ones. In vertex sparsification we are given a graph and a set of terminals. We aim to find a graph with the terminals as vertices, that preserves some property of interest. For vertex- flow sparsification we aim to preserve flows. Moitra proved that vertex-flow sparsifiers exist with quality O( log k/ log log k) , where k is the number of terminals. There is a classical algorithm with runtime ˜O(m2) to find such vertex-flow sparsifier, where m is the number of edges of the original graph. In this work we present a new quantum algorithm with runtime ˜O(m11/6n1/6) that finds the same quality vertex-flow sparsifier, where n is the number of vertices of the original graph. This is a small polynomial speedup for dense graphs. The quantum speedup is based on the classical algorithm, but uses various quantum subroutines from the literature.

Additional Metadata | |
---|---|

R.M. de Wolf (Ronald) | |

Organisation | Algorithms and Complexity |

Grevink, L. (2024, July 17). Quantum algorithms for vertex sparsification. |