Related papers: Quantum algorithms for the Goldreich-Levin learning problem

Quantum algorithms for the Goldreich-Levin learning problem

URL: http://arxiv.org/abs/2001.00014v1
Date: Tue, 31 Dec 2019 14:52:36 GMT
Title: Quantum algorithms for the Goldreich-Levin learning problem
Authors: Hongwei Li
Abstract summary: Goldreich-Levin algorithm was originally proposed for a cryptographic purpose and then applied to learning. It takes a $poly(n,frac1epsilonlogfrac1delta)$ time to output the vectors $w$ with Walsh coefficients $S(w)geqepsilon$ with probability at least $1-delta$. In this paper, a quantum algorithm for this problem is given with query complexity $O(fraclogfrac1deltaepsilon4)$, which is independent of $n$.
Score: 3.8849433921565284
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Goldreich-Levin algorithm was originally proposed for a cryptographic purpose and then applied to learning. The algorithm is to find some larger Walsh coefficients of an $n$ variable Boolean function. Roughly speaking, it takes a $poly(n,\frac{1}{\epsilon}\log\frac{1}{\delta})$ time to output the vectors $w$ with Walsh coefficients $S(w)\geq\epsilon$ with probability at least $1-\delta$. However, in this paper, a quantum algorithm for this problem is given with query complexity $O(\frac{\log\frac{1}{\delta}}{\epsilon^4})$, which is independent of $n$. Furthermore, the quantum algorithm is generalized to apply for an $n$ variable $m$ output Boolean function $F$ with query complexity $O(2^m\frac{\log\frac{1}{\delta}}{\epsilon^4})$.

Related papers

Learning low-degree quantum objects [5.2373060530454625]
We show how to learn low-degree quantum objects up to $varepsilon$-error in $ell$-distance. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely boundedpolynomials.
arXiv Detail & Related papers (2024-05-17T17:36:44Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
arXiv Detail & Related papers (2023-06-02T18:55:27Z)
Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
arXiv Detail & Related papers (2023-02-20T19:11:44Z)
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)
Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
arXiv Detail & Related papers (2021-09-21T13:19:04Z)
Testing Boolean Functions Properties [1.5924410290166868]
The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is $varepsilon$-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm.
arXiv Detail & Related papers (2021-09-14T15:27:38Z)
Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
We show a quantum algorithm with complexity $widetilde O(T_Dn)$, where $T_D D+1$. While the best known classical algorithm is $textpoly(m,n)log n T_Dn$, the time complexity of our quantum algorithm is $textpoly(m,n)log n T_Dn$.
arXiv Detail & Related papers (2021-04-29T14:50:03Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z)
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)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
arXiv Detail & Related papers (2020-06-06T13:34:41Z)
Fast digital methods for adiabatic state preparation [0.0]
We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error.
arXiv Detail & Related papers (2020-04-08T18:00:01Z)

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