Quantum Computing for AI: The Future of Computation

On 23 October 2019, Google published a paper in Nature claiming its 53-qubit Sycamore processor had achieved "quantum supremacy": it ran a specific random-circuit-sampling task in about 200 seconds that Google estimated would take the world's fastest classical supercomputer, Summit, roughly 10,000 years (Arute et al., 2019). Headlines ran with "quantum computers now beat classical ones." Two days before Nature's official publication, IBM researchers had already published a rebuttal arguing that with a smarter use of Summit's secondary storage, the same simulation could run in about 2.5 days, not 10,000 years — a gap of six orders of magnitude, not infinity (Pednault et al., 2019). Both claims can be true at once: Sycamore really did sample a probability distribution that is astronomically hard to simulate naively, and a better classical algorithm really did close most of the gap. Neither side's number tells you anything about whether Sycamore could train a neural network, optimise a delivery route, or do anything an AI engineer cares about — because random circuit sampling has no known connection to any AI-relevant computation.

That gap between a genuine, narrow, physics result and the "quantum AI revolution" headline it gets turned into is the subject of this chapter. Two companion chapters in this curriculum, Quantum Machine Learning and Quantum Computing and Quantum Machine Learning: Quantum Advantages in AI, build up the mechanics of variational quantum circuits — parameterised quantum gates trained like neural-network layers. This chapter deliberately does not repeat that ground. Instead it asks a harder, more useful question for an AI engineer in 2026: of the things quantum hardware can actually do today, on real noisy machines with a few thousand qubits, which ones touch AI at all, and by how much? The honest answer runs through a different branch of quantum computing entirely — quantum annealing — and through a class of problems called QUBOs that show up constantly in machine learning pipelines: feature selection, clustering, and training certain probabilistic models.

What NISQ Actually Means

Physicist John Preskill coined the term NISQ — Noisy Intermediate-Scale Quantum — in a 2018 paper to describe the hardware era we are still in (Preskill, 2018). "Noisy" means every qubit operation has a real error rate: even IBM's best superconducting processors run two-qubit gates with error rates on the order of 10⁻³ per gate, and errors compound multiplicatively across a circuit, so a 100-gate algorithm retains only around 90% of its original fidelity, and error accumulation only gets worse as circuits deepen. "Intermediate-scale" means qubit counts in the hundreds to low thousands — IBM's Condor chip reached 1,121 qubits in December 2023, and D-Wave's annealing hardware has scaled further, with the Advantage system offering just over 5,000 qubits on a "Pegasus" connectivity graph and the newer Advantage2 topology ("Zephyr") pushing past 4,000 more densely connected qubits. These are large numbers next to the 53 qubits of Sycamore, but they are minuscule next to what fault-tolerant quantum computing needs: useful error-corrected algorithms are projected to require thousands of physical qubits per logical qubit once error-correction overhead is included. NISQ machines have no error correction. Every result they produce is a raw, noisy sample, and treating that sample as a certain answer is the single most common mistake in "quantum AI" reporting.

Two Different Machines, One Confused Public

