Quantum Speedup: Will AI Run Faster on Quantum Computers?

By. J. Philippe Blankert, 13 March 2025

Introduction

Quantum speedup refers to the performance gain achieved when a quantum algorithm solves a problem faster than the best known classical algorithm. In complexity theory terms, this often means a lower asymptotic runtime scaling. Some quantum algorithms offer polynomial speedups (e.g., a quadratic improvement), while others achieve exponential speedups. For example, Grover’s quantum search algorithm provides a polynomial (quadratic) speedup, whereas Shor’s algorithm for integer factoring yields an exponential speedup over classical approaches [microsoft.com]. Such dramatic speedups are significant because they suggest certain computational tasks that are infeasible for classical computers (e.g., breaking RSA encryption via prime factoring) could become tractable on quantum hardware.

AI researchers are intrigued by whether similar speedups could accelerate AI algorithms. Modern AI, especially deep learning, is heavily constrained by classical hardware limitations. The computational cost of training state-of-the-art AI models has grown exponentially – the compute used in the largest training runs increased 300,000× from 2012 to 2018, far outpacing Moore’s Law (which would yield only a 7× increase in that period) [openai.com]. This insatiable demand for compute means training cutting-edge models often requires massive clusters of GPUs or TPUs running for days or weeks. As we approach the limits of classical silicon chips and face slowing hardware improvement, there is growing interest in alternative computing paradigms. Quantum computers operate on fundamentally different principles and, in theory, can process certain computations in parallel superpositions, raising the question: can quantum computing expedite machine learning and other AI tasks? Indeed, “the question of whether quantum computing can speed up the learning process is important and largely unanswered” [link.aps.org].

In this article, we explore several key questions to assess if and how AI might run faster on quantum computers. We begin by reviewing the concept of quantum speedup in algorithmic complexity terms and known quantum algorithms that could impact AI. We then examine the potential advantages of running AI workloads on quantum hardware – from faster optimization to improved sampling and novel quantum-inspired models – along with concrete examples of current quantum processors (Google Sycamore, IBM Quantum, D-Wave, Xanadu, etc.). Next, we discuss the limitations and challenges facing quantum computing in the context of AI, including noise, scalability, and the lack of quantum memory. We survey recent benchmarking efforts comparing quantum and classical approaches on machine learning tasks, highlighting what has (and hasn’t) been achieved so far. Finally, we provide a future outlook on what theoretical and hardware breakthroughs are needed to make practical quantum AI a reality in the coming decade.

Understanding Quantum Speedup

Quantum speedup is formally understood by comparing the time complexity of the best quantum algorithm for a problem to that of the best known classical algorithm. A polynomial speedup means the quantum algorithm’s runtime scales as a polynomial of lower degree than the classical runtime. A classic example is Grover’s search: to search an unsorted database of size N, a classical brute-force needs ~N steps, whereas Grover’s algorithm finds the target in ~√N steps – a quadratic speedup (if N = 1,000,000 items, Grover finds the solution in about 1000 steps vs. 1,000,000 classically) [microsoft.com]. In contrast, an exponential speedup implies the quantum algorithm’s time grows exponentially slower with input size than the classical method. Shor’s factoring algorithm is the prime example: it can factor an n-bit integer in roughly polynomial time O(n^3), whereas the best known classical algorithms require sub-exponential or exponential time for large n. In complexity class terms, if a problem is in BQP (Bounded-Error Quantum Polynomial time) but believed to require super-polynomial time on a classical computer (not in P or BPP), a quantum computer can solve instances that are effectively intractable classically.

These distinctions are crucial – a quadratic speedup (like Grover’s) is valuable but might be outpaced by constant-factor improvements in classical hardware, whereas exponential speedup (like Shor’s) enables fundamentally new capabilities.

How does this translate to AI algorithms? Many AI problems, such as finding optimal parameters in a high-dimensional model or searching through combinatorial structures (like rule sets or feature selections), can be extremely computationally intensive. If such tasks can be mapped to known quantum algorithms or complexity classes with better scaling, AI could indeed “run faster” on a quantum computer. A few quantum algorithms are frequently discussed in the context of AI and machine learning:

