Computational reach of machine learning models is independent of untrained quantum resources

arXiv:2309.13967 · quant-ph · Submitted 2023-09-25 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Computational reach of machine learning models is independent of untrained quantum resources".

Mira: Here's the gist of the paper. The gist: This paper proves that if an untrained quantum circuit is used as a resource in a machine learning workflow, then on average no quantum circuit is better than any other that can achieve the same set of computational effects.

Kai: No Free Lunch Theorem The titular no free lunch theorem states that if an untrained quantum circuit is used as a resource in a machine learning workflow, then on average no quantum circuit is better than any other that can achieve the same set of computational effects This result casts serious doubt on several proposals to use untrained quantum circuits in machine learning workflows.

Mira: The paper also proves a supporting theorem that even if the idealisations of the no free lunch theorem are omitted, the average quantum advantage remains negligible at best.

Kai: Resource Theories and Model Structures The analysis begins by introducing resource theories to explain no free lunch theorems, focusing on whether samples obtained by measuring a certain quantum state are more useful on average.

Title and authors: Kai: So we're looking at this paper today by Steven Herbert from Quantinuum about this no free lunch theorem for untrained quantum circuits in machine learning.

Mira: It’s a really strong claim, Kai, suggesting that on average, you can't get better performance just by throwing an untrained circuit into a workflow.

Lev: From my side, I’m wondering what the real hardware implications are for us if we start relying on these random circuits.

Kai: Well, the core idea is that if you use an untrained quantum circuit as a resource in a machine learning workflow, it doesn't actually give you any advantage on average over another circuit that achieves the same set of computational effects.

Mira: That means if we're building these generative models, the specific quantum state we measure from an untrained circuit isn't going to make us fundamentally better at generating the target samples unless there’s some hidden reason for it.

Lev: If you're running this on actual hardware, that means your error correction overhead is just going to be spent preparing something that doesn't actually help the model learn anything new.

Kai: The paper formalizes this using resource theories, looking at how samples from a measured quantum state might reduce the cost of preparing the target distributions.

Mira: They define two main ways an untrained circuit can act as a resource: either you pass your input through it and measure the output, or it just produces a static state that doesn't change based on your input.

Lev: That separation is important because it lets us analyze the cost of preparing permutations versus just using that fixed state, which is where the gate count comparison comes in.

Kai: They define a cost function c(P) for preparing a family of target distributions, which is either the minimum number of gates from some gateset that implements P or a binary value if a circuit with fewer gates than some threshold exists.

Mira: And they talk about equivalence classes for permutations based on whether two permutations have identical output statistics, defining the overall cost C as the sum of minimal costs for each class.

Lev: That cost definition is key because it ties the quantum resource directly to how complex it is to implement those specific computational effects we care about.

Kai: The main proof, Theorem twenty-two establishes this no free lunch theorem for models where nx equals zero stating that if U zero⟩ is distinct and 2n+ distinct, then there's no free lunch.

Mira: This relies on Lemma nineteen showing that for distinct and 2n+ distinct states, multiplicative equivalence classes are the same as permutation equivalence classes.

Lev: That structural link between the equivalences is what lets them conclude that the set of computational effects can be defined independently of your input state, which really supports the no free lunch claim.

Kai: They also address two major idealisations: first, that every possible computational effect is treated as equally important, and second, that the resource states are distinct and 2n+ distinct <ref:2309.13967#pg3>.

Mira: They show that you need distinctness by building a counter-example where different resource states give different average costs.

Lev: And when you relax the idea that every effect is equally important, they use a relaxed notion of cost C˜ and Theorem thirty-one shows C˜ is bounded from below by e nin, while Theorem thirty-two shows circuits exist where it's bounded from above by e nin.

Kai: So the conclusion here is that the exhaustive list of computational effects that can be achieved in a machine learning workflow is independent of any untrained resource quantum circuit almost surely.

Mira: This means if there isn't some hidden bias toward certain computational effects, then no resource quantum circuit will outperform another one that achieves the same set of effects.

Lev: That suggests that any advantage we see in proof-of-principle demonstrations will likely persist as the size increases, implying there must be some reason why the untrained circuit is well matched to the problem space we're interested in.

