Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

• URL: http://arxiv.org/abs/2605.17412v2
• Date: Mon, 25 May 2026 10:54:23 GMT
• Title: Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics
• Abstract summary: We present a quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes.<n>We verify the resulting approximation factor satisfies $le 21 q/2=1664.5$ for ML-KEM-1024.<n>We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings with quantum algorithms.
• Score: 1.0152838128195467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes. Combining with Parts I-III, we provide an algorithm and verify the resulting approximation factor satisfies $γ\le 21 < q/2=1664.5$ for ML-KEM-1024, with a success probability $\ge 0.99$. We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain $\Q\subset \Q(ζ_8)\subset\cdots\subset \Q(ζ_{2^k})$ which yields a polynomial-time quantum algorithm costing $O(n^3 \log^2 n)$ gates, $O(n^2 \log n)$ qubits, and poly$(n)$ classical bit operations. We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings with polynomial-time quantum algorithms.

Related papers

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• Permutation-symmetric quantum trajectories [42.05677589454327]
  We show how one may perform a unraveling which respects weak permutation symmetry for models of $N$ emitters coupled to a common system.<n>For problems involving 2-level emitters, such an unravelling reduces the computational cost from $mathcalO(N5)$ to $mathcalO(N2)$.
  arXiv  Detail & Related papers  (2026-05-11T18:08:08Z)
• IQP circuits for 2-Forrelation [2.5782420501870296]
  2-Forrelation problem provides optimal separation between classical and quantum query complexity.<n>We show that 2-Forrelation can be solved using Instantaneous Quantum Polynomial-time ($mathsfIQP$) circuits.
  arXiv  Detail & Related papers  (2026-04-16T17:24:25Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• A new entanglement measure based on the total concurrence [2.003078340059495]
  A bona fide measure of quantum entanglement is introduced, the $mathcalCt_q$-concurrence ($q geq 2$)<n>An analytical expression is derived for the $mathcalCt_q$-concurrence in the cases of isotropic and Werner states.<n>The monogamy relations that the $mathcalCt_q$-concurrence satisfies for qubit systems are examined.
  arXiv  Detail & Related papers  (2025-12-30T07:58:55Z)
• Quantum Advantage via Solving Multivariate Polynomials [21.099298465042583]
  We show that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage.<n>We show that there is a expected-time quantum algorithm that provably solves $p_i(x_ldots,x_n)=y_i_iin [m]$ for $mn$ over $mathbbF$.
  arXiv  Detail & Related papers  (2025-09-08T23:19:20Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices.<n>We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Security of Key-Alternating Ciphers: Quantum Lower Bounds and Quantum Walk Attacks [5.221158079775365]
  We study the quantum security of key-alternating ciphers (KAC)<n>We prove security of the $t$-round KAC against a non-adaptive adversary in both the Q1 and Q2 models.<n>We give the first non-trivial quantum key-recovery algorithm for $t$-round KAC in the Q1 model.
  arXiv  Detail & Related papers  (2024-12-06T13:23:29Z)
• Incompressibility and spectral gaps of random circuits [2.359282907257055]
  reversible and quantum circuits form random walks on the alternating group $mathrmAlt (2n)$ and unitary group $mathrmSU (2n)$, respectively.<n>We prove that the gap for random reversible circuits is $Omega(n-3)$ for all $tgeq 1$, and the gap for random quantum circuits is $Omega(n-3)$ for $t leq Theta(2n/2)$.
  arXiv  Detail & Related papers  (2024-06-11T17:23:16Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Pauli-based model of quantum computation with higher-dimensional systems [0.0]
  Pauli-based computation (PBC) is a universal model for quantum computation with qubits. We generalize PBC for odd-prime-dimensional systems and demonstrate its universality.
  arXiv  Detail & Related papers  (2023-02-27T12:05:13Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• On quantum algorithms for the Schr\"odinger equation in the semi-classical regime [27.175719898694073]
  We consider Schr"odinger's equation in the semi-classical regime. Such a Schr"odinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics.
  arXiv  Detail & Related papers  (2021-12-25T20:01:54Z)
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
  The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth and size complexity remain open when ancillary qubits are available. In this paper, we study efficient constructions of quantum circuits with $m$ ancillary qubits that can prepare $psi_vrangle$ in depth. Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime.
  arXiv  Detail & Related papers  (2021-08-13T09:47:11Z)
• Emulating Quantum Interference with Generalized Ising Machines [0.0]
  This paper presents an exact and general procedure for mapping any sequence of quantum gates onto a network of probabilistic p-bits. We can view this structure as a Boltzmann machine whose states each represent a Feynman path leading from an initial configuration of qubits to a final configuration. Our results for mapping an arbitrary quantum circuit to a Boltzmann machine with a complex energy function should help push the boundaries of the simulability of quantum circuits with probabilistic resources.
  arXiv  Detail & Related papers  (2020-07-14T22:10:29Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games. We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
  arXiv  Detail & Related papers  (2020-05-18T16:55:08Z)

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.