Introduction

Machine learning gobbles data. Neural networks, kernel methods, and clustering algorithms all require comparing data points — sometimes millions of them — and the arithmetic piles up fast. So when quantum computers appeared with their promise of exponential parallelism, it was natural to ask: could they turbocharge learning?

Quantum machine learning (QML) is the field that takes that question seriously. Early results seemed thrilling: quantum algorithms for linear systems (HHL, 2009) appeared to offer exponential speedups, and quantum versions of principal-component analysis, support-vector machines, and recommendation engines followed. Researchers dreamed of a machine learning revolution driven by qubits.

Then the ground shifted. Starting around 2018, a wave of dequantization results — led by Ewin Tang — showed that many of the celebrated quantum speedups evaporate once you allow classical algorithms access to the same kind of quantum-inspired data structure. The speedups were not coming from quantum mechanics; they were coming from sampling tricks that classical computers can imitate.

The result is a field in productive tension: some quantum speedups are believed to be real (quantum kernel methods, variational circuits, certain simulation tasks), while others have been proven illusory. Understanding which is which is one of the central open questions in both quantum computing and machine learning.

Try It: Quantum vs. Classical Kernel

Kernel methods classify data by measuring similarity between points. A quantum kernel uses the inner product of quantum states prepared from the data; a classical RBF (radial basis function) kernel uses Gaussian similarity. On a small 2D dataset, how close are they?

<p class="hint">
  A <b>quantum kernel</b> measures similarity via inner products of quantum feature states. A classical <b>RBF kernel</b> uses Gaussian similarity. Compare them on a tiny 2D dataset.
</p>
<div class="controls">
  <button id="btnNew" type="button">New dataset</button>
  <button id="btnCompute" type="button">Compute kernels</button>
  <label class="slider-label">
    Bandwidth γ
    <input id="gamma" type="range" min="1" max="20" value="5" step="1">
    <span id="gammaVal">5</span>
  </label>
</div>
<div class="panels">
  <div class="panel">
    <div class="panel-title">Dataset (8 points, 2 classes)</div>
    <canvas id="scatter" width="180" height="180"></canvas>
  </div>
  <div class="panel">
    <div class="panel-title">Quantum kernel K<sub>Q</sub></div>
    <canvas id="kq" width="180" height="180"></canvas>
  </div>
  <div class="panel">
    <div class="panel-title">Classical RBF kernel K<sub>RBF</sub></div>
    <canvas id="krbf" width="180" height="180"></canvas>
  </div>
