Quantum Computing and AI

The previous three chapters explored alternative learning paradigms: reinforcement learning, continual learning, and intrinsic motivation. All of them operate within the classical computational framework — silicon chips pushing bits through logic gates. This chapter asks whether a fundamentally different computational substrate could change the game.

The short answer is: not yet, and probably not soon. But the longer answer involves understanding what quantum computing actually does, what makes it different, and why the intersection with AI is simultaneously exciting and overhyped. Since Alfonso has a background in quantum mechanics, this chapter will move through the physics quickly and focus on the computational implications.

Quick Mechanics Recap

Three quantum-mechanical phenomena are relevant to quantum computing:

Superposition. A classical bit is either 0 or 1. A quantum bit (qubit) can exist in a superposition of both states simultaneously, described as α|0⟩ + β|1⟩, where α and β are complex amplitudes satisfying |α|² + |β|² = 1. When measured, the qubit collapses to |0⟩ with probability |α|² or |1⟩ with probability |β|². Before measurement, the qubit is genuinely in both states — not "we don't know which," but "it's both."

Entanglement. Two or more qubits can be correlated in ways that have no classical analog. If two qubits are entangled, measuring one instantly determines the state of the other, regardless of distance. Entanglement allows quantum circuits to create and manipulate correlations between qubits that classical computers cannot efficiently represent. An n-qubit system requires 2ⁿ complex amplitudes to fully describe its state — this exponential state space is the source of quantum computing's potential power.

Measurement / collapse. Accessing quantum information destroys the superposition. You can't "read out" a qubit's amplitudes; you can only get a single classical bit (0 or 1) from each measurement. The art of quantum algorithm design is arranging the amplitudes so that, when you measure, the answer you want has high probability. This is fundamentally different from classical computing, where you can inspect intermediate results freely.

Quantum Gates and Circuits

Just as classical computing builds computation from logic gates (AND, OR, NOT), quantum computing builds computation from quantum gates that operate on qubits. The key difference: quantum gates are unitary operations — they're reversible transformations on the qubit state that preserve the total probability.

Common quantum gates:

A quantum circuit is a sequence of gates applied to a register of qubits. The circuit starts with qubits in a known state (typically all |0⟩), applies a sequence of gates that create superpositions, entangle qubits, and manipulate amplitudes, then measures some or all qubits to extract a classical result. The challenge is designing gate sequences where quantum interference — constructive for correct answers, destructive for incorrect ones — amplifies the probability of the desired outcome.

What Quantum Computing Is Good At

Quantum computers aren't faster at everything. They provide provable speedups for specific classes of problems, and the nature of those speedups matters for understanding the relevance to AI.

Shor's Algorithm: Factoring

Peter Shor's 1994 algorithm can factor large integers in polynomial time, compared to the best known classical algorithms, which are sub-exponential.¹ This is the most famous quantum algorithm because it breaks RSA encryption. But factoring has essentially no relevance to AI. It's mentioned here only because it's the clearest example of quantum advantage — a problem where quantum computers are provably, dramatically faster than classical ones.

Grover's Algorithm: Unstructured Search

Lov Grover's 1996 algorithm searches an unstructured database of N items in O(√N) time, compared to O(N) classically.² This is a quadratic speedup — real, but not exponential. For a database of a million items, Grover's searches in ~1000 steps instead of ~1,000,000. Useful, but not the kind of exponential gap that would transform a problem from impossible to tractable.

Optimization and Sampling

