Classical Surrogates and Dequantization of Variational Models

A variational quantum model earns its keep only if no efficient classical algorithm reproduces its outputs. That one sentence organizes an entire subfield. VQE ansätze, QAOA circuits, and quantum-machine-learning feature maps all advertise advantage by living in a Hilbert space of dimension $2^n$ — but advertising is not proof. The study of classical surrogates and dequantization asks, precisely: for which trained or trainable circuits can a classical algorithm running in $\mathrm{poly}(n,1/\varepsilon)$ time match the outputs to accuracy $\varepsilon$ ? Two distinct programmes answer it. Surrogation builds a classical function mimicking the expectations a circuit produces, exploiting that any expectation value $f(\boldsymbol\theta)=\langle\psi(\boldsymbol\theta)|O|\psi(\boldsymbol\theta)\rangle$ is a trigonometric polynomial in the gate angles whose Fourier support is shrunk by locality or concentration. Dequantization, in Ewin Tang's linear-algebra sense, observes that if a quantum routine's speedup comes only from low-rank structure read in superposition, a classical algorithm with $\ell^2$ -norm sample-and-query access matches it up to polynomial overhead. The lesson is sobering. Constant-depth circuits, symmetry-restricted ansätze, and barren-plateau-flattened landscapes are all already classically tractable — the structure that makes a model trainable tends to make it simulable. Genuine advantage survives only in a narrow band this article maps: an exponentially rich, untruncated spectrum that nonetheless keeps its gradients alive.

Key takeaways

A classical surrogate reproduces a trained model's input–output behaviour to accuracy $\varepsilon$ ; dequantization is a provable classical algorithm matching a quantum routine's accuracy and runtime up to polynomial overhead.
Every parameterized expectation value is a bounded-degree trigonometric polynomial in the gate angles, because each Pauli generator has eigenvalues $\pm1$ and injects only frequencies $0,\pm1$ per angle.
Shallow light cones, low-degree spectra, Lie-restricted symmetry, and barren-plateau concentration each leave polynomially-many relevant Fourier modes — and therefore a classical surrogate.
Tang-style dequantization collapses low-rank quantum speedups (recommendation, PCA, regression) to polynomial overhead once the classical baseline gets the fair $\ell^2$ sample-and-query access that mirrors state preparation.
Classical simulability is the null hypothesis every advantage claim must defeat, and surrogates double as benchmarks, warm starts, and error-mitigation controls.
Key idea: Every parameterized expectation value is a bounded-degree trigonometric polynomial in the gate angles; whenever locality, symmetry, or concentration forces this polynomial to have polynomially many relevant Fourier modes, the model is classically learnable and thus surrogable, so quantum advantage requires an exponentially rich, untruncated frequency spectrum that nonetheless remains trainable.

Where this lives today

Surrogation and dequantization are now standard equipment. Every serious advantage proposal is expected to survive its own surrogate — light-cone simulation for shallow ansätze, low-degree Fourier learning for bounded-spectrum cost functions, classical-shadow regression for feature maps — and several early speedup claims for quantum kernels and recommendation tasks were reframed once the matched baseline was run. Constructively, a trigonometric-polynomial fit from a few hundred parameter-shift evaluations is optimized classically to yield a warm-start $\boldsymbol\theta_0$ in a region of large gradient, tying surrogation to barren-plateau mitigation, and a device that strays from its light-cone surrogate reveals its own error budget for zero-noise extrapolation. The open frontier is the second figure's narrow band: an ansatz with provably exponential, untruncated Fourier support whose gradients nonetheless stay $\Omega(1/\mathrm{poly}(n))$ — expressive, trainable, and provably hard to surrogate at once. No unconditional example is known, and finding one is among the central open problems of near-term quantum computing.

The physical picture

Picture a variational circuit as a box of knobs. Each knob $\theta_j$ enters through a rotation $e^{-i\theta_j H_j/2}$ , and because the Pauli generator $H_j$ squares to the identity — eigenvalues $\pm1$ — turning it can only make the output oscillate as $\cos\theta_j$ and $\sin\theta_j$ , never faster. The whole expectation value is therefore a finite sum of sines and cosines with integer frequencies — exactly, not approximately. If only polynomially many frequencies carry appreciable weight, you learn the function from polynomially many evaluations and store it in a classical table. That table is the surrogate, and the quantum device is redundant. Locality supplies the first reason the spectrum is small. An observable supported on a few qubits only feels the gates inside its backward light cone; in a constant-depth circuit that cone touches $O(1)$ qubits, so the expectation depends on $O(1)$ angles and can be computed by hand. The first figure makes this concrete for a real register.