Kai: It’s a big statement because it casts serious doubt on proposals to use untrained quantum circuits just because they look interesting or simple.

Mira: We're talking about something that suggests we need an actual reason, not just a hope, before we introduce these kinds of resources into our machine learning pipelines.

Lev: If you're running this on real hardware, the overhead for preparing that resource state is going to be negligible compared to the error correction we already have to deal with.

Kai: So yeah, that’s what this paper argues about in "Computational reach of machine learning models is independent of untrained quantum resources."

Mira: It boils down to the idea that without a specific reason why an untrained circuit would help, you shouldn't introduce it for better performance.

Lev: If we're going to build something on this, we need to focus on those real-world costs and see if any of these theoretical bounds actually translate into useful engineering constraints.

The paper's summary: Kai: So, to wrap up what we just talked about, this paper argues that if you use an untrained quantum circuit as a resource in any machine learning workflow, on average it doesn't give you any advantage over another circuit that achieves the same computational effects.

Mira: Exactly. It’s not about finding a magical random state that helps your generative model perform better than one built with a standard, trained resource. It suggests that if there isn't some specific reason why an untrained circuit would help, you shouldn't introduce it just because it looks interesting or simple.

Lev: From the error correction side, this means that the overhead you spend preparing that random state is essentially wasted in terms of computational advantage for the model itself. You still have to deal with all the usual noise and gate complexity when running on real hardware.

Kai: I mean, it’s a strong claim because it basically says that the set of computational effects you can achieve with any given machine learning workflow is independent of any untrained resource quantum circuit almost surely.

Mira: That really puts things in perspective for generative models. If we're trying to convert samples from a latent distribution into target samples, the specific quantum state we pick from an untrained circuit won't fundamentally change how useful that state is on average compared to other possibilities.

Lev: So, if you’re building a system with deep circuits or complex error correction, this means you don't get any extra efficiency boost just by swapping in a random resource. The complexity required to achieve those computational effects remains the same regardless of which untrained circuit you use.

Kai: It implies that if there isn't some a priori bias toward certain computational effects, then no quantum circuit will outperform another one that achieves the same set of effects.

Mira: And this whole thing really hinges on these resource theories they introduced earlier, looking at how samples from a measured state might reduce the cost of preparing those target distributions. It’s about quantifying that "resource value."

Lev: So, what does this mean for us building actual hardware? It means we don't need to hunt for some exotic random circuit to beat the exponential bounds we already expect. The expected complexity is still there, but it’s not being lowered by an untrained resource in this way.

Kai: It's a big statement because it casts serious doubt on proposals to use untrained quantum circuits just because they look interesting or simple.

Mira: We're talking about something that suggests we need an actual reason, not just a hope, before we introduce these kinds of resources into our machine learning pipelines if we want any real performance gain.

Lev: If you're running this on actual hardware, the overhead for preparing that resource state is going to be negligible compared to the error correction you already have to deal with.

Kai: So yeah, that’s what this paper argues about in "Computational reach of machine learning models is independent of untrained quantum resources."

Mira: It boils down to the idea that without a specific reason why an untrained circuit would help, you shouldn't introduce it for better performance.

Lev: If we're going to build something on this, we need to focus on those real-world costs and see if any of these theoretical bounds actually translate into useful engineering constraints.

Kai: That’s the main point here for us right now. We need to figure out what *does* help the model, not just throw in random resources hoping for a boost.

The paper's improvements: Tom: So, we've talked about how the paper argues that if you use an untrained quantum circuit as a resource in any machine learning workflow, on average it doesn't give you any advantage over another circuit that achieves the same computational effects. Kai It’s not about finding a magical random state that helps your generative model perform better than one built with a standard, trained resource.

Mira: And it suggests that if there isn't some specific reason why an untrained circuit would help, you shouldn't introduce it just because it looks interesting or simple.

Lev: From the error correction side, this means that the overhead you spend preparing that random state is essentially wasted in terms of computational advantage for the model itself.

Kai: The paper formalizes this using resource theories, looking at how samples from a measured quantum state might reduce the cost of preparing those target distributions.

Lev: That separation is important because it lets us analyze the cost of preparing permutations versus just using that fixed state, which is where the gate count comparison comes in.