Grover’s Search – While originally formulated for database search, Grover’s algorithm (and its generalization, amplitude amplification) can speed up any brute-force search by a square root factor. If an AI task involves searching through N possibilities (e.g., hyperparameter tuning or finding a specific failure case in a dataset), Grover’s approach could in principle cut the search iterations from N to ~√N. This is a polynomial speedup [microsoft.com]. In practice, one must have a way to construct a quantum oracle for the search problem, which is not always straightforward for arbitrary AI problems. Nonetheless, Grover’s algorithm is a reminder that unstructured search steps in AI algorithms might be quadratically accelerated.
Quantum Approximate Optimization Algorithm (QAOA) – QAOA is a hybrid quantum-classical algorithm introduced by Farhi et al. (2014) for solving combinatorial optimization problems by variationally evolving a quantum state [arxiv.org]. In QAOA, one sets up a parameterized quantum circuit alternating between applying a “problem” Hamiltonian (encoding the cost function of an optimization problem) and a “mixing” Hamiltonian. By tuning these parameters (with a classical optimizer), QAOA attempts to prepare a quantum state that encodes a high-quality solution (e.g., near-optimal assignment for an NP-hard optimization). The algorithm can be run at increasing depths p to improve solution quality [arxiv.org]. While QAOA does not provably provide an exponential speedup for generic NP-hard problems (which would be surprising, as that would imply NP⊆BQP), it is hoped to give better approximations or require fewer iterations than classical heuristics for certain problems. In the context of AI, many learning tasks (e.g., weight optimization in discrete models, scheduling of training jobs, or feature selection) can be formulated as optimization problems. QAOA, or other quantum optimization algorithms, could potentially find good solutions faster than classical algorithms like simulated annealing or genetic algorithms in some cases. Early studies have applied QAOA to small instances of portfolio optimization and scheduling, with performance being actively researched.
Variational Quantum Eigensolver (VQE) – VQE is another variational algorithm originally developed for quantum chemistry (finding ground-state energies) but broadly applicable to optimization [arxiv.org]. VQE uses a quantum circuit with adjustable parameters (an ansatz state) and a classical optimizer to minimize the expectation value of a given Hamiltonian. Essentially, it’s a quantum analog of variational methods: the quantum processor evaluates a cost function (via measurements of the Hamiltonian on the parameterized state), and a classical optimizer tweaks the parameters. The variational principle guarantees the cost (energy) is always an upper-bound to the true minimum, so it can iteratively converge. While the typical application is finding molecular ground energies, one can imagine using VQE-like approaches to minimize cost functions in machine learning (for example, formulating the training objective of a neural network as the expectation of some Hamiltonian). In fact, certain quantum neural network models (discussed below) use VQE-style training where the “cost Hamiltonian” encodes the training loss. VQE is considered one of the most promising near-term quantum algorithms because it can work with noisy hardware and relatively shallow circuits [arxiv.org]. However, like QAOA, it doesn’t guarantee a specific speedup over classical optimization; its success would depend on the optimizer landscape and whether the quantum state space provides a more efficient route to minima.
Quantum Linear Algebra Algorithms – Several quantum algorithms have been proposed to speed up linear algebra tasks that are core to machine learning. The Harrow-Hassidim-Lloyd (HHL) algorithm can solve a system of linear equations in time polylogarithmic in the dimension under certain conditions, an exponential improvement over classical Gaussian elimination which is polynomial in the dimension (though HHL has stringent requirements like a well-conditioned matrix and efficient data loading). Building on HHL, researchers have proposed quantum algorithms for tasks like least-squares regression, principal component analysis (quantum PCA), and support vector machines that in theory offer exponential or significant polynomial speedups for those specific linear algebra problems [arxiv.org]. For example, a quantum least-squares solver could potentially find regression coefficients in O(log N) time for N data points, given oracular access to the data – an exponential theoretical speedup [arxiv.org]. However, an important caveat is that these algorithms often assume the ability to efficiently load large classical data into quantum states (via quantum RAM) and to retrieve outputs, which may nullify the speedup if those steps are slow. We will revisit this caveat in the context of current hardware limitations. Nonetheless, the existence of quantum routines for linear algebra highlights that many subroutines of machine learning (linear regression, clustering via distance computations, matrix decompositions) could be accelerated if the I/O and precision issues are resolved.

In summary, quantum computing offers a variety of algorithmic techniques that, on paper, can outperform classical algorithms – sometimes modestly (polynomially) and sometimes spectacularly (exponentially). The relevance to AI is clear: if we can map parts of AI workflows (such as searching for a solution, optimizing a loss function, sampling from a complex distribution, or performing linear algebra on large vectors) to a quantum algorithm that has lower complexity, then we have a path for AI to run faster on quantum hardware. The next section looks at these potential advantages in more concrete terms, especially focusing on near-term quantum hardware and hybrid algorithms.

Potential Advantages of Running AI on Quantum Hardware

While fully error-corrected quantum computers capable of executing long algorithms are still in development, even noisy intermediate-scale quantum (NISQ) devices could provide speedups or improvements for certain AI-related tasks. Here we outline several potential advantages of using quantum hardware for AI, along with examples and emerging evidence:

