Quantum Ml

Classical Simulability and Dequantization

Some quantum machine learning methods can be matched by classical algorithms, so a proposed advantage only holds if no efficient classical method exists.

The moving classical baseline

A quantum method offers an advantage only relative to the best classical alternative, and that baseline keeps improving. Dequantization is the discovery of a classical algorithm that reproduces a quantum method's performance with comparable resources, erasing the claimed speedup. Several prominent quantum machine learning proposals have been dequantized, which is why simulability analysis is essential to any advantage claim.

Circuits that classical computers can simulate

Kronos motion — classical vs quantum

Clifford circuits: gates from the Clifford group are classically simulable in polynomial time by the Gottesman-Knill theorem, despite producing entanglement.
Low-entanglement circuits: states with bounded entanglement are efficiently represented by tensor networks such as matrix product states.
Shallow or geometrically local circuits in low dimensions: often simulable with modest resources.
Product-state models: circuits without entangling gates factorize and are trivial to simulate.

Quantum-inspired dequantization

A powerful line of work assumes the same length-squared sampling access to input data that a quantum algorithm implicitly assumes, then builds classical algorithms with matching complexity. This approach dequantized quantum recommendation systems, low-rank matrix inversion, and principal component analysis, showing their apparent exponential speedups depended on the data-access model, not on quantum mechanics.

Implications for kernels and variational models

For quantum kernels, an advantage requires that the kernel be both useful and hard to estimate classically; many proposed kernels are classically approximable. For variational models, if the reachable states have low entanglement or match a simulable class, a tensor-network method can imitate them. Designers who want advantage must place their model outside the simulable regimes above, which usually means genuine, structured, high entanglement.

python

# Cheap simulability sanity check via entanglement entropy
# If the max bipartite entropy across a training run stays small,
# a matrix-product-state simulation likely reproduces the model.
S = bipartite_entropy(state(theta), cut=n//2)
if S < threshold:
    print('warning: likely classically simulable with an MPS')

The honest takeaway

Dequantization is not a failure of quantum computing; it is the field policing its own claims. It teaches that entanglement alone is not advantage, that data-access assumptions must be stated, and that a quantum result is only interesting once someone has seriously tried and failed to reproduce it classically. This scrutiny is exactly why the surviving advantage claims, mostly for quantum-native data, deserve their credibility.