Lev: That cost definition is key because it ties the quantum resource directly to how complex it is to implement those specific computational effects we care about.

Kai: The main proof establishes this no free lunch theorem for models where nx equals zero stating that if U zero⟩ is distinct and 2n+ distinct, then there's no free lunch <ref:2309.13967#pg3>.

Mira: This relies on Lemma nineteen showing that for distinct and 2n+ distinct states, multiplicative equivalence classes are the same as permutation equivalence classes <ref:2309.13967#pg3>.

Mira: They show that you need distinctness by building a counter-example where different resource states give different average costs.

Mira: This means if there isn't some a priori bias toward certain computational effects, then no resource quantum circuit will outperform another one that achieves the same set of effects.

Kai: It’s a big statement because it casts serious doubt on proposals to use untrained quantum circuits just because they look interesting or simple.

Lev: If you're running this on actual hardware, the overhead for preparing that random state is going to be negligible compared to the error correction you already have to deal with.

Kai: So yeah, that’s what this paper argues about in "Computational reach of machine learning models is independent of untrained quantum resources."

Mira: It boils down to the idea that without a specific reason why an untrained circuit would help, you shouldn't introduce it for better performance.

Lev: If we're going to build something on this, we need to focus on those real-world costs and see if any of these theoretical bounds actually translate into useful engineering constraints.

Conclusion: Kai: So we're wrapping up this talk on "Computational reach of machine learning models is independent of untrained quantum resources." We've looked at how the paper proves that on average, an untrained circuit doesn't give you a performance edge in a machine learning workflow.

Mira: It really boils down to the idea that if there isn't some specific reason why an untrained circuit would help, you shouldn't introduce it just because it looks interesting.

Lev: From the hardware side, this means the overhead you spend preparing that random state is essentially wasted in terms of computational advantage for the model itself.

Kai: It implies that if there isn't some a priori bias toward certain computational effects, then no quantum circuit will outperform another one that achieves the same set of effects.

Mira: If we're trying to convert samples from a latent distribution into target samples, the specific quantum state we pick from an untrained circuit won't fundamentally change how useful that state is on average compared to other possibilities.

Lev: So if you’re building a system with deep circuits or complex error correction, you don't get any extra efficiency boost just by swapping in a random resource. The complexity required to achieve those computational effects remains the same regardless of which untrained circuit you use.

Kai: It’s a big statement because it casts serious doubt on proposals to use untrained quantum circuits just because they look interesting or simple.

Lev: If you're running this on actual hardware, the overhead for preparing that random state is going to be negligible compared to the error correction you already have to deal with.

Kai: That’s what this paper argues about in "Computational reach of machine learning models is independent of untrained quantum resources."

Mira: It boils down to the idea that without a specific reason why an untrained circuit would help, you shouldn't introduce it for better performance.

Lev: If we're going to build something on this, we need to focus on those real-world costs and see if any of these theoretical bounds actually translate into useful engineering constraints.

Kai: I think the next thing we should look at is what *does* actually help the model, not just throwing in random resources hoping for a boost.

University of Cambridge

quant-ph

Submitted: 2023-09-25

Updated: 2026-10-22

Comments: 13 pages; uploaded final version consistent with accepted peer-reviewed article

License: http://creativecommons.org/licenses/by-sa/4.0/

Importance score: 92/100

The gist: The gist: This paper proves that if an untrained quantum circuit is used as a resource in a machine learning workflow, then on average no quantum circuit is better than any other that can achieve the

Key concepts

No Free Lunch Theorem: This theorem states that if you use an untrained quantum circuit as a resource in machine learning, on average, it will not outperform any other circuit that can produce the same set of computational results. This suggests there is no inherent benefit to using random or untrained circuits unless there's a specific reason beforehand.
Resource Theories: These theories explain how samples from a quantum state become useful in machine learning. The paper examines two ways an untrained circuit can act as a resource: either by processing the input and measuring it, or by producing a fixed, static state that is always fed into the model.
Cost Definition: The cost of preparing different target distributions is measured by the minimum number of gates required to implement them. This cost helps compare how efficient different quantum circuits are at achieving specific computational effects, forming the basis for determining if one resource state is better than another.

Terminology