Faster optimization and training: Many core AI tasks boil down to high-dimensional optimization (e.g., adjusting millions of neural network weights to minimize a loss function). Quantum algorithms might accelerate optimization in multiple ways. One possibility is quantum-enhanced gradient descent. Researchers have explored using quantum circuits to estimate gradients or solve linear systems involved in gradient calculations much faster than classical methods. For instance, one recent algorithm leverages quantum state amplitude encoding to perform sparse matrix inversion in logarithmic time, which can be used to train a deep neural network to a given error threshold exponentially faster than classical gradient descent, assuming the training data can be loaded efficiently into quantum memory [arxiv.org]. In a study by Zlokapa et al. (2021), they proposed training a wide and deep classical neural network using a quantum algorithm for solving linear equations; if the data distribution allows efficient state preparation, the quantum method runs in O(log n) time (for n training samples) compared to O(n) for classical gradient methods, an exponential speedup end-to-end [arxiv.org]. They demonstrated on the MNIST dataset that the quantum approach could achieve the same accuracy as a classical network, highlighting the potential for quantum speedup in training if the technical requirements (like fast quantum RAM) are met [arxiv.org]. Beyond gradient descent, quantum variants of other optimization techniques (like quantum evolutionary algorithms or quantum particle swarm optimizers) could similarly speed up the search for good model parameters. Quantum computers can also naturally evaluate multiple candidate solutions in superposition, potentially avoiding some local minima by tunneling through energy barriers (a principle exploited by quantum annealing).
Improved sampling and generative modeling: Sampling from complex probability distributions is another area where quantum computers may excel. Many generative AI models (e.g., Boltzmann machines, variational autoencoders) require sampling from high-dimensional distributions which can be slow to converge on classical hardware. Quantum devices can natively sample from probability amplitudes encoded in a quantum state. A prominent example is the use of quantum annealers (like the D-Wave system) to sample from Boltzmann-like distributions. Instead of using Gibbs sampling or Markov Chain Monte Carlo (which may mix slowly in networks with many variables), one can physically implement the model’s energy function as a quantum Ising Hamiltonian and let the quantum system sample low-energy states. In 2015, Adachi and Henderson showed that a D-Wave 2X quantum annealer could be used to train a Restricted Boltzmann Machine (RBM) by drawing samples from the model’s distribution [arxiv.org]. In their experiment on a small-scale image dataset, the quantum sampling-based training achieved comparable or better accuracy than conventional contrastive divergence (CD) training, while using significantly fewer iterations of the slow classical Gibbs sampler [arxiv.org]. This suggests that for certain generative learning tasks, quantum hardware might converge faster by more efficiently exploring the distribution of probable states. More generally, quantum random sampling could aid AI tasks that involve probabilistic inference, such as Bayesian network learning or probabilistic graphical models, by providing faster unbiased samples. Another concept is quantum Monte Carlo integration, where amplitude amplification can reduce the number of samples needed for estimation. If an AI algorithm spends a lot of time sampling (for example, in reinforcement learning for exploring policy space, or in generative modeling to sample outputs), quantum computers might offer a polynomial speedup by more quickly drawing high-quality samples from the target distribution.
Quantum-inspired neural networks: Quantum computing also introduces new forms of models inspired by quantum mechanics, which could enrich the toolbox of AI. One example is the Quantum Boltzmann Machine (QBM) [link.aps.org]. A QBM is a quantum analogue of a classical Boltzmann machine; it relies on quantum distributions (e.g., a quantum Hamiltonian with non-commuting terms) rather than classical Boltzmann distributions. The QBM can, in principle, represent probability distributions that classical networks find hard to capture (due to quantum entanglement between variables). Training a QBM is non-trivial (because measuring the quantum state can collapse the distribution), but researchers have developed methods to train these models by variational approaches or bounding the quantum probabilities [link.aps.org]. If successfully implemented at scale, QBM or related quantum graphical models could provide more expressive generative models for AI – potentially requiring fewer units or parameters than a classical network to model certain phenomena. Another promising direction is the use of variational quantum circuits as trainable models. In a quantum neural network or quantum circuit learning framework, one uses a parameterized quantum circuit (with tunable rotation angles, etc.) as the model, and a classical optimizer to adjust those parameters based on a cost function [link.aps.org]. Mitarai et al. (2018) showed that a low-depth quantum circuit can be trained to approximate nonlinear functions and perform binary classification, using a hybrid quantum-classical approach [link.aps.org]. These variational quantum circuits essentially act like neural networks (with the quantum gates analogous to neurons/weights) and can be trained on data. The hope is that such models, running on quantum hardware, might generalize better or learn representations more efficiently for certain problems than classical neural networks, especially if the data has inherently quantum characteristics (like quantum physics data) or lives in a very high-dimensional feature space that quantum states naturally inhabit. Even in purely classical data domains, some researchers speculate that quantum models might have an advantage in representational power (this is analogous to kernel methods: quantum states provide a high-dimensional feature space for free). Quantum circuits have also been proposed as quantum convolutional networks and quantum recurrent networks for sequence data, showing early promise in fields like quantum chemistry and finance for pattern recognition. While these quantum-inspired neural networks are in their infancy, they enlarge the landscape of AI models and could eventually surpass classical networks in speed (if each quantum layer is faster than a massive matrix multiplication on a classical CPU/GPU) or even in accuracy for certain tasks.
Hybrid quantum-classical systems: It’s worth noting that many near-term advantages will likely come from hybrid approaches that offload specific subroutines to quantum chips while keeping the rest of the AI workload classical. For example, one might use a quantum co-processor to compute a difficult sub-problem (like sampling a Gibbs distribution or computing a kernel matrix) faster than the classical CPU, thereby accelerating the overall algorithm. Another example is using quantum hardware to search for a good initial solution or pre-train a model which is then fine-tuned classically. These hybrid strategies align with the strengths of current quantum devices, which excel at certain tasks (like certain linear algebra or optimization primitives) but cannot handle a full end-to-end ML pipeline alone due to limited size and decoherence. By intelligently partitioning an AI workflow, one could achieve an overall speedup without requiring the quantum computer to do everything. Many quantum machine learning algorithms being explored (quantum kernel methods, variational classifiers, QAOA for ML, etc.) assume this hybrid model where quantum and classical resources work in concert. This is analogous to how today’s AI accelerators work (GPUs handle matrix multiplications, CPUs handle logic, etc.), except here the “GPU” is replaced by a QPU (quantum processing unit) specialized for certain computations.
Examples of quantum hardware relevant to AI: As of 2025, there are several quantum computing platforms that AI researchers are experimenting with:
- Superconducting Qubits (Gate-based) – Google’s Sycamore processor (53 qubits) famously demonstrated the power of quantum computing by performing in 200 seconds a random circuit sampling task that was estimated to take 10,000 years on a classical supercomputer [sciencedaily.com]. While that specific task (random bitstring sampling) was not a practical AI problem, it proved that quantum hardware can massively outperform classical computing on certain specialized problems. Google’s quantum AI team has also used Sycamore and its successors to run small quantum machine learning experiments (like quantum classification and generative modeling on few-qubit examples) using frameworks such as TensorFlow Quantum. IBM’s superconducting quantum computers are also advancing quickly – IBM’s Eagle processor (127 qubits, announced 2021) was the first to break the 100-qubit barrier. IBM noted that simulating a general 127-qubit state on a classical machine is practically impossible (each added qubit doubles the memory needed) [ibm.com], indicating that these quantum processors are entering regimes beyond brute-force classical simulation. IBM has since unveiled the Osprey chip with 433 qubits (2022) and has a roadmap toward machines with thousands of qubits in the next few years. These gate-based machines are the most flexible – in principle they can implement any quantum algorithm (Grover, QAOA, VQE, etc.) relevant to AI tasks, constrained only by circuit depth and noise.
- Quantum Annealers – D-Wave Systems has taken a different approach, building quantum annealing machines tailored for optimization problems. Their latest Advantage system boasts over 5,000 qubits with 15-way connectivity between qubits [thequantuminsider.com]. These qubits are not gate-programmable in the same way as universal quantum computers; instead, they evolve according to quantum annealing dynamics to find low-energy solutions of an Ising model that corresponds to the optimization problem of interest. D-Wave’s annealers have been used in discrete optimization tasks and sampling problems, including some machine learning applications like the Boltzmann machine training mentioned above. While annealers do not offer the algorithmic diversity of gate-based QPUs (and their theoretical speedup is limited to specific types of problems), they can handle larger numbers of qubits today and have been useful as a form of quantum accelerator for optimization-centric AI tasks (e.g., feature selection, scheduling, clustering via QUBO formulations). Notably, in a very recent result, D-Wave’s Advantage2 prototype was used to simulate a complex magnetic material faster than a classical supercomputer, completing in minutes a task that would take millions of years classically [ir.dwavesys.com]– a striking demonstration of raw quantum capability applied to a “useful” problem (materials simulation). This gives hope that for certain AI-relevant computations (like sampling complex energy landscapes), quantum annealers might already offer a huge advantage.
- Photonic Quantum Computers – Xanadu, a Canadian quantum computing company, is pursuing photonic quantum processors which use squeezed states of light as qubits (often called “qumodes” for continuous-variable quantum computing). Xanadu’s device Borealis with 216 photonic qumodes recently achieved a quantum computational advantage in Gaussian boson sampling, performing a task in 36 microseconds that would take a classical supercomputer an estimated 9,000 years [phys.org]. Photonic QCs are particularly interesting for AI because they can in principle operate at room temperature and interface with optical communication – one could imagine quantum optical neural networks that directly process optical data. Photonic systems can also implement certain mathematical operations (like matrix multiplication) very naturally using linear optics and squeezing. Xanadu’s software library PennyLane is designed to let machine learning researchers construct hybrid quantum-classical models that could run on photonic (or other) QPUs. While photonic quantum computers are still specialized (Borealis is not a general-purpose machine, it was built for boson sampling), they highlight an important point: there are multiple quantum hardware modalities, each with different strengths, and some might align very well with AI tasks like vector-matrix products, convolution operations, or generative sampling.
- Other platforms – Ion trap quantum computers (offered by IonQ, Quantinuum) also deserve mention. They have high-fidelity qubits and fully connected gates (making them good for algorithms like VQE on chemistry problems), though typically with tens of qubits so far. AI researchers have used IonQ devices for small-scale experiments like quantum SVMs and variational classifiers. Additionally, emerging architectures like neutral atom processors (Pasqal, QuEra) promise hundreds of highly connected qubits, which could be advantageous for graph-based machine learning. Each platform (superconducting, annealing, photonic, ion traps, etc.) might find its niche in accelerating different sub-tasks of AI.

