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:2206.11506 · Physical Review A

Quantum approximation of normalized Schatten norms and applications to learning

Yiyou Chen, Hideyuki Miyahara, Louis‐S. Bouchard, Vwani Roychowdhury

Published Nov 9, 2022• 4 citations
arXivHTMLPDF

Abstract

Efficient measures to determine the similarity of quantum states, such as the fidelity metric, have been widely studied. In this paper, we address the problem of defining a similarity measure for quantum operations that can be efficiently estimated. Given two quantum operations, ${U}_{1}$ and ${U}_{2}$, represented in their circuit forms, we first develop a quantum sampling circuit to estimate the normalized Schatten 2-norm of their difference ($\ensuremath{\parallel}{U}_{1}\ensuremath{-}{U}_{2}{\ensuremath{\parallel}}_{{S}_{2}}$) with precision $\ensuremath{\epsilon}$, using only one clean qubit and one classical random variable. We prove a $\text{Poly}(\frac{1}{\ensuremath{\epsilon}})$ upper bound on the sample complexity, which is independent of the size of the quantum system. We then show that such a similarity metric is directly related to a functional definition of similarity of unitary operations using the conventional fidelity metric of quantum states ($\mathcal{F}$): If $\ensuremath{\parallel}{U}_{1}\ensuremath{-}{U}_{2}{\ensuremath{\parallel}}_{{S}_{2}}$ is sufficiently small (e.g., $\ensuremath{\le}\frac{\ensuremath{\epsilon}}{1+\sqrt{2(1/\ensuremath{\delta}\ensuremath{-}1)}}$) then the fidelity of states obtained by processing the same randomly and uniformly picked pure state $|\ensuremath{\psi}\ensuremath{\rangle}$ is as high as needed $[\mathcal{F}({U}_{1}|\ensuremath{\psi}\ensuremath{\rangle},{U}_{2}|\ensuremath{\psi}\ensuremath{\rangle})\ensuremath{\ge}1\ensuremath{-}\ensuremath{\epsilon}]$ with probability exceeding $1\ensuremath{-}\ensuremath{\delta}$. We provide example applications of this efficient similarity metric estimation framework to quantum circuit learning tasks, such as finding the square root of a given unitary operation.

DOI
10.1103/physreva.106.052409

Related papers

On estimating operator norm distance, with optimal trace distance estimation when one state is pure

Yupan Liu, Qisheng Wang, Zhan Yu

We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(ρ_0,ρ_1)$, defined via the operator norm $\|A\|_{\infty} = σ_{\max}(A)$, given ${\rm poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $ρ_0$ and $ρ_1$. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using $Θ(1/ε)$ queries to the state-preparation circuits. Consequently, for constant additive error, say $ε=1/5$, our estimator runs in ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)$ is exactly half of the trace distance ${\rm T}(|ψ\rangle\!\langleψ|,ρ)$, our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with ${\rm rank}(ρ)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/ε^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf QMA}$ upper bound sketched by Liu and Wang (ESA 2025). Together with an $Ω(1/ε)$ quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state $|ψ\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\rangle\!\langleψ|-ρ$, reflecting a structural feature specific to the operator norm distance.

quant-pharXiv:2607.03905•Leibniz international proceedings in informatics•Jul 7, 2026•1 citation

The Quantum Complexity of Computing Schatten ppp-norms

Chris Cade, Ashley Montanaro

We consider the quantum complexity of computing Schatten p-norms and related quantities, and find that the problem of estimating these quantities is closely related to the one clean qubit model of computation. We show that the problem of approximating Tr(|A|^p) for a log-local n-qubit Hamiltonian A and p=poly(n), up to a suitable level of accuracy, is contained in DQC1; and that approximating this quantity up to a somewhat higher level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by the quantum algorithm is substantially better than a natural classical algorithm for the problem. The same problem can be solved for arbitrary sparse matrices in BQP. One application of the algorithm is the approximate computation of the energy of a graph.

arXiv:1706.09279•Leibniz international proceedings in informatics•Jun 28, 2017•27 citations

Agnostic learning of qudit stabilizer states