Quantum Circuits — 1× in this paper · explained in 2 episodes

Summary

The gist: This paper proves that if an untrained quantum circuit is used as a resource in a machine learning workflow, then on average no quantum circuit is better than any other that can achieve the same set of computational effects.

No Free Lunch Theorem

The titular no free lunch theorem states that if an untrained quantum circuit is used as a resource in a machine learning workflow, then on average no quantum circuit is better than any other that can achieve the same set of computational effects This result casts serious doubt on several proposals to use untrained quantum circuits in machine learning workflows. The paper also proves a supporting theorem that even if the idealisations of the no free lunch theorem are omitted, the average quantum advantage remains negligible at best.

Resource Theories and Model Structures

The analysis begins by introducing resource theories to explain no free lunch theorems, focusing on whether samples obtained by measuring a certain quantum state are more useful on average. The paper explores two ways an untrained quantum circuit can act as a resource: firstly, the input could be passed through the quantum circuit, with the output measured and then fed into the classical machine learning model, and secondly, the quantum circuit could just produce a static “resource” state that does not vary with the input and instead the same measured state is always fed into the machine learning model. These structures are formalized in Definitions 2 and 3.

Cost Definition and Equivalence Classes

The cost of preparing a family of target distributions is defined based on the cost function c(P), which can be defined as either the minimum number of gates from some gateset (that is universal for permutations) that are required to implement P as a circuit or a binary value 0 if a circuit to prepare P with fewer gates than some threshold value exists, and 1 otherwise. A notion of equivalence of permutations is established based on the output statistics being identical for two permutations if they are in the same equivalence class. The overall cost C is then defined as the sum of minimal costs for each equivalence class.

Main Proof and Generalizations

Theorem 22 proves the no free lunch theorem for models with nx = 0, stating that if U 0⟩ is distinct and 2n+ -distinct, then there is no free lunch. The proof relies on Lemma 19, which shows that for distinct and 2n+ -distinct states, multiplicative equivalence classes are the same as permutation equivalence classes. Corollary 24 extends this to models with any nx, showing no free lunch if U 0⟩ is distinct and 2n+ -distinct. The analysis further uses the fact that the set of computational effects (i.e., the set of permutation equivalence classes) can be defined such that it is independent of the input state to conclude no free lunch.

Relaxing Idealizations

The paper addresses two key idealisations: first, that the state is distinct and 2n+ -distinct, and second, that every possible computational effect is treated as equally important. The authors show that distinctness is required by constructing a counter-example where different resource states yield different average costs. Furthermore, relaxing the requirement of every possible computational effect being equally important breaks the ability to define permutation equivalence classes, invalidating the approach. However, by using a relaxed notion of cost C˜ defined over subsets of equivalence classes P′, Theorem 31 shows that C˜ ∈ Ω(˜ e nin). This result, combined with Theorem 32 showing circuits exist such that C˜ ∈ O˜(e nin), backs up the no free lunch theorem by demonstrating that in the absence of some a priori reason to believe that the untrained quantum circuit is accelerating computational effects from some subset of all computational effects that we care about, there is no reason to introduce such an untrained circuit.

Conclusion on Usefulness

The conclusion drawn is that the exhaustive list of computational effects that can be achieved with any given machine learning workflow (model structure) is independent of any untrained resource quantum circuit almost surely. This implies that if there is no a priori bias towards certain computational effects, then no resource quantum circuit is better than any other that can achieve the same set of computational effects. This conclusion is backed up by the general analysis in Section 4, addressing the case where certain idealisations needed to make the no free theorem work are dropped. The paper suggests that any advantage observed in reduced-size proof-of-principle demonstrations will persist as the size increases, implying that there must be some reason why the untrained circuit is “well matched” to problem space in question.

How it works

The analysis formalizes machine learning models where an untrained quantum circuit acts as a resource, defining two structures: one where the input is passed through the circuit and measured, and another where the circuit produces a static resource state.
The cost is defined based on the minimum number of gates required to prepare permutations or equivalent computational effects, leading to an overall cost C.
The core of the proof establishes that for distinct and 2n+ -distinct resource states, multiplicative equivalence classes coincide with permutation equivalence classes.
The final result shows that the average circuit size needed is (nearly) exponentially large at best, while naive implementation requires only slightly more than exponential size.

