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:2110.05517 · Physical Review Letters

One T Gate Makes Distribution Learning Hard

Marcel Hinsche, Marios Ioannou, Alexander Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter, Jean‐Pierre Seifert, Jens Eisert, Ryan Sweke

Published Jun 13, 2023• 65 citations
arXivHTMLPDF

Abstract

The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits are of central importance in both quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we extensively characterize the learnability of output distributions of local quantum circuits. Firstly, we contrast learnability with simulatability by showing that Clifford circuit output distributions are efficiently learnable, while the injection of a single T gate renders the density modeling task hard for any depth d=n^{Ω(1)}. We further show that the task of generative modeling universal quantum circuits at any depth d=n^{Ω(1)} is hard for any learning algorithm, classical or quantum, and that for statistical query algorithms, even depth d=ω[log(n)] Clifford circuits are hard to learn. Our results show that one cannot use the output distributions of local quantum circuits to provide a separation between the power of quantum and classical generative modeling algorithms, and therefore provide evidence against quantum advantages for practically relevant probabilistic modeling tasks.

DOI
10.1103/physrevlett.130.240602

Related papers

On the average-case complexity of learning output distributions of quantum circuits

Alexander Nietner, Marios Ioannou, Ryan Sweke +4 more

In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on n qubits of depth d , we show three main results:– At super logarithmic circuit depth d=ω(log⁡(n)) , any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance.– There exists a d=O(n) , such that any learning algorithm requires Ω(2n) queries to achieve a O(2−n) probability of success over the randomly drawn instance.– At infinite circuit depth d→∞ , any learning algorithm requires 22Ω(n) many queries to achieve a 2−2Ω(n) probability of success over the randomly drawn instance.As an auxiliary result of independent interest, we show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with probability 1−O(2−n) , which confirms a variant of a conjecture by Aaronson and Chen.

arXiv:2305.05765•Quantum•Oct 13, 2025•26 citations

Protocols for classically training quantum generative models on probability distributions

Sachin Kasture, Oleksandr Kyriienko, Vincent E. Elfving

Quantum generative modeling (QGM) relies on preparing quantum states and generating samples from these states as hidden---or known---probability distributions. As distributions from some classes of quantum states (circuits) are inherently hard to sample classically, QGM represents an excellent test bed for quantum supremacy experiments. Furthermore, generative tasks are increasingly relevant for industrial machine learning applications, and thus QGM is a strong candidate for demonstrating a practical quantum advantage. However, this requires that quantum circuits are trained to represent industrially relevant distributions, and the corresponding training stage has an extensive training cost for current quantum hardware in practice. In this work, we propose protocols for classical training of QGMs based on circuits of the specific type that admit an efficient gradient computation, while remaining hard to sample. In particular, we consider instantaneous quantum polynomial (IQP) circuits and their extensions. Showing their classical simulability in terms of the time complexity, sparsity, and anticoncentration properties, we develop a classically tractable way of simulating their output probability distributions, allowing classical training to a target probability distribution. The corresponding quantum sampling from IQPs can be performed efficiently, unlike when using classical sampling. We numerically demonstrate the end-to-end training of IQP circuits using probability distributions for up to 30 qubits on a regular desktop computer. When applied to industrially relevant distributions this combination of classical training with quantum sampling represents an avenue for reaching advantage in the noisy intermediate-scale quantum (NISQ) era.

arXiv:2210.13442•Physical Review A•Oct 5, 2023•19 citations

Prospects for quantum advantage in machine learning from the representability of functions

Sergi Masot-Llima, Elies Gil-Fuster, Carlos Bravo-Prieto +2 more

Demonstrating quantum advantage in machine learning tasks requires navigating a complex landscape of proposed models and algorithms. To bring clarity to this search, we introduce a framework that connects the structure of parametrized quantum circuits to the mathematical nature of the functions they can actually learn. Within this framework, we show how fundamental properties, like circuit depth and non-Clifford gate count, directly determine whether a model's output leads to efficient classical simulation or surrogation. We argue that this analysis uncovers common pathways to dequantization that underlie many existing simulation methods. More importantly, it reveals critical distinctions between models that are fully simulatable, those whose function space is classically tractable, and those that remain robustly quantum. This perspective provides a conceptual map of this landscape, clarifying how different models relate to classical simulability and pointing to where opportunities for quantum advantage may lie.

quant-pharXiv:2512.15661•Dec 18, 2025•8 citations

