Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2210.14936

A super-polynomial quantum-classical separation for density modelling

Niklas Pirnay, Ryan Sweke, Jens Eisert, Jean‐Pierre Seifert

Published Oct 26, 2022• 4 citations
arXivHTMLPDF

Abstract

Density modelling is the task of learning an unknown probability density function from samples, and is one of the central problems of unsupervised machine learning. In this work, we show that there exists a density modelling problem for which fault-tolerant quantum computers can offer a super-polynomial advantage over classical learning algorithms, given standard cryptographic assumptions. Along the way, we provide a variety of additional results and insights, of potential interest for proving future distribution learning separations between quantum and classical learning algorithms. Specifically, we (a) provide an overview of the relationships between hardness results in supervised learning and distribution learning, and (b) show that any weak pseudo-random function can be used to construct a classically hard density modelling problem. The latter result opens up the possibility of proving quantum-classical separations for density modelling based on weaker assumptions than those necessary for pseudo-random functions.

DOI
10.48550/arxiv.2210.14936

Related papers

On provable quantum advantages in combinatorial optimization and distribution learning

Pirnay, Niklas

This dissertation investigates the fundamental computational capabilities of quantum algorithms with respect to combinatorial optimization and distribution learning. We establish rigorous quantum advantages over classical algorithms for such problems under both widely accepted cryptographic assumptions and unconditionally. First, we demonstrate a super-polynomial quantum advantage for approximating solutions to combinatorial optimization problems, explicitly constructing advantage-bearing instances of Integer Linear Programming. Our proofs build upon approximation hardness results that instantiate a connection between the representation-independent hardness of learning and approximation hardness, as captured by Occam’s razor within computational learning theory. We show that the instances we construct can be efficiently approximated by quantum algorithms utilizing Shor’s factoring algorithm, yet remain classically intractable unless standard cryptographic assumptions fail. Second, we fill a previously open gap by proving a super-polynomial quantum advantage for learning the density function of probability distributions, complementing prior results established for generative distribution learning. We show that the hardness of density modeling can be established under weaker cryptographic assumptions involving pseudorandom functions. The quantum advantage for density modeling fundamentally arises from Shor’s algorithm for computing discrete logarithms. Moreover, we explicitly articulate known connections between Boolean function learning hardness and distribution learning hardness using established constructions. Third, addressing practical constraints of near-term quantum devices, we establish an unconditional quantum advantage for generative distribution learning using shallow, constant-depth quantum circuits. We find that shallow quantum circuits pose a superior class of hypotheses compared to classical counterparts. This result underscores the potential of near-term quantum hardware by highlighting the unique computational capabilities enabled by quantum entanglement and non-local correlations, offered even by constrained devices. Collectively, these contributions deepen our understanding of quantum computational advantages for combinatorial optimization and distribution learning, clarifying their foundations and pointing toward promising avenues for future exploration.

•Jan 1, 2025•0 citations

Classical Hardness of Learning Functions of Hamiltonians

Sota Hashimoto, Akinori Kawachi

Morohoshi, Nakayama, Manabe, and Mitarai proposed a physically motivated quantum machine learning problem in which the goal is to predict quantities of the form $\operatorname{Tr}[f(H)ρ]$ from classical descriptions of a Hamiltonian $H$ and a quantum state $ρ$, where $f$ is an unknown function. We call this problem Hamiltonian function learning in this paper. They constructed an efficient quantum learning algorithm under suitable conditions, while leaving a rigorous proof of average-case classical hardness open. In this paper, we rigorously prove the average-case classical hardness for two distribution-specific Hamiltonian function learning problems for $f_{\cos,π}(λ)=\cos(πλ)$ and $f_{\exp,β}(λ)=e^{-βλ}$ discussed in the paper of Morohoshi et al. under the assumption of the average-case hardness of factoring random RSA moduli. More specifically, we show that an efficient classical randomized learner under squared loss whose output hypotheses are evaluable in classical polynomial time for either problem would yield a classical randomized polynomial-time algorithm for factoring random RSA moduli.

quant-pharXiv:2610.01141•Oct 2, 2026•0 citations

Unconditional Quantum PAC Learning Advantage in the Large Error Regime

Igor C. Oliveira

