Quantum Machine Learning: Quantum Advantage for AI

In April 2023 the Union Cabinet approved India's National Quantum Mission with an outlay of ₹6,003.65 crore through 2031, funding quantum computing hardware, communication, and sensing across IITs, IISc, and startups. One of those startups, the Bengaluru-based QpiAI, builds at the exact seam this chapter is about: it does not choose between quantum computing and AI, it fuses them, using quantum processors to accelerate parts of machine learning pipelines — molecular property prediction for drug candidates, combinatorial search over chip layouts — where the object being learned is itself a quantum system or a search space too large for classical enumeration. That fusion is quantum machine learning (QML), and the question this chapter answers precisely is: where does a quantum computer actually help a learning algorithm, where is the help only conjectured, and where has the claimed help been disproven outright? All three answers matter, and conflating them is the single most common error in how QML gets reported.

Why classical learning strains against a wall quantum states don't hit

You already know, from feature maps in kernel SVMs and from the query-key inner products inside transformer attention, that a learning algorithm's expressive power depends on the space it computes similarity in. A classical computer represents a vector of n real features with n real numbers. A system of n qubits, in contrast, lives in a Hilbert space of dimension 2ⁿ — the state is a complex vector of 2ⁿ amplitudes, and operations on it (unitary gates) act linearly across the entire exponentially large space at once. Twenty qubits already span a million-dimensional space; fifty qubits needs roughly 18 petabytes just to hold the amplitudes in double precision — beyond the RAM of all but the world's largest supercomputers — and by around 270 qubits the state vector would need more numbers than there are atoms in the observable universe. This is precisely why classically simulating quantum chemistry — the wavefunction of a mid-sized drug molecule's electrons — is intractable past a few dozen strongly correlated orbitals, which is the actual, well-established motivation for VQE-based quantum chemistry (Peruzzo et al., Nature Communications 5, 4213, 2014). Quantum machine learning asks a narrower, harder-to-answer question: can that same exponential state space be turned into a genuine computational resource for the very different task of classification, regression, or generative modelling over ordinary data — molecules, images, tabular features — not the wavefunction of a quantum system itself? The rest of this chapter builds the two families of quantum learning models that attempt this (quantum kernels and variational quantum circuits), derives their mechanics exactly, and then draws the line between where the exponential space actually pays off and where it doesn't.

The quantum feature map: encoding classical data into a Hilbert space

The kernel trick you already know computes similarity via K(x,y) = φ(x)·φ(y) for some feature map φ you never have to write down explicitly, as long as you can compute the inner product. A quantum feature map does exactly this, with φ(x) realised as a quantum state |ψ(x)⟩ prepared by a data-dependent circuit U(x) acting on |0⟩. The simplest version, on a single qubit, uses an angle-encoding rotation gate:

RY(θ) = [ cos(θ/2)  -sin(θ/2) ]
          [ sin(θ/2)   cos(θ/2) ]

|ψ(x)⟩ = RY(x)|0⟩ = [ cos(x/2), sin(x/2) ]ᵀ

The quantum kernel is the squared overlap (fidelity) between two encoded states: K(x₁,x₂) = |⟨ψ(x₁)|ψ(x₂)⟩|², measurable on hardware via a SWAP test or, for this simple case, directly from the statevector. Expand the inner product:

⟨ψ(x1)|ψ(x2)⟩ = cos(x1/2)cos(x2/2) + sin(x1/2)sin(x2/2)
                = cos((x2 - x1)/2)      [cosine difference identity]

K(x1,x2) = cos²((x2 - x1)/2)

This is an exact, closed-form kernel — a genuine Mercer kernel over the encoded data, produced by a physical device rather than a hand-picked function like the RBF kernel. Trace it numerically. Take two training points x₁ = 0.4 rad, x₂ = 1.0 rad:

import numpy as np, math

def RY(theta):
    c, s = math.cos(theta/2), math.sin(theta/2)
    return np.array([[c, -s],
                      [s,  c]])

zero = np.array([1.0, 0.0])

x1, x2 = 0.4, 1.0
psi1 = RY(x1) @ zero        # [0.98006658, 0.19866933]
psi2 = RY(x2) @ zero        # [0.87758256, 0.47942554]

inner  = np.vdot(psi1, psi2)   # 0.9553364891256061
kernel = abs(inner) ** 2       # 0.9126678074548393

print(round(kernel, 6))        # 0.912668

