Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCan graph properties have exponential quantum speedup?
134
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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).
We show that any language in nondeterministic time $exp(exp(cdots exp(n)))$, where the number of iterated exponentials is an arbitrary function $R(n)$, can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness $1$ and soundness $1 - exp(-Cexp(cdotsexp(n)))$, where the number of iterated exponentials is $R(n)-1$ and $C>0$ is a universal constant. The result was previously known for $R=1$ and $R=2$; we obtain it for any time-constructible function $R$. The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC17). As a separate consequence of this technique we obtain a different proof of Slofstras recent result (unpublished) on the uncomputability of the entangled value of multiprover games. Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP* contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelsons problem on the relation between the commuting operator and tensor product models for quantum correlations.
We show that there exist real parameters $c$ for which the Julia set $J_c$ of the quadratic map $z^2+c$ has arbitrarily high computational complexity. More precisely, we show that for any given complexity threshold $T(n)$, there exist a real parameter $c$ such that the computational complexity of computing $J_c$ with $n$ bits of precision is higher than $T(n)$. This is the first known class of real parameters with a non poly-time computable Julia set.
We demonstrate that the ability to estimate the relative sign of an arbitrary $n$-qubit quantum state (with real amplitudes), given only $k$ copies of that state, would yield a $kn$-query algorithm for unstructured search. Thus the quantum sample complexity of sign estimation must be exponential: $Omega(2^{n/2}/n)$. In particular, we show that an efficient procedure for solving the sign estimation problem would allow for a polynomial time solution to the NP-complete problem 3-SAT.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
