Efficiency of k-Local Quantum Search and its Adiabatic Variant on Random
k-SAT
- URL: http://arxiv.org/abs/2403.03237v1
- Date: Tue, 5 Mar 2024 15:03:47 GMT
- Title: Efficiency of k-Local Quantum Search and its Adiabatic Variant on Random
k-SAT
- Authors: Mingyou Wu
- Abstract summary: This paper introduces a family of structured quantum search algorithms, termed $k$-local quantum search.
We prove that the max-$k$-SSAT is on average if $m=Omega(n2+epsilon)$ based on the average-case complexity theory.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The computational complexity of random $k$-SAT problem is contingent on the
clause number $m$. In classical computing, a satisfiability threshold is
identified at $m=r_k n$, marking the transition of random $k$-SAT from
solubility to insolubility. However, beyond this established threshold,
comprehending the complexity remains challenging. On quantum computers, direct
application of Grover's unstructured quantum search still yields exponential
time requirements due to oversight of structural information. This paper
introduces a family of structured quantum search algorithms, termed $k$-local
quantum search, designed to address the $k$-SAT problem. Because search
algorithm necessitates the presence of a target, our focus is specifically on
the satisfiable side of $k$-SAT, i.e., max-$k$-SAT on satisfiable instances,
denoted as max-$k$-SSAT, with a small $k \ge 3$. For random instances with
$m=\Omega(n^{2+\epsilon})$, general exponential acceleration is proven for any
small $\epsilon>0$ and sufficiently large $n$. Furthermore, adiabatic $k$-local
quantum search improves the bound of general efficiency to
$m=\Omega(n^{1+\epsilon})$, within an evolution time of $\mathcal{O}(n^2)$.
Specifically, for $m=\Theta(n^{1+\delta+\epsilon})$, the efficiency is
guaranteed in a probability of $1-\mathcal{O}(\mathrm{erfc}(n^{\delta/2}))$. By
modifying this algorithm capable of solving all instances, we prove that the
max-$k$-SSAT is polynomial on average if $m=\Omega(n^{2+\epsilon})$ based on
the average-case complexity theory.
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) - Measuring quantum relative entropy with finite-size effect [53.64687146666141]
We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.
Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
arXiv Detail & Related papers (2024-06-25T06:07:20Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$.
Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions.
We show that the quantum query complexities for $ell1$- and $ell2$-closeness testing are $O(sqrtn/varepsilon)$ and $O(sqrtnk/varepsilon)$.
We propose the first quantum algorithm for this problem with query complexity $O(sqrtnk/varepsilon)
arXiv Detail & Related papers (2023-04-25T15:32:37Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$ [0.0]
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) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
We show that quantum algorithms can find an $epsilon$-SOSP with poly-logarithmic,, or exponential number of queries in $d.
We also characterize the domains where quantum algorithms can find an $epsilon$-SOSP with poly-logarithmic,, or exponential number of queries in $d.
arXiv Detail & Related papers (2022-12-05T19:10:32Z) - 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) - The Algorithmic Phase Transition of Random $k$-SAT for Low Degree
Polynomials [18.00315760946089]
It is known that a satisfying assignment exists with high probability at clause density $m/n 2k log 2 - frac12.
We show that low degree algorithms can find a satisfying assignment at clause density $(1 - o_k(1)) 2k log k / k$.
arXiv Detail & Related papers (2021-06-03T21:01:02Z) - 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)
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.