Run the closed-form check independently: (x₂ − x₁)/2 = 0.3 rad, cos(0.3) = 0.955336…, squared = 0.912668… — matching the matrix computation to six decimal places, because the RY matrix product and the trigonometric identity are the same statement written two ways. Points encoded close together in angle produce a kernel near 1 (highly similar); points encoded far apart approach 0. This is a legitimate similarity function a classical SVM could then use — the point of QML is not this single-qubit case, which a classical computer reproduces trivially, but what happens when you scale it up with entanglement.

Where entanglement makes the kernel hard to fake

Havlíček, Córcoles, Temme, Harrow, Kandala, Chow, and Gambetta (Nature 567, 209–212, 2019) construct a feature map on n qubits that first applies single-qubit rotations encoding each feature, then an entangling layer of two-qubit gates whose angle depends on the product of two features, x_ix_j (their "ZZFeatureMap"), repeated for a few layers. The resulting state's amplitudes are a function of the data that mixes every pair of features through entanglement — not a Cartesian concatenation of independent per-feature rotations. The specific claim in that paper is a complexity-theoretic conjecture, not a proof: circuits of this "instantaneous quantum polynomial" (IQP) structure are believed, based on results connecting their output distributions to counting problems in the polynomial hierarchy, to be exponentially hard for a classical computer to sample from or estimate inner products of, for a generic choice of the entangling structure. "Believed hard" is doing real work in that sentence — it rests on standard but unproven complexity assumptions (the polynomial hierarchy does not collapse), the same class of assumption underlying most claims of quantum computational advantage, including Google's 2019 sampling experiment. Treat it as a strong conjecture with real hardware evidence (Havlíček et al. ran small versions on IBM hardware and got a functioning classifier), not as a settled theorem — because whether that hardness ever converts into a practical advantage for a real, noisy dataset is exactly the open question the rest of this field is fighting over, and the misconception section below shows one specific case where an equally confident early claim did not survive.

Variational quantum circuits: the quantum analogue of a trainable network

A quantum kernel is one architecture; the other, more widely used one is the variational quantum circuit (VQC), sometimes called a quantum neural network. Rather than fixing the feature map and handing overlaps to a classical SVM, a VQC adds a second block of gates whose rotation angles θ are trainable parameters, exactly analogous to weights in a classical layer:

1. Encode: classical input x is loaded via a fixed feature map U(x), producing |ψ(x)⟩.
2. Transform: a parameterised "ansatz" W(θ) — alternating layers of single-qubit rotations RY(θ_i) and fixed entangling CNOT gates — acts on the encoded state, producing W(θ)U(x)|0⟩.
3. Measure: an observable such as Pauli-Z on one qubit is measured, repeated over many circuit executions ("shots") to estimate its expectation value ⟨Z⟩.
4. Compute loss: a classical computer compares ⟨Z⟩ to the true label and computes a loss L(θ).
5. Update: a classical optimiser updates θ and the loop repeats.

This is a genuinely hybrid algorithm — the quantum processor only ever does step 2 and 3 (state preparation and measurement), while every other step, including deciding how to change θ, runs on an ordinary CPU. That hybrid loop is what the diagram below depicts.

Training on a quantum computer: the parameter-shift rule

Classical backpropagation needs the intermediate activations of every layer to compute ∂L/∂θ via the chain rule. A quantum circuit gives you no such access: the state vector is not observable, only measurement outcomes are, and measuring the state destroys it. You cannot "peek inside" a quantum circuit the way autograd peeks inside a PyTorch graph. This forces a different gradient method, and the one used in essentially every VQC library (Qiskit, PennyLane) is the parameter-shift rule (Mitarai, Negoro, Kitagawa & Fujii, Phys. Rev. A 98, 032309, 2018; Schuld, Bergholm, Gogolin, Izaac & Killoran, Phys. Rev. A 99, 032331, 2019).

For a gate of the form G(θ) = exp(−iθP/2) where P is a Pauli operator (so P² = I) — exactly the RY gate above — the expectation value of any observable as a function of θ is a pure sinusoid in θ, and its exact derivative is:

∂C/∂θ = ½ [ C(θ + π/2) − C(θ − π/2) ]

This is not a finite-difference approximation — it is an algebraic identity, exact for any θ, derived from the fact that C(θ) itself is a single cosine. Trace it. Let the observable be ⟨Z⟩ after a bare RY(θ) rotation on |0⟩, so C(θ) = cosθ exactly. Evaluate at θ = 0.6 rad:

import math
theta = 0.6
C      = math.cos(theta)                    # 0.825336
C_plus = math.cos(theta + math.pi/2)         # -0.564642
C_minus= math.cos(theta - math.pi/2)         #  0.564642
grad_shift    = 0.5 * (C_plus - C_minus)     # -0.564642
grad_analytic = -math.sin(theta)             # -0.564642

