PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Convolutional Neural Networks are Effectively Classically Simulable

Pablo Bermejo, Paolo Braccia, Manuel S. Rudolph, Zoë Holmes, Lukasz Cincio, M. Cerezo

arXiv:2408.12739v2quant-phcs.LGstat.ML

TL;DR

The paper asks whether QCNNs can be classically simulated in a way that supports successful training, not merely average-case loss estimation. It constructs shadow-based classical surrogates and reports comparable or better benchmark performance, while noting that its simulations focus on one-dimensional architectures.

  • Problem

    Average-case QCNN simulation does not establish whether a classical surrogate can reproduce successful training on the optimizer-relevant parts of the landscape.

    Source: §I · p. 1

  • Method

    The authors construct classical surrogates using low-bodyness Pauli propagation and classical shadows of the input data.

    Source: §I · p. 2, a. Pauli propagation · p. 24

  • Results

    Simulated QCNNs reach similar or better performance than reported full QCNNs, and finite-sample shadow simulations can outperform full QCNNs trained without finite sampling.

    Source: §IV · p. 7

  • Takeaways & Limitations

    The authors argue that non-trivial datasets are needed to establish QCNN utility beyond tasks classifiable from low-bodyness observables.

    Source: §V · p. 12

    The study focuses on one-dimensional tracing-out and measurement-based QCNNs; higher-dimensional or more exotic topologies could raise simulation costs, potentially prohibitively even at modest sizes.

    Source: §V · p. 12

Abstract

from arXiv · show

Quantum Convolutional Neural Networks (QCNNs) are widely regarded as a promising model for Quantum Machine Learning (QML). In this work we tie their heuristic success to two facts. First, that when randomly initialized, they can only operate on the information encoded in low-bodyness measurements of their input states. And second, that they are commonly benchmarked on "locally-easy'' datasets whose states are precisely classifiable by the information encoded in these low-bodyness observables subspace. We further show that the QCNN's action on this subspace can be efficiently classically simulated by a classical algorithm equipped with Pauli shadows on the dataset. Indeed, we present a shadow-based simulation of QCNNs on up-to $1024$ qubits for phases of matter classification. Our results can then be understood as highlighting a deeper symptom of QML: Models could only be showing heuristic success because they are benchmarked on simple problems, for which their action can be classically simulated. This insight points to the fact that non-trivial datasets are a truly necessary ingredient for moving forward with QML. To finish, we discuss how our results can be extrapolated to classically simulate other architectures.

I. INTRODUCTION

The paper asks whether QCNNs can be simulated through training, beyond average-case simulation, and argues that their apparent success is tied to low-bodyness information and locally-easy benchmarks. It proposes classical shadow-based surrogates and frames the need for non-trivial datasets as an open challenge.

I. INTRODUCTION

  • Classical simulability during training remains unresolved: average-case results do not establish whether a surrogate can reproduce successful training on optimizer-relevant regions.The paper presents this as a model- and task-dependent question.Source: §I · pp. 1–2
  • The authors construct classical shadow-enhanced surrogates for both tracing-out and measurement-based QCNNs and report comparable or improved accuracy on standard classical and quantum datasets.The approach avoids training a QCNN through a hybrid quantum-classical loop, though quantum data may still require an initial measurement phase.Source: §I · p. 2
  • The paper calls for non-trivial datasets on which QCNNs can work outside the classically simulable regime, since existing heuristic successes may reflect locally-easy tasks.The authors note that constructed hard examples based on Shor’s algorithm or cryptographic assumptions are mathematical artifacts rather than realistic practical problems.Source: §I · p. 2, Figure 1 · p. 2

A. Supervised learning with QCNNs

  • QCNNs alternate convolutional processing with pooling that traces out or measures qubits, yielding logarithmic depth and local output measurements in typical architectures.The paper focuses on tracing-out and measurement-based variants.Source: Figure 2 · p. 3, A. Supervised learning with QCNNs · p. 3

B. Notions of classical simulability

The paper distinguishes average loss estimation at sampled parameter settings from classical simulation that can solve the task. Its focus is a shadow-assisted classical surrogate that can be trained after an initial quantum data-acquisition phase.

