Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications

• URL: http://arxiv.org/abs/2212.14433v1
• Date: Thu, 29 Dec 2022 19:07:39 GMT
• Title: Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications
• Authors: Kamil Khadiev and Liliya Safina
• Abstract summary: We present a quantum algorithm for the dynamic programming approach for problems on directed acyclic graphs (DAGs) We show that we can solve problems that use OR, AND, NAND, MAX, and MIN functions as the main transition steps.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we present a quantum algorithm for the dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is $O(\sqrt{\hat{n}m}\log \hat{n})$, and the running time of the best known deterministic algorithm is $O(n+m)$, where $n$ is the number of vertices, $\hat{n}$ is the number of vertices with at least one outgoing edge; $m$ is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX, and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non-constant depth evaluation. Another two are the single source longest paths search for weighted DAGs and the diameter search problem for unweighted DAGs.

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)
• 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)
• 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)
• Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
  Given $s, t$ in an unweighted undirected graph $G$, the goal of the pathfinding problem is to find an $s$-$t$ path. We construct a graph $G$ based on welded trees and define a pathfinding problem in the adjacency list oracle $O$. We prove that no classical algorithm can find an $s$-$t$ path in subexponential time with high probability.
  arXiv  Detail & Related papers  (2023-07-24T02:50:34Z)
• Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
  The maximum $k$-plex problem is important but computationally challenging in applications such as graph mining and community detection. We present an exact algorithm parameterized by $g_k(G)$, which has the worst-case running time in the size of the input graph and exponential in $g_k(G)$. We further extend our discussion to an even smaller parameter $cg_k(G)$, the gap between the community-degeneracy bound and the size of the maximum $k$-plex.
  arXiv  Detail & Related papers  (2023-06-23T01:28:24Z)
• Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem [2.107421958337625]
  We consider an inverse problem for a finite graph $(X,E)$ where we are given a subset of vertices. We show that this problem has unique solution under certain conditions and develop quantum computing methods to solve it.
  arXiv  Detail & Related papers  (2023-06-08T14:48:48Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  We introduce a batch algorithm inspired by finite-arm bandit algorithms. We show that it achieves the cumulative regret upper bound $Oast(sqrtTgamma_T)$ using $O(loglog T)$ batches within time horizon $T$. In addition, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches.
  arXiv  Detail & Related papers  (2021-10-15T00:54:04Z)
• Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
  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.
  arXiv  Detail & Related papers  (2020-12-02T15:32:52Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi random graph. We show that the class of low-degree algorithms can find independent sets of half-optimal size but no larger.
  arXiv  Detail & Related papers  (2020-10-13T17:26:09Z)
• 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)

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.