Figure

A single-qubit observable in a depth-3 nearest-neighbour circuit on 50 qubits: only the gates inside the backward light cone matter, so the expectation depends on at most 2L+1 = 7 qubits and costs 2⁷ = 128 amplitudes to simulate exactly, versus 2⁵⁰ ≈ 1.1×10¹⁵ for the full state

Deep circuits with global entanglement break the light-cone argument — but they usually pay with a barren plateau, a landscape so flat the output concentrates around a fixed value a constant reproduces for free. The two easy regimes bracket the interesting one: too shallow and the cone is small, too deep and the landscape is flat. The second figure maps where surrogation succeeds and where advantage might still hide.

Figure

The surrogability map: a model escapes every known classical surrogate only in the narrow top-right band — Fourier support of order 2ⁿ together with non-vanishing gradient variance of order 1/poly(n). Barren plateaus at the bottom obey Var = 2⁻ᵅⁿ so a constant surrogate matches them, and shallow or low-degree circuits at the left are simulable

Dequantization flips a hidden assumption rather than a geometric one. A quantum algorithm reads an amplitude-encoded vector "for free" in superposition, while a naive classical algorithm seems forced to touch all $2^n$ entries. Grant the classical side sampling access — drawing index $i$ with probability $|v_i|^2/\lVert v\rVert^2$ — and importance sampling reproduces the same low-rank projections the quantum subroutine extracts. This $\ell^2$ access is the fair classical analogue of state preparation, and under it the recommendation, PCA, and regression speedups shrink to polynomial.

The core equations

A variational model output is the expectation value of a fixed observable in a parameterized state, built by interleaving fixed gates with single-parameter rotations — a scalar function of the angles.

f(\boldsymbol\theta)=\langle\psi(\boldsymbol\theta)|\,O\,|\psi(\boldsymbol\theta)\rangle,\qquad |\psi(\boldsymbol\theta)\rangle=\prod_{j}e^{-i\theta_j H_j/2}\,U_j\,|0\rangle^{\otimes n} \qquad (1)

where: $f$ — scalar cost or model output; $\boldsymbol\theta$ — vector of $m$ tunable angles; $H_j$ — Pauli-string generator of the $j$ -th rotation, eigenvalues $\pm1$ ; $U_j$ — fixed gates; $O$ — measured observable. The reading: everything trainable lives in $\boldsymbol\theta$ , and the eigenstructure of the $H_j$ constrains how $f$ depends on it. Expanding each rotation and collecting terms shows $f$ is a multivariate trigonometric polynomial — a finite Fourier series with integer frequency vectors, each Pauli generator contributing only $0$ and $\pm1$ to its own angle.

f(\boldsymbol\theta)=\sum_{\boldsymbol\omega\in\Omega}\hat f_{\boldsymbol\omega}\,e^{\,i\,\boldsymbol\omega\cdot\boldsymbol\theta},\qquad \boldsymbol\omega\in\{-1,0,+1\}^{m} \qquad (2)

where: $\Omega$ — frequency support, the set of active modes; $\hat f_{\boldsymbol\omega}$ — complex coefficient of mode $\boldsymbol\omega$ ; $\boldsymbol\omega\cdot\boldsymbol\theta=\sum_j\omega_j\theta_j$ — accumulated phase. The reading: surrogability is entirely about $\Omega$ — a small or learnable support is a classical model. Because each angle carries a single frequency, its derivative is recovered exactly by two evaluations shifted by $\pm\pi/2$ — the parameter-shift rule, at once the standard gradient estimator and the sharpest diagnostic of bounded frequency.

\frac{\partial f}{\partial\theta_j}=\tfrac{1}{2}\Big[f\big(\theta_j+\tfrac{\pi}{2}\big)-f\big(\theta_j-\tfrac{\pi}{2}\big)\Big] \qquad (3)

where: the shift $\pm\pi/2$ is fixed by the unit frequency of a Pauli generator. The reading: an exact derivative from two points is only possible because $f$ is a single-frequency sinusoid in $\theta_j$ — the same fact that makes the global function learnable. Locality bounds the support geometrically. An observable evolves in the Heisenberg picture; only gates in its backward light cone change it, and on a bounded-degree graph that cone grows at a controlled rate with depth.