B. Notions of classical simulability

  • Average-case simulability estimates loss at fixed or randomly sampled parameters, but does not show that the task can be solved by simulating optimizer-relevant regions.Prior results cited by the paper bound average error using low-bodyness approximations.Source: B. Notions of classical simulability · p. 4
  • The paper’s task-oriented criterion allows quantum access during initial data acquisition, followed by classical computation without further quantum access.The acquisition phase prepares and measures copies of input states using efficient shadow techniques.Source: B. Notions of classical simulability · pp. 4–5
  • Under this criterion, a simulated trained model must achieve classification accuracy comparable to the quantum model, while the quantum device is reduced to collecting data measurements.The authors describe this as substantial dequantization, not full dequantization when quantum experiments remain necessary.Source: B. Notions of classical simulability · p. 5

III. CONCEPTUALIZING THE SUCCESS OF QCNNs

For randomly initialized QCNNs, contributions from higher-bodyness Pauli operators decay on average, so predictions are dominated by low-bodyness observables. This connection helps explain barren-plateau avoidance, but does not itself guarantee simulation throughout training or apply when data are too entangled.

A. Randomly initialized QCNNs

  • For randomly initialized tracing-out QCNNs, each Pauli contribution to the Heisenberg-evolved measurement decays exponentially with its bodyness on average.The analysis assumes independently sampled local gates forming 2-designs over U(4).Source: A. Randomly initialized QCNNs · p. 5
  • The dominant prediction terms therefore use O(1)-bodyness observables, linking large loss gradients and barren-plateau avoidance to local terms in the evolved measurement.The companion result cited by the paper also finds that low-bodyness truncation error decays exponentially with the cutoff.Source: A. Randomly initialized QCNNs · p. 5
  • When input states are too entangled, local observables may be exponentially suppressed, invalidating the low-bodyness guarantees and allowing barren plateaus.The paper names volume-law entanglement as an example.Source: A. Randomly initialized QCNNs · pp. 5–6
  • These results are average statements for random initializations and do not establish faithful simulation across optimizer-driven training; the numerical extension is heuristic and dataset-specific.The authors distinguish their end-to-end training demonstrations from prior average-case simulation.Source: A. Randomly initialized QCNNs · pp. 5–6

B. Locally-easy datasets

The paper defines locally-easy datasets by whether low-bodyness observables suffice for classification and reports that considered benchmark datasets can be solved within that subspace. For measurement-based QCNNs, the same low-bodyness pattern holds, while measurements reduce expressive power relative to tracing-out variants.

B. Locally-easy datasets

  • A dataset is locally-easy when expectation values of low-bodyness observables suffice to classify its input states.This is a necessary, but not sufficient, condition for optimization to remain in the low-bodyness subspace.Source: B. Locally-easy datasets · p. 6
  • The benchmark datasets compiled by the authors are heuristically found to be locally-easy and classifiable while remaining in the low-bodyness subspace.Appendix results report perfect random-forest classification on 100-qubit XXX bond-alternating states using local Pauli observables plus a few two-qubit observables.Source: B. Locally-easy datasets · p. 6

C. Measurement-based QCNNs

  • For randomly initialized measurement-based QCNNs, Pauli contributions decay exponentially with bodyness, so training initially uses a polynomially sized low-bodyness subspace.The paper connects this result to barren-plateau avoidance in that architecture.Source: C. Measurement-based QCNNs · pp. 6–7
  • Measurement-based QCNNs have larger measurement variance than tracing-out QCNNs, which the paper says indicates reduced expressive power.Source: C. Measurement-based QCNNs · p. 7

IV. NUMERICAL RESULTS FOR CLASSICALLY SIMULATED QCNNs

This section tests whether simulated QCNNs can classify quantum datasets using low-bodyness information extracted from Pauli classical shadows. For the 1024-qubit bond-alternating XXX model, 100 shadows per state yielded test accuracy above 90%.

IV. NUMERICAL RESULTS FOR CLASSICALLY SIMULATED QCNNs

  • The study evaluates scalability up to 1024 qubits and examines how classification performance depends on the number of training points and shadows per state.The listed quantum benchmarks use LOWESA-based simulation, while the broader numerical section also describes restricted-bodyness tensor-network simulation for classical data.Source: §IV · p. 7

A. Quantum datasets

  • The quantum-dataset study finds that low-bodyness information can suffice for phase classification, using a simulated QCNN trained directly on Pauli shadows rather than to emulate exact QCNN training.The simulations use LOWESA-based Pauli propagation; the surrogate is self-consistently trained to solve the task.Source: A. Quantum datasets · p. 7, §IV · p. 7
  • The four quantum datasets are ground states from the bond-alternating XXX, Haldane-chain, ANNNI, and cluster models, with evenly distributed states per phase.The states were obtained with DMRG, and the QCNN simulation traces out half the remaining qubits at each pooling layer.Source: A. Quantum datasets · p. 7

