Related papers: Quantum Speedups for Bayesian Network Structure Learning

Quantum Speedups for Bayesian Network Structure Learning

URL: http://arxiv.org/abs/2305.19673v1
Date: Wed, 31 May 2023 09:15:28 GMT
Title: Quantum Speedups for Bayesian Network Structure Learning
Authors: Juha Harviainen (1), Kseniya Rychkova (2), Mikko Koivisto (1) ((1) University of Helsinki, (2) IQM)
Abstract summary: For networks with $n$ nodes, the fastest known algorithms run in time $O(cn)$ in the worst case, with no improvement in two decades. Inspired by recent advances in quantum computing, we ask whether BNSL admits a quantum speedup. We give two algorithms achieving $c leq 1.817$ and $c leq 1.982$.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Bayesian network structure learning (BNSL) problem asks for a directed acyclic graph that maximizes a given score function. For networks with $n$ nodes, the fastest known algorithms run in time $O(2^n n^2)$ in the worst case, with no improvement in the asymptotic bound for two decades. Inspired by recent advances in quantum computing, we ask whether BNSL admits a polynomial quantum speedup, that is, whether the problem can be solved by a quantum algorithm in time $O(c^n)$ for some constant $c$ less than $2$. We answer the question in the affirmative by giving two algorithms achieving $c \leq 1.817$ and $c \leq 1.982$ assuming the number of potential parent sets is, respectively, subexponential and $O(1.453^n)$. Both algorithms assume the availability of a quantum random access memory.

Related papers

Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
Gradient descent is one of the most basic algorithms for solving continuous optimization problems. We propose a quantum algorithm that returns an $varepsilon$-approximation of its gradient with query complexity $widetildeO (1/varepsilon)$. We also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method.
arXiv Detail & Related papers (2024-07-04T11:03:48Z)
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)
Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD. Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers. Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used quantum machines.
arXiv Detail & Related papers (2024-04-30T23:55:03Z)
On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z)
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
We give a quantum algorithm for computing an $epsilon$-approximate Nash equilibrium of a zero-sum game in a $m times n$ payoff matrix with bounded entries. Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time $widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$ and outputs a classical representation of the $epsilon$-approximate Nash equilibrium.
arXiv Detail & Related papers (2023-01-10T02:56:49Z)
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)
Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
arXiv Detail & Related papers (2022-04-22T12:37:56Z)
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)
Quantum Algorithm for Fidelity Estimation [8.270684567157987]
For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem. We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
arXiv Detail & Related papers (2021-03-16T13:57:01Z)
Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
arXiv Detail & Related papers (2020-12-03T14:03:20Z)

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