In summary, quantum hardware is rapidly maturing, and even with current devices, researchers have started to identify niches where they can outperform or augment classical computation. Faster optimization, better sampling, and novel quantum models are three broad avenues for quantum advantage in AI. The examples above illustrate that these are not just theoretical – early evidence (though on small scales) shows quantum computers speeding up training iterations [arxiv.org] or matching classical performance with fewer steps [arxiv.org]. The variety of hardware means we might deploy quantum accelerators in different ways: a superconducting QPU to do a complex linear algebra step in a deep learning pipeline, or a quantum annealer to fine-tune a combinatorial feature selection. However, it’s equally important to temper these exciting possibilities with a clear understanding of the current roadblocks. We turn next to the limitations and challenges that must be addressed before AI can routinely run faster (and better) on quantum computers.

Current Limitations and Challenges

Despite the theoretical promise and early demonstrations, running AI workloads on quantum computers today faces significant challenges. We are in the NISQ era, where devices are noisy, of limited size, and lack error correction. Here we outline the key limitations and why a balanced view is necessary:

Noise and Decoherence: Quantum bits (qubits) are extremely fragile. They lose their quantum state (decohere) after a short time due to interactions with their environment, and quantum gates have non-zero error rates. Current superconducting qubits, for example, might maintain coherence for only tens or hundreds of microseconds, and two-qubit gate error rates are on the order of 0.1-1% in the best systems. This noise imposes a limit on how deep a circuit can be executed reliably – too many operations and the accumulated errors will wash out any quantum advantage. For AI algorithms, which often require many iterative steps (think of a training loop with thousands of parameter updates, or a large neural network with many layers), the circuit depth required may far exceed what a noisy quantum processor can handle without error correction. Although techniques like error mitigation and circuit recompilation can extend what’s feasible, they don’t fully solve the problem. As IBM’s quantum hardware team noted, building devices beyond 100 qubits was a huge challenge because “qubits can decohere – or forget their quantum information – with even the slightest nudge from the outside world” [ibm.com]. Until full quantum error correction is achieved, quantum computers must operate with a very low “instruction budget” before the probability of a fault becomes too high. This particularly impacts algorithms for AI: a quantum speedup on paper might require a large problem size that in turn needs many qubits and operations, but current hardware can only run small problem instances before noise dominates.
Limited Qubit Count and Connectivity: The number of qubits available in general-purpose quantum computers is still modest (tens to a few hundred). While special-purpose annealers have thousands of qubits, those qubits are not equivalent to the error-corrected logical qubits one would need for algorithms like Shor’s or HHL. In a future fault-tolerant quantum computer, it’s estimated we might need thousands or millions of physical qubits to encode the logical qubits for a complex algorithm. At present, no device can store the millions of parameters of a large neural network, for example. Additionally, connectivity (which qubits can directly interact with which) is limited in many architectures (e.g., a 2D grid for superconducting qubits). This can increase the circuit depth needed for multi-qubit operations (swapping qubits around), further straining the noise budget. Scaling is a major challenge: even though quantum information grows exponentially with qubit count (which is why simulating ~50 qubits is already intractable for classical computers [ibm.com]), we need structured, controllable qubit growth to tackle real AI problems. IBM’s 127-qubit and 433-qubit processors are important milestones, but still far off from the thousands of high-fidelity qubits likely required to do something like train a deep learning model better than classical hardware. In an AI context, this means that currently we can only set up relatively small toy models on quantum hardware (for instance, a quantum neural network with maybe 5–10 qubits, equivalent to a very small classical network). These small models can be valuable testbeds, but they cannot compete with the scale of modern deep learning which often involves billions of parameters trained on millions of data points.
Lack of Quantum Memory / Data Loading Bottleneck: One often overlooked issue is feeding data into a quantum algorithm. Many quantum machine learning algorithms assume the existence of a QRAM (Quantum Random Access Memory) that can load N data points into an n-qubit superposition in O(n) or O(log N) time. In reality, no such memory device exists yet. Currently, loading classical data (say the pixel values of an image, or a large dataset for training) into a quantum state is a slow process that could nullify any theoretical speedup. To illustrate, if you have to input a million data points one by one (which takes at least a million steps) into a quantum algorithm that then gives you a sqrt(N) speedup, you gained nothing overall. The encoding of data is thus a critical challenge. Most research papers assume an idealized ability to initialize quantum states with the data encoded in amplitudes or phases, but building a hardware QRAM with sufficient throughput and low error is very difficult – it would require a lot of qubits and operations itself [qcware.com]. A recent announcement by QC Ware highlighted that “most research assumes the availability of QRAM to load data on quantum computers; however, very few have worked on QRAM, and the few proposals around it come with very significant hardware requirements in qubit count and circuit depth” [qcware.com]. They instead developed specialized data loader algorithms as a workaround, but generally, quantum memory remains an open problem. For AI, this means that even if we had a powerful quantum accelerator for the computing part, the I/O of getting large training datasets in and results out could be a bottleneck. Similarly, storing the output model (say the learned weights of a neural network) in quantum form and using it for predictions would require either keeping the quantum state coherent (which is not possible indefinitely) or writing the model to classical memory, which could be expensive. Until there are breakthroughs in quantum memory or clever algorithms that minimize data movement, many proposed quantum ML speedups might not materialize in practice because “loading the bus” dominates the runtime.
Balancing Classical vs Quantum (When does classical win?): It’s important to recognize that a quantum computer will not automatically speed up every computation. Some tasks are inherently sequential or have low circuit complexity, and a classical processor might handle them as fast as or faster than a quantum one, especially given decades of optimization of classical algorithms and hardware. Currently, for almost all practical ML tasks, classical computing massively outperforms quantum simply because the quantum devices are so limited. For example, a classical GPU can train a small neural network in seconds, whereas trying to do the same on a few-qubit quantum device (even if theoretically possible) would be far slower and less accurate at present. In recent benchmarking experiments, quantum classifiers and quantum kernel methods have been compared to classical machine learning algorithms on the same data. The findings generally show parity or a gap in favor of classical methods for the small problem sizes where both can run. In one study, a variational quantum classifier with 10 qubits was tested on a high-energy physics dataset; with only 100 training samples, its performance was similar to classical SVM and decision tree classifiers [arxiv.org]– which is encouraging for the quantum side, but also a reminder that classical ML is very effective on small data too. Importantly, as soon as one scales up the dataset or model complexity, the classical algorithm can continue to run (perhaps taking more time), whereas the quantum experiment might be unable to scale due to qubit/depth limits. There’s also the overhead of hybrid algorithms: many quantum machine learning approaches use an outer classical optimization loop (like training parameters of a quantum circuit). Each iteration requires several quantum circuit executions to estimate gradients or evaluate the cost, which can be slow due to quantum device’s limited throughput (each circuit execution might be milliseconds including resetting qubits, etc., and you may need many repeated runs to get reliable statistics due to quantum measurement uncertainty). In contrast, classical GPUs can perform 1000+ parallel operations with almost unlimited repetition rates. So for now, classical computing often outperforms quantum except on contrived problems engineered to show quantum advantage. The crossover point – where a quantum method beats the best classical method – is a moving target and depends on both hardware progress and algorithm improvements. Hybrid quantum-classical algorithms try to mitigate this by letting each part do what it’s best at, but determining the split and managing the interaction overhead is a challenge in itself.
Algorithmic Uncertainties: Another challenge is more theoretical – we often do not know for sure if a particular AI problem has a super-polynomial quantum speedup. Some early claims of exponential speedups in quantum machine learning have been revisited by classical researchers who found “de-quantized” classical algorithms that achieve similar performance. A famous example is the quantum recommendation system algorithm (2009) which was later mimicked by a classical algorithm using sampling techniques (E. Tang, 2019) such that the purported exponential speedup vanished for practical purposes. This taught the community an important lesson: sometimes the quantum algorithm’s advantage relies on specific data assumptions or norms that may not hold generally, and a clever classical workaround can erode the gap. Thus, for each potential quantum advantage in AI, one must ask: is the problem genuinely hard for classical computers or can classical heuristics catch up? For instance, quantum annealing might find good solutions faster for some optimization, but classical simulated annealing and other solvers are also improving and may remain competitive. It’s an arms race – quantum algorithms open new paths, but we must ensure classical algorithms truly can’t easily replicate those results, or else the “quantum speedup” is not practically meaningful. At this time, there are no clear-cut examples of an AI task where a quantum approach indisputably outperforms all classical ones (on a fair footing with problem size). This doesn’t mean there won’t be – just that we have to carefully validate quantum advantages and be mindful that classical computing is a moving baseline.