1. Heisenberg bond-alternating XXX model

  • The XXX benchmark uses a binary phase-classification task on 1024 qubits, with a thermodynamic-limit transition between trivial and topologically protected phases at J2/J1 = 1.The simulation was reported as the largest QCNN implementation with classical shadows known to the authors, run on a modern laptop.Source: A. Quantum datasets · p. 7, §1 · p. 8
  • In the reported QCNN classification, 100 classical shadows per data point consistently yielded test accuracy above 90%, with no more than 20,000 total training measurement shots.The experiment used 100 states, capped operator bodyness at two, and trained on the 400 operators with the largest variance across the shadows dataset.Source: §1 · p. 8

2. Haldane Chain

The Haldane chain is tested as a binary classification task, while ANNNI and cluster models are treated as multiclass phase-classification tasks. The simulated QCNN achieves the reported accuracies using low-bodyness observables, with errors near phase transitions potentially affected by finite-size label mismatch.

2. Haldane Chain

  • For the Haldane chain, increasing the number of shadows improved classification accuracy, while training-point count had a smaller effect, likely because same-phase states have large overlap.At 10 training points and 500 shadows per state, the experiment required 5000 measurements; the operator bodyness was capped at three.Source: §2 · pp. 8–9, Figure 4 · p. 9

3. ANNNI model

  • For ANNNI, test accuracy was 85.8% with 200 training points and 80.2% with 20, using a four-bodyness cap and 4000 or 2500 shadows per state, respectively.The corresponding train accuracies were 82.8% and 87%.Source: §3 · p. 9, Figure 5 · p. 10

4. Cluster Hamiltonian

  • For the cluster model, test accuracy was 84% with 200 training points and 77.6% with 20, comparable to or higher than prior attempts.Train accuracies were 80.9% and 85%, respectively; the simulation used 4000 shadows per state and averaged over five runs.Source: §4 · p. 10
  • For ANNNI and cluster classification, most errors lie near phase transitions and may partly reflect labels from the thermodynamic-limit diagram misaligned with finite-size data.The authors note that this label mismatch can increase as system size decreases.Source: §4 · p. 10

B. Classical datasets

The classical-dataset section simulates QCNN classification across four image datasets and encoding schemes, while the discussion qualifies the scope of the simulations and argues for more demanding benchmarks.

B. Classical datasets

  • The study considers MNIST, Fashion-MNIST, EuroSAT, and GTSRB, using amplitude and angle encodings to simulate QCNN classification.The table caption identifies the encoding variants and states that results use constrained bodyness 2, except starred results, which use 3.Source: B. Classical datasets · p. 10, Table I · p. 11
  • Image states are prepared as normalized matrix-product states, and angle encodings are kept shallow to preserve efficient MPS decompositions.The simulations use constrained-bodyness MPS and a mean-squared error loss.Source: B. Classical datasets · p. 11
  • For the classical data considered, the embeddings and QCNN models are fully classically simulable, so the authors argue that quantum resources are unnecessary for these tasks.The passage connects this point to the use of classically simulable data-encoding schemes.Source: B. Classical datasets · p. 11

V. DISCUSSION

  • The authors construct efficient classical surrogates for one-dimensional tracing-out and measurement-based QCNNs, but do not claim that every QCNN task is classically simulable.They state that their work does not prove the absence of any scenario requiring QCNN training on a quantum computer.Source: §V · p. 11
  • The analysis focuses on popular one-dimensional architectures; higher-dimensional or more exotic topologies could raise simulation costs, and were not pursued.The authors note that such architectures have not been explored or shown useful where simpler one-dimensional QCNNs fail.Source: §V · p. 12
  • The simulations are not a full dequantization: quantum input data still require a quantum computer to obtain classical shadows.The authors say state preparation and single-qubit measurements are easier than running the QCNN on quantum hardware, but do not eliminate quantum resources.Source: §V · p. 12
  • The authors propose extending low-bodyness classical training to other local-gate quantum neural networks, while whether the relevant solutions exist remains an open question.They say this requires case-by-case analysis through direct simulation.Source: §V · p. 12
  • The authors report finding no studied task that required QCNN action beyond the small low-bodyness subspace and call for non-trivial benchmarks.For the considered condensed-matter datasets, local order parameters allow classification even through phase transitions; why existing benchmarks are simple remains open.Source: §V · p. 12