The two agree to full floating-point precision, because cos(θ+π/2) = −sinθ and cos(θ−π/2) = sinθ, so ½[(−sinθ) − sinθ] = −sinθ, exactly the calculus derivative of cosθ. On real hardware, C(θ+π/2) and C(θ−π/2) are each estimated by running the circuit with that shifted angle many times and averaging the measured ±1 outcomes — two extra full circuit executions per parameter, per training step. That cost — linear in the number of parameters, and each evaluation itself needs many shots to beat measurement shot noise — is the real practical bottleneck of training VQCs, distinct from and additional to the barren-plateau problem below.

The NISQ ceiling: barren plateaus and noise

Classical deep networks have a vanishing-gradient problem that architecture fixes (residual connections, normalisation, careful initialisation). Variational quantum circuits have a structurally different and so far unsolved version. McClean, Boixo, Smelyanskiy, Babbush & Neven (Nature Communications 9, 4812, 2018) prove that for a sufficiently expressive, randomly initialised ansatz, the variance of ∂C/∂θ shrinks exponentially in the number of qubits n. Practically: on a random 20-qubit ansatz, most gradient components are so close to zero that no realistic number of shots distinguishes them from measurement noise, and the optimiser cannot tell which direction to move — a "barren plateau" rather than a slope. This is not fixed by a better classical optimiser, because the signal genuinely isn't there in the measured expectation values; it has to be fixed by constraining the ansatz itself (shallower circuits, problem-informed structure instead of a generic random one, or the "local cost function" restructuring proposed in follow-up work). Layer this on top of decoherence and gate error on real NISQ-era hardware — the noisy intermediate-scale quantum regime Preskill names and characterises in Quantum 2, 79 (2018) — and you get why every VQC result reported today runs on a handful of qubits and a handful of ansatz layers, not the deep, wide circuits the complexity-theoretic hardness arguments actually require to matter.

Misconception: "quantum superposition means an automatic exponential speedup for any ML task"

The instinct is that because a qubit register holds a superposition over 2ⁿ basis states at once, a quantum algorithm evaluates a function on all 2ⁿ inputs "in parallel" and so must be exponentially faster at anything. This is false, and the field's own history shows exactly why. In 2016, Kerenidis & Prakash proposed a quantum recommendation-system algorithm claiming polylogarithmic runtime in the dimensions of a user–item matrix — an apparently exponential speedup over the best known classical algorithms, and for several years it was cited as one of the flagship examples of quantum advantage for ML. In 2018–19, Ewin Tang — then an undergraduate — showed a classical randomized algorithm, given the same kind of sample-and-query access to the data that the quantum algorithm assumed (via an efficiently sampleable data structure, not raw matrix access), that matched the polylogarithmic scaling (Tang, "A quantum-inspired classical algorithm for recommendation systems," STOC 2019). The quantum algorithm was "dequantized": its apparent advantage came from comparing it against classical algorithms without an equivalent access model, not from any genuine use of superposition or entanglement. The same dequantization program has since matched or closed the gap for several other early linear-algebra-flavoured QML claims (quantum PCA, quantum supervised clustering). Measurement is the reason parallelism doesn't give a free lunch: a superposition over 2ⁿ states collapses to exactly one outcome when read out, so a useful quantum algorithm has to engineer constructive interference so the right answer's amplitude survives to be the one you're likely to measure — that engineering is the actual hard part, it is task-specific, and it is exactly what is missing (or provably unnecessary) in the tasks that got dequantized. The honest statement of quantum advantage in ML is narrow: it holds only where a task-specific, adversarially-checked hardness argument exists (as with the IQP-based kernels above, or with genuinely simulating a quantum system as VQE does), never as a blanket property of superposition itself.

Active recall

Attempt these before reading the worked answers.