|\mathrm{cone}_t(O)|\le |\mathrm{supp}(O)|\,\Delta^{\,t},\qquad f(\boldsymbol\theta)=\mathrm{Tr}\!\big[O\,U_{\mathrm{cone}}\,\rho_{\mathrm{cone}}\,U_{\mathrm{cone}}^{\dagger}\big] \qquad (4)

where: $t$ — circuit depth; $\Delta$ — degree of the interaction graph; $\mathrm{supp}(O)$ — qubits $O$ acts on; $U_{\mathrm{cone}}$ — sub-circuit inside the cone. The reading: gates outside cancel as $V^{\dagger}V=I$ , so $f$ is the expectation of a small sub-circuit, computable in time $2^{O(|\mathrm{cone}|)}$ . When the landscape is flat, concentration replaces locality: Chebyshev's inequality turns an exponentially small variance into an exponentially good constant surrogate.

\Pr_{\boldsymbol\theta}\big[\,|f(\boldsymbol\theta)-\bar f|\ge\delta\,\big]\le \frac{\mathrm{Var}_{\boldsymbol\theta}[f]}{\delta^{2}},\qquad \mathrm{Var}_{\boldsymbol\theta}[f]\in 2^{-\Omega(n)} \qquad (5)

where: $\bar f=\mathbb E_{\boldsymbol\theta}[f]$ — the parameter-averaged value, equal to $\mathrm{Tr}(O)/2^n$ for a Pauli $O$ on a deep random circuit; $\delta$ — accuracy target. The reading: in a barren plateau the constant $g\equiv\bar f$ is a surrogate with mean-square error equal to the tiny variance. Dequantization replaces quantum amplitude access with a matched classical primitive: sample-and-query access, which draws indices from the squared-amplitude distribution and reads individual entries.

\mathrm{SQ}(v):\quad \text{sample } i\sim \frac{|v_i|^2}{\lVert v\rVert^2},\quad \text{query } v_i,\quad \text{return } \lVert v\rVert \qquad (6)

where: $v$ — a vector such as a matrix row; $\lVert v\rVert$ — its Euclidean norm, the analogue of a state-preparation amplitude. The reading: this is the fair baseline — without it the classical side is charged $2^n$ just to read the input, a spurious exponential gap. Finally, the surrogate one ships is a sparse Fourier series over a learned frequency set.

\widetilde f(\boldsymbol\theta)=\sum_{\boldsymbol\omega\in S}\hat f_{\boldsymbol\omega}\,e^{\,i\,\boldsymbol\omega\cdot\boldsymbol\theta},\qquad |S|=\mathrm{poly}(n),\quad \lVert f-\widetilde f\rVert_2\le\varepsilon \qquad (7)

where: $S$ — dominant frequencies found by low-degree Fourier learning; $\widetilde f$ — the surrogate. The reading: when the weight concentrates on $\mathrm{poly}(n)$ modes, this series matches $f$ to $\varepsilon$ with no quantum hardware.

Derivation AWhy every expectation value is a bounded-degree trigonometric polynomial

The goal is to prove the structural fact on which the whole subject rests: that $f(\boldsymbol\theta)$ in equation (1) is a finite Fourier series with integer frequency vectors, with each angle contributing only the frequencies $0$ and $\pm1$ . The argument uses nothing beyond the eigenstructure of a Pauli generator, so it holds for any ansatz built from Pauli rotations, and it yields the parameter-shift rule as a corollary rather than a separate trick.

Step 1. Expand a single rotation. Because $H_j^2=I$ for a Pauli string, the exponential's Taylor series collapses to $e^{-i\theta_j H_j/2}=\cos(\theta_j/2)\,I-i\sin(\theta_j/2)\,H_j$ . Why: even powers give cosines and odd powers give sines — no room for a higher harmonic.

Step 2. Conjugate an operator through the rotation in the Heisenberg picture: $e^{i\theta_j H_j/2}A\,e^{-i\theta_j H_j/2}=\cos\theta_j\,A_{\parallel}+\sin\theta_j\,A_{\perp}+A_{0}$ , splitting $A$ into commuting and anticommuting parts. Why: conjugation by a $\pm1$ -eigenvalue generator produces only $\cos\theta_j$ , $\sin\theta_j$ , and constants — frequencies $0,\pm1$ in that angle.

