Related papers: Leveraging Unknown Structure in Quantum Query Algorithms

Leveraging Unknown Structure in Quantum Query Algorithms

URL: http://arxiv.org/abs/2012.01276v2
Date: Thu, 10 Jun 2021 13:43:48 GMT
Title: Leveraging Unknown Structure in Quantum Query Algorithms
Authors: Noel T. Anderson, Jay-U Chung, Shelby Kimmel
Abstract summary: We show a modified span program algorithm to show these speed-ups persist even without having a promise ahead of time. Our algorithm uses $tildeO(sqrtkn)$ queries to solve this problem if there is a path with at most $k$ edges.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Quantum span program algorithms for function evaluation commonly have reduced query complexity when promised that the input has a certain structure. We design a modified span program algorithm to show these speed-ups persist even without having a promise ahead of time, and we extend this approach to the more general problem of state conversion. For example, there is a span program algorithm that decides whether two vertices are connected in an $n$-vertex graph with $O(n^{3/2})$ queries in general, but with $O(\sqrt{k}n)$ queries if promised that, if there is a path, there is one with at most $k$ edges. Our algorithm uses $\tilde{O}(\sqrt{k}n)$ queries to solve this problem if there is a path with at most $k$ edges, without knowing $k$ ahead of time.

Related papers

Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
We give two bounded-error quantum algorithms in the adjacency list model that solve the problem on structured instances. The first approach is based on sparsifying the original graph via sampling the quantum flow state and running a classical algorithm on the smaller problem. The second approach is based on a divide and conquer procedure that outputs the shortest path in $tildeO(lsqrtm)$ steps.
arXiv Detail & Related papers (2024-08-19T21:30:02Z)
A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
arXiv Detail & Related papers (2024-02-09T19:01:48Z)
Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Grover's algorithm is capable of finding $k$ elements in an unordered database with $N$ elements using $O(sqrtN/k)$ steps. This work tackles the problem of using the quantum counting algorithm for estimating the value $k$ of marked elements in other graphs.
arXiv Detail & Related papers (2023-12-05T21:15:09Z)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z)
Logarithmic Regret from Sublinear Hints [76.87432703516942]
We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
arXiv Detail & Related papers (2021-11-09T16:50:18Z)
Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$. Our algorithm is based on non-binary span programs and their efficient implementation.
arXiv Detail & Related papers (2021-05-18T06:51:11Z)
Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees [0.19573380763700712]
We consider online algorithms for the $k$-server problem on trees. Chrobak and Larmore proposed a $k$-competitive algorithm for this problem that has the optimal competitive ratio. We propose a new time-efficient implementation of this algorithm that has $O(nlog n)$ time complexity for preprocessing.
arXiv Detail & Related papers (2020-08-01T14:21:45Z)
Quantum algorithms for graph problems with cut queries [17.149741568581096]
We show that a quantum algorithm can learn a graph with maximum degree $d$ after $O(d log(n)2)$ many cut queries. We also show that a quantum algorithm can learn a general graph with $O(sqrtm log(n)3/2)$ many cut queries.
arXiv Detail & Related papers (2020-07-16T12:21:01Z)
Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
arXiv Detail & Related papers (2020-02-17T18:41:49Z)
Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
arXiv Detail & Related papers (2020-02-17T10:53:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.