Wentao Qi, Boyan Xu, Shiguang Feng +1 more

Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown $n$-qudit pure state $|ψ\rangle$ that has fidelity $τ$ with some stabilizer state, our algorithm outputs a stabilizer state $|φ\rangle$ such that $\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon$ with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as $(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)$, where the dimension $d$ is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime $τ> \cos^2(π/8)$, establishing a qudit analogue of the threshold-based approach in prior qubit work.

quant-pharXiv:2607.15559•Jul 20, 2026•1 citation

Fidelity Estimation to a Known Quantum State Is Nearly Quadratic in the Smaller Rank

Gye Jin Lee, Sunghyeon Jo

We study the number of copies needed to estimate the root Uhlmann fidelity between an unknown quantum state and a classically known reference, under collective measurements. If the unknown state has rank at most $s$, we give an estimator using $O(s^2/\varepsilon^2)$ copies, uniformly in the ambient dimension and reference rank. The estimator applies a random-purification channel and a covariant pure-state measurement, then rescales the observed amplitude before evaluating a weighted nuclear norm. Combined with the lower bound established independently in our first version and in concurrent work of Wang, this determines the worst-case complexity under rank bounds $r,s$ as $\min\{r,s\}^2/\varepsilon^2$ up to logarithmic factors in the smaller rank. The same estimator gives the upper bound $O(r(\operatorname{tr}\sqrtσ)^2/\varepsilon^2)$ for a rank-$r$ reference $σ$. We combine spectral truncation with lower bounds obtained by embedding hard instances for the maximally mixed reference into spectral subspaces. For spectra $λ_i\propto i^{-α}$ with fixed $1<α\le2$, as $\varepsilon\downarrow0$ with $r\ge C_α\varepsilon^{-2/(α-1)}$, the bounds determine the complexity as $\widetildeΘ_α(\varepsilon^{-4/(α-1)})$. In particular, inverse-square spectra have accuracy exponent four. The lower-bound construction uses exact moment matching and an explicitly computable Schur measure.

quant-pharXiv:2608.01770•Aug 4, 2026•3 citations

Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling

Ramis Movassagh

One-parameter interpolations between any two unitary matrices (e.g., quantum gates) $U_1$ and $U_2$ along efficient paths contained in the unitary group are constructed. Motivated by applications, we propose the continuous unitary path $U(θ)$ obtained from the QR-factorization \[ U(θ)R(θ)=(1-θ)A+θB, \] where $U_1 R_1=A$ and $U_2 R_2=B$ are the QR-factorizations of $A$ and $B$, and $U(θ)$ is a unitary for all $θ$ with $U(0)=U_1$ and $U(1)=U_2$. The QR-algorithm is modified to, instead of $U(θ)$, output a matrix whose columns are proportional to the corresponding columns of $U(θ)$ and whose entries are polynomial or rational functions of $θ$. By an extension of the Berlekamp-Welch algorithm we show that rational functions can be efficiently and exactly interpolated with respect to $θ$. We then construct probability distributions over unitaries that are arbitrarily close to the Haar measure. Demonstration of computational advantages of NISQ over classical computers is an imperative near-term goal, especially with the exuberant experimental frontier in academia and industry (e.g., IBM and Google). A candidate for quantum computational supremacy is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. The aforementioned mathematical results provide a new way of scrambling quantum circuits and are applied to prove that exact RCS is $\#P$-Hard on average, which is a simpler alternative to Bouland et al's. (Dis)Proving the quantum supremacy conjecture requires "approximate" average case hardness; this remains an open problem for all quantum supremacy proposals.

arXiv:1810.04681•Oct 10, 2018•35 citations

Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning

Jeongho Bang, Kyoungho Cho, Jeongwoo Jae