Step 3. Compose the angles. Evolving $O$ backward through all $m$ rotations multiplies factors each drawn from $\{1,\cos\theta_j,\sin\theta_j\}$ , whose products expand into a sum of exponentials $e^{i\boldsymbol\omega\cdot\boldsymbol\theta}$ with every $\omega_j\in\{-1,0,+1\}$ — equation (2). Why: the support $\Omega$ can never leave the integer box, so surrogability reduces to bounding how many modes carry weight.

Step 4. Read off the parameter-shift rule. Freezing all but $\theta_j$ leaves $f=a\cos\theta_j+b\sin\theta_j+c$ ; evaluating at $\theta_j\pm\pi/2$ and subtracting cancels $a$ and $c$ to give $2(b\cos\theta_j-a\sin\theta_j)=2\,\partial_j f$ , equation (3). Why: the exactness of a two-point gradient is not a numerical accident but a certificate that each angle's frequency is at most one.

Go deeper · Derivation B · 1 minConstant-depth circuits are their own classical surrogate

Derivation BConstant-depth circuits are their own classical surrogate

The goal is to show that a shallow circuit on a bounded-degree connectivity graph, measured through a local observable, can be evaluated classically in $\mathrm{poly}(n)$ time — so no advantage is possible there, and the circuit is literally its own surrogate. The argument combines the Heisenberg-picture cancellation from the previous derivation with a counting bound on how fast a causal cone can spread, and it is the workhorse that rules out advantage claims for many near-term ansätze.

Step 1. Write the expectation as backward evolution of the observable, $f=\langle 0|^{\otimes n}\,U^{\dagger}OU\,|0\rangle^{\otimes n}$ with $U=U_L\cdots U_1$ . Why: pushing $O$ through the layers, rather than propagating the state forward, exposes which gates can influence the result.

Step 2. Bound the causal cone. Each layer enlarges the operator's support by at most the graph degree $\Delta$ , so $|\mathrm{cone}_L(O)|\le|\mathrm{supp}(O)|\,\Delta^{L}$ ; on a $1$ D nearest-neighbour lattice this tightens to $|\mathrm{supp}(O)|+2L$ . Why: a gate only entangles qubits it directly couples, so the reachable set grows at a rate set by connectivity.

Step 3. Discard everything outside the cone. Any gate $V$ disjoint from the current operator commutes through and cancels as $V^{\dagger}V=I$ ; only the cone's gates, qubits, and angles survive, giving $f=\mathrm{Tr}[O\,U_{\mathrm{cone}}\rho_{\mathrm{cone}}U_{\mathrm{cone}}^{\dagger}]$ , equation (4). Why: most of the circuit is causally irrelevant to a local observable and is thrown away exactly, not approximately.

Step 4. Cost it. Exact simulation of the cone costs $2^{O(|\mathrm{cone}|)}$ ; with $L=O(1)$ , $\Delta=O(1)$ this is $O(1)$ , and even $L=O(\log n)$ on a bounded-degree graph stays $\mathrm{poly}(n)$ . Why: this pins the boundary — depth must grow faster than logarithmically, or entanglement spread on an expander-like graph, before the surrogate fails.

Go deeper · Derivation C · 1 minTang-style dequantization of low-rank linear algebra

Derivation CTang-style dequantization of low-rank linear algebra

The goal is to show how a quantum algorithm whose only speedup is low-rank structure loses it once the classical baseline gets the fair $\ell^2$ sample-and-query access of equation (6). We build the matcher from importance sampling and a small Gram-matrix estimate, following the template Tang used to dequantize recommendation systems and, later, PCA and low-rank regression. The punchline: the advertised exponential gap was measured against an unfair baseline.

Step 1. Fix the access model. Grant $\mathrm{SQ}(A)$ : sample a row $i$ with probability $\Pr[i]=\lVert A_{i,\cdot}\rVert^2/\lVert A\rVert_F^2$ and read chosen entries. Why: quantum algorithms assume amplitude encoding — a superposition weighted by entries — and $\mathrm{SQ}$ is that assumption made classical, so comparing without it compares different problems.