How it works

The paper utilizes specific mathematical tools to prove the equivalence of permutation and multiplicative equivalence classes for resource states. It defines sets V and W of block matrices that capture the structure of these equivalences. Lemma 19 is crucial in showing that if a state is distinct and 2n+ -distinct, then permutation equivalence classes are equivalent to multiplicative equivalence classes. This structural equivalence ensures that the total cost C is independent of the resource state.

How it works

The paper demonstrates that even when idealisations are dropped, a relaxed notion of cost C˜ is bounded by exponential complexity in terms of input size n, i.e., C˜ ∈ Ω(˜ e nin). This lower bound is derived from counting the number of computational effects that must be prepared. Simultaneously, Theorem 32 proves that circuits exist such that C˜ ∈ O˜(e nin), showing the upper bound is similarly exponential. This comparison supports the no free lunch theorem by showing the required circuit size is (nearly) exponentially large at best.

How it works

The paper concludes that the exhaustive list of computational effects achievable in a machine learning workflow is independent of any untrained resource quantum circuit almost surely. This means that if there is no a priori bias towards certain computational effects, then no resource quantum circuit is better than any other that can achieve the same set of computational effects. The paper emphasizes that this result requires empirical demonstration to substantiate claims of advantage.

How it works

The authors conclude by noting that highly-entangled highly “non-classicall” quantum circuits / states would have superior resource value, but they show that a sufficient condition for two nq-qubit candidate resource states to prepare the same family of target distributions is that they differ by a computational basis state permutation. This suggests that CNOT gates are both entangling and permutations, making it easy to construct examples of a pair of states that differ by a computational basis state permutation.

Improvements for AI systems

No free lunch theorem for untrained quantum circuits in machine learning: This theorem proves that if an untrained quantum circuit is used as a resource in a machine learning workflow, then on average no quantum circuit is better than any other that can achieve the same set of computational effects. This implies that introducing an untrained quantum circuit will not increase performance on average without a priori theoretical reason.
Resource theory application for generative models: The paper formalizes the task of generative modeling as converting samples from the latent distribution (i.e., some resource randomness) into samples from the target distribution, allowing researchers to quantify whether specific quantum states are more useful on average by measuring their resource value.
Model structure definition for quantum resources: The analysis defines two ways an untrained circuit acts as a resource: either passing the input through it with output measured, or producing a static resource state. This allows for the construction of machine learning maps using circuits like Definition 2 and states like Definition 3.
Cost comparison based on gate count: The cost of preparing a permutation is defined as the minimum number of gates from some gateset (that is universal for permutations) that are required to implement P as a circuit, which serves as the measure for comparing quantum circuit efficiency in different models.
No free lunch theorem for zero-input generative models: For models where nx equals 0, the theorem proves if U 0⟩ is distinct and 2n+ distinct, then there is no free lunch, meaning the set of computational effects achievable by any resource state is independent of the specific quantum state used as a resource.
Robustness against input variation: Corollary 23 shows that if an input state |x> allows for distinct and 2n+ distinct properties, the no free lunch theorem still holds even when the input varies, confirming that "the full range of computational effects as |x> is allowed to vary as an input" does not grant a priori advantage.
Haar random circuit utilization: The paper demonstrates that if a unitary operator U is obtained by a Haar random sample, then there is no free lunch almost surely, suggesting that using truly untrained, randomly chosen circuits provides no inherent benefit over other resources.

Abstract

This paper proves that if an untrained quantum circuit is used as a resource in a machine learning model, then on average no resource quantum circuit is better than any other that can achieve the same set of computational effects. The paper also proves a supporting theorem that even if certain mild idealisations are omitted, the average quantum advantage remains negligible at best. These results cast serious doubt on several proposals to use untrained quantum circuits in machine learning models: at best such claims should be substantiated empirically, as this paper proves there is no a priori theoretical reason to suppose that introducing an untrained quantum circuit will increase performance.

Sources

Quantum Kitchen Sinks: An algorithm for machine learning on near-term quantum computers

Listen

Transcript

Key concepts

Terminology

Summary

Improvements for AI systems

Abstract

Sources

Related papers