Appendix A: Proof of Result 1

The appendix derives average k-purities by expressing the Heisenberg-evolved measurement operator in a Pauli-weight basis and propagating its second moments through local gates.

Appendix A: Proof of Result 1

  • The proof tracks the Heisenberg-evolved measurement operator by Pauli bodyness, defining k-purity as its projection onto Paulis of weight k.Bodyness is the number of qubits on which a Pauli acts nontrivially.Source: §1 · p. 18

2. Weingarten calculus

  • Weingarten calculus represents Haar-averaged gate moments as projections onto commutant spaces, enabling their calculation in a finite-dimensional basis.For the two-qubit gates, the relevant identity and swap vectors span the space used to study overlapping gate actions.Source: §2 · pp. 19–20
  • The average k-purities are obtained by projecting vectorized operators into the identity-and-swap basis and evolving them through P-gates arranged in the QCNN topology.The appendix constructs the P-gate representation from the second moment of local two-qubit gates.Source: §2 · p. 20

3. Exact derivation of the k-purities for a prototypical QCNN ansatz

For the analyzed QCNN ansatz, the average contribution of a Pauli decays exponentially with its bodyness, leaving the evolved measurement operator supported essentially on low-bodyness Paulis.

3. Exact derivation of the k-purities for a prototypical QCNN ansatz

  • The average contribution of a Pauli with bodyness k decays exponentially with k, and the evolved measurement operator has support essentially on Paulis with bodyness in O(1).Figure 8 plots average contribution per bodyness; the proof derives the distribution by mapping s-content to Pauli bodyness.Source: §3 · pp. 20, 22, Figure 8 · p. 23
  • The formal theorem assumes independent local two-qubit gates forming 2-designs and defines k-purity for a single-qubit Pauli measurement.The analyzed non-crossing gate configuration is chosen to keep the exact operator-bodyness calculation tractable.Source: §3 · pp. 20–21
  • The proof tracks identity-and-swap components from a single-Pauli measurement through non-crossing convolutional layers, using s-content to count pairs of swap components.Each gate acts on at least one identity component, and the first layer contributes a coefficient a = 2/5.Source: §3 · pp. 21–22, Figure 7 · p. 21

Appendix B: Classical simulability of QCNNs

The simulation methods restrict processing to low-bodyness information to represent QCNN action efficiently.

Appendix B: Classical simulability of QCNNs

  • The methods truncate Heisenberg-evolved measurement operators to bodyness O(1), yielding an efficient representation of the backwards-evolved operators.The input-state overlaps are computed by projection into the low-bodyness subspace, using Pauli classical shadows for quantum datasets.Source: Appendix B · p. 23
  • The paper uses LOWESA, a Pauli-propagation surrogate algorithm, to simulate QCNN action on the restricted subspace.LOWESA is identified as a Pauli Propagation Surrogate within the broader family of Pauli Propagation algorithms.Source: Appendix B · p. 23
  • A second simulation approach uses tensor networks with restricted bodyness.Source: Appendix B · p. 23

1. LOWESA

LOWESA simulates circuit expectations by propagating Pauli operators and restricting the calculation to a manageable low-bodyness subspace. Its Pauli Propagation Surrogate (PPS) stores path structure first, then evaluates only paths associated with operators selected as important for the task.

a. Pauli propagation

  • A Pauli gate either leaves an operator unchanged or splits it into two terms, so propagation can generate exponentially many operators in the number of gates.Breadth-first propagation can merge identical Pauli operators by adding their coefficients.Source: a. Pauli propagation · p. 24, Figure 9 · p. 25
  • Restricting propagation to low-bodyness operators truncates the sum to a classically manageable subset.A path is stopped when its Pauli operator crosses the chosen bodyness threshold.Source: a. Pauli propagation · p. 24

b. Pauli propagation surrogate

  • PPS first stores a graph of Pauli-path splitting and merging, then reevaluates only paths leading to operators deemed important for the task.This trades pre-computation time and memory for faster expectation evaluation.Source: b. Pauli propagation surrogate · p. 25, Figure 9 · p. 25
  • Pauli classical shadows estimate state overlaps used by the surrogate when the input states are more intricate than simple product states.The shadow representation replaces the input state in the expectation estimator.Source: b. Pauli propagation surrogate · p. 25
  • Frequency truncation removes paths by coefficient frequency, while surrogate truncations can select nearby-qubit operators or paths with high variance across input states.The frequency of a path is its number of sine and cosine factors; high-variance paths are heuristically treated as more useful for classification.Source: b. Pauli propagation surrogate · p. 26

