A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles

• URL: http://arxiv.org/abs/2503.08403v1
• Date: Tue, 11 Mar 2025 13:06:38 GMT
• Title: A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles
• Authors: Ben Priestley, Petros Wallden,
• Abstract summary: NP-hardness of the closest vector problem (CVP) is an important basis for quantum-secure cryptography.<n>Recent work with quantum algorithms indicates the possibility to find close approximations to (constrained) CVP instances.<n>This work explores the potential for a quantum advantage for approximate CVP, without regard for the subsequent factoring claims.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The NP-hardness of the closest vector problem (CVP) is an important basis for quantum-secure cryptography, in much the same way that integer factorisation's conjectured hardness is at the foundation of cryptosystems like RSA. Recent work with heuristic quantum algorithms (arXiv:2212.12372) indicates the possibility to find close approximations to (constrained) CVP instances that could be incorporated within fast sieving approaches for factorisation. This work explores both the practicality and scalability of the proposed heuristic approach to explore the potential for a quantum advantage for approximate CVP, without regard for the subsequent factoring claims. We also extend the proposal to include an antecedent "pre-training" scheme to find and fix a set of parameters that generalise well to increasingly large lattices, which both optimises the scalability of the algorithm, and permits direct numerical analyses. Our results further indicate a noteworthy quantum speed-up for lattice problems obeying a certain `prime' structure, approaching fifth order advantage for QAOA of fixed depth p=10 compared to classical brute-force, motivating renewed discussions about the necessary lattice dimensions for quantum-secure cryptosystems in the near-term.

Related papers

• Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
  We derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries.
  arXiv  Detail & Related papers  (2025-04-25T09:07:55Z)
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation [3.9857517408503567]
  Quantum Approximate optimisation algorithm (qaoa) is a widely studied quantum-classical iterative for optimisation. We introduce a new algorithmic variant based on non-iterative computation that is instance-independent, but problem-specific. Our approach is based on proving a long-standing conjecture regarding quantum-independent structures in qaoa.
  arXiv  Detail & Related papers  (2024-08-12T21:02:58Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• Improved Quantum Algorithms for Eigenvalues Finding and Gradient Descent [0.0]
  Block encoding is a key ingredient in the recently developed quantum singular value transformation (QSVT) framework. In this article, we affirm this perspective by leveraging block encoding to substantially enhance two previously proposed quantum algorithms. Our findings demonstrate that even just elementary operations within the unitary block encoding framework can eliminate major scaling factors.
  arXiv  Detail & Related papers  (2023-12-22T15:59:03Z)
• Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes [32.07657827173262]
  We introduce an innovative quantum framework for the agent's engagement with an unknown MDP. We show that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning.
  arXiv  Detail & Related papers  (2023-10-18T03:17:51Z)
• Integer Factorization through Func-QAOA [0.0]
  No efficient classical algorithm for cryptographic-time integer factorization has been found. We present the Func-QAOA approach for factorization, which premises overcoming some of the limitations of previous approaches.
  arXiv  Detail & Related papers  (2023-09-26T18:00:25Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• 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)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
  arXiv  Detail & Related papers  (2021-05-14T11:31:14Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.