We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage $λ(n) = n^{-ω(1)}$, we construct a concept class that a polynomial-time quantum learner learns to agreement $1/2+λ(n)$ with success probability at least $1-1/n^k$. The learner uses only quantum random examples and outputs a polynomial-size deterministic classical circuit. In contrast, no polynomial-time classical learner achieves agreement $1/2 + λ(n)/n^k$ with success probability greater than $1/n^k$, even with membership queries. To achieve this, we develop a nearly-optimal quantum learner that uses quantum random examples to produce a hypothesis achieving a prescribed correlation with an arbitrary Boolean function. The learner generalizes Fourier sampling from parity hypotheses to quadratic hypotheses. While standard Fourier sampling is insensitive to the sign of the correlation, we use interference to bias sampling toward positively correlated hypotheses. This is combined with a careful analysis of the resulting distribution to boost both the learner's success probability and its agreement with the target function. We believe that the resulting quantum learning algorithm might be of independent interest. Finally, although a robust quantum PAC learning advantage holds unconditionally in the large error regime, we note that an analogous separation between quantum and classical learning in the small error regime would imply that $\mathsf{NP} \nsubseteq \mathsf{BPP}$.

cs.CCCross-listedarXiv:2610.23268•Oct 19, 2026•0 citations

Superpolynomial quantum-classical separation for density modeling

Niklas Pirnay, Ryan Sweke, Jens Eisert +1 more

Density modeling is a machine learning task with the goal of learning an underlying probability distribution from samples. Here the authors show that, when solving certain density modeling problems, algorithms that use fault-tolerant quantum computers have an advantage over classical ones.

Physical Review A•Apr 13, 2023•18 citations

Learnability of the output distributions of local quantum circuits

Marcel Hinsche, Marios Ioannou, Alexander Nietner +6 more

There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries -- including those for training quantum circuit Born machines -- our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective.

arXiv:2110.05517•Oct 11, 2021•8 citations

Quantum machine learning advantages beyond hardness of evaluation

Riccardo Molteni, Simon C. Marshall, Vedran Dunjko

The most general examples of quantum learning advantages involve data labeled by cryptographic or intrinsically quantum functions, where classical learners are limited by the infeasibility of evaluating the labeling functions using polynomial-sized classical circuits. While broad in scope, such results reveal little about advantages arising from the learning process itself. In cryptographic settings, further insight is possible via random-generatability - the ability to classically generate labeled data - enabling hardness proofs for identification tasks, where the goal is to identify the labeling function from a dataset, even when evaluation is classically intractable. These tasks are particularly relevant in quantum contexts, including Hamiltonian learning and identifying physically meaningful order parameters. However, for quantum functions, random-generatability is conjectured not to hold, leaving no known identification advantages in genuinely quantum regimes. In this work, we give the first proofs of quantum identification learning advantages under standard complexity assumptions. We confirm that quantum-hard functions are not random-generatable unless BQP is contained in the second level of the polynomial hierarchy, ruling out cryptographic-style data generation strategies. We then introduce a new approach: we show that verifiable identification - solving the identification task for valid datasets while rejecting invalid ones - is classically hard for quantum labeling functions unless BQP is in the polynomial hierarchy. Finally, we show that, for a broad class of tasks, solving the identification problem implies verifiable identification in the polynomial hierarchy. This yields our main result: a natural class of quantum identification tasks solvable by quantum learners but hard for classical learners unless BQP is in the polynomial hierarchy.

