Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses

• URL: http://arxiv.org/abs/2403.03237v2
• Date: Sun, 03 Nov 2024 10:00:18 GMT
• Title: Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses
• Authors: Mingyou Wu,
• Abstract summary: We show that max-k-SSAT is the computational algorithm on average when $m=Omega(n2+delta+epsilon)$ based on the average-case complexity theory. We also prove that max-k-SSAT is on average when $m=Omega(n2+delta+epsilon)$ based on the average-case complexity theory.
• Score: 0.0
• License:
• Abstract: The random k-SAT instances undergo a "phase transition" from being generally satisfiable to unsatisfiable as the clause number m passes a critical threshold, $r_k n$. This causes a drastic reduction in the number of satisfying assignments, shifting the problem from being generally solvable on classical computers to typically insolvable. Beyond this threshold, it is challenging to comprehend the computational complexity of random k-SAT. In quantum computing, Grover's search still yields exponential time requirements due to the neglect of structural information. Leveraging the structure inherent in search problems, we propose the k-local quantum search algorithm, which extends quantum search to structured scenarios. Grover's search, by contrast, addresses the unstructured case where k=n. Given that the search algorithm necessitates the presence of a target, we specifically focus on the problem of searching the interpretation of satisfiable instances of k-SAT, denoted as max-k-SSAT. If this problem is solvable in polynomial time, then k-SAT can also be solved within the same complexity. We demonstrate that, for small $k \ge 3$, any small $\epsilon>0$ and sufficiently large n: $\cdot$ k-local quantum search achieves general efficiency on random instances of max-k-SSAT with $m=\Omega(n^{2+\delta+\epsilon})$ using $\mathcal{O}(n)$ iterations, and $\cdot$ k-local adiabatic quantum search enhances the bound to $m=\Omega(n^{1+\delta+\epsilon})$ within an evolution time of $\mathcal{O}(n^2)$. In both cases, the circuit complexity of each iteration is $\mathcal{O}(n^k)$, and the efficiency is assured with overwhelming probability $1 - \mathcal{O}(\mathrm{erfc}(n^{\delta/2}))$. By modifying this algorithm capable of solving all instances of max-k-SSAT, we further prove that max-k-SSAT is polynomial on average when $m=\Omega(n^{2+\epsilon})$ based on the average-case complexity theory.

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)
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
  We present a quantum $tildeO(sqrtnk+k2)$-time algorithm that uses $tildeO(sqrtnz)$ queries, where $tildeO(cdot)$ hides polylogarithmic factors. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of $tildeO(sqrtnz)$.
  arXiv  Detail & Related papers  (2023-11-03T09:09:23Z)
• 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)
• Efficient Quantum State Synthesis with One Query [0.0]
  We present a time analogue quantum algorithm making a single query (in superposition) to a classical oracle. We prove that every $n$-qubit state can be constructed to within 0.01 error by an $On/n)$-size circuit over an appropriate finite gate set.
  arXiv  Detail & Related papers  (2023-06-02T17:49:35Z)
• 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)
• 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)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants. We exploit quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
  arXiv  Detail & Related papers  (2022-10-12T19:10:43Z)
• 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)
• 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.