</div>
<div id="status" class="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.slider-label { display: flex; align-items: center; gap: .4rem; font-size: .85rem; font-weight: 600; }
input[type=range] { width: 100px; }
#gammaVal { font-size: .85rem; min-width: 1.5ch; }
.panels { display: flex; gap: .7rem; flex-wrap: wrap; }
.panel { display: flex; flex-direction: column; align-items: center; }
.panel-title { font-size: .78rem; font-weight: 600; color: #555; margin-bottom: .3rem; text-align: center; }
canvas { border: 1px solid #cdd9e3; border-radius: 6px; background: #f8fafc; display: block; }
.status { font-size: .88rem; font-weight: 600; min-height: 1.3em; margin-top: .6rem; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Quantum-inspired ZZ feature map kernel (simplified, exact for 2 features) ──
// For a 2D point x = [x0, x1] the ZZ feature map encodes into a 4-dimensional
// (2-qubit) Hilbert space. The kernel is:
//   K_Q(x, y) = |<phi(x)|phi(y)>|^2
// where |phi(x)> = cos(x0)*cos(x1)|00> + cos(x0)*sin(x1)|01>
//               + sin(x0)*cos(x1)|10> + sin(x0)*sin(x1)|11>
// This is a rank-1 state, so the inner product is:
//   <phi(x)|phi(y)> = cos(x0-y0)*cos(x1-y1)  [product formula]
// => K_Q(x, y) = cos^2(x0-y0) * cos^2(x1-y1)
// This is a deterministic, analytically exact quantum kernel (no sampling).

const N = 8; // number of data points
let pts = [];  // [{x, y, cls}]
let gamma = 5;

function featureScale(v) {
  // Map [0,1] -> [0, pi] for the quantum circuit angle
  return v * Math.PI;
}

function kQuantum(a, b) {
  const ax = featureScale(a.x), ay = featureScale(a.y);
  const bx = featureScale(b.x), by = featureScale(b.y);
  const c0 = Math.cos(ax - bx), c1 = Math.cos(ay - by);
  return c0 * c0 * c1 * c1;
}

function kRBF(a, b, g) {
  const dx = a.x - b.x, dy = a.y - b.y;
  return Math.exp(-g * (dx * dx + dy * dy));
}

function generateDataset() {
  pts = [];
  // Two roughly separable clusters
  for (let i = 0; i < N; i++) {
    const cls = i < N / 2 ? 0 : 1;
    const cx = cls === 0 ? 0.28 : 0.72;
    const cy = cls === 0 ? 0.28 : 0.72;
    pts.push({
      x: Math.max(0.05, Math.min(0.95, cx + (Math.random() - 0.5) * 0.35)),
      y: Math.max(0.05, Math.min(0.95, cy + (Math.random() - 0.5) * 0.35)),
      cls
    });
  }
}

function drawScatter() {
  const cv = document.getElementById('scatter');
  const ctx = cv.getContext('2d');
  const W = cv.width, H = cv.height;
  ctx.clearRect(0, 0, W, H);
  const PAD = 18;
  const toX = v => PAD + v * (W - 2 * PAD);
  const toY = v => PAD + (1 - v) * (H - 2 * PAD);
  // Axes
  ctx.strokeStyle = '#cdd9e3'; ctx.lineWidth = 1;
  ctx.strokeRect(PAD, PAD, W - 2 * PAD, H - 2 * PAD);
  // Points
  pts.forEach(p => {
    ctx.beginPath();
    ctx.arc(toX(p.x), toY(p.y), 6, 0, 2 * Math.PI);
    ctx.fillStyle = p.cls === 0 ? '#1d6fa4' : '#e63946';
    ctx.fill();
    ctx.strokeStyle = '#fff'; ctx.lineWidth = 1.5;
    ctx.stroke();
  });
}

function kernelMatrix(kFn) {
  return pts.map(a => pts.map(b => kFn(a, b)));
}

function drawKernel(canvasId, mat) {
  const cv = document.getElementById(canvasId);
  const ctx = cv.getContext('2d');
  const W = cv.width, H = cv.height;
  ctx.clearRect(0, 0, W, H);
  const n = mat.length;
  const cw = W / n, ch = H / n;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const v = mat[i][j]; // in [0,1]
      // Color: white=0, deep blue=1
      const r = Math.round(255 * (1 - v * 0.82));
      const g = Math.round(255 * (1 - v * 0.7));
      const b = Math.round(255 * (1 - v * 0.15));
      ctx.fillStyle = `rgb(${r},${g},${b})`;
      ctx.fillRect(j * cw, i * ch, cw + 1, ch + 1);
      // Diagonal: red dot
      if (i === j) {
        ctx.fillStyle = 'rgba(230,57,70,0.5)';
        ctx.fillRect(j * cw, i * ch, cw + 1, ch + 1);
      }
    }
  }
  // Grid lines
  ctx.strokeStyle = 'rgba(255,255,255,0.4)'; ctx.lineWidth = 0.5;
  for (let i = 0; i <= n; i++) {
    ctx.beginPath(); ctx.moveTo(i * cw, 0); ctx.lineTo(i * cw, H); ctx.stroke();
    ctx.beginPath(); ctx.moveTo(0, i * ch); ctx.lineTo(W, i * ch); ctx.stroke();
  }
}

function frobeniusSim(A, B) {
  let num = 0, da = 0, db = 0;
  for (let i = 0; i < A.length; i++) for (let j = 0; j < A[i].length; j++) {
    num += A[i][j] * B[i][j];
    da += A[i][j] * A[i][j];
    db += B[i][j] * B[i][j];
  }
  return num / (Math.sqrt(da) * Math.sqrt(db));
}

function computeAndDraw() {
  const matQ = kernelMatrix(kQuantum);
  const matR = kernelMatrix((a, b) => kRBF(a, b, gamma));
  drawKernel('kq', matQ);
  drawKernel('krbf', matR);
  const sim = frobeniusSim(matQ, matR);
  document.getElementById('status').textContent =
    fmt('Kernel similarity (cosine of matrices): %v%% — %v2%', { v: (sim * 100).toFixed(1), v2: sim > 0.9 ? 'very close (quantum speedup likely illusory here)' :
     sim > 0.7 ? 'moderate difference (some quantum structure)' :
                 'significant difference (quantum kernel is distinct)' });
  console.log('K_Q diagonal check (should all be 1):', matQ.map(r => r[matQ.indexOf(r)]).map(v => v.toFixed(4)).join(' '));
  console.log('K_RBF diagonal check (should all be 1):', matR.map((r, i) => r[i]).map(v => v.toFixed(4)).join(' '));
}

// Init
generateDataset();
drawScatter();
document.getElementById('btnNew').addEventListener('click', () => {
  generateDataset();
  drawScatter();
  document.getElementById('kq').getContext('2d').clearRect(0, 0, 180, 180);
  document.getElementById('krbf').getContext('2d').clearRect(0, 0, 180, 180);
  document.getElementById('status').textContent = 'New dataset generated. Click "Compute kernels".';
});
document.getElementById('btnCompute').addEventListener('click', computeAndDraw);
document.getElementById('gamma').addEventListener('input', function () {
  gamma = parseInt(this.value);
  document.getElementById('gammaVal').textContent = gamma;
  if (document.getElementById('status').textContent) computeAndDraw();
});
Result
Console

Click New dataset to generate random points in two classes, then click Compute kernels to see the similarity matrices side by side. Notice that for many datasets the two kernels agree closely — this is the intuition behind dequantization: if a classical kernel can mimic the quantum one, any quantum speedup for training is illusory. Adjust the bandwidth γ slider to see how the RBF kernel changes, and look for datasets where the quantum kernel produces a distinctly different similarity structure.

The Real Complexity

The central question in QML is deceptively simple: do quantum computers offer a provable, practical speedup for learning from data? The answer, as of 2025, remains open — and the evidence cuts both ways.

The dequantization blow. In 2018, Ewin Tang (then an undergraduate) showed that the celebrated quantum recommendation-system algorithm of Kerenidis and Prakash (2016) could be matched by a classical algorithm using quantum-inspired sampling — reducing a claimed exponential speedup to a polynomial one. Similar dequantization followed for quantum PCA, quantum SVMs, and quantum linear-systems solvers when applied to machine learning tasks. The key insight: many quantum speedups relied on reading data from a quantum RAM (QRAM); once you allow a classical algorithm the same efficient sampling access, the quantum edge disappears.

What may survive. Not all hope is lost:

  • Quantum kernels: using quantum circuits as feature maps creates kernels that cannot be efficiently computed classically if the underlying circuit is hard to simulate. Whether these kernels are useful (not just hard) is open.
  • Variational quantum circuits: hybrid quantum-classical optimizers (VQE, QAOA variants) are actively studied, but barren plateaus — exponentially vanishing gradients — plague training of deep circuits.
  • Quantum simulation for chemistry: learning molecular properties via quantum simulation retains strong theoretical backing, though practical advantage awaits fault-tolerant hardware.

Status: open (2025). There is no proven separation between quantum and classical learning in the standard computational model. The field is experimental, and the question of whether a quantum advantage for general machine learning is achievable — and for what problems — remains one of the most important open problems at the intersection of complexity theory and data science. It sits alongside P vs NP in the sense that a decisive answer would reshape computing.

Where It Matters

Even without a settled theory, QML is already influencing research and industry:

  • Drug discovery and quantum chemistry: simulating molecular energies is a natural quantum task. Variational quantum eigensolvers (VQE) target ground-state energies of small molecules, with direct relevance to designing new drugs and materials. This is where the clearest near-term quantum advantage is expected.
  • Optimization: many machine learning problems reduce to optimization. Quantum annealing and QAOA are studied for combinatorial problems like portfolio optimization and scheduling — though classical solvers remain competitive.
  • Finance: quantum amplitude estimation can speed up Monte Carlo pricing of financial derivatives quadratically, a genuine (polynomial) quantum speedup over classical sampling.
  • Classical algorithm design: perhaps the most surprising payoff of QML research. Dequantization showed that quantum-inspired sampling (via low-rank approximations and efficient data structures) can dramatically speed up classical algorithms for recommendation and linear algebra — a direct gift from quantum thinking to classical computing.
  • Error correction research: quantum error correction is itself an ML-adjacent task; neural-network decoders are a promising approach.

The honest assessment: near-term quantum advantage in ML is likely domain-specific (chemistry, simulation) rather than general. But the theoretical cross-pollination with classical algorithm design has already paid dividends.

Conclusion

Quantum machine learning is a field that lived through a rapid arc of hype and correction — and emerged more interesting for it. The early dream of exponential speedups for arbitrary learning tasks was too good to be true; dequantization showed that the quantum advantage in many algorithms came from sampling tricks, not from the strangeness of quantum mechanics itself.

What remains is more nuanced and arguably more exciting: a precise, ongoing investigation into exactly which data tasks genuinely benefit from quantum computation, and which can be matched by clever classical algorithms. Quantum kernels, simulation of physical systems, and quadratic speedups for Monte Carlo tasks are live candidates. General quantum learning advantage remains open.

The lesson echoes through all of complexity theory: the hardness of a problem is about its structure, not its disguise. Understanding what makes a quantum speedup real — rather than apparent — is teaching us deep truths about computation itself. Whether you follow P vs NP or quantum advantage, the questions are different faces of the same mystery: what can be computed, and how fast?

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quantum-machine-learning/Content licensed under CC BY-NC 4.0.