In summary, the path to making AI run faster on quantum computers is obstructed by hardware noise, scale limitations, data I/O issues, and the need to prove true algorithmic advantages. As one Nature review succinctly put it, while quantum machine learning offers tantalizing prospects, “recent work has produced quantum algorithms that could act as building blocks of machine learning programs, but the hardware and software challenges are still considerable” [pubmed.ncbi.nlm.nih.gov]. To progress, researchers are actively working on error mitigation techniques, more efficient quantum algorithms (that use fewer qubits or tolerate noise), and hybrid methods that minimize quantum resource usage. The next section will look at how some of these experimental efforts are proceeding and what benchmarks tell us about the state-of-the-art in quantum vs classical AI performance.

Benchmarking AI on Quantum Computers

Given the challenges above, what have actual experiments shown so far when attempting AI or machine learning on quantum hardware? In this section, we discuss a few representative benchmarks and case studies from recent research, comparing quantum approaches to classical baselines in tasks relevant to AI.

Quantum Classifiers on Real Devices: One area of active research is using small quantum circuits to perform classification, similar to a tiny neural network or kernel method. In 2019, a team at IBM demonstrated a quantum kernel classifier where data is mapped into a quantum feature space and a simple classifier is implemented via interference. They showed that for carefully chosen synthetic data, a quantum feature mapping could separate classes that a classical linear classifier could not (a hint at possible advantage), though classical nonlinear kernels could often achieve similar results with enough feature engineering. More recently, Wu et al. (2021) applied a quantum variational classifier to real data from high-energy physics on an IBM quantum processor [arxiv.org]. They used 10 qubits to encode processed collider event data and trained a variational circuit to distinguish Higgs boson events from background noise. The results were encouraging: with a very small training set (100 events), the quantum classifier achieved accuracy on par with classical methods like Support Vector Machines (SVM) and boosted decision trees on the same data [arxiv.org]. Moreover, the quantum classifier’s performance on actual hardware was close to its simulated performance, indicating that noise was manageable at that scale [arxiv.org]. This experiment didn’t show a quantum speedup per se (since classical and quantum accuracies were similar, and classical training was actually much faster in wall-clock time), but it proved that current quantum machines can learn from data and reach classical-level accuracy for small problems. It’s a necessary first step: demonstrate viability on hardware. The next steps are scaling to larger datasets and more complex models, where perhaps quantum advantages might emerge. At the moment, any quantum model that can be simulated classically (which is the case for up to ~30 qubits or so) can also be trained classically, often faster. So the true test will come when quantum classifiers reach problem sizes beyond classical simulation, and we see if they still maintain accuracy or find patterns faster than classical training would.
Quantum Annealing for Machine Learning: D-Wave’s quantum annealers have been used in a number of machine learning contexts, usually by encoding a training or inference task as an optimization problem. A notable example, discussed earlier, was using the D-Wave to train Boltzmann machines. In the experiment by Adachi and Henderson [arxiv.org], the goal was to train a Restricted Boltzmann Machine (RBM) on a simplified MNIST dataset. Classically, RBM training uses Gibbs sampling which can be slow to converge because the Markov chain needs many steps to approximate the model distribution. By instead using the quantum annealer to draw samples (taking advantage of quantum fluctuations to traverse energy barriers), they were able to achieve the same or better quality models with far fewer sampling steps than classical training required [arxiv.org]. This is evidence of a concrete speedup in training iterations (albeit not a time-to-solution speedup in this case, since each quantum sampling step had overhead). It shows that quantum hardware can explore the solution space of a learning problem differently than classical methods, which might lead to faster convergence. Following this, other works have tried annealers for clustering (formulating k-means as a binary optimization problem), for feature selection in datasets, and for combinatorial graph analytics that have learning interpretations. While annealers don’t give a complexity-theoretic speedup, they might have a constant-factor or heuristic advantage on certain problems. D-Wave and its users often report results like “found solutions with better objective values than classical heuristics for certain instances”, though one has to be careful to ensure fair comparison. Nonetheless, these case studies are valuable as proof-of-concept that quantum hardware can be applied to AI model training in non-trivial ways.
Hybrid Quantum Neural Networks: Some teams have trained small hybrid quantum-classical neural networks, where a few quantum layers are inserted into a classical deep learning pipeline (for example, replacing a classical layer with a small variational quantum circuit). These networks are trained end-to-end using frameworks like PennyLane or TensorFlow Quantum that support automatic differentiation through quantum circuits. Benchmarks on simple image recognition (e.g., classifying tiny images like 4×4 pixel handwritten digits) have shown that these hybrid networks can learn similarly to all-classical networks for those cases. Again, the interest is whether for a fixed model size, the quantum hybrid might generalize better or require fewer training examples – as of now, no clear superiority has been demonstrated, but research is ongoing. A specific benchmark by Google’s Quantum AI group involved a hybrid quantum classifier for MNIST digits where the quantum circuit part was run on their Sycamore processor for up to 8 qubits; the accuracy was comparable to a classical neural network with a similar number of parameters. These experiments help debug the quantum software/hardware stack and will be crucial for learning how to co-design quantum circuits and classical networks to complement each other.
Quantum Recommender System and Linear Algebra Benchmarks: On the theoretical side, several algorithms claiming exponential speedups (like the quantum recommender system, quantum PCA, quantum linear regression) have been tested on classical simulators with very small sizes to see if they produce correct results, which they do. But when it comes to actual hardware, implementing HHL or similar algorithms has been extremely challenging due to depth. One exception was a simple quantum linear system solve done by IBM with 4 qubits that solved 2×2 linear equations – a sort of “hello world” demonstration of HHL. It worked, but obviously very far from the scale of interest. The takeaway from these linear algebra benchmarks is that the quantum algorithms often have large hidden constants; for instance, HHL might have complexity ~O(log N) in theory, but with a factor that is polynomial in the condition number of the matrix and error tolerance required, which can make it infeasible. Therefore, while small hardware demos are important to show the algorithm’s components are functional, a direct comparison to classical is not meaningful until the quantum hardware can handle larger instances.
Comparative Results: To date, no quantum machine learning experiment has definitively beaten the best classical approach on a practical problem. Most papers will have a section comparing to classical and will report something like “the quantum method performs as well as the classical one on this small test” or “the quantum method reached the correct solution faster than an unoptimized classical method, but when classical is optimized they tie”. This is expected at this early stage. The field is watching certain metrics: for example, the concept of “quantum volume” and improved error rates in hardware, to guess when a quantum advantage might become possible. Additionally, researchers are identifying niche tasks that might show quantum advantage sooner. One candidate is in quantum chemistry or materials (which can be considered an AI problem if the goal is to predict chemical properties – essentially a learning task where the quantum computer directly simulates the quantum system). Another is in optimization problems where classical solvers scale poorly but a quantum heuristic might do better (some suggest things like the Number Partitioning problem or certain constraint satisfaction problems could show quantum advantage which would indirectly benefit AI planning/optimization tasks).
Industry and Startup Contributions: Companies like IBM, Google, and startups (Xanadu, QC Ware, Zapata, etc.) have been publishing results in quantum machine learning. IBM’s Qiskit Machine Learning opensource project provides a suite of quantum ML algorithms that users can try on IBM’s quantum cloud, including tutorials to classify data using quantum kernels or train a Quantum Support Vector Machine. Google released TensorFlow Quantum, integrating quantum circuits as layers in TensorFlow models, and has showcased its use in hybrid quantum-classical reinforcement learning and combinatorial optimization (in simulation). Startups are perhaps even more aggressively pursuing quantum advantage in AI: for instance, QC Ware recently announced techniques to load data faster onto quantum computers and perform distance estimation for clustering, claiming it could speed up timelines for practical QML by tackling the data-loading problem [qcware.com]. Another startup, Zapata Computing, worked with materials companies on quantum ML for drug discovery (though mainly using quantum-inspired algorithms on classical hardware until the quantum devices catch up). Academic collaborations are also key: NASA, Oak Ridge National Lab, and various universities have run experiments like quantum neural network classifiers for satellite image analysis, quantum GANs (Generative Adversarial Networks) generating simple distributions, and more. Each of these benchmarks, while limited, helps to chart the path forward and identify what improvements would have the biggest impact.