Quantum annealing (used by D-Wave's quantum processors) attempts to find the global minimum of a cost function by exploiting quantum tunneling to escape local minima. In principle, this could accelerate combinatorial optimization problems — the kind with many variables and constraints, like scheduling, logistics, or protein folding. In practice, definitive quantum advantage over the best classical optimization algorithms has not been demonstrated on real-world problems at commercially relevant scales.

Sampling from complex probability distributions is another area where quantum devices may have an edge. Google's 2019 "quantum supremacy" experiment showed that their 53-qubit Sycamore processor could sample from a specific probability distribution in 200 seconds, a task they estimated would take a classical supercomputer ~10,000 years.³ This was a genuine milestone, but the sampled distribution was specifically designed to be hard for classical computers — it had no practical application. IBM subsequently disputed the classical estimate, suggesting it could be done in days with clever techniques. The point stands that quantum computers can do something faster, but the "something" was purpose-built to showcase quantum advantage.

Quantum Machine Learning

The intersection of quantum computing and machine learning has generated enormous interest and a substantial body of theoretical work. The main approaches:

Variational Quantum Circuits

Also called parameterized quantum circuits or quantum neural networks, these are quantum circuits with tunable gate parameters that are optimized using classical gradient-based methods. The circuit acts as a model: input data is encoded into qubit states, the circuit processes it, and measurements produce output. The classical optimizer adjusts the gate parameters to minimize a loss function, just like training a classical neural network.

This is a hybrid quantum-classical approach — the quantum circuit does the forward pass, and the classical computer handles the optimization. It's designed for near-term "noisy intermediate-scale quantum" (NISQ) devices that don't have enough qubits or low enough error rates for full fault-tolerant algorithms.

Quantum Kernels

Kernel methods (support vector machines and related algorithms) compute similarity between data points using a kernel function. The idea behind quantum kernels is that mapping data into a quantum state space creates a feature space that's exponentially larger than any classical feature space of the same input dimension. If the "right" features for a classification task happen to live in this quantum feature space, a quantum kernel could be more powerful than any classical one.

The "if" in that sentence is doing a lot of work. There's no general argument for why real-world data would be better classified in quantum feature spaces, and empirical demonstrations have been limited to small-scale problems.

Quantum Approximate Optimization Algorithm (QAOA)

QAOA, proposed by Farhi, Goldstone, and Gutmann in 2014, uses a variational quantum circuit specifically designed for combinatorial optimization problems.⁴ It alternates between two types of quantum gates — one encoding the problem constraints and one encouraging exploration — with the number of alternation steps as a tunable depth parameter. As the depth increases, QAOA theoretically approaches the optimal solution. In practice, the achievable depth on current hardware is very limited.

What Quantum Doesn't Obviously Help

Here is the uncomfortable truth for anyone hoping quantum computing will accelerate AI in the near term:

Training a transformer involves three computationally expensive operations:

1. Matrix multiplication — computing attention scores, projections, and feedforward layers. Classical GPUs perform this with extraordinary efficiency at massive scale. The best known quantum algorithms for matrix multiplication (based on quantum linear algebra) require fault-tolerant quantum computers with orders of magnitude more qubits than currently exist.
2. Backpropagation — computing gradients through the network. This is fundamentally a chain of matrix operations applied sequentially. Quantum parallelism doesn't help with sequential dependencies.
3. Optimization — updating parameters using computed gradients. This is iterative by nature. Each step depends on the previous one.

The mismatch is fundamental. Quantum computing excels at problems with specific mathematical structure (periodicity for Shor's, unstructured search for Grover's, specific optimization landscapes for annealing). Deep learning's computational bottleneck is raw linear algebra throughput on known, structured operations — the exact regime where GPUs excel and quantum computers offer no clear advantage.

Current Hardware Reality

Understanding the gap between quantum computing's theoretical potential and its practical state requires looking at the hardware:

The error correction overhead is the critical bottleneck. Current quantum error correction codes require roughly 1,000 physical qubits to create one reliable logical qubit. This means that a quantum computer with 1,000 physical qubits has, in error-corrected terms, approximately 1 logical qubit — not enough to do anything useful. Google's 2024 Willow chip demonstrated that their error correction was improving with scale (a crucial threshold), but the path from there to millions of reliable logical qubits is long.⁵

Where Quantum Might Actually Matter

Setting aside the hype, there are areas where quantum computing could genuinely intersect with AI, though most of these are indirect rather than "making transformers faster":

• Molecular simulation — simulating quantum-mechanical systems (molecules, materials) is exponentially expensive on classical computers but natural on quantum ones. This could accelerate drug discovery, materials science, and chemistry — not by making AI faster, but by generating training data or solving problems that AI systems are applied to.
• Combinatorial optimization — if quantum annealing or QAOA achieves practical advantage on real optimization problems, this could help with aspects of AI like neural architecture search, hyperparameter optimization, or certain planning problems.
• Sampling from complex distributions — some generative AI applications involve sampling from probability distributions that are hard to represent classically. Quantum computers might enable sampling from distributions that classical computers can't efficiently sample from, though whether these distributions are useful for practical AI tasks is unclear.
• Quantum-enhanced feature spaces — if certain classification or regression problems are naturally suited to quantum feature spaces, quantum kernels could outperform classical methods. This is speculative but not impossible.

The Timeline Question

Experts in the field generally estimate that practical quantum advantage for real-world AI tasks is at least a decade away, and possibly much more. The path requires:

1. Dramatic improvement in qubit quality and error rates
2. Scaling to millions of physical qubits (currently at ~1,000)
3. Development of quantum algorithms that actually outperform the best classical algorithms on relevant problems (not just purpose-built benchmarks)
4. A software and tooling ecosystem that makes quantum computing accessible to ML practitioners

Each of these is a major engineering and scientific challenge. The history of quantum computing has been one of persistent optimism about timelines that consistently prove too aggressive. This is not to say the technology is unimportant — it's potentially transformative — but the timeline for transformation is measured in decades, not years.

Quantum computing asks whether a different computational substrate could change what's computable in practice. The next chapter asks a complementary question: instead of changing the computer, what if we change the interface — connecting artificial computing directly to the biological neural substrate? Neural interfaces blur the boundary between artificial and biological intelligence in a different way entirely.