Time and Query Optimal Quantum Algorithms Based on Decision Trees

• URL: http://arxiv.org/abs/2105.08309v2
• Date: Sun, 16 Oct 2022 10:15:46 GMT
• Title: Time and Query Optimal Quantum Algorithms Based on Decision Trees
• Authors: Salman Beigi, Leila Taghavi, Artin Tajdini
• Abstract summary: 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.
• Score: 2.492300648514128
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It has recently been shown that starting with a classical query algorithm (decision tree) and a guessing algorithm that tries to predict the query answers, we can design a quantum algorithm with query complexity $O(\sqrt{GT})$ where $T$ is the query complexity of the classical algorithm (depth of the decision tree) and $G$ is the maximum number of wrong answers by the guessing algorithm [arXiv:1410.0932, arXiv:1905.13095]. In this paper we show that, given some constraints on the classical algorithms, this quantum algorithm can be implemented in time $\tilde O(\sqrt{GT})$. Our algorithm is based on non-binary span programs and their efficient implementation. We conclude that various graph theoretic problems including bipartiteness, cycle detection and topological sort can be solved in time $O(n^{3/2}\log n)$ and with $O(n^{3/2})$ quantum queries. Moreover, finding a maximal matching can be solved with $O(n^{3/2})$ quantum queries in time $O(n^{3/2}\log n)$, and maximum bipartite matching can be solved in time $O(n^2\log n)$.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• 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)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  We present an exact quantum algorithm for computing $textMOD_mn$. We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
  arXiv  Detail & Related papers  (2023-03-20T08:17:32Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm. Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• 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)
• 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)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm. The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)
• Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems [0.0]
  We study algorithms for solving three problems on strings. The first one is the Most Frequently String Search Problem. The second is searching intersection of two sequences of strings. The third problem is sorting of $n$ strings of length $k$.
  arXiv  Detail & Related papers  (2020-01-07T07:22:02Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.