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
- 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) - Classical-to-Quantum Transfer Learning Facilitates Machine Learning with Variational Quantum Circuit [62.55763504085508]
We prove that a classical-to-quantum transfer learning architecture using a Variational Quantum Circuit (VQC) improves the representation and generalization (estimation error) capabilities of the VQC model.
We show that the architecture of classical-to-quantum transfer learning leverages pre-trained classical generative AI models, making it easier to find the optimal parameters for the VQC in the training stage.
arXiv Detail & Related papers (2023-05-18T03:08:18Z) - 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) - 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.