arXiv:2504.15964•Apr 22, 2025•0 citations
Density modelling is the task of learning an unknown probability density function from samples, and is one of the central problems of unsupervised machine learning. In this work, we show that there exists a density modelling problem for which fault-tolerant quantum computers can offer a super-polynomial advantage over classical learning algorithms, given standard cryptographic assumptions. Along the way, we provide a variety of additional results and insights, of potential interest for proving future distribution learning separations between quantum and classical learning algorithms. Specifically, we (a) provide an overview of the relationships between hardness results in supervised learning and distribution learning, and (b) show that any weak pseudo-random function can be used to construct a classically hard density modelling problem. The latter result opens up the possibility of proving quantum-classical separations for density modelling based on weaker assumptions than those necessary for pseudo-random functions.
This dissertation investigates the fundamental computational capabilities of quantum algorithms with respect to combinatorial optimization and distribution learning. We establish rigorous quantum advantages over classical algorithms for such problems under both widely accepted cryptographic assumptions and unconditionally. First, we demonstrate a super-polynomial quantum advantage for approximating solutions to combinatorial optimization problems, explicitly constructing advantage-bearing instances of Integer Linear Programming. Our proofs build upon approximation hardness results that instantiate a connection between the representation-independent hardness of learning and approximation hardness, as captured by Occam’s razor within computational learning theory. We show that the instances we construct can be efficiently approximated by quantum algorithms utilizing Shor’s factoring algorithm, yet remain classically intractable unless standard cryptographic assumptions fail. Second, we fill a previously open gap by proving a super-polynomial quantum advantage for learning the density function of probability distributions, complementing prior results established for generative distribution learning. We show that the hardness of density modeling can be established under weaker cryptographic assumptions involving pseudorandom functions. The quantum advantage for density modeling fundamentally arises from Shor’s algorithm for computing discrete logarithms. Moreover, we explicitly articulate known connections between Boolean function learning hardness and distribution learning hardness using established constructions. Third, addressing practical constraints of near-term quantum devices, we establish an unconditional quantum advantage for generative distribution learning using shallow, constant-depth quantum circuits. We find that shallow quantum circuits pose a superior class of hypotheses compared to classical counterparts. This result underscores the potential of near-term quantum hardware by highlighting the unique computational capabilities enabled by quantum entanglement and non-local correlations, offered even by constrained devices. Collectively, these contributions deepen our understanding of quantum computational advantages for combinatorial optimization and distribution learning, clarifying their foundations and pointing toward promising avenues for future exploration.
Morohoshi, Nakayama, Manabe, and Mitarai proposed a physically motivated quantum machine learning problem in which the goal is to predict quantities of the form Tr⁡[f(H)ρ]\operatorname{Tr}[f(H)ρ]Tr[f(H)ρ] from classical descriptions of a Hamiltonian HHH and a quantum state ρρρ, where fff is an unknown function. We call this problem Hamiltonian function learning in this paper. They constructed an efficient quantum learning algorithm under suitable conditions, while leaving a rigorous proof of average-case classical hardness open. In this paper, we rigorously prove the average-case classical hardness for two distribution-specific Hamiltonian function learning problems for fcos⁡,π(λ)=cos⁡(πλ)f_{\cos,π}(λ)=\cos(πλ)fcos,π​(λ)=cos(πλ) and fexp⁡,β(λ)=e−βλf_{\exp,β}(λ)=e^{-βλ}fexp,β​(λ)=e−βλ discussed in the paper of Morohoshi et al. under the assumption of the average-case hardness of factoring random RSA moduli. More specifically, we show that an efficient classical randomized learner under squared loss whose output hypotheses are evaluable in classical polynomial time for either problem would yield a classical randomized polynomial-time algorithm for factoring random RSA moduli.
We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage λ(n)=n−ω(1)λ(n) = n^{-ω(1)}λ(n)=n−ω(1), we construct a concept class that a polynomial-time quantum learner learns to agreement 1/2+λ(n)1/2+λ(n)1/2+λ(n) with success probability at least 1−1/nk1-1/n^k1−1/nk. The learner uses only quantum random examples and outputs a polynomial-size deterministic classical circuit. In contrast, no polynomial-time classical learner achieves agreement 1/2+λ(n)/nk1/2 + λ(n)/n^k1/2+λ(n)/nk with success probability greater than 1/nk1/n^k1/nk, even with membership queries. To achieve this, we develop a nearly-optimal quantum learner that uses quantum random examples to produce a hypothesis achieving a prescribed correlation with an arbitrary Boolean function. The learner generalizes Fourier sampling from parity hypotheses to quadratic hypotheses. While standard Fourier sampling is insensitive to the sign of the correlation, we use interference to bias sampling toward positively correlated hypotheses. This is combined with a careful analysis of the resulting distribution to boost both the learner's success probability and its agreement with the target function. We believe that the resulting quantum learning algorithm might be of independent interest. Finally, although a robust quantum PAC learning advantage holds unconditionally in the large error regime, we note that an analogous separation between quantum and classical learning in the small error regime would imply that NP⊈BPP\mathsf{NP} \nsubseteq \mathsf{BPP}NP⊈BPP.
There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries -- including those for training quantum circuit Born machines -- our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective.
The most general examples of quantum learning advantages involve data labeled by cryptographic or intrinsically quantum functions, where classical learners are limited by the infeasibility of evaluating the labeling functions using polynomial-sized classical circuits. While broad in scope, such results reveal little about advantages arising from the learning process itself. In cryptographic settings, further insight is possible via random-generatability - the ability to classically generate labeled data - enabling hardness proofs for identification tasks, where the goal is to identify the labeling function from a dataset, even when evaluation is classically intractable. These tasks are particularly relevant in quantum contexts, including Hamiltonian learning and identifying physically meaningful order parameters. However, for quantum functions, random-generatability is conjectured not to hold, leaving no known identification advantages in genuinely quantum regimes. In this work, we give the first proofs of quantum identification learning advantages under standard complexity assumptions. We confirm that quantum-hard functions are not random-generatable unless BQP is contained in the second level of the polynomial hierarchy, ruling out cryptographic-style data generation strategies. We then introduce a new approach: we show that verifiable identification - solving the identification task for valid datasets while rejecting invalid ones - is classically hard for quantum labeling functions unless BQP is in the polynomial hierarchy. Finally, we show that, for a broad class of tasks, solving the identification problem implies verifiable identification in the polynomial hierarchy. This yields our main result: a natural class of quantum identification tasks solvable by quantum learners but hard for classical learners unless BQP is in the polynomial hierarchy.