Polynomial Resource Classification of Quantum Circuit Familes via Classical Shadows

• URL: http://arxiv.org/abs/2604.25708v2
• Date: Fri, 01 May 2026 17:11:57 GMT
• Title: Polynomial Resource Classification of Quantum Circuit Familes via Classical Shadows
• Abstract summary: We classify three quantum circuit families: I, Clifford, and Clifford$+T$.<n>We find $Z$-only measurements outperform multi-basis and classical shadows across all qubit counts.<n>All four strategies collapse to near-chance accuracy ($approx 0.33$) above approximately 12 qubits under the quadratic shot budget.
• Score: 4.519665961894666
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We compare four polynomial-resource measurement strategies, (I) $Z$-basis-only, (II) nearest-neighbor $ZZ$ (NN), (III) multi-basis ($Z$, $X$, $Y$), and (IV) classical shadows, for classifying three quantum circuit families: IQP, Clifford, and Clifford$+T$. We find $Z$-only measurements outperform multi-basis and classical shadows across all qubit counts and all four classifiers evaluated, and the $O(\nqubits)$-feature NN strategy matches $Z$-only to within $0.02$ in Random Forest accuracy. The best result is a Random Forest accuracy of $0.91$ at 4--5 qubits under $Z$-only ($0.89$ for NN, $0.85$ for multi-basis, $0.67$ for shadows). All four strategies collapse to near-chance accuracy ($\approx 0.33$) above approximately 12 qubits under the quadratic shot budget $\shots = 16\nqubits^2$. These findings indicate that the discriminative signal between these circuit families is concentrated in local, nearest-neighbor $Z$-basis correlations, consistent with the diagonal gate structure of IQP circuits, and that additional Pauli correlator types or long-range correlations carry no compensating discriminative power for this task. We provide a formal theoretical framework showing that circuits with high diagonal fraction in a given basis concentrate their correlator structure in that basis, and that any deviation from the dominant basis incurs a provably higher estimator variance. These results establish that a quadratic shot budget is insufficient for reliable classification above approximately 12 qubits, but do not rule out the existence of a subquadratic or otherwise more efficient polynomial-resource strategy; whether any polynomial measurement protocol can classify these families at large qubit counts remains an open question.

Related papers

• BRiG-AFA: Bellman Risk-to-Go Learning for Non-Myopic Active Feature Acquisition [8.363536351727978]
  Active feature acquisition asks which unobserved feature to measure next for each test instance under a budget.<n>We introduce method, a deployable, supervised alternative that learns a separate candidate-conditioned risk-to-go function for every remaining budget.
  arXiv  Detail & Related papers  (2026-08-03T14:30:44Z)
• Adaptive operator-generated subspaces for effective many-body Hamiltonians [0.0]
  We present the Adaptive Clifford-Algebra Subspacesolver (A-CASE)<n>Overlap, Hamiltonian, observable, and response matrices are reconstructed from one shared Pauli-expectation bank.<n>A grouped iteration propagates finite-shot variability through thresholding, root matching, spectral weights, susceptibility, and broadening.
  arXiv  Detail & Related papers  (2026-08-01T09:51:25Z)
• A Complexity Measure for Active Learning in Multi-group Mean Estimation [8.550300650352732]
  We study a emphmax-risk objective for active learning in a multi-group mean estimation $d$-armed bandits.<n>A learner adaptively allocates a budget of $T$ samples across $d$ groups to minimize the worst-case uncertainty index.<n>For smooth classes, the $mathrmVLC$ is a reparametrization of a variance--Fisher information, with closed-form values for common families.
  arXiv  Detail & Related papers  (2026-06-12T17:54:26Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Algorithms with Polynomially-Improved Approximation Factors for the $2 \ ightarrow q$ Norm, and Applications [13.39372872460586]
  The $2 rightarrow q$ norm of a matrix $X in mathbbRn times d$ is defined as $lVert X rVert_2 rightarrow q = sup_lVert v rVert = 1 lVert Xv rVert_q$.<n>We show that a simple spectral algorithm can achieve an approximation factor better than $2sqrtlog n$, assuming the Exponential Time Hypothesis (FOCS'
  arXiv  Detail & Related papers  (2026-05-24T23:56:06Z)
• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
  We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability.<n>Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning.<n>We also highlight several open questions on quantitative sample complexity and evaluability.
  arXiv  Detail & Related papers  (2026-05-13T15:41:30Z)
• Learning Hippo: Multi-attractor Dynamics and Stability Effects in a Biologically Detailed CA3 Extension of Hopfield Networks [0.0]
  We present a biologically detailed extension of the classical Hopfield/Marr auto-associative memory model for CA3.<n>We implement ten populations (two asymmetric pyramidal subtypes, eight GABAergic interneuron classes), forty-seven compartments, multi-rule plasticity, and a bimodal cholinergic encoding/consolidation cycle.
  arXiv  Detail & Related papers  (2026-04-22T15:28:17Z)
• Blind Catalytic Quantum Error Correction: Target-State Estimation and Fidelity Recovery Without \textit{A Priori} Knowledge [0.0]
  We introduce emphblind CQEC, which estimates the target from the noisy output alone before catalytic recovery.<n>Five estimation strategies are benchmarked across three noise models.
  arXiv  Detail & Related papers  (2026-04-13T08:27:08Z)
• Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
  The model is composed of $M$ arms and $K$ plays.<n>Each arm has a number of capacities, and each unit of capacity is associated with a reward function.<n>When multiple plays compete for the arm capacity, the arm capacity is allocated in a larger priority weight first manner.
  arXiv  Detail & Related papers  (2025-12-25T11:19:09Z)
• An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
  We recast qubit-efficient optimization as a geometry problem.<n>Local-consistency problem coincides exactly with the Sherali-Adams level-2 polytope $mathrmSA(2)$.
  arXiv  Detail & Related papers  (2025-11-11T15:38:57Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  We introduce a new adaptive $k$-nearest neighbours ($kK$-NN) algorithm that explores the local curvature at a sample to adaptively defining the neighborhood size. Results on many real-world datasets indicate that the new $kK$-NN algorithm yields superior balanced accuracy compared to the established $k$-NN method.
  arXiv  Detail & Related papers  (2024-09-08T13:08:45Z)
• Multilayer Correlation Clustering [12.492037397168579]
  We establish Multilayer Correlation Clustering, a novel generalization of Correlation Clustering (Bansal et al., FOCS '02) to the multilayer setting. In this paper, we are given a series of inputs of Correlation Clustering (called layers) over the common set $V$. The goal is then to find a clustering of $V$ that minimizes the $ell_p$-norm ($pgeq 1$) of the disagreements vector.
  arXiv  Detail & Related papers  (2024-04-25T15:25:30Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Scalable estimation of pure multi-qubit states [0.0]
  We introduce an inductive $n$-qubit pure-state estimation method. The proposed method exhibits a very favorable scaling in the number of qubits when compared to other estimation methods. We experimentally demonstrate the proposed method in one of IBM's quantum processors.
  arXiv  Detail & Related papers  (2021-07-12T19:02:56Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.