Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=p2hZL38tqAs


Duration: 1:03:37
852 views
21

Simon Apers (INRIA)
The Quantum Wave in Computing
Seminar, Apr. 7, 2020

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a quantum speedup for spectral sparsification. We also prove that our algorithm is tight up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient construction for k-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut.

https://simons.berkeley.edu/events/quantum-speedup-graph-sparsification-cut-approximation-and-laplacian-solving



Other Videos By Simons Institute for the Theory of Computing


2020-04-27Watermarking and Traitor Tracing for PRFs
2020-04-27New Techniques for Practical Lattice-Based Zero-Knowledge
2020-04-27Signatures, Commitments, Zero-Knowledge, and Applications
2020-04-23Post-Quantum Multi-Party Computation in Constant Rounds
2020-04-23Quantum Coupon Collector
2020-04-23Laconic Function Evaluation
2020-04-20A Tale of Turing Machines, Quantum-Entangled Particles, and Operator Algebras
2020-04-15Robust Polynomial Method and a Sub-Volume Law for Locally Gapped Frustration-Free Spin Systems
2020-04-13Optimal Broadcast Encryption from Pairings and LWE
2020-04-09Secure Multi-party Quantum Computation with a Dishonest Majority
2020-04-09Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving
2020-04-08NIZK from LPN and Trapdoor Hash via Correlation Intractability for Approximable Relations
2020-04-08Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
2020-04-07The Digital Fence: Taiwan’s Response to COVID-19
2020-04-06Lattices, Post-Quantum Security and Homomorphic Encryption — Q&A
2020-04-06Lattices, Post-Quantum Security and Homomorphic Encryption
2020-04-03What Do Algorithmic Fairness and COVID-19 Case-Severity Prediction Have in Common?
2020-04-02Efficient Learning of Pauli Channels
2020-04-02Not All Benchmarks Are Created Equal
2020-04-02Cycle Benchmarking: The New Paradigm for Assessing All Relevant Errors and Error Correlations...
2020-04-02Cross-Platform Verification of Intermediate Scale Quantum Devices with Randomized Measurements


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing