You already know the kernel trick from classical SVMs: when two classes aren't linearly separable in the original feature space, you map the data into a higher-dimensional space where a hyperplane can separate them, and you never have to compute that mapping explicitly — only the inner products between mapped points, via a kernel function K(x, x') = <φ(x), φ(x')>. The RBF kernel implicitly maps into an infinite-dimensional space and still costs you nothing beyond evaluating an exponential.
Quantum kernel methods ask a sharper question: what if φ maps into a Hilbert space that a quantum computer can prepare as a physical state but that no classical computer can write down or manipulate efficiently? This isn't a hypothetical. IBM's original demonstration (Havlíček et al., Nature 567, 2019) built exactly this pipeline — encode classical data into an entangled quantum state via a parameterized circuit, estimate the resulting inner products on hardware, feed the resulting kernel matrix into an ordinary classical SVM. The two sibling chapters in this track cover the building blocks: basic qubits and gates, and variational circuits trained by gradient descent like neural-network layers. This chapter is about a different training paradigm entirely — one where the quantum computer never runs an optimizer at all. It only estimates numbers; a classical convex solver does the rest. That distinction matters more than it sounds, and by the end of this chapter you'll be able to derive, by hand, exactly what those numbers are and why quantum ML researchers frequently disagree about whether they're worth computing at all.
The quantum feature map, precisely
A quantum feature map is a unitary circuit U(x), parameterized by a classical data vector x, applied to a fixed reference state (almost always |0...0>):
|φ(x)> = U(x) |0...0>Unlike the variational circuits in the sibling chapter, U(x) here has no trainable parameters you gradient-descend on. Its only job is to encode x into a quantum state. The "learning" in this pipeline is entirely classical: it happens in the SVM's dual optimization, which touches the quantum state only through the numbers K(x_i, x_j) = |<φ(x_i)|φ(x_j)>|² — the fidelity, or overlap, between two encoded states. This quantity is a legitimate kernel (symmetric, positive semi-definite, because it's a squared inner product of vectors in a Hilbert space) so every guarantee that makes SVMs work classically — convexity of the dual problem, the representer theorem, generalization bounds in terms of margin — carries over unchanged. What's new is only where the numbers in the kernel matrix come from.
Worked example: a one-qubit feature map you can compute by hand
Take the simplest possible feature map: encode a single real number x (already scaled into radians) as a rotation of one qubit about the Y-axis of the Bloch sphere, starting from |0>:
|φ(x)> = RY(x)|0> = cos(x/2)|0> + sin(x/2)|1>This is a real-valued, two-component state vector — genuinely a point on a great circle of the Bloch sphere, nothing exotic. Now compute the kernel between two data points x and x':
<φ(x)|φ(x')> = cos(x/2)cos(x'/2) + sin(x/2)sin(x'/2)
= cos((x - x')/2) [cosine difference identity]
K(x, x') = |<φ(x)|φ(x')>|² = cos²((x - x')/2)That's a closed form — no circuit simulation needed to evaluate it. Take x = 0.4 and x' = 1.2 radians: K(0.4, 1.2) = cos²(0.4) = 0.8484 (rounded to four decimals; verified numerically below). Points with a small angular gap land close to 1 (nearly identical states, maximally similar); points 90° apart in angle land at exactly 0.5; points diametrically opposite (|x - x'| = π) land at 0 — orthogonal states, zero overlap.
Extend this to a tiny four-point toy dataset with angles x ∈ {0.0, 0.4, 1.2, 1.6} radians and compute the full 4×4 Gram matrix — the object an SVM actually consumes:
import numpy as np
def feature_state(x):
# RY(x) applied to |0>: cos(x/2)|0> + sin(x/2)|1>
return np.array([np.cos(x / 2), np.sin(x / 2)])
def quantum_kernel(x, xp):
phi_x = feature_state(x)
phi_xp = feature_state(xp)
overlap = np.dot(phi_x, phi_xp) # both states are real-valued
return overlap ** 2
data = [0.0, 0.4, 1.2, 1.6]
gram = np.array([[quantum_kernel(xi, xj) for xj in data] for xi in data])
np.set_printoptions(precision=4, suppress=True)
print(gram)Tracing this by hand for the (0,1) entry: feature_state(0.0) = [1, 0], feature_state(0.4) = [cos(0.2), sin(0.2)] = [0.98007, 0.19867], their dot product is 0.98007, squared gives 0.9605 — matching cos²(0.2) exactly, as the identity above guarantees. Running the full loop (verified by executing this exact code) prints:
[[1. 0.9605 0.6812 0.4854]
[0.9605 1. 0.8484 0.6812]
[0.6812 0.8484 1. 0.9605]
[0.4854 0.6812 0.9605 1. ]]This is the same matrix rendered as a heatmap in the diagram below (stage 4). Notice the Toeplitz-like structure: entries depend only on |x_i - x_j|, a direct consequence of the closed form — a feature you should expect to disappear the moment the feature map stops being this simple.
Estimating the kernel when you can't write down the closed form
The one-qubit example above was solvable by hand precisely because it was too simple to need a quantum computer at all — you'll see why that's the whole point in a moment. For a feature map that entangles multiple qubits, <φ(x)|φ(x')> generally has no such shortcut, and the standard way to measure it on hardware is the SWAP test: a small, fixed circuit that turns an unknown overlap into a measurement probability.
Load |φ(x)> into one register and |φ(x')> into another, add one ancilla qubit initialized to |0>, and run: Hadamard on the ancilla, a controlled-SWAP of the two data registers conditioned on the ancilla, then a second Hadamard on the ancilla, then measure it. Trace the state through each step:
Start: |0>_a |φ(x)> |φ(x')>
After H: (1/√2)( |0>_a + |1>_a ) |φ(x)> |φ(x')>
After C-SWAP: (1/√2)[ |0>_a |φ(x)>|φ(x')> + |1>_a |φ(x')>|φ(x)> ]
After H: (1/2)[ |0>_a ( |φ(x)>|φ(x')> + |φ(x')>|φ(x)> )
+ |1>_a ( |φ(x)>|φ(x')> - |φ(x')>|φ(x)> ) ]The probability of measuring the ancilla in |0> is the squared norm of its coefficient branch:
P(0) = (1/4) · ||φ(x)>|φ(x')> + |φ(x')>|φ(x)>||²
= (1/4)[ 1 + |<φ(x)|φ(x')>|² + |<φ(x)|φ(x')>|² + 1 ]
= 1/2 + (1/2)|<φ(x)|φ(x')>|²
= 1/2 + (1/2) K(x, x')(The cross terms both equal |<φ(x)|φ(x')>|² because <a|b><b|a> = |<a|b>|² for any states.) So the SWAP test converts a kernel value in [0,1] into a biased-coin probability in [0.5, 1], recoverable as K = 2P(0) - 1. Plugging in our worked value K(0.4, 1.2) = 0.8484: P(0) = 0.5 + 0.5(0.8484) = 0.9242. Simulating 2000 shots at this true probability (a representative draw, shown for illustration rather than reproduced from executed code) gives 1846 zero-outcomes, so estimated_K = 2(1846/2000) - 1 = 0.846 — within 0.0024 of the true 0.8484, consistent with the expected shot noise for a Bernoulli estimator at this sample size (standard error ≈ √(p(1-p)/N) ≈ 0.006 on P(0), doubled to ≈0.012 on K).
This is the systems-engineering cost that doesn't show up in the elegant closed-form math: every entry of an n × n Gram matrix needs its own SWAP-test circuit and its own batch of shots to reach precision ε, and Hoeffding-bound shot counts scale as O(1/ε²) per entry. Building a full training kernel matrix therefore costs roughly O(n²/ε²) circuit executions — before you've even started the classical SVM solve. For datasets in the thousands, this is the practical bottleneck that variational circuits (which touch the quantum device once per gradient step, not once per pair of training points) don't share.
Where a real quantum advantage could live — and where it provably does
The one-qubit example was deliberately chosen to be classically trivial: cos²((x-x')/2) is a two-line NumPy function, no quantum hardware required. A single-qubit feature map is always a product state with no entanglement, and product-state overlaps are always classically efficient to compute. This is the essential design lever: real quantum kernel methods use entangling feature maps, most famously the ZZ feature map from Havlíček et al. (2019), which — after a layer of Hadamards — applies single-qubit phase rotations exp(ix_j Z_j) together with two-qubit terms exp(ix_j x_k Z_j Z_k), repeated across qubit pairs and typically over several layers. The Z_j Z_k terms are what entangle the qubits; without them, the circuit factorizes into independent single-qubit rotations and the whole thing collapses back to something as classically tractable as our worked example.
Entanglement alone doesn't guarantee a speedup — it only removes the easy classical shortcut. Havlíček et al. constructed their feature map around a problem believed to be classically hard (related to the discrete logarithm) precisely so that no known classical algorithm could estimate the resulting kernel efficiently, and they demonstrated the pipeline on real superconducting hardware. Liu, Arunachalam, and Temme (Nature Physics 17, 2021) went further and proved something rare in this field: a rigorous, unconditional exponential speed-up for a specific supervised-learning task built on the discrete-log problem, using a quantum kernel classifier of this type — not a conjecture, an actual proof, though for a dataset engineered to showcase the hardness, not a naturally occurring one.
That's the good news, tightly scoped. The caution — equally load-bearing — comes from two later results. Huang et al. ("Power of data in quantum machine learning," Nature Communications 12, 2021) showed empirically that on realistic datasets without engineered hardness structure, quantum kernels frequently underperform well-tuned classical kernels (RBF, polynomial), because the classical kernel's inductive bias happens to fit the data better — the Hilbert space being "big" doesn't help if the winning hypothesis wasn't hiding in the part only quantum states can reach. Thanasilp, Wang, Cerezo, and Holmes documented a sharper structural problem: as the number of qubits (and often circuit depth) grows, kernel values for generic entangling feature maps concentrate exponentially close to a fixed constant — nearly every pair of points looks equally "similar," which is fatal for a kernel's whole job of discriminating between points. Distinguishing a real signal from shot noise at that point requires exponentially many shots, erasing any quantum advantage in resource terms even where one exists in principle. There's also a structural bridge worth knowing: Schuld (arXiv:2101.11020, 2021) showed that supervised quantum ML models — including the variational circuits from the sibling chapter — can always be rewritten as kernel methods with an implicit feature map, meaning the two "different" quantum ML paradigms are two views of the same underlying object, evaluated differently (explicit kernel estimation here, versus a trained linear functional in Hilbert space there).
Common misconception
The mistake this chapter is built to correct: "Encoding classical data into qubits already gives you a quantum advantage, because the qubits are in superposition." Our own worked example is the counterexample: RY(x)|0> puts a qubit into a genuine superposition of |0> and |1>, and the resulting kernel is still exactly cos²((x-x')/2) — two lines of classical code, no advantage whatsoever, because a single qubit's state is fully described by two real numbers a classical computer stores and multiplies just as easily. Superposition of one isolated qubit buys you nothing; what a classical simulator cannot efficiently track is entanglement across many qubits, where the state vector's dimension grows as 2^n and no known compact classical description exists for a generic instance. And even entanglement is necessary but not sufficient — Huang et al. and Thanasilp et al. show that entangled feature maps routinely still lose to classical kernels or become useless due to exponential concentration. "Advantage" here is not a property of the qubit count; it's a property of a specific, provable computational-hardness gap for a specific problem structure, of which the discrete-log construction is currently the clearest known example.
The full pipeline
Active recall
Q1. Using the closed form K(x,x') = cos²((x-x')/2), compute K(0.0, 3.1416) (i.e. x' ≈ π) without a calculator, using only the fact that cos(π/2) = 0.
A1. (x-x')/2 = -π/2, and cos(-π/2) = cos(π/2) = 0, so K = 0² = 0. The two states are orthogonal — RY(0)|0> = |0> and RY(π)|0> = |1> exactly, which are maximally distinguishable, consistent with zero overlap.
Q2. In the SWAP test derivation, why does the cross term <φ(x)|φ(x')><φ(x')|φ(x)> appear twice (once from each cross-pairing when expanding the squared norm), and why does that make the final coefficient 1/2 rather than 1/4?
A2. Expanding ||A+B||² = <A|A> + <A|B> + <B|A> + <B|B> with A = |φ(x)>|φ(x')> and B = |φ(x')>|φ(x)> gives four terms. <A|A> = <B|B> = 1 (normalized states). The two cross terms, <A|B> and <B|A>, are complex conjugates of each other and each equals |<φ(x)|φ(x')>|², so they add rather than cancel. Total: 1 + K + K + 1 = 2 + 2K, times the outer 1/4, gives 1/2 + K/2 — the doubling of the cross term is exactly what turns the leftover 1/4 into 1/2.
Q3. Suppose the feature map angle in the worked example is rescaled by a hyperparameter γ, so the encoding becomes RY(γx) instead of RY(x). If γ=2, recompute K(0.4, 1.2), and then trace the full ripple: does the Gram matrix's Toeplitz structure survive? Does the SWAP-test shot budget change?
A3. The kernel becomes K_γ(x,x') = cos²(γ(x-x')/2). With γ=2: effective angles are 0.8 and 2.4, difference 1.6, halved is 0.8, so K = cos²(0.8) = 0.4854 — the value that previously sat at K(0, 1.6) in the unscaled matrix, not the old K(0.4,1.2)=0.8484 (verified: quantum_kernel(0.8, 2.4) = 0.48540..., matching). The ripple is not confined to one entry: every pairwise gap in the dataset is doubled by γ=2, so the entire Gram matrix changes — the Toeplitz structure survives (it's still a function only of γ(x_i-x_j)), but the matrix becomes more oscillatory in x, meaning points that used to look similar can now look dissimilar once their scaled angular gap crosses past π/2. This changes which support vectors the classical SVM selects and shifts its decision boundary, even though nothing about the SVM's own optimization changed. The SWAP-test shot budget (O(1/ε²) per entry) is unaffected in scaling — γ changes what value is being estimated, not how precisely a fixed number of shots estimates a probability — but if γ pushes many kernel values toward exponential concentration around a constant (large γ, many qubits, deep entangling maps), the effective shots needed to resolve real differences between kernel entries grows, tying back to the exponential-concentration caution above.
Q4. A classmate says: "Since the feature map circuit runs on a quantum computer, the whole classification pipeline is a quantum algorithm with the usual quantum speedup." What's wrong with this claim, referencing the pipeline diagram?
A4. Only stages 2 and 3 (feature map and SWAP test) run on quantum hardware; stage 5, the actual optimization that finds the classifier, is a classical convex quadratic program run on a classical computer, exactly as in ordinary kernel SVMs. "Quantum ML" here means quantum-assisted kernel evaluation, not a quantum optimizer. Even the quantum part isn't automatically advantaged — as the misconception section argues, only entangling feature maps built around a problem structure with a proven or strongly conjectured classical hardness gap (like the discrete-log construction) have any claim to speedup; a generic feature map, quantum or not, might just be computing something a classical kernel already computes as well or better.
Q5. Why is K(x,x') as defined here guaranteed to be a valid kernel (symmetric, positive semi-definite) regardless of what circuit U(x) is?
A5. K(x,x') = |<φ(x)|φ(x')>|² is, for any Hilbert space, exactly the squared magnitude of an inner product of two vectors — this is a Gram-matrix construction by definition. Symmetry follows because |<a|b>| = |<b|a>| for any states. Positive semi-definiteness follows from the general fact that any matrix of the form M_ij = <v_i, v_j> (or its modulus-squared variant built from a valid inner product) is PSD by construction — you can write it as V†V (V-dagger V) for some matrix of vectors V. This holds no matter what U(x) is, entangling or not, hardware-realizable or not — it's a property of quantum states living in a Hilbert space, not of the specific circuit.
Q6. Estimate, order of magnitude, how many total shots a full training run needs for n = 200 training points at precision ε = 0.01 per kernel entry, and identify the single biggest lever for reducing that cost that doesn't touch precision at all.
A6. Number of distinct off-diagonal entries in a symmetric 200 × 200 Gram matrix: 200·199/2 ≈ 19,900. At O(1/ε²) = O(1/0.0001) = O(10,000) shots per entry, total shots ≈ 19,900 × 10,000 ≈ 2 × 10⁸ — roughly 200 million circuit executions, which is the real reason quantum kernel methods are currently demonstrated on datasets of tens to low hundreds of points, not the millions classical SVMs handle routinely. The lever that doesn't touch precision: only computing entries actually needed by the SVM's support vectors after an initial coarse pass, or using a smaller, curated subset of "landmark" points (Nystrom-style low-rank kernel approximation) instead of the full n² matrix — trading exactness in the kernel approximation, not in each individual entry's shot precision, for a linear rather than quadratic scaling in n.
Practice Exercises
Now it is time to practice! Complete these challenges to solidify your understanding:
- Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
- Exercise 2: Find a real-world example where quantum machine learning: quantum advantages in ai is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
- Exercise 3: Create a mind-map connecting quantum machine learning: quantum advantages in ai to at least 3 other topics you have studied.
Key Takeaways — Summary and Recap
Let us recap what we covered: the core ideas behind quantum machine learning: quantum advantages in ai, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.