Step 2. Estimate the Gram matrix by importance-weighted sub-sampling: draw $s=\mathrm{poly}(k,1/\varepsilon)$ rows and form $\widehat{A^{\dagger}A}=\tfrac{1}{s}\sum_{r}A_{i_r,\cdot}^{\dagger}A_{i_r,\cdot}/p_{i_r}$ , an unbiased estimator that, because rows are drawn by norm, captures high-weight directions with few samples (the FKV construction). Why: the top singular structure lives in a $k$ -dimensional subspace, and importance sampling concentrates samples exactly where it has weight.

Step 3. Diagonalize the small $s\times s$ estimate to recover approximate top- $k$ singular values and vectors with spectral error $\le\varepsilon\lVert A\rVert_F$ , with high probability. Why: the heavy work is now on an object sized by $k$ and $\varepsilon$ , not the ambient dimension $2^n$ where the exponential factor used to hide.

Step 4. Reconstruct the output by projecting the query vector onto the estimated subspace, reproducing the quantum answer to additive $\varepsilon$ in time $\mathrm{poly}(k,\kappa,1/\varepsilon,\lVert A\rVert_F)$ with no explicit $2^n$ . Why: the runtime depends on the ambient space only through norms and the condition number, so the exponential separation vanishes — it was never a property of the problem, only the baseline.

Limiting cases

Whether a variational model is surrogable is decided by which structural regime it occupies.

Case	Result	Meaning
Constant depth, local observable	$L=O(1),\ \|\mathrm{cone}(O)\|=O(1)$	Cone touches $O(1)$ qubits; $f$ depends on $O(1)$ angles and is exactly, efficiently computable — the circuit is its own surrogate.
Barren plateau	$\mathrm{Var}_{\boldsymbol\theta}[\partial_j f]\sim 2^{-n}$	Output concentrates on $\bar f$ ; the constant surrogate $g\equiv\bar f$ matches $f$ to $O(2^{-n/2})$ — trivially dequantized.
Low-degree spectrum	$\deg f\le d,\ d=O(\log n)$	A bounded-degree trigonometric polynomial is learnable from $\mathrm{poly}(n)$ samples by low-degree Fourier learning; surrogable.
Low-rank linear algebra	$\mathrm{rank}\,A=k=O(1)$	Dequantized by $\ell^2$ sample-and-query: classical runtime $\mathrm{poly}(k,\kappa,1/\varepsilon)$ , no $n$ -dependent exponential gap.
Rich spectrum, live gradients	$\|\Omega\|=2^{\Omega(n)},\ \mathrm{Var}[\partial f]=\Omega(1/\mathrm{poly})$	The conjectured advantage regime — exponential support and non-vanishing gradients together. No general surrogate is known; the genuine frontier.

Worked examples

1 · Parameter-shift as a surrogability certificate (fully worked)

Take a single-angle model $f(\theta)=0.5\cos\theta+0.3\sin\theta+0.1$ , the exact form any Pauli-rotation angle must produce. Recover its gradient from two evaluations, then count how many pin down the whole function — and how that explodes with the number of angles.

Step 1. Shifts at $\theta=0$ : $f(+\tfrac{\pi}{2})=0.3+0.1=\mathbf{0.4}$ and $f(-\tfrac{\pi}{2})=-0.3+0.1=\mathbf{-0.2}$ .

Step 2. Apply equation (3): $\partial_\theta f=\tfrac{1}{2}(0.4-(-0.2))=\mathbf{0.3}$ . Calculus agrees: $\partial_\theta f=-0.5\sin\theta+0.3\cos\theta=0.3$ at $\theta=0$ . The two-point estimate is exact, not approximate — the signature of a single-frequency function.

Step 3. The function has three coefficients $(a,b,c)=(0.5,0.3,0.1)$ , so three evaluations (say $\theta=0,\pm\tfrac{2\pi}{3}$ ) fix it everywhere. That triple is the surrogate; the device is never queried again.

Step 4. Scale to $m$ angles: each carries frequencies $\{-1,0,+1\}$ , so the generic support has $3^m$ modes — for $m=20$ , $3^{20}\approx\mathbf{3.5\times10^{9}}$ coefficients, already intractable brute-force. Bounded degree alone is not enough; surrogability needs sparse or low-degree support — exactly what locality, symmetry, and concentration supply.

2 · Light-cone simulation cost (fully worked)

A single-qubit Pauli- $Z$ observable is measured on a depth- $L=3$ , $1$ D nearest-neighbour brickwork circuit over $n=50$ qubits. How large is the backward light cone, and what does exact classical evaluation cost versus full state-vector simulation?

