Learning with errors may remain hard against quantum holographic attacks

• URL: http://arxiv.org/abs/2509.22833v2
• Date: Thu, 16 Oct 2025 20:53:00 GMT
• Title: Learning with errors may remain hard against quantum holographic attacks
• Authors: Yunfei Wang, Xin Jin, Junyu Liu,
• Abstract summary: Recent results show that estimating entanglement entropy is as hard as Learning with Errors (LWE), creating tension with quantum gravity and AdS/CFT.<n>This suggests a paradoxical route to solving LWE by building holographic duals and measuring extremal surfaces, seemingly an easy task.<n>We show that holographic entropy remains consistent with quantum computational limits without requiring an intractable holographic dictionary.
• Score: 20.779821328622454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Learning with Errors (LWE) problem underlies modern lattice-based cryptography and is assumed to be quantum hard. Recent results show that estimating entanglement entropy is as hard as LWE, creating tension with quantum gravity and AdS/CFT, where entropies are computed by extremal surface areas. This suggests a paradoxical route to solving LWE by building holographic duals and measuring extremal surfaces, seemingly an easy task. Three possible resolutions arise: that AdS/CFT duality is intractable, that the quantum-extended Church-Turing thesis (QECTT) fails, or that LWE is easier than believed. We develop and analyze a fourth resolution: that estimating surface areas with the precision required for entropy is itself computationally hard. We construct two holographic quantum algorithms to formalize this. For entropy differences of order N, we show that measuring Ryu-Takayanagi geodesic lengths via heavy-field two-point functions needs exponentially many measurements in N, even when the boundary state is efficiently preparable. For order one corrections, we show that reconstructing the bulk covariance matrix and extracting entropy requires exponential time in N. Although these tasks are computationally intractable, we compare their efficiency with the Block Korkine-Zolotarev lattice reduction algorithm for LWE. Our results reconcile the tension with QECTT, showing that holographic entropy remains consistent with quantum computational limits without requiring an intractable holographic dictionary, and provide new insights into the quantum cryptanalysis of lattice-based cryptography.

Related papers

• Variational Quantum Algorithm for Solving the Liouvillian Gap [0.0]
  In open quantum systems, the Liouvillian gap characterizes the relaxation time toward the steady state.<n>We propose a variational quantum algorithm for efficiently estimating the Liouvillian gap.
  arXiv  Detail & Related papers  (2025-05-22T05:59:55Z)
• Operator-Projected Variational Quantum Imaginary Time Evolution [0.0]
  We show that requiring the imaginary-time evolution to be correct only when projected onto a chosen set of operators allows to achieve a twofold reduction in circuit depth. We demonstrate by a simulation of the transverse-field Ising model that our algorithm achieves a several orders of magnitude improvement in the number of measurements required for the same accuracy.
  arXiv  Detail & Related papers  (2024-09-18T14:30:05Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• One-Shot Min-Entropy Calculation Of Classical-Quantum States And Its Application To Quantum Cryptography [21.823963925581868]
  We develop a one-shot lower bound calculation technique for the min-entropy of a classical-quantum state.<n>It offers an alternative tight finite-data analysis for the BB84 quantum key distribution scheme.<n>It gives the best finite-key bound known to date for a variant of device independent quantum key distribution protocol.
  arXiv  Detail & Related papers  (2024-06-21T15:11:26Z)
• Stable computation of entanglement entropy for 2D interacting fermion systems [1.3165428727965363]
  entanglement entropy (EE) can be used to infer the organizing principle of 2D interacting fermion systems. EE has not been succeeded with reliable data that the universal scaling regime can be accessed. We show how to overcome the conceptual and computational barrier with the incremental algorithm.
  arXiv  Detail & Related papers  (2023-03-25T01:56:09Z)
• 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)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm [0.0]
  This work proposes a novel approach by using the Quantum Amplitude Damping operation as a resource, in order to construct an efficient quantum algorithm for solving homogeneous LDEs. We show that such an open quantum system-inspired circuitry allows for constructing the real exponential terms in the solution in a non-interferometric.
  arXiv  Detail & Related papers  (2021-11-10T11:25:32Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• The refined quantum extremal surface prescription from the asymptotic equipartition property [0.0]
  One-shot information-theoretic entropies are more fundamental entropy measures from the quantum information perspective. We combine the technical methods from both quantum information and quantum gravity to put this idea on firm grounds. We derive the refined quantum extremal surface prescription for fixed-area states via a novel AEP replica trick.
  arXiv  Detail & Related papers  (2021-05-12T18:26:30Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32: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.