1. Starting from |ψ(x)⟩ = RY(x)|0⟩, derive the single-qubit quantum kernel formula K(x₁,x₂) = cos²((x₂−x₁)/2), showing the trigonometric identity used.
2. Using the same feature map, the training point is at x₁ = 0.4 rad. A test point arrives at x = 1.6 rad. Compute K(0.4, 1.6) and state whether this test point is more or less similar to the training point than the original x₂ = 1.0 rad point was.
3. Now suppose the encoding is changed to half-angle, |ψ'(x)⟩ = RY(x/2)|0⟩. Rederive the kernel formula for this new map and recompute it for x₁ = 0.4, x₂ = 1.0. Then state whether the parameter-shift gradient rule for the trainable ansatz RY(θ) gate (downstream of this feature map) also needs to change, and why or why not.
4. A cost function is C(θ) = ⟨Z⟩ = cosθ after a bare RY(θ) rotation. Use the parameter-shift rule to compute ∂C/∂θ at θ = 1.2 rad, and check it against the calculus derivative.
5. Explain, in one or two sentences, why the parameter-shift rule gives the exact gradient for a Pauli-rotation gate, while a classical finite-difference estimate (e.g. [C(θ+ε)−C(θ−ε)]/2ε for small ε) only approximates it.
6. A classmate says: "Ewin Tang dequantized quantum recommendation systems, so quantum computers have no real advantage anywhere in machine learning." What is wrong with this generalisation, and name one QML task where a quantum advantage is still a live, defensible claim (proven or strongly conjectured) rather than a dequantized one.

Worked answers

1. RY(x)|0⟩ = [cos(x/2), sin(x/2)]^T. The inner product ⟨ψ(x₁)|ψ(x₂)⟩ = cos(x₁/2)cos(x₂/2) + sin(x₁/2)sin(x₂/2). This is exactly the cosine-difference identity cosAcosB + sinAsinB = cos(A−B) with A = x₁/2, B = x₂/2, giving cos((x₁−x₂)/2) = cos((x₂−x₁)/2) (cosine is even). Squaring for the kernel (fidelity) gives K = cos²((x₂−x₁)/2).

2. K(0.4, 1.6) = cos²((1.6−0.4)/2) = cos²(0.6) = 0.681179. Compare to the original K(0.4, 1.0) = cos²(0.3) = 0.912668. The new test point has a lower kernel value, so it is less similar to the x₁ = 0.4 training point than the original x₂ = 1.0 point was — consistent with 1.6 rad being farther from 0.4 rad in angle than 1.0 rad is.

3. With |ψ'(x)⟩ = RY(x/2)|0⟩ = [cos(x/4), sin(x/4)]^T, the identical derivation gives K'(x₁,x₂) = cos²((x₂−x₁)/4). For x₁=0.4, x₂=1.0: (1.0−0.4)/4 = 0.15, K' = cos²(0.15) = 0.977668 — noticeably higher than before, because halving the angle compresses all points closer together in Hilbert space, inflating every kernel value toward 1 and reducing the model's ability to discriminate between distant points. The parameter-shift rule for the ansatz's RY(θ) gate, however, does not change: the shift rule is a property of the trainable gate exp(−iθP/2) itself (it needs P²=I, satisfied by any Pauli rotation regardless of what precedes it), not of the fixed, non-trainable feature-map block that comes before it in the circuit. This is the trap: changing the encoding changes the kernel and the data the ansatz receives, but leaves the gradient rule for θ untouched, since θ and x are different gates with different (in this case, no) coupling.

4. C(1.2) = cos(1.2) = 0.362358. C(1.2+π/2) = cos(2.770796) = −0.932039. C(1.2−π/2) = cos(−0.370796) = 0.932039. Shift-rule gradient = ½(−0.932039 − 0.932039) = −0.932039. Calculus derivative: −sin(1.2) = −0.932039. Match to full precision.

5. Because C(θ) for a Pauli-rotation gate is exactly a single sinusoid in θ (not merely locally smooth), the two points θ±π/2 sit at the sinusoid's zero-crossings of curvature relative to θ, and the algebra above shows the resulting difference formula equals −sinθ exactly for any θ, with no truncation. A classical finite-difference estimate instead relies on a Taylor expansion truncated after the linear term, so it only approaches the true derivative as ε→0, and any nonzero ε carries an O(ε²) error.

6. The flaw is generalising from one dequantized linear-algebra task to all of machine learning. Tang's result specifically undercuts algorithms whose claimed speedup came from a privileged sampling/query access model on data with low-rank structure — it says nothing about tasks where hardness comes from a different source. Quantum kernel estimation using an entangling IQP-style feature map (Havlíček et al., 2019) is still a live, defensible case: its conjectured classical hardness rests on sampling-complexity arguments (tied to the polynomial hierarchy not collapsing), not on the linear-algebra access-model gap that dequantization exploits, and it has not been dequantized. VQE for molecular ground-state energy estimation (Peruzzo et al., 2014) is a stronger case still, since the object being computed — the state of an actual quantum system — is exactly what classical computers struggle to represent at all, dequantization or not.

Think About It

Think about this: How would you explain quantum machine learning: quantum advantage for ai to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

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 advantage for 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 advantage for 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 advantage for 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.