Hardness of Quantum Distribution Learning and Quantum Cryptography

• URL: http://arxiv.org/abs/2507.01292v1
• Date: Wed, 02 Jul 2025 02:12:38 GMT
• Title: Hardness of Quantum Distribution Learning and Quantum Cryptography
• Authors: Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae,
• Abstract summary: One-way puzzles (OWPuzzs) provide a natural quantum analogue of one-way functions (OWFs)<n>In this paper, we establish the first complete characterization of OWPuzzs based on the hardness of a well-studied learning model: distribution learning.
• Score: 11.85957541950196
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The existence of one-way functions (OWFs) forms the minimal assumption in classical cryptography. However, this is not necessarily the case in quantum cryptography. One-way puzzles (OWPuzzs), introduced by Khurana and Tomer, provide a natural quantum analogue of OWFs. The existence of OWPuzzs implies $PP\neq BQP$, while the converse remains open. In classical cryptography, the analogous problem-whether OWFs can be constructed from $P \neq NP$-has long been studied from the viewpoint of hardness of learning. Hardness of learning in various frameworks (including PAC learning) has been connected to OWFs or to $P \neq NP$. In contrast, no such characterization previously existed for OWPuzzs. In this paper, we establish the first complete characterization of OWPuzzs based on the hardness of a well-studied learning model: distribution learning. Specifically, we prove that OWPuzzs exist if and only if proper quantum distribution learning is hard on average. A natural question that follows is whether the worst-case hardness of proper quantum distribution learning can be derived from $PP \neq BQP$. If so, and a worst-case to average-case hardness reduction is achieved, it would imply OWPuzzs solely from $PP \neq BQP$. However, we show that this would be extremely difficult: if worst-case hardness is PP-hard (in a black-box reduction), then $SampBQP \neq SampBPP$ follows from the infiniteness of the polynomial hierarchy. Despite that, we show that $PP \neq BQP$ is equivalent to another standard notion of hardness of learning: agnostic. We prove that $PP \neq BQP$ if and only if agnostic quantum distribution learning with respect to KL divergence is hard. As a byproduct, we show that hardness of agnostic quantum distribution learning with respect to statistical distance against $PPT^{\Sigma_3^P}$ learners implies $SampBQP \neq SampBPP$.

Related papers

• Quantum Cryptography and Hardness of Non-Collapsing Measurements [10.237675529033163]
  One-way puzzles (OWPuzzs) are a quantum analogue of one-way functions (OWFs)<n>In this paper, we base OWPuzzs on hardness of non-collapsing measurements.<n>We introduce a new primitive, distributional collision-resistant puzzles (dCRPuzzs)
  arXiv  Detail & Related papers  (2025-10-06T02:42:20Z)
• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  We show structural results for p/mBQP, p/mQ(C)MA, $textp/mQSZK_texthv$, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, and p/mPSPACE.<n>Surprisingly, our findings uncover relationships that diverge from their classical analogues.<n>For applications, we address interesting questions in quantum cryptography, quantum property testing, and unitary synthesis.
  arXiv  Detail & Related papers  (2024-11-06T07:29:52Z)
• Quantum Cryptography and Meta-Complexity [2.6089354079273512]
  In classical cryptography, one-way functions (OWFs) are the minimal assumption, while it is not the case in quantum cryptography. We show that one-way puzzles (OWPuzzs) exist if and only if GapK is weakly-quantum-average-hard. We also show that if quantum PRGs exist then GapK is strongly-quantum-average-hard.
  arXiv  Detail & Related papers  (2024-10-02T09:30:06Z)
• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  Recent separations have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if hierarchy collapses. We show that quantum cryptography can be based on the extremely mild assumption that $mathsfP#P notsubseteq mathsf(io)BQP/qpoly$.
  arXiv  Detail & Related papers  (2024-09-23T17:45:33Z)
• New Bounds on Quantum Sample Complexity of Measurement Classes [18.531114735719274]
  This paper studies quantum supervised learning for classical inference from quantum states. The hardness of learning is measured via sample complexity under a quantum counterpart of the well-known probably approximately correct (PAC)
  arXiv  Detail & Related papers  (2024-08-22T18:43:13Z)
• Proper vs Improper Quantum PAC learning [3.292420364429101]
  We present an algorithm for the Quantum Coupon Collector problem with sample complexity. We prove that its sample complexity matches that of the classical Coupon Collector problem for both modes of learning. We hope that padding can more generally lift other forms of classical learning behaviour to quantum setting.
  arXiv  Detail & Related papers  (2024-03-05T19:49:44Z)
• 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)
• Provable Advantage in Quantum PAC Learning [3.291862617649511]
  We show that PAC learners can achieve a generic advantage in quantum learning. Up to polylogarithmic factors, this is a square root improvement over the classical learning sample complexity.
  arXiv  Detail & Related papers  (2023-09-19T19:26:20Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

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.