Equivalence Between Average-Case Hardness of Learning and Cryptography for Mixed Quantum States

• URL: http://arxiv.org/abs/2608.14331v1
• Date: Fri, 14 Aug 2026 14:20:46 GMT
• Title: Equivalence Between Average-Case Hardness of Learning and Cryptography for Mixed Quantum States
• Abstract summary: We prove that the existence of AHL for mixed quantum states is equivalent to the existence of inefficiently verifiable one-way state generators (IV-OWSGs)<n>As a corollary to existing results, we obtain a separation between IV-OWSGs and OWSGs relative to the SWAP oracle.
• Score: 46.644955105516466
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The relationship between cryptography and learning theory has long been a central theme in the foundations of theoretical computer science: cryptographic primitives can imply hardness of learning, while hardness of learning can in turn be used to construct cryptographic schemes. Recent works have begun exploring analogous connections in the quantum setting, relating the average-case hardness of learning quantum states (AHL) to cryptographic primitives such as one-way state generators (OWSG). Despite recent progress exploring this for pure states, the relationship for mixed states has remained an open question. In this work, we prove that the existence of AHL for mixed quantum states is equivalent to the existence of inefficiently verifiable one-way state generators (IV-OWSGs). As a consequence, this relates mixed-state AHL to EFI pairs. Moreover, as a corollary of existing results, we obtain a separation between IV-OWSGs and OWSGs relative to the SWAP oracle.

Related papers

• Quantum One-Way Functions and Related Cryptographic Primitives [0.0]
  We review quantum one-way functions and a range of closely related quantum-state primitives.<n>We discuss both computational and information-theoretic notions of quantum one-wayness.
  arXiv  Detail & Related papers  (2026-08-06T08:39:09Z)
• Learnable yet not simulable: a quantum resource theory of learning models [57.695822250391906]
  It remains unclear which quantum resource governs the classical learnability of quantum circuits.<n>We study the expectation-value functions of families of tunable quantum circuits.<n>These results establish a quantitative resource-theoretic framework for delineating the boundary between classical simulation and learning.
  arXiv  Detail & Related papers  (2026-08-03T14:48:03Z)
• Evidential Quantum Vertical Federated Learning [19.065815604895818]
  We propose Evidential Quantum Vertical Federated Learning (eviQVFL) for privacy-preserving collaborative learning.<n>eviQVFL employs a hybrid classical-quantum architecture for party-side feature processing, mapping local features into a quantum state.<n>To preserve privacy and avoid information loss, party-side output states are directly transmitted to the server via quantum teleportation.
  arXiv  Detail & Related papers  (2026-03-22T07:36:21Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Computational Complexity of Learning Efficiently Generatable Pure States [11.180439223883962]
  We study the computational complexity of quantum state learning. We show that if unknown quantum states are promised to be pure states and efficiently generateable, then there exists a quantum time algorithm. We also observe the connection between the hardness of learning quantum states and quantum cryptography.
  arXiv  Detail & Related papers  (2024-10-06T06:25:36Z)
• 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)
• Pseudo-Entanglement is Necessary for EFI Pairs [0.0]
  We consider a new quantum resource, pseudo-entanglement, and show that the existence of EFI pairs implies the existence of pseudo-entanglement. Our result has important implications for the field of computational cryptography.
  arXiv  Detail & Related papers  (2024-06-11T01:44:16Z)
• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process. We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
  arXiv  Detail & Related papers  (2024-05-12T09:05:13Z)
• Exponential Quantum One-Wayness and EFI Pairs [18.481934628015004]
  In classical cryptography, one-way functions are widely considered to be the minimal computational assumption. There are currently two major candidates for the minimal assumption: the search quantum generalization of one-way functions are one-way state generators (OWSG) We show that IV-OWSGs are precisely equivalent to EFI pairs, with an exponential loss in the reduction.
  arXiv  Detail & Related papers  (2024-04-21T15:55:00Z)
• Entanglement Classification via Neural Network Quantum States [58.720142291102135]
  In this paper we combine machine-learning tools and the theory of quantum entanglement to perform entanglement classification for multipartite qubit systems in pure states. We use a parameterisation of quantum systems using artificial neural networks in a restricted Boltzmann machine (RBM) architecture, known as Neural Network Quantum States (NNS)
  arXiv  Detail & Related papers  (2019-12-31T07:40:23Z)

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.