Researchers have demonstrated that constant-depth quantum circuits using one and two qubit gates outperform their classical counterparts for a specific machine learning task. N. Pirnay of Technische Universität Berlin and colleagues proved an unconditional quantum advantage within the probably approximately correct (PAC) distribution learning framework, identifying a generative distribution learning problem where shallow quantum circuits excel.

The work builds on previous sampling advances by Bene Watts and Parham, technically extending those results to a hyperplane learning problem and pinpointing non-local correlations as the source of the quantum benefit. This finding offers a pathway toward practical applications for near-term quantum computers.

PAC Distribution Learning with Shallow Quantum Circuits

This finding identifies a specific generative distribution learning problem where constant-depth quantum circuits outperform their classical counterparts, a key step toward realizing practical applications for near-term quantum computers. The research focuses on comparing quantum circuits comprised of one and two qubit gates to constant-depth classical circuits with bounded fan-in gates as hypothesis classes within the learning framework.

The team’s work centers on the probably approximately correct (PAC) learning framework, a rigorous machine learning paradigm used to define the conditions under which an algorithm can reliably learn a distribution. Their analysis defines a target distribution class, built from constant-depth quantum circuits and classical circuits, and then demonstrates a learning algorithm using quantum circuits that surpasses the capabilities of classical algorithms for this specific class.

This advantage isn’t merely theoretical; it’s a quantifiable difference in the ability to accurately generate distributions, as measured by the total variation distance between the learned and original distributions. Specifically, the researchers constructed a distribution based on a function they term a component important to their learning algorithm. This construction allows for a comparison of learning performance between the quantum and classical circuits, revealing the origin of the quantum advantage.

The theorem established in the work, Theorem IV. 1, states that the hypothesis choice of quantum circuits yields an advantage in total variation distance of at least 1/π minus a term that diminishes with the size of the input. While related to the broader challenge of learning shallow quantum circuits themselves, the current work focuses on a distinct problem: learning from shallow quantum circuits as generators.

The researchers acknowledge that further work is needed to extend these findings to unstructured data and bring the ideas closer to practical implementation. They write, suggesting that this result may lead to more complex and applicable quantum learning algorithms. The team, including S. Jerbi and J.-P. Seifert of Technische Universität Berlin, along with J. Eisert from Freie Universität Berlin, Fraunhofer Heinrich Hertz Institute and Helmholtz-Zentrum für Materialien und Energie, built on previous results by Bene Watts and Parham on shallow circuit sampling to achieve this advancement.

Constant-Depth Quantum Circuits vs. Classical Circuit Hypotheses

The ability to learn a distribution with a constant-depth quantum circuit surpasses that of its classical counterparts, according to a new theoretical demonstration. The work centers on learning a generator for a distribution defined as D_n, where the output is determined by a majority mod p operation under hyperplane s, combined with a parity check. Learning this generator requires identifying the hyperplane s from a set of examples drawn from D_n. Theorem IV.

Any classical circuit requiring n + n^δ random bits as input and achieving similar proximity to D_n must have a depth of Ω(log log n). The researchers emphasize that the concept class studied is polynomial in size, aligning with common settings in classical PAC learning theory. This contrasts with some quantum machine learning proposals that rely on exponentially large feature spaces.

“We are now in a position to state our main result, which is a meaningful advantage of a shallow quantum circuit over instances of classical circuits in a well-defined learning task,” the paper states. The study highlights that learning with constant-depth hypotheses is also a well-established area of research within classical learning theory, providing a valuable point of comparison.

The implications extend beyond the specific distribution D_n. The researchers suggest that this work identifies a learning problem where shallow quantum circuits demonstrably outperform classical circuits, offering a concrete example of a quantum advantage in a machine learning context. This is distinct from simply demonstrating that a quantum computer can solve a problem. It shows that a quantum circuit offers a superior approach to learning a specific type of distribution.

Uplifting Sampling to Hyperplane Learning for Advantage

The work establishes a separation in a sampling problem, introducing a class of distributions where a constant-depth quantum circuit samples with higher fidelity than any comparable classical circuit could achieve. The researchers constructed a PAC generator learning problem by introducing a “majority mod p under hyperplane s” function, generalizing a previously established “majority mod p” function central to their sampling constructions.

This function, defined for each input x in 0, $1^{n - 1}$ , prime p, and hyperplane s, allows for the creation of a learning task where the goal is to generate a distribution closely resembling an unknown target distribution. The team’s approach effectively transforms the sampling advantage into a learning advantage, moving beyond a single distribution per problem size to a more robust learning scenario. The core finding, detailed in Theorem IV.

The researchers note this advantage is achieved by using the “poor man’s majority mod p” function within their framework.

Non-Local Correlations as Origin of Quantum Learnability

Building on recent advances in quantum sampling, researchers have technically extended those results to demonstrate how non-local correlations within quantum circuits drive a learning advantage over classical counterparts. This work identifies a specific mechanism behind the observed quantum speedup, moving beyond simply demonstrating a computational edge to pinpointing its origin within the quantum system. The team achieved this by transforming a sampling problem, previously shown to favor shallow quantum circuits, into a hyperplane learning problem, a common task in machine learning.

This difference in computational complexity establishes a clear separation between the capabilities of shallow quantum and classical circuits for this particular learning task. The researchers used a family of distributions, denoted as $D_{n}$ , where the quantum circuit’s approximation closely matches the target distribution, while classical circuits struggle to achieve the same level of proximity.

The state vector of the final qubit, after measuring the initial 2n-2 qubits, is approximately described by a cosine and sine function, dependent on the sum of inputs and the parameter s. This approximation is critical, as it allows for the efficient generation of the target distribution using the quantum circuit. The researchers emphasize that the observed quantum advantage is a demonstrable benefit rooted in the non-local correlations present in the quantum state. These correlations, inherent to the way quantum circuits manipulate information, are fundamentally different from the correlations achievable with classical circuits, and are the key to unlocking this learning advantage.

Role of Measurements in Preparing Quantum States

Measurements, though not employed mid-circuit, are integral to preparing the quantum states that demonstrate an advantage in distribution learning, a nuance often discussed in both quantum computing and condensed matter physics research. This preparation results in what the researchers term a ‘binary tree poor man’s GHZ state’, highlighting the important role of measurement in state preparation even when not used for mid-circuit correction. The ability to generate this approximate distribution hinges on the circuit’s capacity to create non-local correlations, which the researchers identify as the origin of the quantum advantage.

Source: https://www.nature.com/articles/s41534-026-01370-4

More like this