On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut

• URL: http://arxiv.org/abs/2411.04124v1
• Date: Wed, 06 Nov 2024 18:58:17 GMT
• Title: On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut
• Authors: Jeremy Ahrens Huang, Young Kun Ko, Chunhao Wang,
• Abstract summary: We show a linear sized reduction from the Maximum Cut Problem (Max-Cut) with $1 - varepsilon$ and soundness $1 - varepsilon1/2$ to the $gamma$-Approximate Closest Vector Problem under any finite $ell_p$-norm. We show that any sub-exponential time (classical or quantum) algorithm for the $o(sqrtlog nfrac1p)$-Approximate Closest Vector Problem in any finite $ell_p$-norm implies a faster than the state-
• Score: 2.2776283699063664
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show a linear sized reduction from the Maximum Cut Problem (Max-Cut) with completeness $1 - \varepsilon$ and soundness $1 - \varepsilon^{1/2}$ to the $\gamma$-Approximate Closest Vector Problem under any finite $\ell_p$-norm including $p = 2$. This reduction implies two headline results: (i) We show that any sub-exponential time (classical or quantum) algorithm for the $o(\sqrt{\log n}^{\frac{1}{p}})$-Approximate Closest Vector Problem in any finite $\ell_p$-norm implies a faster than the state-of-the-art (by Arora, Barak, and Steurer [\textit{Journal of the ACM}, 2015]) sub-exponential time (classical or quantum) algorithm for Max-Cut. This fills the gap between the results by Bennett, Golovnev, and Stephens-Davidowitz [\textit{FOCS} 2017] which had an almost optimal runtime lower bound but a very small approximation factor and the results by Dinur, Kindler, Raz, and Safra [\textit{Combinatorica}, 2003] which had an almost optimal approximation factor but small runtime lower bound, albeit using a different underlying hard problem; (ii) in combination with the classical results of Aggarwal and Kumar [\textit{FOCS} 2023] and our quantization of those results, there are no fine-grained reductions from $k$-SAT to Max-Cut with one-sided error, nor are there non-adaptive fine-grained (classical or quantum) reductions with two-sided error, unless the polynomial hierarchy collapses (or unless $\mathrm{NP} \subseteq \mathrm{pr} \text{-} \mathrm{QSZK}$ in the quantum case). The second result poses a significant barrier against proving the fine-grained complexity of Max-Cut using the Strong Exponential Time Hypothesis (or the Quantum Strong Exponential Time Hypothesis).

Related papers

• Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry [0.0]
  We prove by a direct reduction from Hstad's theorem that no-time algorithm can exceed the randomassignment ratio $r/q$ by any constant.<n>This threshold coincides with the $ell/m to 0$ limit of the semicircle law governing decoded quantum interferometry.
  arXiv  Detail & Related papers  (2026-03-04T19:26:26Z)
• Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions [1.43494686131174]
  We show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2(1-varepsilon)n)$ for any $varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH)<n>We provide a quantum algorithm that runs in $O(sqrt2n)$ time for an arbitrary $1/mathrmpoly(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Goss
  arXiv  Detail & Related papers  (2026-02-16T01:11:55Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems.<n>Our framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation.
  arXiv  Detail & Related papers  (2025-09-20T20:18:49Z)
• Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
  We present a framework for quantum computation, similar to Adiabatic Quantum Computation (AQC) By performing randomised dephasing operations at intervals determined by a Poisson process, we are able to track the eigenspace associated to a particular eigenvalue. We derive a simple differential equation for the fidelity, leading to general theorems bounding the time complexity of a class of algorithms.
  arXiv  Detail & Related papers  (2024-06-06T11:33:29Z)
• Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
  We show that $1L 1$ can be used to improve some state-of-the-art problems even for a multilevel Carlo iteration. We provide an analysis for inexact Halperness estimators for $1L 1$ when the only hold with respect to a solution is a new $1L 1$ theory.
  arXiv  Detail & Related papers  (2024-02-07T18:22:41Z)
• The classical limit of Quantum Max-Cut [0.18416014644193066]
  We show that the limit of large quantum spin $S$ should be understood as a semiclassical limit. We present two families of classical approximation algorithms for $mathrmQMaxCut_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states.
  arXiv  Detail & Related papers  (2024-01-23T18:53:34Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  We prove that the recently proposed Quantum Hamiltonian (QHD) algorithm is able to solve any $d$dimensional queries from this family. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical algorithms/solvers would require a superpolynomial time to solve such queries.
  arXiv  Detail & Related papers  (2023-11-01T19:51:00Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• 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)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms [0.0]
  We consider the power of local algorithms for approximately solving Max $k$XOR. In Max $k$XOR each constraint is the XOR of exactly $k$ variables and a parity bit. We show that the quantum algorithm outperforms the threshold algorithm for $k > 4$.
  arXiv  Detail & Related papers  (2021-09-22T16:50:45Z)
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
  This paper establishes the complexity for finding approximate stationary points of non-strongly-concave (NC-SC) smooth minimax problems. We deploy a proposed sequence of $Omega-strong$lyconcave sub-2 problems in both general complexity and averaged complexity. In our proposed finite-sum setting, our proposed algorithm provides a nearly-tight dependence on the condition number.
  arXiv  Detail & Related papers  (2021-03-29T18:53:57Z)
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization [61.66927778694731]
  Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale (2011) was deemed a breakthrough for strongly convex minimization. Our result is the first one that shows Epoch-GDA can achieve the optimal rate of $O (1/T)$ for the duality gap of SCSC min-max problems.
  arXiv  Detail & Related papers  (2020-02-13T02:16:57Z)

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.