"Quantum computer" covers two fundamentally different architectures, and conflating them is where a lot of hype gets manufactured. Gate-model machines (IBM, Google, Sycamore, and the variational circuits the sibling chapters cover) apply a programmable sequence of quantum logic gates to qubits, in direct analogy to classical logic circuits — general-purpose, but currently limited to shallow circuits before noise destroys the signal. Quantum annealers (D-Wave's commercial line, the machines this chapter focuses on) are special-purpose: they are built to do exactly one thing, find low-energy configurations of a specific mathematical object called an Ising model, by physically evolving a bank of qubits from an easy starting state into the problem's energy landscape. Annealers are not general-purpose computers — you cannot run a text classifier or a transformer on one — but the one thing they do is a computation AI systems need constantly: combinatorial optimisation. That narrower target, plus larger qubit counts and non-existence of the gate-error-accumulation problem, is why annealing produces the most mature evidence base for near-term quantum-AI intersection, and why it deserves its own honest audit.

QUBO: The Language Annealers Speak

A Quadratic Unconstrained Binary Optimisation problem asks you to choose binary variables x₁, …, xₙ ∈ {0, 1} to minimise an energy function of the form E(x) = Σᵢ Qᵢᵢxᵢ + Σᵢ<ⱼ Qᵢⱼxᵢxⱼ, where Q is a matrix of coefficients you design to encode your actual problem — the diagonal terms reward or penalise individual choices, the off-diagonal terms reward or penalise pairs of choices made together. QUBO is mathematically equivalent to the Ising model of statistical physics (a simple substitution sᵢ = 2xᵢ − 1 turns one into the other), which is exactly what an annealer's qubits are built to minimise physically: cool a bank of coupled qubits, tune the couplings to match your Qᵢⱼ, and let the adiabatic theorem do the work. The adiabatic theorem says that if a quantum system starts in the ground state of an easy, well-understood Hamiltonian and you change that Hamiltonian slowly enough into the hard one you actually care about, the system stays in the ground state throughout — so at the end, measuring it gives you (with high probability) the minimum-energy configuration, which is your optimisation answer. "Slowly enough" is the catch, and it is quantitative: the required anneal time scales as roughly 1/Δ², where Δ is the smallest energy gap the system passes through during the anneal. A large gap means a fast, reliable anneal. A small gap means either a very slow anneal or noisy, unreliable output — and, crucially, the size of that gap is a property of your specific problem instance, not something you control. This single fact is the real reason quantum annealing does not uniformly "solve NP-hard problems fast," and it is worth internalising with numbers rather than as a slogan.

Worked Example: Selecting Cricket-Analytics Features by QUBO

Suppose an IPL analytics team is building a compact win-probability model and must pick exactly k = 2 of three candidate features to feed it: Strike Rate (SR), Economy Rate (ER), Powerplay Wickets (PW). Each feature has a relevance score against the win-label (higher is more predictive) and each pair has a redundancy score (higher means the two features carry overlapping information, so paying for both is wasteful):

relevance:  SR = 0.8   ER = 0.6   PW = 0.5
redundancy: SR-ER = 0.3   SR-PW = 0.1   ER-PW = 0.2

The naive approach — just take the two highest-relevance features — picks SR and ER. A QUBO formulation instead minimises E(x) = −Σᵢ rᵢxᵢ + Σᵢ<ⱼ redᵢⱼ xᵢxⱼ + P(Σᵢxᵢ − k)², where the first term rewards relevance (negative sign because we minimise), the second penalises redundant pairs, and the last term is a soft constraint forcing exactly k = 2 selections, with penalty weight P chosen large enough to make constraint violation costly. Using P = 1.5 (large enough to dominate any single feature's 0.8-point relevance gain) and expanding (Σxᵢ − 2)² = −3Σxᵢ + 2Σᵢ<ⱼxᵢxⱼ + 4 (using xᵢ² = xᵢ for binary variables), the full energy function collapses to linear coefficients (SR: −5.3, ER: −5.1, PW: −5.0) and quadratic coefficients (SR-ER: 3.3, SR-PW: 3.1, ER-PW: 3.2), plus a constant +6. This is exactly the 3×3 QUBO matrix shown in the diagram below.

With only 3 binary variables there are 2³ = 8 candidate configurations, small enough to check by brute force and confirm what the annealer's physics is supposed to find:

import itertools

relevance = {"SR": 0.8, "ER": 0.6, "PW": 0.5}
redundancy = {("SR", "ER"): 0.3, ("SR", "PW"): 0.1, ("ER", "PW"): 0.2}
P = 1.5
k = 2
features = ["SR", "ER", "PW"]

results = []
for bits in itertools.product([0, 1], repeat=3):
    x = dict(zip(features, bits))
    linear = -sum(relevance[f] * x[f] for f in features)
    quad = sum(redundancy[pair] * x[pair[0]] * x[pair[1]] for pair in redundancy)
    penalty = P * (sum(x.values()) - k) ** 2
    energy = linear + quad + penalty
    results.append((bits, round(energy, 2)))

results.sort(key=lambda t: t[1])
for bits, energy in results:
    print(bits, energy)

Running this prints, in ascending order of energy (bits are ordered SR, ER, PW):

(1, 0, 1) -1.2
(1, 1, 0) -1.1
(0, 1, 1) -0.9
(1, 1, 1) 0.2
(1, 0, 0) 0.7
(0, 1, 0) 0.9
(0, 0, 1) 1.0
(0, 0, 0) 6.0

The true minimum is (1, 0, 1): select SR and PW, not the naive top-two pick of SR and ER, which sits second at −1.1. The reason is exactly the redundancy term the naive approach ignores: SR and ER overlap by 0.3 (batters with high strike rate often also have low economy against them in T20 data, so the two features are partially telling the model the same thing), while SR and PW overlap by only 0.1. PW's slightly lower standalone relevance (0.5 versus ER's 0.6) is more than compensated by how much new information it adds once SR is already selected. This is the actual value QUBO-based feature selection offers over greedy relevance ranking, and it is a real, published class of formulation, not a toy invention for this chapter.

Now look at the gap between the true ground state (−1.2) and the next-best feasible configuration (−1.1): only 0.1 energy units. By the adiabatic scaling argument above, a gap this small is a genuinely hard instance for an annealer — it needs a slow anneal or it will frequently report the wrong (but still fairly good) answer. The diagram's readout panel shows this happening: even with the correct QUBO matrix loaded onto the hardware, repeated anneals return the true optimum only part of the time, with the near-miss (SR, ER) showing up often enough to matter. That is not a bug in the demonstration — it is the actual statistical behaviour you get back from a real annealer, and any pipeline built on one has to treat its output as a noisy sample, not a certified answer.

Misconception: "Superposition Lets It Try Every Answer at Once"

The most common thing students believe after a first exposure to quantum computing is that because n qubits can be placed in superposition of all 2ⁿ basis states simultaneously, a quantum computer effectively evaluates every candidate answer to a search or optimisation problem in parallel and "just knows" the best one. This is wrong in a specific, important way: superposition gives the system amplitude spread across all 2ⁿ states, but the instant you measure — which is the only way to get an answer out — the superposition collapses to exactly one basis state, chosen randomly with probability given by the amplitudes (for gate-model machines) or by something close to a thermal Boltzmann distribution over the annealed energies (for annealers). You get one sample per run, not a readout of "all the answers." That is exactly what the histogram in the diagram shows: 1,000 independent anneals of the identical QUBO produce a distribution over outcomes, weighted toward low energy but scattered across several states, precisely because the ground state's advantage (a 0.1 gap) is small enough for thermal and control noise to blur the picture. Getting a reliable answer out of a quantum device is therefore a statistical exercise — run many shots, take the most frequent or lowest-energy result — and the number of shots you need to be confident grows as the energy gap shrinks, via the same 1/Δ² adiabatic-theorem scaling that governs how slowly you must anneal in the first place. "Exponential parallelism" describes the amplitudes that exist inside the device between input and measurement; it does not describe what you are allowed to read out.

Does Quantum Annealing Actually Beat Classical Solvers?

The evidence is much narrower than commercial framing suggests, and it is worth naming the specific results rather than gesturing at "yes" or "no." In 2016, a Google-led team including Vasil Denchev benchmarked a D-Wave 2X annealer against simulated annealing on spin-glass instances deliberately engineered to have tall, thin energy barriers — the exact geometry where quantum tunneling should help most (Denchev et al., 2016, Physical Review X). They found up to a roughly 10⁸-times speedup over single-core simulated annealing on those specific instances — but a more sophisticated classical algorithm, quantum Monte Carlo simulation, matched the annealer's scaling on the same problems, meaning the "speedup" was really evidence about which classical algorithm to compare against, not proof of an unbeatable quantum advantage. In 2021, D-Wave researcher Andrew King and collaborators reported a clearer scaling advantage over path-integral Monte Carlo methods, but on a physics simulation task — modelling geometrically frustrated magnetic materials — that is a natural fit for what annealing hardware literally is, not a generic optimisation or machine-learning benchmark. Independent benchmarking work, notably by Catherine McGeoch and collaborators comparing D-Wave systems against tuned classical QUBO solvers on varied problem instances, has repeatedly found that generic, real-world-shaped optimisation problems do not show a consistent quantum edge once you compare against well-implemented classical heuristics rather than naive ones. The pattern across all of this: real speedups exist, but they are instance-specific and comparison-specific, not a blanket "quantum beats classical" result you can assume transfers to your feature-selection or scheduling problem.

Where Annealing Actually Touches AI Today

The most direct published link between quantum annealing and machine learning training is Adachi and Henderson's 2015 study, which used a D-Wave 2X to train a restricted Boltzmann machine — a generative model whose training procedure ordinarily requires sampling from a Boltzmann distribution via Gibbs sampling or contrastive divergence, both of which are classically slow approximations. Because an annealer's physical readout is approximately a Boltzmann-distributed sample over an Ising energy function, it is a natural (if unproven) fit for replacing that sampling step. Their RBM was trained on a coarse-grained, heavily downsampled version of MNIST-style digit images — small enough to fit the qubit budget of 2015 hardware — and the result showed the approach was feasible: a quantum-sampled RBM could learn a usable generative model of the data. It did not show a speed or accuracy advantage over classical training; the contribution was proof-of-concept, not superiority. Extending this from tens of visible units to the scale of any production computer-vision or NLP model — millions of parameters — is not a matter of degree, it is a wall: minor embedding chains grow with problem density, and a densely connected QUBO of even a few hundred logical variables can consume most of a 5,000-physical-qubit annealer's budget, because each logical variable's chain needs multiple physical qubits wired together to fake the connectivity a dense problem requires on a sparse hardware graph. This is the honest reason "quantum will train tomorrow's foundation models" claims do not survive contact with the hardware specifications: the qubit count on the datasheet and the usable problem size for your actual (usually densely connected) QUBO are very different numbers, and the gap between them is the embedding overhead visible in panel 2 of the diagram above.

The Honest Scorecard

Active Recall

Q1. A classmate says: "A quantum annealer with 5,000 qubits can obviously optimise problems classical computers can't touch, since it explores all 2⁵⁰⁰⁰ configurations in superposition." What is wrong with this statement, precisely?

Q2. In the SR/ER/PW worked example, recompute the ground state if the penalty weight P is lowered from 1.5 to 0.5. Does the optimal feature selection change? What else changes, and why does it matter for a real annealer?

Q3. Explain, using the adiabatic theorem's 1/Δ² scaling, why the SR/ER/PW instance (gap = 0.1) is a genuinely hard case for an annealer, and what an engineer could do about it (two options).

Q4. What specifically did Google's Sycamore experiment demonstrate, and what did it not demonstrate? Why does IBM's rebuttal matter more as a lesson in how to read quantum-advantage claims than as a verdict on who "won"?

Q5. What is minor embedding, and why does it mean the qubit count advertised for an annealer overstates the size of problem you can actually load onto it?

Q6. Adachi and Henderson (2015) trained a restricted Boltzmann machine using a D-Wave annealer. What did they actually show, and why is citing this result as evidence that "quantum computers can train deep learning models" a misuse of the paper?

Worked Answers

A1. Superposition does place amplitude across all 2ⁿ basis states simultaneously inside the device, but the moment you measure to extract a result, the state collapses to exactly one basis state, chosen with a probability set by the amplitudes (or, for an annealer, roughly the thermal distribution over Ising energies). You never get to read out all 2⁵⁰⁰⁰ configurations or "the best one directly" — you get one noisy sample per anneal, and must run repeated shots and take the lowest-energy or most-frequent result, exactly as the readout histogram in this chapter's diagram shows for a problem with only 8 possible configurations.

A2. With P = 0.5, the penalty expansion changes the linear coefficients to SR: −2.3, ER: −2.1, PW: −2.0 and the quadratic coefficients to SR-ER: 1.3, SR-PW: 1.1, ER-PW: 1.2, with constant +2. Re-evaluating all 8 states gives the same ranking order as before, with (1,0,1) — SR+PW — still the minimum at E = −1.2, so the optimal feature selection does not change. What does change is the margin protecting that answer: the three-feature state (1,1,1) falls from E = 0.2 (a 1.4-unit penalty relative to the optimum, effectively unreachable by noise) to E = −0.8 (only a 0.4-unit penalty, now competitive with the two-feature states). A weaker penalty still finds the right unconstrained optimum on this instance, but it erodes the safety margin against the constraint being violated under thermal noise — on real hardware, a lower P risks the annealer frequently returning an invalid answer (the wrong number of features selected) even when the underlying trade-off ranking is unaffected. This is why penalty-weight tuning is itself a nontrivial, instance-dependent step in QUBO engineering, not an afterthought.

A3. The adiabatic theorem requires the anneal time to scale roughly as 1/Δ², where Δ is the minimum energy gap the system passes through. With Δ = 0.1 in the worked example (the gap between the ground state at −1.2 and the first excited state at −1.1), 1/Δ² = 100 — a hundred-fold longer required anneal time than an instance with a gap of 1.0 would need, for the same reliability. Two practical responses: (1) anneal more slowly (increase the anneal schedule duration), trading speed for accuracy, though real annealers also accumulate more decoherence and control drift the longer they run, which caps how far this helps; (2) increase the number of shots and post-process by taking the lowest-energy sample observed rather than trusting any single read, which is exactly what the 1,000-shot histogram in the diagram represents.

A4. Sycamore demonstrated that a 53-qubit gate-model processor could sample from the output distribution of a specific pseudo-random quantum circuit faster than Google's classical estimate for the best available algorithm at the time — a well-defined, narrow computational task with no established connection to optimisation, machine learning, or any other AI-relevant computation. It did not demonstrate any AI capability, nor a permanent, uncontested classical-versus-quantum gap: IBM's rebuttal, using better exploitation of Summit's secondary storage, cut the claimed 10,000-year classical runtime to about 2.5 days. The lesson is that "quantum advantage" claims are moving targets that depend entirely on which classical algorithm you compare against, and a claim's size (10,000 years! six orders of magnitude!) says nothing about its relevance to any other problem — the correct habit is always to ask "advantage over what specific classical method, on what specific task" before treating a number as meaningful.

A5. A QUBO's variables can, in principle, need to interact with every other variable (a fully connected problem graph), but physical annealing hardware only wires each qubit to a small, fixed number of neighbours (15 on D-Wave's Pegasus topology). Minor embedding is the process of representing one logical variable as a chain of several physical qubits wired together and forced to agree, so that the chain as a whole can reach enough physical neighbours to fake the connectivity the logical problem needs. Denser logical problems need longer chains, and chains consume physical qubits without adding new logical capacity — so a hardware datasheet's qubit count (e.g., ~5,000) substantially overstates the number of logical variables you can actually embed for anything but sparse, hardware-graph-friendly problems.

A6. Adachi and Henderson used a D-Wave 2X annealer's physical readout, which approximates sampling from a Boltzmann distribution over an Ising energy function, to replace the sampling step inside restricted Boltzmann machine training — a step classical training normally approximates with contrastive divergence or Gibbs sampling. They showed this substitution was feasible: a generative model trained this way learned usable structure from a small, coarse-grained image dataset. They did not show it was faster, more accurate, or scalable, and the dataset size (tens of visible units, far below any production model's parameter count) was dictated by 2015 hardware limits, not chosen to demonstrate an advantage. Treating this as evidence that "quantum computers can train deep learning models" overstates a feasibility demonstration into a capability claim the paper never made and current hardware cannot support at any competitive scale.

Think About It

Think about this: How would you explain quantum computing for ai: the future of computation 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.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind quantum computing for ai: the future of computation, 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.