Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving.
Simon ApersRonald de WolfPublished in: SIAM J. Comput. (2022)
Keyphrases
- laplacian matrix
- graph laplacian
- orders of magnitude
- minimum cut
- least squares
- planar graphs
- random walk
- graph representation
- weighted graph
- graph structure
- approximation algorithms
- vertex set
- tikhonov regularization
- closed form
- structured data
- graph theory
- directed graph
- quantum computing
- combinatorial optimization
- adjacency matrix
- spectral decomposition
- constant factor
- quantum inspired
- graph model
- families of valid inequalities
- heat kernel
- min cut
- graph databases
- objective function
- bipartite graph
- error bounds
- semi supervised
- lower bound