Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving
333
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with $n$ nodes and $m$ edges, outputs a classical description of an $epsilon$-spectral sparsifier in sublinear time $tilde{O}(sqrt{mn}/epsilon)$. This contrasts with the optimal classical complexity $tilde{O}(m)$. We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions 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.
rate research
Read More
Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity $R$ of any graph property $mathcal{P}$ has $R(mathcal{P}) = O(Q(mathcal{P})^{6})$, where $Q$ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove $R(mathcal{P}) = O(Q(mathcal{P})^{3l})$ for any $l$-uniform hypergraph property $mathcal{P}$ in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.
We present three new quantum algorithms in the quantum query model for textsc{graph-collision} problem: begin{itemize} item an algorithm based on tree decomposition that uses $Oleft(sqrt{n}t^{sfrac{1}{6}}right)$ queries where $t$ is the treewidth of the graph; item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses $O(sqrt{n}+sqrt{alpha^{**}})$ queries, where $alpha^{**}(G)$ is a graph parameter defined by [alpha^{**}(G):=min_{VCtext{-- vertex cover of}G}{max_{substack{Isubseteq VCItext{-- independent set}}}{sum_{vin I}{deg{v}}}};] item an algorithm for a subclass of circulant graphs that uses $O(sqrt{n})$ queries. end{itemize} We also present an example of a possibly difficult graph $G$ for which all the known graphs fail to solve graph collision in $O(sqrt{n} log^c n)$ queries.
We consider the task of approximating the ground state energy of two-local quantum Hamiltonians on bounded-degree graphs. Most existing algorithms optimize the energy over the set of product states. Here we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an $n$-qubit product state $|vrangle$ with mean energy $e_0=langle v|H|vrangle$ and variance $mathrm{Var}=langle v|(H-e_0)^2|vrangle$, and outputs a state with an energy that is lower than $e_0$ by an amount proportional to $mathrm{Var}^2/n$. In a typical case, we have $mathrm{Var}=Omega(n)$ and the energy improvement is proportional to the number of edges in the graph. When applied to an initial random product state, we recover and generalize the performance guarantees of known algorithms for bounded-occurrence classical constraint satisfaction problems. We extend our results to $k$-local Hamiltonians and entangled initial states.
Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning linear systems to make them more numerically stable. We study the power and limitations of quantum algorithms for these problems. We provide quantum implementations of two classical (in both senses of the word) methods: Sinkhorns algorithm for matrix scaling and Osbornes algorithm for matrix balancing. Using amplitude estimation as our main tool, our quantum implementations both run in time $tilde O(sqrt{mn}/varepsilon^4)$ for scaling or balancing an $n times n$ matrix (given by an oracle) with $m$ non-zero entries to within $ell_1$-error $varepsilon$. Their classical analogs use time $tilde O(m/varepsilon^2)$, and every classical algorithm for scaling or balancing with small constant $varepsilon$ requires $Omega(m)$ queries to the entries of the input matrix. We thus achieve a polynomial speed-up in terms of $n$, at the expense of a worse polynomial dependence on the obtained $ell_1$-error $varepsilon$. We emphasize that even for constant $varepsilon$ these problems are already non-trivial (and relevant in applications). Along the way, we extend the classical analysis of Sinkhorns and Osbornes algorithm to allow for errors in the computation of marginals. We also adapt an improved analysis of Sinkhorns algorithm for entrywise-positive matrices to the $ell_1$-setting, leading to an $tilde O(n^{1.5}/varepsilon^3)$-time quantum algorithm for $varepsilon$-$ell_1$-scaling in this case. We also prove a lower bound, showing that our quantum algorithm for matrix scaling is essentially optimal for constant $varepsilon$: every quantum algorithm for matrix scaling that achieves a constant $ell_1$-error with respect to uniform marginals needs to make at least $Omega(sqrt{mn})$ queries.
Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs (where graph symmetry is manifested differently), we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