2. Constrained bodyness tensor network

The constrained-bodyness tensor-network method classifies data using low-bodyness information, optimizing a measurement operator represented as an MPS. Complementary analyses report modest shadow-scaling behavior and perfect classification of the XXX model using local Pauli features, while noting scope and tuning limits.

2. Constrained bodyness tensor network

  • The method is currently limited to binary classification and works best with one-dimensional quantum systems.Extensions to multiclass problems and higher-dimensional topologies are left for future work.Source: §2 · p. 26
  • The three-step procedure truncates input data to low-bodyness information, optimizes a classifying MPS operator, and optionally compiles the ansatz toward that operator.Quantum-state components can be reconstructed over the small-weight Pauli subspace using shadow tomography.Source: §2 · p. 26
  • The low-bodyness-constrained MPS operator reproduces average randomly initialized QCNN behavior and suffices to solve the classification task.The method optimizes MPS overlaps without parametric gradient computation, then can optionally compile the circuit ansatz toward the optimized operator.Source: §2 · p. 27

Appendix C: Analysis of scaling and overfitting during training

  • Shadow demand grows sublinearly with system size for the XXX model and appears size-independent for the Haldane model; increasing training samples leaves the required shadows barely changed.The appendix analysis uses 500 samples, with 400 used for training.Source: Appendix C · pp. 27–28
  • Further tuning could make the XXX classification process barely depend on system size, so its observed scaling may reflect the current optimization choices.Suggested changes include preselecting relevant Pauli strings and increasing iteration counts.Source: Appendix C · p. 28

Appendix D: Random Forest classification of the XXX Bond alternating model

  • 100% accuracy was achieved on 100-qubit XXX ground states using single-qubit Pauli features plus 500 two-qubit operators in a random forest.The result supports classification from local observables independently of a QCNN.Source: Appendix D · pp. 28–29, Figure 12 · p. 29

Appendix E: Measurement-based QCNN

  • The measurement-based QCNN considered here measures qubits at pooling layers and uses outcomes to control neighboring unitaries.Source: Appendix E · p. 29

1. Concentration properties and Heisenberg-evolved measurement operator

Pooling measurements alter the Heisenberg-propagated operator and reduce concentration in measurement-based QCNNs. Their dominant contributions are local, except in a pathological all-q_j=1 case.

1. Concentration properties and Heisenberg-evolved measurement operator

  • Adding pooling measurements changes the propagated operator through factors q_j = p_j(0)^2 + p_j(1)^2, with 0 ≤ q_j ≤ 1.The bound is saturated only when a measured qubit is a computational-basis state, indicating no entanglement between the measured qubits.Source: §1 · p. 31
  • Measurement-based QCNNs concentrate less than tracing-out QCNNs, reducing expressive power regardless of convolutional-layer arrangement.Source: §1 · p. 32
  • Randomly initialized measurement-based QCNNs predominantly process local input information because coefficients decay exponentially with the number of s terms.Source: §1 · p. 32
  • In the pathological all-q_j=1 case, global operators can persist, but Haar-random two-qubit gates prevent this case on average.Source: §1 · p. 32
  • Outside the average case, q_j=1 for every measured qubit requires unentangled computational-basis inputs, whose structure is readily reproduced by tensor networks.In that case, both the QCNN and input data are classically simulable.Source: §1 · p. 32

2. Classical simulability

Pauli shadows combined with tensor networks enable MPS simulation of measurement-based QCNNs. The reported cost is polynomial, with practical simulations reaching large qubit counts.

2. Classical simulability

  • Pauli shadows provide separable product-state inputs, while measurement-based pooling cannot increase entanglement on average, enabling efficient MPS simulation.Source: §2 · p. 32
  • In the tested brick-like architecture, pooling measures qubits and uses each outcome to control a single-qubit gate on a neighboring site.Source: §2 · p. 32
  • For random-gate product-state runs, bond dimension rises initially, then pooling halts its growth as half the qubits are measured out; the final state has χ=1.Source: §2 · p. 32, Figure 14 · p. 33
  • The reported MPS simulation cost scales as O(n^3), following the stated bond-dimension bound and SVD cost.Source: §2 · p. 32
  • 32,768 qubits are within the stated laptop-simulation reach at χ≈4096; the random-gate test is worst-case, with smaller χ expected during typical training.Source: §2 · p. 33

Related papers

Loading 2408.12739v2…