An efficient quantum algorithm for lattice problems achieving subexponential approximation factor

• URL: http://arxiv.org/abs/2201.13450v1
• Date: Mon, 31 Jan 2022 18:58:33 GMT
• Title: An efficient quantum algorithm for lattice problems achieving subexponential approximation factor
• Authors: Lior Eldar and Sean Hallgren
• Abstract summary: We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices. The running time of the quantum algorithm is for one range of approximation factors and subexponential time for a second range of approximation factors. This view makes for a clean quantum algorithm in terms of finite abelian groups, uses relatively little from lattice theory, and suggests exploring approximation algorithms for lattice problems in parameters other than dimension alone.
• Score: 2.3351527694849574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices. The quantum algorithm uses a well-known but challenging-to-use quantum state on lattices as a type of approximate quantum eigenvector to randomly self-reduce the BDD instance to a random BDD instance which is solvable classically. The running time of the quantum algorithm is polynomial for one range of approximation factors and subexponential time for a second range of approximation factors. The subclass of lattices we study has a natural description in terms of the lattice's periodicity and finite abelian group rank. This view makes for a clean quantum algorithm in terms of finite abelian groups, uses very relatively little from lattice theory, and suggests exploring approximation algorithms for lattice problems in parameters other than dimension alone. A talk on this paper sparked many lively discussions and resulted in a new classical algorithm matching part of our result. We leave it as a challenge to give a classcial algorithm matching the general case.

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)
• Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
  We present a quantum algorithm for a non-linear differential equation of the form $fracd|urangledt. We also introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case.
  arXiv  Detail & Related papers  (2024-07-10T14:08:58Z)
• A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More [1.1893324664457547]
  This paper studies the limitations of the generic approaches to solving cryptographic problems in classical and quantum settings. In both models, the quantum lower bounds in both models allow certain types of classical preprocessing.
  arXiv  Detail & Related papers  (2024-02-17T13:00:47Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
  arXiv  Detail & Related papers  (2023-12-18T18:29:01Z)
• Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
  We establish a generic model of quantum computation for group-theoretic problems, which we call the quantum generic group model. We show the quantum complexity lower bounds and almost matching algorithms of the DL and related problems in this model. variations of Shor's algorithm can take advantage of classical computations to reduce the number of quantum group operations.
  arXiv  Detail & Related papers  (2023-07-06T15:32:50Z)
• Quantum Multiplication Algorithm Based on the Convolution Theorem [0.0]
  We propose a quantum algorithm for integer multiplication with time complexity $O(sqrtnlog2 n)$. Unlike the Harvey algorithm, our algorithm does not have the restriction of being applicable solely to extremely large numbers. The paper also reviews the history and development of classical multiplication algorithms and motivates us to explore how quantum resources can provide new perspectives and possibilities for this fundamental problem.
  arXiv  Detail & Related papers  (2023-06-14T12:40:54Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions [4.2698418800007865]
  We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. We modify the classical algorithm of vStefankovivc, Vempala and Vigoda to improve its sample complexity. We quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei.
  arXiv  Detail & Related papers  (2020-09-23T17:27:28Z)

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.