In summary, benchmarking efforts so far reveal a consistent pattern: quantum AI algorithms can work in principle and match classical performance on very small scales, but have not yet exceeded classical methods in any end-to-end metric for meaningful problem sizes. There have been promising hints, such as speedups in sampling for Boltzmann machines [arxiv.org] or potential advantage in specially structured classification tasks, but these remain to be scaled up. The good news is that many foundational pieces (data encoding, circuit training, result readout) have been demonstrated on hardware. The next few years of benchmarks will likely occur at the boundary of what classical simulation can handle (maybe 50–100 qubit QML experiments). If those show an advantage, it will be a significant milestone. Until then, quantum and classical hybrid benchmarking continues, serving as a reality check and guiding the development of better algorithms and hardware.

Future Outlook and Research Directions

Given the current state of affairs, what does the future hold for AI on quantum computers? Experts maintain a cautious optimism. Achieving substantial quantum speedup for AI will require progress on multiple fronts: hardware, algorithms, and our understanding of where quantum can best complement classical methods. Here we outline some future directions and our expectations for the next decade:

Hardware Scaling and Error Correction: The most obvious need is larger and better quantum computers. The quantum computing roadmap for major players points to rapid scaling. Google, for instance, announced an aim to build a fault-tolerant quantum computer by 2029, essentially meaning a machine with enough qubits (perhaps on the order of a million physical qubits) and error-correcting overhead to run long algorithms reliably [dug.com]. IBM similarly has a detailed roadmap: after 433 qubits in 2022, they plan 1121-qubit chips by 2023/24, and beyond that are working on multi-chip modules and networked quantum processors to reach millions of qubits with error correction in the later years of the decade. If these roadmaps hold, by ~2030 we may have the first generation of quantum computers that can handle problems truly beyond classical, not just in complexity theory but in practice. For AI, this could mean the ability to train quantum neural networks that are too large to classically simulate, or to perform optimization over billions of possibilities using Grover’s algorithm or QAOA with depths that classical solvers can’t match. Fault tolerance will also drastically reduce noise, enabling deeper circuits and more complex algorithmic sequences that current NISQ devices cannot manage. We expect that as hardware improves, some of the smaller-scale quantum algorithms already tested will smoothly scale up and start outperforming classical methods on certain tasks. There might be a period akin to the early days of GPUs for ML, where for some tasks specialized hardware (quantum in this case) starts taking over because it becomes simply more efficient beyond a crossover point.
Near-term Hybrid Solutions: In the interim before full fault tolerance, much research is focused on error mitigation and hybrid algorithms. Techniques like zero-noise extrapolation, probabilistic error cancellation, and subspace expansion are being refined to squeeze more mileage out of NISQ devices without full error correction. On the algorithm side, a lot of effort is going into making quantum algorithms “resource-efficient” – using fewer qubits, shallower circuits, and smarter pre- and post-processing. For example, finding ways to encode data that reduce qubit requirements, or compressing quantum circuits via machine learning itself (some researchers use AI to discover shorter quantum circuits for a given task). We also see interest in quantum-inspired algorithms running on classical hardware as a stepping stone; these mimic quantum approaches to get insights and sometimes even improve classical algorithms. A likely scenario in the next 5 years is the emergence of specialized quantum accelerators integrated into HPC systems, where certain modules of an AI workflow call a quantum routine. We might witness quantum-enhanced services in cloud platforms – for instance, a cloud ML service that under the hood uses a quantum subroutine for part of a computation (much like cloud providers now offer GPU/TPU acceleration). These hybrid solutions will pave the way and build familiarity, even if they don’t offer massive speedups initially.
Algorithmic Breakthroughs and Theory: On the theoretical side, discovering new quantum algorithms for AI (or improving existing ones) is a crucial area. Many algorithms we discussed (QAOA, VQE, variational QNNs) are heuristics; they seem to work, but their advantages are not fully characterized. There is ongoing work to understand the conditions under which these algorithms excel. For example, what types of cost functions can QAOA optimize more efficiently than any classical algorithm? Or can we prove that a variational quantum model has greater expressive power than a classical one with a similar number of parameters? Partial answers are emerging. Another frontier is dequantization results – paradoxically, these are also useful, because by understanding how classical algorithms simulate quantum ones, we identify exactly what gives quantum an edge. The goal is to pinpoint tasks that have an inherent “quantum-ness” such that any classical simulation would take exponential time (a candidate might be something involving quantum interference patterns that are hard to emulate, like certain quantum kernel functions or sampling tasks with specific structures). Theoretical computer science will continue to guide us on where quantum speedups likely exist. Also, improvements in quantum error-correcting codes and architectures (e.g., better ways to do fault-tolerant logical qubits, or noise-biased qubits that are easier to correct) will directly translate to lower overhead for algorithms, making quantum solutions more competitive.
Application-Specific Progress: We should consider that “AI” is broad – it includes neural network training, inference, planning, reasoning, etc. Perhaps the first real quantum advantage in AI will come in a niche application. For example, quantum computers might excel at certain optimization problems in combinatorial machine learning (like the optimal feature selection problem, or training discrete models like Boolean networks) even if they don’t yet beat classical methods in training deep continuous neural networks. Or quantum simulation (which is naturally what quantum computers do best) could revolutionize AI for science – AI models that require quantum physics data (like predicting chemical reactions or materials properties) could incorporate on-the-fly quantum computations as a part of the model. This blurs the line between simulation and machine learning, but it is an exciting direction where quantum computers do heavy lifting in domains that classical AI struggles with. Another area is cryptography and security in AI: quantum computers will break certain cryptosystems, which could impact how AI models securely share and handle data; quantum algorithms might also be used to generate hard instances for training robust models.
Timeline and Expectations: In the next 2-3 years, we expect to see quantum processors with a few hundred high-quality qubits performing specific machine learning tasks at a scale just beyond what we can classically simulate (like maybe doing a quantum kernel method on a dataset that would be memory-intensive to simulate classically, perhaps showing a mild advantage). By ~5 years, if hardware trends continue, there might be early demonstrations of a “quantum advantage” in an AI-relevant problem, for instance using ~1000 qubits with some error correction to solve a clustering or optimization problem noticeably faster than a classical solver. These would likely be special cases, but significant as milestones. In ~10 years, if million-qubit error-corrected machines come online as Google and others predict [dug.com], we could be looking at far more routine use of quantum computing in AI. At that stage, one can imagine training moderately-sized quantum neural networks that cannot be emulated classically, or performing data analysis on encrypted data using quantum homomorphic encryption (since quantum computing could handle certain encrypted computations faster). The hope is that by around a decade from now, practical quantum AI applications will exist – perhaps not in everyday consumer products yet, but in specialized domains (scientific research, logistics optimization, finance) where even a small edge is very valuable. A realistic expectation is that quantum computers will complement classical AI hardware (CPUs, GPUs, TPUs) rather than outright replace them. Much like today we offload different tasks to different processors, in the future an AI workflow might use classical processors for data pre-processing and simple layers, quantum co-processors for heavy lifting on specific layers or optimization steps, and then classical processors again for post-processing. This hybrid model plays to each side’s strengths.
Open Research Challenges: To reach the above future, several research challenges need attention:
- Developing efficient quantum memory (QRAM)or finding clever algorithms that minimize data movement, as the lack of fast data loading is a glaring bottleneck.
- Improving qubit coherence and gate fidelity– even incremental improvements widen the horizon of what algorithms can run. Also, new qubit technologies (e.g., topological qubits pursued by Microsoft) could change the game if they achieve intrinsically lower error rates.
- Creating better noise-aware quantum algorithmsfor ML that can tolerate imperfections – for instance, algorithms that use error in a beneficial way or that require only relative accuracy in intermediate steps (some analog quantum computing paradigms might be useful here).
- Benchmarking and metrics: establishing standard benchmarks for quantum machine learning that can track progress, similar to classical ML benchmarks (like ImageNet for vision, GLUE for NLP). Right now, each research uses bespoke tasks; a common suite of tasks would help quantify improvements concretely.
- Integration with AI workflows: developing software and hardware interfaces such that an ML engineer can easily call a quantum subroutine in their code (today it requires specialized knowledge). Projects like IBM’s Qiskit, Google’s Cirq and TensorFlow Quantum, and Xanadu’s PennyLane are steps in this direction. Continued improvement in these tools and perhaps abstraction layers that automatically decide if a quantum or classical backend should be used for a given operation will make quantum acceleration more accessible.
- Education and Skill: Training a new generation of researchers fluent in both quantum computing and AI is itself a challenge. Cross-disciplinary expertise will be needed to identify opportunities and solve problems at the intersection of these fields.