Step 1. On a $1$ D nearest-neighbour lattice the cone spreads by at most one qubit per side per layer, so $|\mathrm{cone}_L(O)|\le|\mathrm{supp}(O)|+2L=1+2(3)=\mathbf{7}$ qubits.

Step 2. Exact simulation of a $7$ -qubit sub-circuit costs $2^{7}=\mathbf{128}$ amplitudes — trivial on a laptop.

Step 3. The naive route stores the full $50$ -qubit state: $2^{50}\approx\mathbf{1.1\times10^{15}}$ amplitudes, about $16$ petabytes — infeasible.

Step 4. The light cone buys a factor $2^{50}/2^{7}=2^{43}\approx\mathbf{8.8\times10^{12}}$ in memory. Any advantage claim here is dead on arrival: the model is its own polynomial-time surrogate, independent of training. (The complementary flat case — a plateau with $\mathrm{Var}[f]=2^{-50}$ — gives constant-surrogate error $2^{-25}\approx3.0\times10^{-8}$ and needs $\sim2^{50}\approx1.1\times10^{15}$ shots to tell apart from the real model, exactly the cost that makes it untrainable.)

Physics of the portrait

Dequantization has an unusually crisp origin: a result produced by an undergraduate asked to prove the opposite.

Origins · 1 minEwin Tang and how this was discovered

Ewin Tang

American computer scientist, b. 2000 · dequantization and sample-and-query algorithms

Ewin Tang was an undergraduate at the University of Texas at Austin when Scott Aaronson set her a thesis problem: show that the quantum recommendation system of Kerenidis and Prakash — then one of the cleanest examples of exponential speedup for a practical task — could not be matched classically, certifying it as genuine advantage. After months of failing to prove hardness, she saw why: the classical baseline had the wrong tools. Granting it $\ell^2$ -norm sample-and-query access — the fair analogue of the quantum algorithm's amplitude encoding — she produced in 2018, at age eighteen, a classical algorithm with only polynomial overhead. The technique generalized fast: within a year she and collaborators had dequantized low-rank matrix inversion, PCA, and supervised clustering, and by 2020 a unified sample-and-query framework subsumed a whole family of "quantum-inspired" algorithms. Tang reframed the advantage question permanently — a linear-algebra speedup is real only if it survives a classical opponent with matched input access — making the fairness of the baseline the first thing any claim must settle.

History

2009

— Harrow, Hassidim, and Lloyd publish the quantum linear-systems algorithm, igniting the low-rank quantum-machine-learning program

2016

— Kerenidis and Prakash give a quantum recommendation system with exponential speedup

2018

— McClean and coauthors identify barren plateaus in variational cost landscapes

2018

— Ewin Tang dequantizes recommendation systems as an undergraduate, erasing the speedup

2020

— Chia, Gilyen, Li, Lin, Tang, and Wang unify the results into a sample-and-query dequantization framework

Going further

References. Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniv. ed., ch. 4 & 8 (circuit model and simulation) · Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2 (2018) 79 · Watrous, The Theory of Quantum Information (2018), chapters on channels and norms · Kitaev, Shen & Vyalyi, Classical and Quantum Computation (complexity foundations) · Tang, A quantum-inspired classical algorithm for recommendation systems, STOC 2019 · Schuld, Sweke & Meyer, The effect of data encoding on the expressive power of variational quantum models, PRA 103 (2021) 032430.

Provenance. The trigonometric-polynomial and parameter-shift structure follow from $H_j^2=I$ for Pauli generators (Nielsen & Chuang ch. 4; a verifier recomputes $e^{-i\theta H/2}=\cos(\theta/2)I-i\sin(\theta/2)H$ ). Light-cone simulability uses Heisenberg-picture cancellation with bounded-degree graph counting (standard; Kitaev–Shen–Vyalyi, Watrous). Barren-plateau surrogacy applies Chebyshev's inequality to design-averaged variance (Preskill NISQ notes; the MSE-equals-variance identity is elementary). Dequantization follows Tang-type $\ell^2$ sample-and-query with FKV low-rank sampling; a verifier checks unbiasedness and spectral concentration of the importance-sampled Gram estimate. The worked numbers ( $2^7=128$ , $2^{50}\approx1.1\times10^{15}$ , $2^{-25}\approx3.0\times10^{-8}$ , $3^{20}\approx3.5\times10^{9}$ , and the parameter-shift gradient $0.3$ ) are recomputed directly; $\bar f=\mathrm{Tr}(O)/2^n$ for a traceless-corrected Pauli observable is the only tabulated relation and is standard.