A central principle in quantum machine learning is that an ansatz should be expressive enough to represent the quantum data of interest. Yet, the expressibility is statistically meaningful only insofar as it can be learned from finitely many copies of an unknown quantum state. In this work, we develop an information-theoretic Occam theory for quantum data generated by finite-size quantum circuits. For the class $S_{n,G}$ of $n$-qubit pure states preparable with at most $G$ two-qubit gates, a metric-entropy argument gives the realizable sample law $\widetildeΘ(G/ε^2)$ in the circuit-limited regime. For an arbitrary source $\hatρ$, we introduce the best $G$-gate approximation error $d_G(\hatρ)$ and the approximate circuit complexity $C_η(\hatρ)$. We prove an agnostic quantum Occam theorem: with $M$ copies, one can learn up to the best $G$-gate approximation error plus a statistical penalty $\widetilde{O}(\sqrt{G/M})$. We then remove the need to know $G$ in advance through an adaptive model-selection theorem whose oracle inequality selects the circuit complexity justified by the data. Matching lower bounds yield a sample-supported expressibility law: at trace-distance accuracy $ε$, $M$ samples can support only $G_{\rm supported} \simeq Mε^2$ gates, up to logarithmic factors and tomography saturation at $2^n$. Thus, the circuit complexity becomes an adaptive statistical resource rather than a static promise. Our framework turns bounded circuit complexity into a model-selection principle for quantum machine learning.