Looking forward, it’s clear that the journey to quantum-accelerated AI is a marathon, not a sprint. Each year we see incremental advances – a few more qubits, a slightly larger quantum dataset handled, a classical algorithm “dequantized” here, a new quantum speedup proposal there. It’s an exciting co-evolution of two of the most impactful technologies of our time.

Conclusion

Quantum computing holds the potential to significantly speed up certain computations, and it’s natural to ask whether AI workloads will be among those to benefit. In this article, we reviewed how quantum speedup is defined and exemplified (from Grover’s polynomial boost to Shor’s exponential advantage), and why AI’s growing computational demands make such speedups alluring. We explored proposed advantages of running AI on quantum hardware – faster optimization, enhanced sampling, and new quantum-inspired models – and saw that early studies have achieved proof-of-concept successes in these areas [arxiv.org]. At the same time, we discussed the sobering limitations: today’s quantum devices are noisy and limited in scale, lacking the quantum memory and stability needed for large-scale AI, and classical methods remain extremely competitive and often superior on practical tasks [arxiv.org]. Benchmarking efforts so far reflect a landscape where quantum techniques can match classical performance on small problems, but have not yet surpassed them in real-world scenarios.

So, will AI run faster on quantum computers? The realistic answer is: Yes, eventually, but not overnight and not universally. In specific areas – likely involving optimization or simulation – quantum acceleration of AI is expected as hardware and algorithms improve. For instance, we may see certain machine learning workflows achieve a polynomial speedup by using a quantum subroutine, which could be transformative for tasks where every exponent of improvement counts (such as large-scale combinatorial optimizations). An exponential speedup for an AI task is the ultimate prize, and while no clear candidate has emerged yet, it’s not ruled out that some problems in learning theory could exhibit exponential gaps between quantum and classical. However, one must set realistic expectations: for the next few years, quantum computing will likely play a supplementary role to classical computing in AI. It’s akin to having a very specialized accelerator that you’d use sparingly for the most challenging parts of your algorithm. End-to-end quantum training of a deep neural network that beats state-of-the-art classical training is still a long-term prospect, probably requiring fault-tolerant machines with many thousands of logical qubits.