Differentiable learning of quantum circuit Born machines

Jin-Guo Liu, Lei Wang

Quantum circuit Born machines are generative models which represent the probability distribution of classical dataset as quantum pure states. Computational complexity considerations of the quantum sampling problem suggest that the quantum circuits exhibit stronger expressibility compared to classical neural networks. One can efficiently draw samples from the quantum circuits via projective measurements on qubits. However, similar to the leading implicit generative models in deep learning, such as the generative adversarial networks, the quantum circuits cannot provide the likelihood of the generated samples, which poses a challenge to the training. We devise an efficient gradient-based learning algorithm for the quantum circuit Born machine by minimizing the kerneled maximum mean discrepancy loss. We simulated generative modeling of the BARS-AND-STRIPES dataset and Gaussian mixture distributions using deep quantum circuits. Our experiments show the importance of circuit depth and the gradient-based optimization algorithm. The proposed learning algorithm is runnable on near-term quantum device and can exhibit quantum advantages for probabilistic generative modeling.

arXiv:1804.04168•Physical Review A•Dec 19, 2018•337 citations

Limits of quantum generative models with classical sampling hardness

Sabrina Herbst, Ivona Brandić, Adrián Pérez-Salinas

Sampling tasks have been successful in establishing quantum advantages both in theory and experiments. This has fueled the use of quantum computers for generative modeling to create samples following the probability distribution underlying a given dataset. In particular, the potential to build generative models on classically hard distributions would immediately preclude classical simulability, due to theoretical separations. In this work, we study quantum generative models from the perspective of output distributions, showing that models that anticoncentrate are not trainable on average, including those exhibiting quantum advantage. In contrast, models outputting data from sparse distributions can be trained. We consider special cases to enhance trainability, and observe that this opens the path for classical algorithms for surrogate sampling. This observed trade-off is linked to verification of quantum processes. We conclude that quantum advantage can still be found in generative models, although its source must be distinct from anticoncentration.

quant-pharXiv:2512.24801•Jan 1, 2026•10 citations

Complexity phase transitions in instantaneous quantum polynomial-time circuits

Chae-Yeun Park, Michael J. Kastoryano

We study the classical hardness of learning the output distribution from instantaneous quantum polynomial-time circuits with a varying density of two-qubit gates. We first investigate the complexity phases relevant to simulating the output distribution. In addition to a known parameter regime for anticoncentration, where the classical simulation is believed to be infeasible, we identify a novel parameter condition such that the classically simulability of the circuit can be proven rigorously. Next, we explore the classical learnability of the output distribution. We prove that a circuit instance whose output distribution is not classically learnable exists, assuming the hardness of learning parity with noise. We numerically study this phenomenon deeply using a classical energy-based model, where we find that the classical model fails to learn the output distribution even when the density of two-qubit gates is much smaller than that for the anticoncentration. We argue that this is mainly due to the fact that an accurate classical description of the output distribution requires exponentially large amount of resources.