quant-pharXiv:2606.12211•Jun 11, 2026•0 citations
Efficient measures to determine the similarity of quantum states, such as the fidelity metric, have been widely studied. In this paper, we address the problem of defining a similarity measure for quantum operations that can be efficiently estimated. Given two quantum operations, U1{U}_{1}U1​ and U2{U}_{2}U2​, represented in their circuit forms, we first develop a quantum sampling circuit to estimate the normalized Schatten 2-norm of their difference (\ensuremath∥U1\ensuremath−U2\ensuremath∥S2\ensuremath{\parallel}{U}_{1}\ensuremath{-}{U}_{2}{\ensuremath{\parallel}}_{{S}_{2}}\ensuremath∥U1​\ensuremath−U2​\ensuremath∥S2​​) with precision \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ, using only one clean qubit and one classical random variable. We prove a Poly(1\ensuremathϵ)\text{Poly}(\frac{1}{\ensuremath{\epsilon}})Poly(\ensuremathϵ1​) upper bound on the sample complexity, which is independent of the size of the quantum system. We then show that such a similarity metric is directly related to a functional definition of similarity of unitary operations using the conventional fidelity metric of quantum states (F\mathcal{F}F): If \ensuremath∥U1\ensuremath−U2\ensuremath∥S2\ensuremath{\parallel}{U}_{1}\ensuremath{-}{U}_{2}{\ensuremath{\parallel}}_{{S}_{2}}\ensuremath∥U1​\ensuremath−U2​\ensuremath∥S2​​ is sufficiently small (e.g., \ensuremath≤\ensuremathϵ1+2(1/\ensuremathδ\ensuremath−1)\ensuremath{\le}\frac{\ensuremath{\epsilon}}{1+\sqrt{2(1/\ensuremath{\delta}\ensuremath{-}1)}}\ensuremath≤1+2(1/\ensuremathδ\ensuremath−1)​\ensuremathϵ​) then the fidelity of states obtained by processing the same randomly and uniformly picked pure state ∣\ensuremathψ\ensuremath⟩|\ensuremath{\psi}\ensuremath{\rangle}∣\ensuremathψ\ensuremath⟩ is as high as needed [F(U1∣\ensuremathψ\ensuremath⟩,U2∣\ensuremathψ\ensuremath⟩)\ensuremath≥1\ensuremath−\ensuremathϵ][\mathcal{F}({U}_{1}|\ensuremath{\psi}\ensuremath{\rangle},{U}_{2}|\ensuremath{\psi}\ensuremath{\rangle})\ensuremath{\ge}1\ensuremath{-}\ensuremath{\epsilon}][F(U1​∣\ensuremathψ\ensuremath⟩,U2​∣\ensuremathψ\ensuremath⟩)\ensuremath≥1\ensuremath−\ensuremathϵ] with probability exceeding 1\ensuremath−\ensuremathδ1\ensuremath{-}\ensuremath{\delta}1\ensuremath−\ensuremathδ. We provide example applications of this efficient similarity metric estimation framework to quantum circuit learning tasks, such as finding the square root of a given unitary operation.
We investigate the computational complexity of estimating the operator norm distance T∞(ρ0,ρ1){\rm T}_{\infty}(ρ_0,ρ_1)T∞​(ρ0​,ρ1​), defined via the operator norm ∥A∥∞=σmax⁡(A)\|A\|_{\infty} = σ_{\max}(A)∥A∥∞​=σmax​(A), given poly(n){\rm poly}(n)poly(n)-size state-preparation circuits of nnn-qubit quantum states ρ0ρ_0ρ0​ and ρ1ρ_1ρ1​. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using Θ(1/ε)Θ(1/ε)Θ(1/ε) queries to the state-preparation circuits. Consequently, for constant additive error, say ε=1/5ε=1/5ε=1/5, our estimator runs in poly(n){\rm poly}(n)poly(n) time. Since the operator norm distance T∞(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)T∞​(∣ψ⟩⟨ψ∣,ρ) is exactly half of the trace distance T(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}(|ψ\rangle\!\langleψ|,ρ)T(∣ψ⟩⟨ψ∣,ρ), our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with rank(ρ){\rm rank}(ρ)rank(ρ), which can be exp⁡(n)\exp(n)exp(n) in general. 2. For general quantum states, we also provide a quantum estimator using O~(1/ε3/2)\widetilde{O}(1/ε^{3/2})O(1/ε3/2) queries to the state-preparation circuits, which shows that the corresponding promise problem is BQP{\sf BQP}BQP-complete and improves the QMA{\sf QMA}QMA upper bound sketched by Liu and Wang (ESA 2025). Together with an Ω(1/ε)Ω(1/ε)Ω(1/ε) quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state ∣ψ⟩|ψ\rangle∣ψ⟩ has overlap at least 1/21/21/2 with the top unit eigenvector of ∣ψ⟩ ⁣⟨ψ∣−ρ|ψ\rangle\!\langleψ|-ρ∣ψ⟩⟨ψ∣−ρ, reflecting a structural feature specific to the operator norm distance.
We consider the quantum complexity of computing Schatten p-norms and related quantities, and find that the problem of estimating these quantities is closely related to the one clean qubit model of computation. We show that the problem of approximating Tr(|A|^p) for a log-local n-qubit Hamiltonian A and p=poly(n), up to a suitable level of accuracy, is contained in DQC1; and that approximating this quantity up to a somewhat higher level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by the quantum algorithm is substantially better than a natural classical algorithm for the problem. The same problem can be solved for arbitrary sparse matrices in BQP. One application of the algorithm is the approximate computation of the energy of a graph.
Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown nnn-qudit pure state ∣ψ⟩|ψ\rangle∣ψ⟩ that has fidelity τττ with some stabilizer state, our algorithm outputs a stabilizer state ∣φ⟩|φ\rangle∣φ⟩ such that ∣⟨φ∣ψ⟩∣2≥τ−ε\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon∣⟨φ∣ψ⟩∣2≥τ−ε with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as (d/τ)O(d2log⁡(1/τ))⋅poly(n,1/ε)(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)(d/τ)O(d2log(1/τ))⋅poly(n,1/ε), where the dimension ddd is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime τ>cos⁡2(π/8)τ> \cos^2(π/8)τ>cos2(π/8), establishing a qudit analogue of the threshold-based approach in prior qubit work.
We study the number of copies needed to estimate the root Uhlmann fidelity between an unknown quantum state and a classically known reference, under collective measurements. If the unknown state has rank at most sss, we give an estimator using O(s2/ε2)O(s^2/\varepsilon^2)O(s2/ε2) copies, uniformly in the ambient dimension and reference rank. The estimator applies a random-purification channel and a covariant pure-state measurement, then rescales the observed amplitude before evaluating a weighted nuclear norm. Combined with the lower bound established independently in our first version and in concurrent work of Wang, this determines the worst-case complexity under rank bounds r,sr,sr,s as min⁡{r,s}2/ε2\min\{r,s\}^2/\varepsilon^2min{r,s}2/ε2 up to logarithmic factors in the smaller rank. The same estimator gives the upper bound O(r(tr⁡σ)2/ε2)O(r(\operatorname{tr}\sqrtσ)^2/\varepsilon^2)O(r(trσ​)2/ε2) for a rank-rrr reference σσσ. We combine spectral truncation with lower bounds obtained by embedding hard instances for the maximally mixed reference into spectral subspaces. For spectra λi∝i−αλ_i\propto i^{-α}λi​∝i−α with fixed 1<α≤21<α\le21<α≤2, as ε↓0\varepsilon\downarrow0ε↓0 with r≥Cαε−2/(α−1)r\ge C_α\varepsilon^{-2/(α-1)}r≥Cα​ε−2/(α−1), the bounds determine the complexity as Θ~α(ε−4/(α−1))\widetildeΘ_α(\varepsilon^{-4/(α-1)})Θα​(ε−4/(α−1)). In particular, inverse-square spectra have accuracy exponent four. The lower-bound construction uses exact moment matching and an explicitly computable Schur measure.
One-parameter interpolations between any two unitary matrices (e.g., quantum gates) U1U_1U1​ and U2U_2U2​ along efficient paths contained in the unitary group are constructed. Motivated by applications, we propose the continuous unitary path U(θ)U(θ)U(θ) obtained from the QR-factorization U(θ)R(θ)=(1−θ)A+θB, U(θ)R(θ)=(1-θ)A+θB, U(θ)R(θ)=(1−θ)A+θB, where U1R1=AU_1 R_1=AU1​R1​=A and U2R2=BU_2 R_2=BU2​R2​=B are the QR-factorizations of AAA and BBB, and U(θ)U(θ)U(θ) is a unitary for all θθθ with U(0)=U1U(0)=U_1U(0)=U1​ and U(1)=U2U(1)=U_2U(1)=U2​. The QR-algorithm is modified to, instead of U(θ)U(θ)U(θ), output a matrix whose columns are proportional to the corresponding columns of U(θ)U(θ)U(θ) and whose entries are polynomial or rational functions of θθθ. By an extension of the Berlekamp-Welch algorithm we show that rational functions can be efficiently and exactly interpolated with respect to θθθ. We then construct probability distributions over unitaries that are arbitrarily close to the Haar measure. Demonstration of computational advantages of NISQ over classical computers is an imperative near-term goal, especially with the exuberant experimental frontier in academia and industry (e.g., IBM and Google). A candidate for quantum computational supremacy is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. The aforementioned mathematical results provide a new way of scrambling quantum circuits and are applied to prove that exact RCS is #P\#P#P-Hard on average, which is a simpler alternative to Bouland et al's. (Dis)Proving the quantum supremacy conjecture requires "approximate" average case hardness; this remains an open problem for all quantum supremacy proposals.
A central principle in quantum machine learning is that an ansatz should be expressive enough to represent the quantum data of interest. Yet, the expressibility is statistically meaningful only insofar as it can be learned from finitely many copies of an unknown quantum state. In this work, we develop an information-theoretic Occam theory for quantum data generated by finite-size quantum circuits. For the class Sn,GS_{n,G}Sn,G​ of nnn-qubit pure states preparable with at most GGG two-qubit gates, a metric-entropy argument gives the realizable sample law Θ~(G/ε2)\widetildeΘ(G/ε^2)Θ(G/ε2) in the circuit-limited regime. For an arbitrary source ρ^\hatρρ^​, we introduce the best GGG-gate approximation error dG(ρ^)d_G(\hatρ)dG​(ρ^​) and the approximate circuit complexity Cη(ρ^)C_η(\hatρ)Cη​(ρ^​). We prove an agnostic quantum Occam theorem: with MMM copies, one can learn up to the best GGG-gate approximation error plus a statistical penalty O~(G/M)\widetilde{O}(\sqrt{G/M})O(G/M​). We then remove the need to know GGG in advance through an adaptive model-selection theorem whose oracle inequality selects the circuit complexity justified by the data. Matching lower bounds yield a sample-supported expressibility law: at trace-distance accuracy εεε, MMM samples can support only Gsupported≃Mε2G_{\rm supported} \simeq Mε^2Gsupported​≃Mε2 gates, up to logarithmic factors and tomography saturation at 2n2^n2n. Thus, the circuit complexity becomes an adaptive statistical resource rather than a static promise. Our framework turns bounded circuit complexity into a model-selection principle for quantum machine learning.