Quantum Augmented Dual Attack

• URL: http://arxiv.org/abs/2205.13983v3
• Date: Thu, 5 Jan 2023 16:37:52 GMT
• Title: Quantum Augmented Dual Attack
• Authors: Martin R. Albrecht, Yixin Shen
• Abstract summary: We present a quantum augmented variant of the dual lattice attack on the Learning with Errors (LWE) problem, using classical memory with quantum random access (QRACM) Applying our results to lattice parameters from the literature, we find that our algorithm outperforms previous algorithms, assuming unit cost access to a QRACM.
• Score: 8.134961550216618
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a quantum augmented variant of the dual lattice attack on the Learning with Errors (LWE) problem, using classical memory with quantum random access (QRACM). Applying our results to lattice parameters from the literature, we find that our algorithm outperforms previous algorithms, assuming unit cost access to a QRACM. On a technical level, we show how to obtain a quantum speedup on the search for Fast Fourier Transform (FFT) coefficients above a given threshold by leveraging the relative sparseness of the FFT and using quantum amplitude estimation. We also discuss the applicability of the Quantum Fourier Transform in this context. Furthermore, we give a more rigorous analysis of the classical and quantum expected complexity of guessing part of the secret vector where coefficients follow a discrete Gaussian (mod \(q\)).

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Mitigating Errors on Superconducting Quantum Processors through Fuzzy Clustering [38.02852247910155]
  A new Quantum Error Mitigation (QEM) technique uses Fuzzy C-Means clustering to specifically identify measurement error patterns. We report a proof-of-principle validation of the technique on a 2-qubit register, obtained as a subset of a real NISQ 5-qubit superconducting quantum processor. We demonstrate that the FCM-based QEM technique allows for reasonable improvement of the expectation values of single- and two-qubit gates based quantum circuits.
  arXiv  Detail & Related papers  (2024-02-02T14:02:45Z)
• Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms [0.0]
  We show how many techniques from randomized linear algebra can be adapted to work under this weaker assumption. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms.
  arXiv  Detail & Related papers  (2023-04-11T02:09:13Z)
• 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)
• Variational quantum algorithms for local Hamiltonian problems [0.0]
  Variational quantum algorithms (VQAs) are a modern family of quantum algorithms designed to solve optimization problems using a quantum computer. We primarily focus on the algorithm called variational quantum eigensolver (VQE), which takes a qubit Hamiltonian and returns its approximate ground state.
  arXiv  Detail & Related papers  (2022-08-23T22:32:56Z)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  We propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization problem. The proposed algorithm is capable of reducing the query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
  arXiv  Detail & Related papers  (2022-05-31T00:14:49Z)
• Fundamental limitations on optimization in variational quantum algorithms [7.165356904023871]
  A leading paradigm to establish such near-term quantum applications is variational quantum algorithms (VQAs) We prove that for a broad class of such random circuits, the variation range of the cost function vanishes exponentially in the number of qubits with a high probability. This result can unify the restrictions on gradient-based and gradient-free optimizations in a natural manner and reveal extra harsh constraints on the training landscapes of VQAs.
  arXiv  Detail & Related papers  (2022-05-10T17:14:57Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices. Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2021-07-11T10:56:24Z)
• Quantum computing critical exponents [0.0]
  We show that the Variational Quantum-Classical Simulation algorithm admits a finite circuit depth scaling collapse when targeting the critical point of the transverse field Ising chain. The order parameter only collapses on one side of the transition due to a slowdown of the quantum algorithm when crossing the phase transition.
  arXiv  Detail & Related papers  (2021-04-02T17:38:20Z)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels. We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
  arXiv  Detail & Related papers  (2020-12-15T15:51:27Z)

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.