Builds on. Parameterized Quantum Circuits and Ansatz Design · Parameter-Shift Rules and Quantum Gradients · Barren Plateaus in Variational Landscapes · Quantum Machine Learning Models. Leads to. Expressibility, Entangling Capability, and Trainability Trade-offs · Strategies to Mitigate Barren Plateaus · QAOA Performance Bounds and Concentration.

Ask the tutor: Ask me to walk through the parameter-shift gradient by hand, count the light cone of your own ansatz, or show exactly where a claimed quantum speedup would have to live to escape both surrogation and dequantization.

What is the difference between a classical surrogate and dequantization?

They answer the same worry from opposite directions. A classical surrogate is empirical: given a trained model, you fit a classical function — a sparse trigonometric-polynomial or classical-shadow regressor — reproducing its outputs to $\varepsilon$ on the input distribution you care about. Dequantization is provable: you show a quantum speedup rested on low-rank structure and build a matched- $\ell^2$ -access classical algorithm polynomial in the same parameters. Surrogation targets a model's outputs; dequantization targets an algorithm's runtime. Both conclude the device was unnecessary — one as a fitted approximation, the other as a complexity-theoretic guarantee.

If my circuit is provably hard to simulate, doesn't that guarantee quantum advantage?

No, and conflating the two is the field's most common mistake. Hardness of exact strong simulation means no classical algorithm can output arbitrary amplitudes efficiently — a statement about the full $2^n$ -dimensional object. A useful model, though, only needs to beat classical methods at reproducing its trained outputs on real inputs. A barren-plateau circuit can be $\#\mathrm{P}$ -hard to simulate exactly yet be matched to sampling noise by a constant, because its outputs concentrate. Simulation hardness is necessary but nowhere near sufficient; you must also show the outputs resist every efficient surrogate.

Why do barren plateaus make a model easy to surrogate rather than hard?

Because a barren plateau is extreme flatness. When the gradient variance decays as $2^{-\Omega(n)}$ , the output variance does too, so $f(\boldsymbol\theta)$ sits within an exponentially small window of its mean $\bar f$ for almost every parameter. The simplest classical model — the constant $g\equiv\bar f$ — matches $f$ with mean-square error equal to that tiny variance. Telling the real model from the constant would take exponentially many shots, the same cost that makes the plateau untrainable. So the plateau kills training and hands you a trivial surrogate at once; no plateaued model is both useful and hard to reproduce.

What exactly does sample-and-query access give the classical algorithm?

Three abilities, all matched to quantum amplitude encoding. Sampling: draw an index $i$ with probability proportional to $|v_i|^2$ , mirroring a measurement of a state whose amplitudes track the entries. Query: read any chosen entry $v_i$ . Norm: return $\lVert v\rVert$ . Together they let a classical algorithm do importance sampling on a matrix's high-weight directions — enough to estimate top singular vectors by sub-sampling. The point is fairness: a quantum algorithm assuming an amplitude-encoded input is assuming exactly this access, so the honest comparison grants it too rather than charging the classical side $2^n$ to read the input.

Does dequantization mean quantum machine learning is pointless?

No — it means the bar is precise. Dequantization removed the exponential speedup only for algorithms whose advantage came solely from low-rank linear algebra via amplitude encoding, and even there a polynomial gap can remain. It says nothing about genuinely high-rank problems, sampling problems with no efficient classical analogue, or fault-tolerant algorithms like Shor's, which rest on different mechanisms. What it killed was one over-optimistic narrative; what it left is the harder question of which problems have structure classical access truly cannot exploit.

How is a surrogate actually built and stored in practice?

The common recipe exploits equation (7): collect a few hundred to a few thousand model evaluations — from the device or its trained parameters via parameter-shift — and fit a sparse Fourier series over a candidate frequency set $S$ , keeping only modes whose coefficients clear a threshold. The stored surrogate is that list of frequencies and coefficients, evaluated on a CPU in microseconds. For shallow circuits you instead store and simulate the light-cone sub-circuit; for feature maps you store a classical-shadow representation and regress against it. The deliverable is always a small classical file reproducing the outputs without quantum hardware.