arXiv:2204.08898•Physical Review Research•Jan 2, 2025•3 citations
The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits are of central importance in both quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we extensively characterize the learnability of output distributions of local quantum circuits. Firstly, we contrast learnability with simulatability by showing that Clifford circuit output distributions are efficiently learnable, while the injection of a single T gate renders the density modeling task hard for any depth d=n^{Ω(1)}. We further show that the task of generative modeling universal quantum circuits at any depth d=n^{Ω(1)} is hard for any learning algorithm, classical or quantum, and that for statistical query algorithms, even depth d=ω[log(n)] Clifford circuits are hard to learn. Our results show that one cannot use the output distributions of local quantum circuits to provide a separation between the power of quantum and classical generative modeling algorithms, and therefore provide evidence against quantum advantages for practically relevant probabilistic modeling tasks.
In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on n qubits of depth d , we show three main results:– At super logarithmic circuit depth d=ω(log⁡(n)) , any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance.– There exists a d=O(n) , such that any learning algorithm requires Ω(2n) queries to achieve a O(2−n) probability of success over the randomly drawn instance.– At infinite circuit depth d→∞ , any learning algorithm requires 22Ω(n) many queries to achieve a 2−2Ω(n) probability of success over the randomly drawn instance.As an auxiliary result of independent interest, we show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with probability 1−O(2−n) , which confirms a variant of a conjecture by Aaronson and Chen.
Quantum generative modeling (QGM) relies on preparing quantum states and generating samples from these states as hidden---or known---probability distributions. As distributions from some classes of quantum states (circuits) are inherently hard to sample classically, QGM represents an excellent test bed for quantum supremacy experiments. Furthermore, generative tasks are increasingly relevant for industrial machine learning applications, and thus QGM is a strong candidate for demonstrating a practical quantum advantage. However, this requires that quantum circuits are trained to represent industrially relevant distributions, and the corresponding training stage has an extensive training cost for current quantum hardware in practice. In this work, we propose protocols for classical training of QGMs based on circuits of the specific type that admit an efficient gradient computation, while remaining hard to sample. In particular, we consider instantaneous quantum polynomial (IQP) circuits and their extensions. Showing their classical simulability in terms of the time complexity, sparsity, and anticoncentration properties, we develop a classically tractable way of simulating their output probability distributions, allowing classical training to a target probability distribution. The corresponding quantum sampling from IQPs can be performed efficiently, unlike when using classical sampling. We numerically demonstrate the end-to-end training of IQP circuits using probability distributions for up to 30 qubits on a regular desktop computer. When applied to industrially relevant distributions this combination of classical training with quantum sampling represents an avenue for reaching advantage in the noisy intermediate-scale quantum (NISQ) era.
Demonstrating quantum advantage in machine learning tasks requires navigating a complex landscape of proposed models and algorithms. To bring clarity to this search, we introduce a framework that connects the structure of parametrized quantum circuits to the mathematical nature of the functions they can actually learn. Within this framework, we show how fundamental properties, like circuit depth and non-Clifford gate count, directly determine whether a model's output leads to efficient classical simulation or surrogation. We argue that this analysis uncovers common pathways to dequantization that underlie many existing simulation methods. More importantly, it reveals critical distinctions between models that are fully simulatable, those whose function space is classically tractable, and those that remain robustly quantum. This perspective provides a conceptual map of this landscape, clarifying how different models relate to classical simulability and pointing to where opportunities for quantum advantage may lie.
Quantum circuit Born machines are generative models which represent the probability distribution of classical dataset as quantum pure states. Computational complexity considerations of the quantum sampling problem suggest that the quantum circuits exhibit stronger expressibility compared to classical neural networks. One can efficiently draw samples from the quantum circuits via projective measurements on qubits. However, similar to the leading implicit generative models in deep learning, such as the generative adversarial networks, the quantum circuits cannot provide the likelihood of the generated samples, which poses a challenge to the training. We devise an efficient gradient-based learning algorithm for the quantum circuit Born machine by minimizing the kerneled maximum mean discrepancy loss. We simulated generative modeling of the BARS-AND-STRIPES dataset and Gaussian mixture distributions using deep quantum circuits. Our experiments show the importance of circuit depth and the gradient-based optimization algorithm. The proposed learning algorithm is runnable on near-term quantum device and can exhibit quantum advantages for probabilistic generative modeling.
Sampling tasks have been successful in establishing quantum advantages both in theory and experiments. This has fueled the use of quantum computers for generative modeling to create samples following the probability distribution underlying a given dataset. In particular, the potential to build generative models on classically hard distributions would immediately preclude classical simulability, due to theoretical separations. In this work, we study quantum generative models from the perspective of output distributions, showing that models that anticoncentrate are not trainable on average, including those exhibiting quantum advantage. In contrast, models outputting data from sparse distributions can be trained. We consider special cases to enhance trainability, and observe that this opens the path for classical algorithms for surrogate sampling. This observed trade-off is linked to verification of quantum processes. We conclude that quantum advantage can still be found in generative models, although its source must be distinct from anticoncentration.
We study the classical hardness of learning the output distribution from instantaneous quantum polynomial-time circuits with a varying density of two-qubit gates. We first investigate the complexity phases relevant to simulating the output distribution. In addition to a known parameter regime for anticoncentration, where the classical simulation is believed to be infeasible, we identify a novel parameter condition such that the classically simulability of the circuit can be proven rigorously. Next, we explore the classical learnability of the output distribution. We prove that a circuit instance whose output distribution is not classically learnable exists, assuming the hardness of learning parity with noise. We numerically study this phenomenon deeply using a classical energy-based model, where we find that the classical model fails to learn the output distribution even when the density of two-qubit gates is much smaller than that for the anticoncentration. We argue that this is mainly due to the fact that an accurate classical description of the output distribution requires exponentially large amount of resources.