It is important to maintain a balanced perspective. As researchers Biamonte et al. noted, quantum machine learning offers tantalizing possibilities but also faces considerable hurdles in both hardware and software [pubmed.ncbi.nlm.nih.gov].

Those hurdles are actively being addressed by a vibrant community at the intersection of quantum computing and AI. Each breakthrough – be it a new error-correction technique, a clever variational algorithm, or a 1000-qubit quantum chip – brings us a step closer to integrating quantum speedups into AI. The coming decade will likely see the first concrete examples of quantum advantage in AI, perhaps in niche domains at first. From there, like all tech, the evolution could accelerate – much as early GPUs for graphics eventually became indispensable for deep learning.

In conclusion, quantum computers have the potential to run certain AI tasks faster, but unlocking that speedup will require continued advancements and ingenuity. The integration of quantum computing into AI workflows will be gradual, with hybrid quantum-classical methods leading the way. AI researchers and quantum specialists are increasingly collaborating, and this interdisciplinary effort will determine how quickly theoretical speedups translate into practical performance gains. While we temper optimism with the realities of engineering, the prospect of quantum-accelerated AI remains a driving inspiration – one that could eventually revolutionize how we train models, make decisions, and process information. The challenge of making AI run faster on quantum computers is an open, exciting research frontier, and progress toward it will deepen our understanding of both intelligent algorithms and quantum technology. The next decade will reveal just how far this quantum-AI synergy can go, and the answers will shape the future of computing in the 21st century.