Quantum Sundays |27⟩ When the Quantum Advantage Disappears: Lessons from Ewin Tang’s Breakthrough

On the Dequantization of Quantum Machine Learning Algorithms: An Analysis of Ewin Tang’s Framework for Low-Rank Linear Algebraic Problems Under Sampling Access Models- Implications for the Computational Complexity of Classical vs. Quantum Algorithms in Applied Machine Learning.

Complimentary Reading

TL;DR — Ewin Tang’s classical algorithm for the recommendation problem matched a celebrated quantum algorithm’s performance, eliminating one of the clearest examples of exponential quantum advantage in machine learning. Her broader framework — “Quantum Machine Learning Without Any Quantum” — shows many quantum speedups on classical data can be replicated classically with similar efficiency under realistic data access models, reshaping quantum research priorities and industry expectations.

Executive Summary

In 2018, an 18-year-old undergraduate quietly rewrote the quantum computing playbook. Ewin Tang’s classical algorithm not only matched a widely celebrated quantum solution — it dismantled the very claim of exponential advantage that had been held up as a field-defining example.

Her work began as an attempt to prove the absence of a fast classical alternative to a quantum recommendation system algorithm. Instead, she discovered one. By leveraging classical randomized linear algebra and efficient sampling techniques, Tang recreated the quantum algorithm’s efficiency without a single qubit. The implications are profound: much of what has been presented as “quantum speedup” in machine learning on classical data collapses when given fair parity in data access.

This is more than a clever algorithm — it is a reframing of strategy. For research leaders, it signals the need to refocus quantum efforts on domains where classical competition cannot easily follow, such as quantum-native data and inherently quantum physical simulations. For industry, it tempers the promise of near-term quantum advantage in mainstream ML tasks, while offering immediate gains via quantum-inspired classical methods that run today on conventional hardware.

As a leader, I view Tang’s breakthrough as both a caution and an opportunity. It is a reminder that emerging technology narratives must be tested against the most rigorous competitive baselines, and it is an example of how intellectual cross-pollination — in this case, quantum thinking inspiring classical innovation — can yield breakthroughs that are strategically valuable, whether or not they originate from the technology we were betting on.

Ewin Tang’s “Quantum Machine Learning Without Any Quantum” Hypothesis — Research, Dissertation, and Breakthroughs, and What It Means for the Future of Quantum Computing and Classical Algorithm Design

Imagine a near-future Netflix that seems almost psychic in its recommendations. It tells you what to watch next without slogging through every single movie in its catalog. For years, optimists believed only a quantum computer could achieve this kind of lightning-fast insight. After all, quantum machines promised to crunch colossal datasets by tapping into mysterious quantum superpositions. But in 2018, a teenage computer scientist named Ewin Tang turned that notion on its head. Without using any exotic quantum hardware — just clever classical math — Tang showed that some of quantum computing’s vaunted advantages might be illusions that classical algorithms can replicate [1]. Her work, encapsulated in the tongue-in-cheek hypothesis “Quantum Machine Learning Without Any Quantum,” has sent shockwaves through both the quantum computing community and classical algorithm design. It’s a story of surprising breakthroughs, intellectual humility, and the productive tension between quantum dreams and classical reality.

In this comprehensive post, we will embark on a journey through Ewin Tang’s world: from her biographical background and the scientific context of her research, to a deep dive into her breakthrough algorithms and dissertation, to the impacts and implications of her work on the future of quantum and classical computing. We’ll break down her quantum-inspired classical algorithm for recommendation systems in approachable terms, compare it to its quantum counterpart, and explore how Tang’s hypothesis is reshaping expectations in quantum machine learning (QML). Along the way, we’ll use analogies, step-by-step illustrations, and even a pinch of storytelling to demystify the technical details. Finally, we’ll consider critical perspectives, limitations of her results, and what all this means for theoretical computer science and industry strategy going forward. By the end, you’ll see how a youthful insight “took the quantum out of quantum computing” [2] in one domain — and what that teaches us about the evolving frontier between classical and quantum computation.

Context

To appreciate the magnitude of Tang’s achievement, it helps to know where she came from and what problem she set out to solve. Ewin Tang’s story starts with precocious talent and opportunity. Born in Texas, Tang rocketed through school, skipping three grade levels and enrolling at the University of Texas at Austin at the astonishing age of 14 [1]. By her late teens she had a double major in mathematics and computer science, and in spring 2017 she took a graduate-level course on quantum information taught by the renowned computer scientist Scott Aaronson [1]. Aaronson, known for his work in quantum complexity theory, quickly recognized Tang’s abilities and agreed to supervise an independent research project during her senior year. Little did either of them know that this mentorship would lead to a result that challenged one of the field’s cherished examples of quantum superiority.

The Quantum Speedup That Captured Imagination: In the mid-2010s, the quantum computing community was buzzing with proposals of quantum algorithms that promised exponential speedups for various tasks. A particularly exciting example emerged in 2016, when researchers Iordanis Kerenidis and Anupam Prakash published a quantum algorithm for the “recommendation problem” [1]. This problem can be likened to what companies like Amazon or Netflix face: given a giant matrix of user preferences (rows representing millions of users, columns representing products or movies, with entries reflecting how much a user likes a given item), how can one quickly recommend a new product to a user? The matrix is enormous and mostly empty (since each user has rated only a tiny fraction of items), yet a good algorithm should predict the missing entries — essentially filling in the blanks to guess what each user would enjoy next [1].

For classical computers, the recommendation problem is daunting. Matrix operations on an m x n preference matrix typically scale poorly — scanning all users and items might take time proportional to mn, which is infeasible for huge datasets. Kerenidis and Prakash’s quantum algorithm, however, appeared to run in polylogarithmic time with respect to the number of users and products [1]. In rough terms, “polylogarithmic” means the runtime grows only as some polynomial function of the logarithm of m and n. (For example, log₂ n grows very slowly — doubling the data size barely budges the runtime if the algorithm truly scales polylogarithmically.) Achieving polylogarithmic time is extremely fast — much faster than any known classical approach — and amounts to an exponential speedup when comparing how the runtime grows with input size. Kerenidis and Prakash’s method exploited quantum physics to achieve this: they used quantum state preparation and sampling techniques to avoid having to examine the whole matrix, effectively grouping users into a small number of preference categories (like “action-movie lovers” vs. “indie-film buffs”) and sampling just enough data to recommend a pretty good match [1]. It was a brilliant blend of quantum linear algebra and sampling, and it stood as one of the best real-world examples of a quantum advantage at the time [1].

Before the Fall — Hype and Belief: By 2017, quantum computing was widely seen as “the next big thing,” with tech giants and startups investing in quantum hardware prototypes. The recommendation problem became a minor celebrity in quantum computing talks — a poster child showing that quantum computers might soon solve problems in machine learning far faster than classical machines. Importantly, no equally fast classical algorithm was known for the recommendation problem, despite years of work on recommender systems in classical machine learning. This gap bolstered a belief: that quantum computers possess almost magical powers for certain data problems. Even Scott Aaronson, a famously critical mind, believed the quantum speedup for recommendation systems was likely genuine — so much so that he challenged his student Ewin Tang to prove a negative result: show that no fast classical algorithm could solve the recommendation problem, thereby cementing the quantum advantage as indisputable [1].

When Tang started her project in late 2017, the community consensus leaned towards “quantum wins here.” As Aaronson later recalled, confirming the absence of a classical counterpart seemed like “an important ‘t’ to cross” in validating quantum machine learning’s promise [1]. Tang herself was initially hesitant to tackle the problem — it looked very hard, and among the options Aaronson offered, it was merely the “least impossible” one [1]. Nonetheless, she plunged in, attempting to either find a fast classical algorithm or prove one can’t exist.

2. The Breakthrough Discovery

Turning Point — A Classical Spark: Instead of finding a wall that classical computing couldn’t climb, Ewin Tang discovered a hidden ladder. As months passed, her attempts to prove classical futility kept failing — in fact, she started suspecting that the opposite was true: maybe a fast classical algorithm could exist [1]. This was a bold thought. If true, it would mean that the shining example of quantum advantage had a classical workaround. It’s akin to a magician revealing the secret behind an illusion — suddenly the impossible feat doesn’t require magic at all, just a clever trick.

Tang trusted her mathematical intuition. With the clock ticking on her senior thesis deadline, she shifted gears from trying to prove impossibility to actively constructing a new algorithm. The result was astonishing: she designed a classical algorithm that mirrored the quantum algorithm’s approach so well that it achieved essentially the same running time — polylogarithmic in the size of the input data [1]. In other words, the purported exponential quantum speedup vanished; classical computers could match it (up to modest polynomial factors) using Tang’s method [1]. In July 2018, at just 18 years old, she posted her paper on the arXiv preprint server, making waves with the provocatively titled result “A quantum-inspired classical algorithm for recommendation systems.” The news spread quickly: a teenager had nullified one of quantum computing’s claim to fame [1].

To appreciate why Tang’s discovery was so surprising, consider what it entailed. She had shown that ordinary computers, with no quantum effects, can solve a problem almost as fast as a quantum computer, given the same type of access to data. This last caveat is crucial, and we’ll delve into it in the next sections. But at a high level, Tang’s algorithm runs in time polylogarithmic in the number of users m and items n — for example, O((log m)ᶜ · (log n)ᵈ) for some small exponents c, d — whereas the best classical algorithms before her required polynomial time (like on the order of mn or at least m + n or similar). Tang’s algorithm was exponentially faster than those prior classical attempts [1], effectively closing the gap with the quantum solution. As Quanta Magazine reported, “18-year-old Ewin Tang has proven that classical computers can solve the ‘recommendation problem’ nearly as fast as quantum computers,” thereby eliminating one of the best examples of quantum speedup [1].

Meet the Quantum-Inspired Algorithm: So what does Tang’s classical algorithm actually do? At a very high level, it copies the blueprint of the Kerenidis-Prakash quantum algorithm but translates each quantum step into a classical analogue. The quantum algorithm had two secret weapons that gave it speed: (1) the ability to encode the entire huge preference matrix into a quantum state superposition almost instantly (this is known as quantum state preparation), and (2) the ability to sample from that quantum state in clever ways to estimate properties of the matrix (like finding those “stereotypical” user preference vectors without scanning everything). Tang realized that these weapons have classical counterparts: with the right data structures, a classical computer can also prepare a kind of probabilistic representation of the data and sample from it efficiently [3]. In essence, what the quantum algorithm achieves via superposition and interference, Tang’s method achieves via randomness and sampling.

Crucially, Tang’s algorithm doesn’t fill in the entire matrix of preferences any more than the quantum algorithm did. Both approaches smartly avoid that hopeless task. Instead, they focus on the important patterns — roughly speaking, identifying a low-dimensional subspace (spanned by a few “archetypal” user behavior patterns) that approximately captures the preferences of all users [2]. If you can find these patterns, recommending a movie to a particular user becomes easier: you determine which pattern (or combination of patterns) the user aligns with, and then recommend popular items within that pattern. The quantum algorithm used quantum linear algebra routines to find those patterns; Tang’s algorithm uses classical sampling routines to achieve a similar end.

Polylogarithmic Time and What It Means: When we say Tang’s algorithm runs in polylogarithmic time, it’s worth pausing to interpret that. Suppose there are m users and n movies. A polylogarithmic runtime might be something like O((log m)²(log n)) or O((log m)(log n)³) — polynomial in the logarithms of m and n. For context, log₂(1,000,000) ≈ 20. So, if m and n are in the millions, log m and log n are on the order of tens. A polylogarithmic factor might be in the low hundreds, which is essentially a constant for practical purposes (especially compared to millions). This contrasts with a linear runtime O(m + n) that would scale in the millions, or quadratic O(mn) which could be in the trillions. Therefore, a polylogarithmic algorithm is extraordinarily fast on large inputs — provided it truly only needs that many operations and doesn’t hide big overheads elsewhere.

Tang’s classical recommendation algorithm indeed achieves such scaling under certain reasonable assumptions on the data (e.g. that the user preference matrix is somewhat low-rank, meaning user tastes can be described by a limited number of factors, and that we have fast access to samples of the data). In more formal terms, Tang’s algorithm complexity is polylogarithmic in m and n, polynomial in other parameters like the rank k of the matrix and an accuracy parameter ε, and also depends on the time to do certain sampling queries [1]. The key takeaway is that it’s exponentially faster than the naive classical approach and on par with the quantum algorithm’s scaling up to those polynomially small overheads.

Unveiling at Berkeley: Before publishing, Tang and Aaronson wanted to be absolutely sure the result was correct — nobody wanted an infamous false claim as a first publication. So in June 2018, Tang presented her algorithm to experts at a quantum computing workshop in Berkeley, where Kerenidis, Prakash, and many other luminaries were in attendance [1]. Over the course of two extended lectures, the community carefully scrutinized her approach. By the end, the verdict was clear: the algorithm worked [1]. Attendees were not only convinced by the math, but also stunned by the presenter’s poise — many hadn’t realized Tang was an undergraduate just 18 years old, as she delivered the talk with the clarity of a seasoned researcher [1]. With this informal peer review passed, Tang’s paper was posted online and later accepted for publication (it appeared in the prestigious STOC 2019 conference proceedings). The quantum computing community had to grapple with what this meant.

A Double-Edged Result: Ewin Tang’s discovery landed as both a setback and a triumph for quantum computing [1]. On one hand, it “eliminated one of the clearest, best examples of a quantum advantage” [1], deflating some of the momentum behind quantum machine learning claims. It was a reminder that classical algorithms may yet catch up to certain quantum ideas, and that presumed quantum supremacy in practical tasks can’t be taken for granted. On the other hand, Tang’s work beautifully illustrated the fruitful interplay between quantum and classical computation [1]. Her classical algorithm was directly inspired by the quantum algorithm; without the quantum approach blazing a trail, Tang might never have found this classical solution [1]. As Aaronson put it, “Tang is killing [the] quantum speedup, but in another sense Tang is giving a big improvement and building on what they did. Tang never would have come up with this classical algorithm but for their quantum algorithm” [1]. In other words, the competition between quantum and classical spurred innovation that benefited classical computing in the end.

This theme — that quantum thinking can lead to classical breakthroughs — will recur as we explore Tang’s subsequent work and its implications. But first, let’s turn to the academic substance of Tang’s research: her dissertation and the series of papers in which she and others fleshed out the “quantum-inspired” approach to classical algorithms.

3. Dissertation & Academic Publications

After her groundbreaking 2018 result, Ewin Tang continued to deepen and generalize her findings. She moved to the University of Washington in Seattle in Fall 2018 to begin a Ph.D. in Computer Science (at the Paul G. Allen School), working with professor James R. Lee in the Theory of Computation group [2]. Over the next few years, Tang and collaborators systematically explored how far the dequantization strategy could go. The culmination of this work is Tang’s doctoral dissertation titled “Quantum Machine Learning Without Any Quantum” (University of Washington, 2021) [4]. This dissertation and the papers surrounding it form the backbone of the Quantum-Inspired Classical Algorithms field — a burgeoning research area marrying quantum computing insights with classical randomized algorithms.

Let’s break down the key contributions in Tang’s academic publications and thesis:

• The 2018 Recommendation Systems Paper: This was Tang’s first and most famous result, described above. Titled “A quantum-inspired classical algorithm for recommendation systems,” it provided the first example of a polynomial-time classical algorithm (with polylogarithmic performance in data size) matching a proposed exponential quantum speedup [1]. It was published in the Proceedings of the 51st ACM Symposium on Theory of Computing (STOC 2019) after making waves on arXiv in 2018. The core theoretical result was an algorithm that, under assumptions of low rank and efficient sampling access to a preference matrix, produces a recommendation nearly as well as the quantum algorithm in O(poly(k, 1/ε) \polylog(mn)) time (here k is the effective rank and ε the approximation error) [1]. This paper introduced computer scientists to the idea that quantum amplitude techniques can inspire classical sampling techniques.
• Follow-up on PCA and Clustering (2018): Soon after, Tang authored or co-authored another paper, “Quantum-inspired classical algorithms for principal component analysis and supervised clustering”. This extended the quantum-inspired approach to two other fundamental tasks:
• Principal Component Analysis (PCA): finding the top eigenvectors (principal components) of a data covariance matrix, widely used for dimensionality reduction.
• Supervised Clustering: grouping data points when given some labeled examples (essentially a semi-supervised learning task).
• These tasks had seen proposed quantum algorithms promising speedups, and Tang showed classical algorithms (using similar sampling and sketching ideas) could achieve comparable results under analogous conditions [2]. By late 2018, as GeekWire reported, two other papers had appeared “proving her breakthrough result will work with other types of machine learning” [5]. Tang’s PCA and clustering paper was likely one of them, demonstrating that the dequantization toolkit was not limited to recommendations.
• Quantum-Inspired Regression (2019): In a collaboration that might seem surprising, Tang worked with physicist Seth Lloyd (a pioneer of quantum algorithms) and others to apply quantum-inspired methods to stochastic regression. The paper “Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension” (Gilyén, Lloyd, & Tang, 2019) developed classical algorithms for solving certain linear systems (a core subroutine in machine learning for regression problems) in time polylogarithmic in the dimension of the system [6]. This mirrored quantum algorithms for solving linear systems (such as the famous Harrow-Hassidim-Lloyd (HHL) quantum algorithm [1] for linear equations) and again showed that if the matrix involved is low-rank or has a special structure and one has sampling access to it, then classical algorithms can perform the solve in sublinear time in the matrix size. In other words, they dequantized yet another supposed quantum advantage.
• Quantum-Inspired Low-rank Matrix Inversion & Systems (2019): Another team (Chia, Lin, Wang 2019) built on Tang’s ideas to address the general problem of solving low-rank linear systems classically in sublinear time [6]. This indicates how quickly the research community picked up on Tang’s breakthrough — within a year, multiple groups were applying the “l2-norm sampling” trick (explained in the next section) to classical algorithms for various linear algebra tasks that had quantum proposals.
• The Dequantization Framework (2020–2021): All these results were unified and expanded in Tang’s dissertation work. A highlight is her development of a classical analogue of the Quantum Singular Value Transformation (QSVT) framework [4]. QSVT (introduced by Gilyén, Su, Low, and Wiebe in 2019) is a powerful quantum algorithmic framework that can perform polynomial transformations of the singular values of a matrix embedded in a quantum state, underpinning many quantum algorithms for linear algebra and machine learning. Tang constructed a classical analogue: a framework that shows how, given similar input assumptions, one can perform analogous transformations classically with only polynomially more time [4]. In her dissertation’s abstract, Tang summarizes that the space of quantum machine learning (QML) algorithms essentially splits into two broad classes:
• (i) QML algorithms on sparse data or data giving full quantum access (often requiring low-rank structure): For these, Tang argues, “the latter class can be ‘dequantized’,” meaning for every such quantum algorithm, a classical algorithm exists that is at most polynomially slower [4]. Her work provides a framework to systematically derive such classical analogues. She and colleagues demonstrated this by dequantizing eight different QML algorithms from the literature, including the recommendation systems algorithm and even quantum algorithms for low-rank semidefinite programming, clustering, PCA, regression, etc. [4]. If a quantum algorithm’s speedup came from linear algebra on effectively low-dimensional data, Tang’s framework shows the speedup isn’t truly quantum — classical sampling can do the job.
• (ii) QML algorithms on fully general data (or that would imply solving NP-hard problems if sped up): These correspond to cases that Tang identifies as BQP-complete or otherwise intractable for classical algorithms [4]. In plainer terms, if a quantum algorithm could handle arbitrary data (without that low-rank or structured assumption) and still get exponential speedup, it would mean quantum computers can solve extremely hard problems (BQP-complete problems) that classical computers likely cannot. Tang’s classification suggests that if we ever find a QML algorithm with a true exponential advantage on classical data, it must be tackling a problem of immense complexity (as hard as the hardest problems quantum computers can solve at all). In absence of that, any “practical” QML speedup on classical datasets will probably turn out to have a classical counterpart.

The dissertation’s results were more than just a list of algorithms; they constituted a new philosophy for algorithm design. As Tang’s Ph.D. advisor James Lee remarked, “Ewin’s work provides more than just a (much) faster algorithm for recommendation systems — it gives a new framework for the design of algorithms in machine learning” [2]. This framework has been coined “quantum-inspired classical algorithms” or simply “dequantization”. It draws heavily on techniques from classical randomized numerical linear algebra (NLA) — a field that, coincidentally, had been developing similar sampling and sketching methods over the past two decades for big data problems, independent of quantum computing. Tang effectively bridged these communities, showing how insights in one can inform the other.

To disseminate these ideas, Tang has also given talks and even written a blog post titled “An overview of quantum-inspired classical sampling” (2019) explaining the techniques for a broad audience [6]. In it, she cites her works and others’ as collectively forming “an introduction to dequantization” — a tongue-in-cheek reference to undoing quantum algorithms to get classical ones [6]. The key message is that many quantum algorithms that start with classical data can be matched by clever classical algorithms, as long as we allow those classical algorithms a comparable “mildly nonstandard” way to access data (like sampling or queries).

In summary, Tang’s publications and dissertation lay out a roadmap: start with a quantum algorithm that assumes some special data structure (like being able to query data in superposition), replace quantum state preparation with classical sample-and-query access, and replace quantum linear algebra subroutines with classical randomized linear algebra. The end product often retains the speed of the quantum original, up to polynomial factors.

4. The “Quantum Machine Learning Without Any Quantum” Hypothesis

With the context set, we can now articulate the core hypothesis or philosophy that emerges from Tang’s work — often paraphrased as “quantum machine learning without any quantum.” What does this phrase mean, and why is it so provocative?

At its heart, this hypothesis is a statement about the limits of quantum speedups in machine learning on classical data. It posits that for many tasks in machine learning and data analysis, if the input is classical data (e.g., a large dataset of numbers) and the output is classical (e.g., a model or recommendation), then any purported exponential quantum speedup can likely be emulated by a classical algorithm, without needing a quantum computer at all. In other words, if you take the “quantum” out of certain quantum machine learning algorithms — by replacing the quantum steps with probabilistic classical steps — you might still solve the problem nearly as fast.

This runs counter to the previously “long-held belief” that quantum algorithms like HHL (for linear systems) were inherently superior for tasks like matrix inversion or recommendation on classical data [3]. Tang’s work challenged that belief by showing classical equivalence in performance where none was expected [3]. As one Medium article neatly summarized, “the apparent quantum speedup thus stems from implicit sampling assumptions, not fundamental computational barriers” [3]. In other words, quantum algorithms often assume they can do something fancy — like load an entire dataset into a quantum state in no time — which gives them a head start. If we grant classical algorithms a comparably fancy ability — like sample from the data in constant time using a special data structure — then the quantum advantage can disappear [3].

Let’s break down the hypothesis into key points:

• State Preparation vs. Sample Access: Most QML algorithms begin by assuming the data is accessible as a quantum state. For example, given a vector of n numbers (maybe a row of the user preference matrix), a quantum algorithm might assume you can create a normalized quantum superposition Σⱼ aⱼ|j⟩ that encodes those numbers aⱼ as amplitudes, in just O(log n) time. This is a big assumption; it’s like reading all n numbers “in parallel” using quantum magic. Tang’s principle is that if a quantum algorithm gets to assume that, a fair classical comparison should allow a classical algorithm to query and sample from the entries aⱼ in similarly fast time [3]. Concretely, the classical model might assume we have a black box that given an index can return aⱼ in O(1), and given a request “sample an index with probability proportional to aⱼ² “ can also do that in O(1). This is sometimes called ℓ₂-norm sampling access to the data. Under this apples-to-apples comparison — quantum with state prep vs. classical with sampling — Tang’s hypothesis is that the classical algorithm can achieve almost the same efficiency [3].
• Dequantization of Known Algorithms: The hypothesis is borne out by evidence: Tang and others dequantized at least eight prominent quantum algorithms for machine learning and optimization [4] [7]. These include algorithms for recommendation systems, PCA, clustering, support vector machines (SVMs), low-rank matrix inversion/regression, low-rank semidefinite programming (an optimization problem), Hamiltonian simulation for low-rank matrices, and even linear discriminant analysis [7]. Each time, the pattern was the same: a quantum algorithm that was believed to offer exponential speedup on some problem turned out to have a classical counterpart (running in time polynomially related to the quantum runtime). This sweeping set of results suggests a general rule: if a quantum algorithm’s speedup comes from clever linear algebra on data that has some compression (like low rank) and that data is initially classical, then the speedup is not quantum-exclusive.
• Implications for QML Research: The “QML without quantum” hypothesis serves as a reality check for the quantum computing field. It implies that a large subset of quantum machine learning proposals do not actually break new computational ground; rather, they highlight opportunities for better classical algorithms. This has several implications:
• Researchers proposing a quantum algorithm for a machine learning task need to analyze whether their speedup might be coming from a data access assumption rather than pure quantum power. If it is, they should consider whether a classical algorithm with a similar assumption could do the same job. In fact, Tang’s work provides a template for such analysis.
• For funding agencies and companies pouring money into quantum machine learning, Tang’s hypothesis advises caution. Not every quantum speedup will survive careful scrutiny. It might be more fruitful to direct quantum efforts towards problems where data is inherently quantum (for instance, analyzing quantum physics data, quantum simulation tasks, etc.) or where even sampling access classically would be too slow.
• The hypothesis also encourages a closer collaboration between classical ML/algorithm experts and quantum algorithm designers. It tells us that quantum algorithms shouldn’t be developed in a silo; their classical analogues might be right around the corner. Indeed, Tang’s story shows the value of cross-pollination: quantum ideas inspiring classical techniques which in turn refine our understanding of quantum limits.
• What It Doesn’t Mean: It’s important to clarify that “quantum ML without quantum” does not mean quantum computers have no value or that all quantum algorithms can be dequantized. Far from it — there are computational problems (like factoring large numbers, certain cryptographic problems, or oracular problems like “forrelation” in complexity theory) where quantum algorithms achieve provable speedups and no classical equivalent is known or expected. Tang’s hypothesis is focused on a particular domain: machine learning on classical datasets. Even within ML, there may be areas where quantum retains an edge (for example, if data is not low-rank and there is no efficient sampling method, or if the quantum algorithm exploits properties like quantum entanglement that have no straightforward classical simulation). Tang’s work significantly narrows the window where exponential quantum speedups can hide, but it doesn’t close it entirely.

We can visualize Tang’s classification of QML algorithms with a simple schematic:

flowchart TB
    direction LR
    subgraph QML Algorithms on Classical Data
        A[Type 1: Requires Quantum Data Access or Sparse Structure]
        B[Type 2: Quantum-Accessible Low-Rank Data]
    end
    A -->|If exponential speedup| Hard{BQP-complete (likely true quantum advantage)}
    B -->|If exponential speedup| Deq[Dequantizable (classical poly-time analog exists)]
    style Hard fill:#FFE4E1,stroke:#333,stroke-width:1px,color:#000
    style Deq fill:#E8F7FF,stroke:#333,stroke-width:1px,color:#000

Figure: Tang’s Two Classes of QML Algorithms. According to Tang’s work, quantum machine learning proposals fall into two broad classes. (Type 1) Those that operate on very general or unstructured data (e.g. extremely sparse data) — if these show exponential speedup, they are tackling BQP-complete problems, meaning they are as hard as the hardest problems quantum computers can solve (and thus represent true potential quantum advantage, though such algorithms are rare and would imply major complexity class separations). (Type 2) Those that assume structured data or data given in quantum-accessible form (like low-rank matrices in QRAM) — any exponential speedup here can be “dequantized,” i.e. there exists a classical algorithm only polynomially slower achieving the same result [4].

In summary, the “quantum machine learning without quantum” hypothesis reframes what we consider a fair fight between quantum and classical algorithms. It asserts that many reputed quantum speedups were never truly about quantum computing’s unique abilities, but about using a different model of data access. When classical algorithms use a similar model (sampling or query access), the quantum mystique often evaporates [3]. This philosophy has now become a guiding principle for evaluating new claims of quantum advantage in data analysis: always ask, could a classical sampler do this too?

5. Algorithmic Insights and Techniques

It’s time to lift the hood and see how Tang’s algorithm works — not in all its gory mathematical detail, but in broad strokes with an intuitive, step-by-step narrative. The goal here is to understand the techniques that allowed a classical algorithm to emulate the quantum one. These techniques mostly revolve around sampling, randomness, and dimension reduction, which are staples of modern classical algorithms but needed a novel twist to match quantum efficiency.

Let’s use the recommendation system problem as our running example, since that’s Tang’s original case. Recall the setting: we have a large m × n matrix A where rows correspond to users, columns to movies (or products), and Aᵢⱼ is the rating of user i for movie j. Most Aᵢⱼ are unknown (the user hasn’t rated that movie), but some are known. The task is to predict a high rating for user i on some new movie j’ they haven’t seen — essentially, recommend a likely hit. One approach is to find similar users or similar movies and use their ratings to infer what i would like. In matrix terms, this boils down to completing the matrix in a way that approximates the true preference matrix but has low rank (since we suspect only a few factors define preferences).

Low-Rank Structure and “Good Enough” Answers. The quantum algorithm of Kerenidis-Prakash didn’t try to predict every missing entry perfectly; it aimed to produce one good recommendation by implicitly factorizing the matrix into a low-rank approximation. Tang’s classical algorithm adopts the same stance — it seeks an approximation of A that is low-rank (say rank k), capturing the dominant patterns of ratings. If k is small (users really vary along only k independent preference dimensions, like genre affinity), then a lot of the heavy computational lifting can happen in an k -dimensional space rather than m — or n -dimensional space. This can dramatically speed up computation.

ℓ₂-Norm Sampling — A Classical Superposition. One of Tang’s key revelations was that creating a quantum superposition of a vector (like a user’s rating vector) is conceptually similar to a classical procedure called ℓ₂-norm sampling from that vector [3]. What is ℓ₂-norm sampling? Given a vector v = (v₁, v₂, …, vₙ), to ℓ₂-sample from v means: pick an index j with probability proportional to vⱼ². This is like saying “the larger the magnitude of entry j, the more likely we pick j.” If the vector is a probability distribution itself (non-negative and sums to 1), then ℓ₂-norm sampling just picks according to those probabilities. In general v might not sum to 1 or might have negative entries (like ratings can be positive or negative differences from an average), but one can sample based on squared values or treat positive and negative parts separately.

Why is this like a quantum superposition? In a quantum state |v⟩ = Σⱼ aⱼ|j⟩, measuring the state will give outcome j with probability |aⱼ|². So if you can prepare |v⟩, measuring it once essentially gives an index j with probability proportional to |aⱼ|². That’s ℓ₂ sampling! The quantum algorithm’s strength is that it can create these states quickly and then sample from them or do interference between them. Tang’s classical approach is: use a data structure that allows ℓ₂-norm sampling from vectors in roughly O(1) or O(log n) time. This replaces the quantum state preparation + measurement step with a classical equivalent.

Data Structure for Fast Sampling: Tang employed a clever binary tree structure (sometimes called a sampling tree or Fenwick tree / segment tree) to achieve this [3]. Imagine a binary tree where each leaf corresponds to an index j of the vector and stores the value vⱼ² (and maybe the sign of vⱼ separately). Each internal node stores the sum of the values of leaves in its subtree. The root then stores Σⱼvⱼ² (which is ||v||₂²). To sample an index proportional to vⱼ², you generate a random number r between 0 and Σvⱼ². Then start at the root: — At a node, look at the left child’s sum. If r is less than the left sum, you go left; otherwise, subtract the left sum from r and go right. — Continue until you reach a leaf, which is the sampled index.

This process takes time proportional to the tree height, which is O(log n) for n items. So we can sample an index in O(log n). Additionally, one can query partial sums or update an entry (if some values change) in O(log n) as well. Tang’s algorithm uses such trees to sample users or items by weight (like sampling a user in proportion to how “active” or informative their ratings are, or sampling an item in proportion to how it differentiates users).

Importance Sampling and Matrix Sketching. Once you can sample rows or columns of the big matrix quickly by their importance (norms or leverage scores), you can build a sketch of the matrix. A sketch is a much smaller matrix that approximates the original. For example, classical algorithms like the Frieze-Kannan-Vempala (FKV) algorithm from 2004 showed that by randomly sampling O(k/ε²) rows and columns (with probability biased by their importance), one can reconstruct a rank-k approximation of a matrix within error ε of optimal, with high probability. The catch was, FKV assumed sampling each row took O(n) to compute its norm, giving an overall time O(mn) to set up sampling probabilities — not much better than reading the whole matrix. Tang’s improvement was to use the data structure and a two-level sampling trick to bypass scanning all rows.

In simplified terms, Tang’s algorithm does something like:

1. Sample User Groups: Group users into a small number of representative clusters. She might sample a set of O(k) users (using ℓ₂ sampling on rows) and use their rating patterns as a basis for user preferences. Intuitively, if we pick users with probability proportional to how “extreme” or informative their tastes are, we’re likely to pick up the prototypical heavy metal fan, the rom-com lover, the sci-fi nerd, etc., if those are the archetypes.
2. 2. Sample Item Groups: Similarly, sample O(k) items (columns) with probability related to their variance across users. This might pick out representative movies that distinguish user tastes (one movie might separate horror lovers from everyone else, another might separate animation fans, etc.).
3. 3. Construct a Small Core Matrix: Now focus on the intersection of those sampled users and items — that’s a much smaller submatrix, maybe O(k) × O(k) in size. Of course, just that small submatrix alone is not enough to recommend to everyone. But it’s like a scaffold: we use it to infer the low-rank factors. For instance, we can do a low-rank approximation (like SVD or PCA) on this small submatrix.
4. 4. Extend to All Users: Having found, say, k basis preference vectors (as singular vectors from the small matrix), we then need to express all users in that basis. For each of the m users, rather than comparing them to all movies, we just need to find their coordinates in the basis. This can be done by sampling a few of their ratings and projecting onto the basis (again using randomness to avoid going through all n movies).
5. 5. Make Recommendation: Finally, for a given target user, we now can compute their expected rating for a particular item by using the low-rank model (which is much faster than scanning everything). We choose an item with a high predicted rating.

The above is a high-level sketch. The actual algorithm has to carefully control errors introduced by sampling, ensuring with high probability the recommendation is nearly as good as if we had full data. But the key is that each step can be done in sublinear time: — Sampling representative users doesn’t require looking at all m users — it uses a clever distribution to pick a few. — Sampling representative items similarly avoids scanning all n. — Computing the SVD of the small submatrix is fast since its size is only k × k. — Expressing each user in the new basis can be done by sampling a few of their known ratings, not all.

Comparison with the Quantum Algorithm: The quantum algorithm essentially did a similar thing: it used quantum state preparation to sample or project onto principal components in polylogarithmic time. Where the quantum algorithm might use a subroutine like quantum phase estimation on a state |uᵢ⟩ (user’s rating state) to find its overlap with principal components, the classical algorithm uses random sampling of entries of uᵢ to estimate the same overlaps. The end results — a recommended item — are achieved via very different mechanics (quantum amplitudes vs. random draws), but mathematically they target the same linear algebra problem: low-rank matrix approximation.

One particularly neat aspect of Tang’s algorithm is how it leverages known results in randomized linear algebra. For instance, one classical method known as the “Johnson-Lindenstrauss transform” or random projection could be used to reduce dimensionality of data while approximately preserving distances. Another is using leverage scores (which measure how “important” a row or column is to the top singular vectors) to sample effectively. Tang’s work connected these concepts to the quantum notion of amplitude distributions. It turned out that many quantum subroutines implicitly were doing something like leverage score sampling — just in the quantum amplitude space.

Pseudocode Illustration: To ground this, here’s a highly simplified pseudocode (non-optimized) for Tang’s recommendation algorithm concept:

Input: Partially filled preference matrix A with m users, n items.
Assume rank ~ k and access to sampling oracles for rows and columns.

1. Use ℓ₂-norm sampling to pick a small set R of O(k log k) representative users.
   - For each user i, let weight w_i = ||row_i||² (the square norm of their known ratings).
   - Build a sampling tree over users with weights w_i.
   - Sample O(k log k) users according to w_i/∑w.
2. Use ℓ₂-norm sampling to pick a small set C of O(k log k) representative items.
   - For each item j, weight z_j = ||col_j||² (or a similar statistic).
   - Sample O(k log k) items according to z_j.
3. Retrieve the submatrix B = A[R, C] (the intersection of chosen users and items).
   - This is an O(k) × O(k) matrix (plus some log factors).
   - Compute an approximate rank-k factorization of B (e.g., via SVD): B ≈ U * Σ * V^T.
   - This yields candidate user feature vectors (basis U) and item feature vectors (basis V).
4. For each user i (or each target user for recommendation):
   - Sample a small number of item indices j (or use those in C) and get A_{ij} for each.
   - Solve for user i's coordinates in the feature basis U (this is small linear regression).
   - Now you can estimate user i's rating for any item j by U_i * Σ * V_j^T (the low-rank reconstruction).
5. Recommend the item j (not already rated by i) that maximizes the estimated rating.

Output: A recommended item (or a set of top items) for each user.

The data structures (step 1 and 2) ensure sampling is fast. Step 3 uses heavy-duty linear algebra on a tiny matrix, which is fine. The final reconstruction in step 4 and scoring is also efficient since it’s done in a k -dimensional space.

The above pseudocode glosses over many details — for example, how to handle sampling bias, ensure diversity, how many samples to get reliable coordinates, etc. The actual algorithm in Tang’s paper is more complex, but conceptually it fits this outline. The end result is an algorithm that achieves a total runtime sublinear in m and n, something like O((k³/ε²)⋅polylog(mn)) for the full process (where ε is error tolerance and the k³ might come from needing to do some robust regression in a k-dimensional space) [1].

A Real-World Analogy: To make this even more relatable — imagine a huge library of books (the items) and millions of readers (the users) who have each read a handful of those books and rated them. We want to recommend a new book to each reader. A brute-force approach reads through each reader’s entire history and compares it book-by-book with others — impossible at scale. The quantum approach was like quantum magic that lets you instantaneously get a sense of all comparisons via a superposition of all books, then measure to find a good suggestion. Tang’s classical approach is like a clever survey: randomly pick a few “representative” readers to interview in depth (e.g., a fantasy lover, a mystery buff, a science fiction nerd), and a few “representative” books that define these genres. By understanding those, you can infer the tastes of everyone else by asking each reader just a couple of pointed questions (“Did you like Lord of the Rings?” “How about Sherlock Holmes?”) — you don’t need to ask about every book. From those few questions, you slot each reader into taste categories and then recommend a book from the category they most align with. This avoids reading all books or interviewing all readers exhaustively, yet yields a good recommendation. That’s essentially what Tang’s algorithm achieves with rigorous math behind the scenes.

In summary, Tang’s algorithmic insights boiled down to this trinity of techniques: 1. Efficient sampling (simulating quantum state prep & measurement) [3], 2. Random projection and sketching (reducing matrix size while preserving key info) [3], 3. Iterative refinement (using the small sketch to inform the whole).

By carefully orchestrating these, her classical algorithm could do what the quantum algorithm did — find a hidden low-rank structure in the data — almost as fast. It was a triumph of algorithmic ingenuity, showing that with the right lens, even classical randomness can reproduce some of quantum’s seeming sorcery.

6. Impact on the Field

Ewin Tang’s breakthrough sent ripples (if not tidal waves) through multiple research communities. The immediate effect was in quantum computing circles, but the impact extended to how people think about machine learning, big data algorithms, and even industry roadmaps for quantum technology. Let’s explore several facets of this impact:

A. Quantum Computing Community Reaction: Initially, there was a mix of surprise, admiration, and a bit of dismay among quantum computing researchers. The surprise and admiration were for Tang’s result itself — an elegant solution from an undergraduate that corrected the field’s understanding. The dismay was because a go-to example of quantum superiority had just evaporated. As Quanta reported, “for quantum computing, Tang’s result is a setback. Or not.” [1]. Some researchers lamented that quantum machine learning lost a poster child, potentially making it harder to argue that near-term quantum computers would revolutionize data science. On the other hand, many took heart in the fact that this development reflected scientific progress. A hypothesis (“quantum is exponentially faster here”) had been tested and found wanting, which refines the roadmap of what quantum can and cannot do.

Notably, Scott Aaronson himself, who had been betting against a fast classical solution, publicly expressed pleasant surprise. He wrote on his blog that Tang’s algorithm “does not provide an example of an exponential quantum speedup for recommendation systems after all” [8], effectively acknowledging that the community’s prior assumptions needed updating. Aaronson, known for championing careful analysis of quantum claims, likely saw this as a healthy outcome — it weeds out one false lead, so researchers can focus on more promising quantum applications.

B. Influence on “Quantum Supremacy” Narratives: The term quantum supremacy refers to the milestone of a quantum computer doing something (anything) faster than a classical computer can. While Google’s 2019 Sycamore experiment achieved quantum supremacy in a contrived task (random circuit sampling), the practical supremacy — doing something useful faster — remains a key goal. Tang’s work suggested that at least in the realm of recommender systems or similar ML tasks, quantum supremacy was farther away than thought. If a classical PC can handle recommendations with comparable speed, then building a quantum computer to do it faster isn’t as impactful as hoped.

This tempered narrative is actually beneficial in the long run: it prevents overhyping quantum computing as a magic wand. It encourages quantum researchers to more rigorously justify where their speedups come from. In parallel, it highlights that classical computing still has untapped potential, especially in combination with randomization and clever data structures. Tang’s result became a frequently cited example in talks and reviews urging caution against blindly assuming quantum advantages. It underscored Preskill’s 2018 remark questioning whether QML algorithms with exponential speedups on classical data would really pan out [4].

C. Academic Cross-Pollination: Tang’s success story fostered greater collaboration between fields. Suddenly, experts in classical algorithms and linear algebra were paying attention to quantum computing papers — not to marvel at them, but to mine them for new classical ideas. Conversely, quantum algorithm researchers took a closer look at classical randomized algorithms to see what was already known and what might be reinvented in quantum guise. The result was a series of joint works (like Tang joining forces with Lloyd, or the multi-author 2019 framework paper [7] that included both quantum and classical experts). This synergy enriched both fields: — Classical benefit: Many classical computer scientists learned about quantum approaches like amplitude amplification or QSVT and translated them into novel classical algorithms (the “quantum-inspired” toolkit). — Quantum benefit: Quantum researchers sharpened their understanding of what truly constitutes a quantum advantage. They began formulating clearer criteria for quantum speedups — for example, “does the algorithm avoid reading the entire input in any form?” If not, then perhaps it’s not a fair speedup.

This is reminiscent of how earlier in complexity theory, studying quantum or other hypothetical models led to insights in classical complexity (for instance, the famous simulation of quantum circuits by classical algorithms under certain noise assumptions). Tang’s work specifically led to a mini-renaissance in randomized linear algebra, with new results improving even on some classical algorithms (e.g., more efficient low-rank approximation methods leveraging her sampling ideas).

D. Industry and Investment Implications: In the tech industry, quantum computing has been pursued by giants like IBM, Google, Microsoft, Amazon and a fleet of startups. A significant portion of the hype around quantum, especially to laypersons or investors, has been the promise of speeding up AI and big data tasks. Headlines like “Quantum computers will supercharge machine learning” have been common. Tang’s result was a reality check: it suggested that at least some of those promises won’t materialize as expected, or at least not without major caveats.

For companies, this could mean: — Shifting Focus: Some companies might pivot their quantum R&D away from generic machine learning applications toward areas where quantum advantages seem more robust (for example, quantum simulation of chemistry/physics, or optimization problems where quantum heuristic methods like annealing might offer something). If recommender systems, a bread-and-butter of modern e-commerce, don’t need quantum, then perhaps resources should go to where classical methods truly hit a wall. — Integrating Classical Advances: The very existence of these new classical algorithms is a boon for industry even without quantum computers. For instance, large firms like Netflix or Amazon could try to incorporate these quantum-inspired algorithms into their recommendation engines to speed them up or reduce computational load (bearing in mind the assumptions, like needing data in suitable structures). Thus, research sparked by quantum ideas could improve classical systems today, without waiting for future hardware. — Rethinking Quantum ROI: The timeline for quantum advantage in ML might be longer, meaning companies expecting quick wins might adjust their expectations. They may prioritize developing quantum hardware for narrower, high-impact tasks (like cryptography or specific simulations) rather than general ML speedups. In fact, GeekWire noted that Tang’s discovery implies “machine learning won’t be the killer app for early quantum computers,” and classical methods will likely suffice for longer than anticipated [5]. It pointed out that quantum computers, being extremely expensive and limited in near-term capability, wouldn’t justify their use in ML if classical algorithms can do the job on regular servers [5]. This kind of analysis helps businesses decide where quantum will really be “table stakes” and where it won’t [5].

On the flip side, one might wonder if Tang’s result slowed down quantum investment. The answer is likely “not significantly on its own.” The general excitement about quantum computing is driven by a broad range of potential applications and the allure of new hardware capabilities. One setback in QML might not faze big-picture investors. However, it certainly contributed to a more nuanced narrative: you’ll now often hear quantum advocates emphasize that “quantum speedups in ML are still unproven in practice” and that we should pursue quantum advantage where it’s clearest. That moderation in messaging is partly thanks to work like Tang’s.

E. Personal Impact and Recognition: It’s worth noting the impact on Ewin Tang’s own career and on role-modeling in STEM. Tang’s achievement landed her on the Forbes “30 Under 30” list in science for 2019 [2]. She became something of a celebrity in theoretical computer science circles — a young scientist whose fresh perspective upended conventional wisdom. Stories about her often highlight her age (18 at the time of the discovery) and her demographic (a woman in a field where women are underrepresented), providing an inspiring example to aspiring students. The narrative of a lone undergraduate disproving experts has a timeless appeal, though Tang herself is quick to credit the quantum algorithm designers whose shoulders she stood on, and the mentorship of Aaronson.

Her success demonstrates the value of mentorship and open-mindedness. Aaronson gave a challenging problem to a student, fully expecting one outcome; the student, not overawed by authority, pursued where the math led and found a different truth. This is a powerful message within academia: sometimes a fresh pair of eyes can see what seasoned researchers overlook.

F. Quantum-Inspired Boom: Tang’s result arguably kicked off a small boom in what is now called quantum-inspired algorithms. Recognizing that many quantum algorithms rely on linear algebra routines, researchers started to ask: what other quantum algorithms can we “inspire” classical versions of? Over 2019–2021, numerous papers appeared (some with Tang’s involvement, some independent) dequantizing algorithms for tasks in machine learning, graph theory, optimization and beyond. For example, work was done on quantum-inspired algorithms for network centrality measures, geometric problems, and so on. While not all were directly in Tang’s thesis, the spirit was similar: analyze the quantum algorithm’s structure and see if classical randomness can emulate it.

This also influenced the way quantum algorithm proposals are evaluated. Now, when someone comes up with a new quantum algorithm that promises a speedup for a classical-data problem, the immediate question from reviewers might be: “Can this be dequantized? What’s the classical baseline if we allow sampling?” If the authors can’t answer that, their quantum speedup claim might be met with skepticism. This raises the bar for claiming a true quantum advantage.

In conclusion, the impact of Tang’s work is multidimensional. It reset expectations in quantum machine learning, strengthened the bond between classical and quantum algorithm research, and provided tangible improvements and insights for classical computing. It serves as a cautionary yet constructive tale: quantum computing is powerful, but one must carefully separate the mystical from the technical. Some speedups might vanish under scrutiny, but even then, knowledge is gained — and sometimes, classical computing gets a free lunch from quantum ideas, as happened here [1].

7. Subsequent Work & Related Research

The story doesn’t end with recommendation systems. Tang’s work opened a door, and many others — including Tang herself — walked through it to explore new territory. In this section, we’ll highlight some of the subsequent research developments that built on or were inspired by Tang’s results. This includes both Tang’s own follow-up projects and independent work by other teams in the vein of quantum-inspired algorithms.

Tang’s Collaborations and Follow-ups: — Clustering and PCA (2018): As noted, Tang followed her recommendation system paper with results on other machine learning tasks. In the supervised clustering problem, one has points in a high-dimensional space and some labeled examples guiding the clustering; Tang’s classical algorithm achieved what a prior quantum algorithm did, grouping points efficiently by sampling features [6]. For PCA, where a quantum algorithm by Lloyd et al. (2014) could find top eigenvectors using quantum phase estimation on a data covariance matrix, Tang’s approach used sampling to approximate the covariance and extract eigenvectors classically. These efforts showed that even unsupervised and supervised learning tasks with linear algebra structure were amenable to dequantization.

The results were disseminated via arXiv and Tang’s talks, even if not all were formally published in conferences.

• Quantum-Inspired Regression (2019): The collaboration between András Gilyén, Seth Lloyd, and Ewin Tang (among others) on low-rank stochastic regression is particularly interesting because Seth Lloyd was an author of some original quantum algorithms that these classical ones emulate. It’s as if the original quantum inventors helped reverse-engineer their algorithms classically. This work showed that solving a set of linear equations Ax = b where A is large but low-rank (or approximable by low-rank) can be done in time polylogarithmic in matrix dimensions, given sampling access to A [6]. The quantum algorithm (the HHL algorithm [1]) had sparked hopes for solving linear systems exponentially faster; the classical result showed that under comparable data assumptions (like being able to sample rows of A by their squared lengths), one can achieve similar performance. This filled in another piece of the puzzle: quantum linear system solvers are not exponentially superior on generic matrices unless those matrices are structured in ways classical algorithms can also exploit.
• Comprehensive Framework (2020): The arXiv paper “Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning” by Chia, Gilyén, Li, Lin, Tang, and Wang (2020) [7] is a landmark summary that generalizes all these separate results under one umbrella. In 77 pages, it systematically develops the theory of quantum-inspired sublinear algorithms:
• It formalizes the input model (sample and query access to entries of matrices/vectors, analogous to QRAM for quantum).
• It presents a classical analogue of the Quantum Singular Value Transformation (QSVT) which underlies many quantum algorithms [7].
• It recovers the specific dequantized algorithms: recommendation systems, PCA, clustering, SVM (classification), low-rank regression, semidefinite programming, and adds a couple more (low-rank Hamiltonian simulation and discriminant analysis) [7].
• It often even improves on the complexity of the initial dequantized solutions by optimizing the sampling approaches.
• In short, this framework essentially declared: “almost any quantum algorithm in the literature that fits this mold (quantum linear algebra on low-rank data) can be systematically transformed into a classical algorithm with only polynomial slowdown.” It’s a sweeping statement backed by detailed proofs. Ewin Tang, as a co-author, helped cement her initial one-off discovery into a general principle with this work.
• Tang’s Recent Focus: By the time she completed her Ph.D., Tang’s research shifted a bit towards more fundamental complexity questions and models of quantum vs classical computation. For instance, in her dissertation she discusses the conditions under which one might ever get a true exponential quantum speedup for a linear algebra task (concluding that it would require confronting BQP-hard problems if data is classical) [4]. After solving several specific problems, the natural question became why and when does dequantization succeed or fail — a line of inquiry that blends with complexity theory. As of 2025, Tang’s interests include not just dequantization but also understanding quantum algorithms in realms beyond dequantization’s reach (like perhaps quantum algorithms on quantum data, or quantum advantage in learning patterns that are hard to linearize).

Independent Related Work: — Nature Review and Surveys: The rapid developments led to surveys and overview articles in top journals. For example, a 2022 Nature Reviews Physics article titled “Dequantizing algorithms to understand quantum advantage in machine learning” (Huang et al., 2022) discusses Tang’s work and related results [3]. This reflects that by then, Tang’s hypothesis had entered the mainstream of quantum computing discourse. These surveys help clarify to the broader scientific audience which QML speedup claims remain standing and which have been knocked down.

• Other Quantum-Inspired Algorithms: Beyond machine learning, the idea of quantum-inspired algorithms has extended to other domains:
• Graph algorithms: Researchers have looked at quantum algorithms for graph problems (like hitting time of Markov chains, or centrality measures) and found classical analogues via sampling.
• Optimization: Quantum algorithms for certain optimization or sampling tasks (like quantum walks or annealing processes) have classical analogues using random walks or simulated annealing. Tang’s work didn’t directly cover these, but it’s part of the same intellectual trend of cross-examining quantum techniques.
• Communication Complexity: Some works studied communication tasks or query complexity tasks to formally pinpoint why certain quantum advantages disappear when classical algorithms get a bit of extra power (like sampling). This is more theoretical, but important to underpin the empirical results with complexity class separations or equalities.
• Quantum Hardware-Inspired: Interestingly, the term “quantum-inspired” is also used by some companies (e.g., Toshiba’s “quantum-inspired optimization” or D-Wave’s classical solvers inspired by quantum annealers). Those efforts are a bit different — often they mean using analogies from quantum physics (like simulated quantum annealing) to solve optimization on classical hardware. It’s a parallel notion: using “quantum thinking” to improve classical algorithms, just as Tang did but in different contexts.
• Validating and Testing: Some computer scientists implemented Tang’s algorithms (or simplified versions) to test them on real data, to see if they’re not just theoretically fast but also practically useful. Results have been mixed: in practice, the constants and overheads of these quantum-inspired algorithms can be significant, and they really shine only on very large and structured data. For moderately sized recommendation problems, a well-tuned classical heuristic (like matrix factorization via stochastic gradient descent) might still win in runtime. However, these implementations serve as proofs of concept that the algorithms do work as described. Over time, as data grows and if implementations improve, quantum-inspired methods could become part of the standard toolkit for big data analytics.

It’s fair to say that Tang’s initial work has snowballed into a subfield. There are now workshops and conference sessions specifically on quantum-inspired classical algorithms. This demonstrates how a single insightful result can reorient a part of a research landscape. The conversation has shifted from “quantum vs classical: which is faster for ML?” to a more nuanced “in what scenarios can quantum beat classical, and how can classical rise to meet the challenge when given similar resources?” That’s a much more informed conversation, thanks to the subsequent research Tang set in motion.

Finally, it’s worth noting that while many quantum ML proposals were dequantized, researchers are actively seeking those that cannot be. The frontier of this field is identifying tasks where quantum might yet have the last laugh — problems where no one can find a classical analogue with comparable performance. We’ll discuss more on those in the next sections (limitations and outlook). But the existence of such a frontier is itself a product of Tang’s influence: we now have to draw that boundary line much further out than we thought.

8. Critical Perspectives & Limitations

In science, no result is above scrutiny, and Tang’s work, celebrated as it is, comes with its own set of caveats and limitations. It’s important to critically assess where these quantum-inspired algorithms excel, where they stumble, and what assumptions they rely on. Moreover, the conversation in the community has included some debates and divergent views on how to interpret these findings.

Let’s examine some key points critically:

A. The Data Access Assumption: The most significant assumption in Tang’s algorithms (and all similar dequantized algorithms) is the requirement of efficient sample and query access to data [3]. In plainer terms, the classical algorithms assume we can grab any entry of the data matrix quickly (query access) and that we can randomly sample entries or indices from distributions based on the data (sample access) in sublinear time. How realistic is this? — If the data (like the user-movie matrix) is stored in a conventional manner (say, in a standard database or even a sparse matrix format), sampling a truly random entry with a precise probability proportional to its value might be as slow as reading the whole dataset. To meet Tang’s assumption, one might have to preprocess the data into a specialized data structure (like those binary trees for each row, and maybe one for columns) [3]. Building such structures typically takes linear time in the number of data entries. In the context of recommendations, if there are, say, one billion ratings in the database, building the data structures might require iterating through those — which is fine if done once, but it means the algorithm isn’t entirely sublinear from scratch. — The algorithms often treat sampling and querying as O(1) or O(log n) operations abstractly. In practice, that means memory overhead and constant factors come into play. There could be large hidden costs in maintaining these structures for dynamic data (if the preference matrix updates with new ratings, how to update the sampling structure efficiently is another question).

In summary, if the data is static and we can afford preprocessing, Tang’s algorithm is fantastic. If the data is streaming or constantly changing, or if we count preprocessing in the runtime, the advantage might shrink. However, note that the quantum algorithm also implicitly required a similar assumption — loading data into a quantum RAM is not trivial either and could be expensive. The conversation around both algorithms often sets aside the initial loading cost to focus on query complexity.

B. Polynomial Slowdown vs. Exponential: Tang’s dequantization results usually show the classical algorithm is slower than the quantum by some polynomial factor (maybe in rank k or error 1/ε, etc.), but polynomial slowdowns are considered benign in complexity theory compared to exponential gaps. Still, a polynomial factor could be big enough to matter in practice. For example, if the quantum algorithm is O(\polylog(n)) and Tang’s is O(\polylog(n) ⋅ k²), and if k = 100, that’s a factor of 10,000 overhead. In theory that’s fine (still polylogarithmic in n), but in practice it might offset any advantage until n is astronomically large. So one limitation is that these classical algorithms, while better than previous classical methods, may not always be practically faster than all classical heuristics for moderate problem sizes or moderate ranks. They shine most when the data has a truly low effective rank and is extremely large.

C. Scenarios Where Quantum Still Wins: — High-Rank or Complex Data: If the user-item matrix had full rank or did not allow a good low-rank approximation, Tang’s algorithm wouldn’t apply (nor would the quantum one, in fairness — that’s not a situation where either method works well). But there might be other tasks where quantum algorithms do something that doesn’t obviously translate to sampling. For instance, consider data that is not just a static matrix but something like a stream or a dynamic process. Quantum algorithms might interfere across time steps in ways classical sampling can’t mimic. Currently, known exponential advantages require structure (like periodicity in Shor’s algorithm for factoring, or the constructed forrelation problem). Tang’s classification suggests we won’t find easy exponential speedups in ML without hitting complexity barriers, but it doesn’t rule out polynomial quantum speedups. A polynomial (say quadratic) speedup might not be dequantizable easily. For example, Grover’s search gives a quadratic speedup over classical. In the ML context, certain tasks might see quantum giving an O(√n) solution vs classical O(n). Those wouldn’t violate Tang’s observation about exponentials but still would be valuable. It’s an open question if such modest but real quantum advantages exist in practical ML. — Quantum Data: Tang’s results apply to classical data being processed. If the task is inherently quantum (for example, analyzing the output of a quantum experiment or quantum sensor data, or classifying quantum states), classical algorithms might not have direct access to the data in a useful form. In those cases, quantum machine learning could be learning patterns in data that classical algorithms literally cannot even see directly (because measuring the quantum data could destroy information). That’s outside the scope of Tang’s dequantization, which explicitly targeted classical input/output algorithms [6]. So quantum ML on quantum data remains a potential frontier where true advantage could lie. — Encryption and Privacy: Another angle is if data is encrypted or needs to be kept private (homomorphic encryption contexts) — quantum might do operations in superposition that are harder classically. But that’s again not in the standard QML scenario Tang considered.

D. Complexity Theory and New Assumptions: Some critics might argue that Tang’s results, while eliminating certain quantum speedups, do so by giving the classical model a power that it normally doesn’t have in standard complexity theory (like sample access or oracles). In standard classical complexity, an algorithm that needs random sampling access to input is not a vanilla algorithm; it’s an oracle-aided algorithm or a two-stage algorithm (preprocessing plus queries). From a pure complexity standpoint, we still don’t know if BQP (quantum polynomial time) equals BPP (classical probabilistic polynomial time). Tang’s work doesn’t suggest BQP = BPP in general — it suggests that for these specific problems under reasonable models, BPP (with some oracular help) covers what BQP can do. So one limitation is that it doesn’t resolve the bigger question of whether quantum computers are fundamentally more powerful than classical ones; it just narrows the gap for applied problems. In fact, Tang’s classification saying one class of QML is BQP-complete [4] leaves open the tantalizing possibility that if a QML algorithm tried to go after something like a generic NP-hard problem or something highly complex without the low-rank assumption, maybe quantum could do something classically infeasible — but more likely, quantum would also fail or it’s just as hard for quantum. This touches on deep complexity conjectures.

E. Critiques in Literature: There were some who initially questioned whether Tang’s algorithm truly matched the quantum one in all regimes. For example, does it handle the exact same output or just an approximate output? Typically, both quantum and Tang’s algorithm are randomized and approximate in nature, so that’s fine. Another question was: what if the quantum algorithm was slightly improved — would the classical follow? So far, the pattern has held: when improved quantum algorithms (like QSVT generalizations) came, the classical got improved accordingly [7]. But if someone found a quantum algorithm that leveraged, say, entanglement across data points in a novel way, could it bypass the sampling trick? As of yet, no clear candidate exists.

F. Practical Implementation Challenges: As touched on, implementing Tang’s algorithm in a production environment requires engineering effort — building and maintaining those sampling data structures, parallelizing steps, and so forth. If the data is extremely large but stored across distributed systems, can you do ℓ₂ sampling easily? Possibly yes, via distributed data structures or clever indexing. But these are non-trivial details that determine whether the algorithm is just a theoretical jewel or a practical tool.

G. The Name “Quantum-Inspired” and Overhyping the Reverse: Interestingly, just as quantum computing had its hype, there’s a risk of overhyping “quantum-inspired” as a buzzword. We should be careful: calling something “quantum-inspired” doesn’t automatically make it better than all previous classical algorithms. In Tang’s case, it genuinely was an improvement. But now the term appears in marketing for algorithms that sometimes were already known by other names (e.g., some quantum-inspired optimizers are really just classical algorithms akin to known methods). In academic literature, however, “quantum-inspired” has a clear meaning: coming from analyzing quantum algorithms. It’s important to keep that grounded and not make it a meaningless label.

H. Residual Quantum Advantages — A Balanced View: Some quantum computing proponents might downplay Tang’s result by pointing out that even if exponential speedups are gone for these tasks, quantum algorithms might still have constant-factor or polylog factors better (especially if hardware improves). For example, maybe the quantum algorithm could have a smaller polynomial in rank k or handle certain distributions better. Additionally, quantum algorithms might be more naturally suited for parallelization or future quantum memory structures. These are speculative, but they remind us that classical victory in these instances doesn’t necessarily trivialize the quantum approach. It just means classical can catch up given similar resource types. But a future where, say, quantum RAM is real and plentiful might resurrect interest in those quantum algorithms, because building huge sampling data structures classically could be comparably hard to just using QRAM on a quantum computer if that tech matured.

In essence, Tang’s results are robust but context-dependent. They carved out a significant territory where classical and quantum stand on equal footing (with classical needing some oracle help). They did not demolish the concept of quantum advantage broadly, and they rely on assumptions that themselves represent interesting engineering or model challenges. The critical perspective to maintain is: always ask under what conditions each algorithm (quantum or classical) operates, and what happens if those conditions change.

From a philosophical angle, Tang’s story reminds us that the boundary between “quantum-fast” and “classical-fast” is not a fixed line but a moving frontier. With ingenuity, that frontier can be moved — sometimes pushing quantum further back, sometimes finding new zones where quantum might remain ahead. Her work pushed the frontier significantly towards the classical side for ML tasks on structured data, which is a victory for classical computing — but the expedition continues in other directions.

9. Theoretical Implications

Ewin Tang’s findings carry profound implications for computational complexity theory and our understanding of the power of quantum versus classical computation. While her work is largely situated in the realm of algorithms (more practical than abstract complexity classes), it nevertheless informs several theoretical discussions:

A. BQP vs. BPP (and P): BQP stands for Bounded-Error Quantum Polynomial-Time, the class of problems solvable efficiently by a quantum computer. BPP is Bounded-Error Probabilistic Polynomial-Time, the class of problems solvable efficiently by a randomized classical computer (essentially, “classical with randomness”). A central question in theoretical CS is: Is BQP larger than BPP? We don’t know for sure. Many suspect BQP is larger (meaning quantum can solve some problems exponentially faster, like factoring, if factoring is indeed outside BPP), but it’s unproven.

Tang’s results don’t resolve this, but they do provide evidence in a specific domain that BQP offers no advantage. Essentially, for the problems she tackled (recommendation system, low-rank linear algebra tasks), she showed the problems are in BPP (with sample access) if they were in BQP with quantum access [4] [7]. In complexity terms, if we define a relational problem or promise problem corresponding to, say, “find a good recommendation” given a preference matrix in a certain input model, Tang placed that problem in BPP (with an oracle for sampling) whereas it was known to be in BQP (with an oracle for state prep). This suggests BQP and BPP are tied for those oracle models. One might say that relative to certain oracles (like oracles that give sample or quantum access to data), BPP = BQP for a broad class of linear-algebraic problems. Complexity theorists often consider such oracle-relative results as insightful hints.

B. Oracle Separations and Relativization: In complexity theory, we sometimes allow both classical and quantum machines an oracle (a black box) and compare them. Tang’s work effectively constructed a classical oracle (sampling access) that matches a quantum oracle (state preparation). It hints that if a quantum algorithm’s speedup relies on an oracle that gives it “unfair” access to data, then giving a similar oracle to classical machines levels the field. This aligns with the idea that we should compare apples to apples when claiming separations. There are known results (like one by Scott Aaronson and Ambainis in 2015) that show an oracle relative to which certain problems separate quantum and classical query complexities, and others where they don’t. Tang’s contributions give concrete examples of no separation in realistic oracular settings.

C. P vs. NP vs. BQP: There’s an indirect but interesting implication. Some of the QML algorithms that got dequantized were thought of as potential ways to solve problems faster that are not known to be in P (like certain linear algebra tasks on large data might be #P-hard in worst-case but become feasible with assumptions). By showing classical algorithms for them, Tang also placed those tasks in P (or BPP technically, which is essentially P with randomness). For instance, low-rank semidefinite programming under certain conditions was a candidate for quantum speedup; Tang’s work suggests those instances are also classical tractable [4]. So, every time we dequantize an algorithm, we’re effectively saying “this problem wasn’t as hard as we thought; it’s actually efficiently solvable classically (with conditions).” This doesn’t directly tackle NP-hard problems — indeed, none of the QML algorithms dequantized were solving NP-hard problems to begin with. It rather clarifies which problems are likely to remain outside P even for quantum: If a QML algorithm purported to solve an NP-hard problem with exponential speedup, we’d be extremely skeptical because it likely exploited some structural assumption. Tang’s classification lends weight to that skepticism: either the problem is structured (and then not NP-hard in practice and likely dequantizable) or it’s genuinely hard (and then quantum probably can’t crack it either, unless we’re in sci-fi territory of nonstandard quantum models).

D. Dequantization & Complexity Class Creation: Tang’s concept of “classical algorithms with sample and query access” might be seen as defining a new resource-based complexity class. Call it, say, BQSAMPLING or something — the class of problems solvable with randomized classical algorithms that have access to an oracle for ℓ₂ sampling from inputs. By formalizing such models, complexity theorists can ask: is BQSAMPLING = BQP (with quantum query access)? Tang’s work suggests yes for a broad set of problems. It also might inspire formal proofs: perhaps one could prove that for any problem in BQP that satisfies certain linear algebraic properties, there’s a corresponding BQSAMPLING algorithm. This is somewhat reminiscent of results like “quantum Fourier transform vs. classical Fourier sampling.” Indeed, some prior works have shown that certain quantum oracles can be simulated by classical oracles with a polynomial factor blow-up.

E. No Speedup on Classical Data — A Principle: There is a growing thesis, supported by Tang’s result and others, that quantum computers are unlikely to give exponential speedups for problems that involve truly classical data that needs to be read. If we have N bits of data in a file, a quantum computer might process it in √N time (Grover’s algorithm kind of scenario) but not in \polylog(N) without further assumptions. This aligns with the “Extended Church-Turing Thesis” which says any reasonable model of computation can only give polynomial speedups over the classical Turing machine model, unless it exploits some structure. Quantum computing challenges that thesis (Shor’s algorithm, for example, is an exponential speedup factoring integers), but factoring exploits the mathematical structure of integers. QML algorithms were another challenger to ECT thesis — Tang’s work basically says, for machine learning on generic data, the ECT thesis holds unless the data has special structure. If we accept that, it steers complexity theory to look for what structural or oracle assumptions allow quantum to jump ahead. Without them, reading input is a bottleneck that quantum can’t fundamentally circumvent beyond quadratic (Grover) type improvements.

F. Splitting Quantum Algorithm Space: Tang’s dissertation explicitly noted splitting QML algorithms into two classes [4]. The interesting part is labeling one class BQP-complete. BQP-complete problems (if they exist; BQP is not known to have complete problems under polynomial-time reductions, but under oracle or promise conditions, yes) are essentially the hardest problems a quantum computer can solve efficiently. By saying the “sparse input” QML tasks are BQP-complete, she’s implying that to get exponential speedup, those tasks are as hard as general quantum computation. That’s a fancy way of saying: you won’t get an exponential quantum speedup on an easy problem; it will only happen on problems that are themselves quantum-hard. This is a bit theoretical, but it resonates with a common-sense notion: quantum computers won’t magically speed up everything — only those problems that inherently have some hidden structure that quantum mechanics can exploit.

G. Dequantization as Proof Technique: In theoretical CS, one way to prove limits of computation is via simulations or diagonals. Dequantization provides a constructive way to show “this quantum algorithm doesn’t provide a super-polynomial advantage”. If someone claims a new quantum algorithm, a dequantizer can try to simulate it classically and see how much overhead is incurred. If only polynomial, then voila — not a super-polynomial separation. This doesn’t prove BQP = BPP in general, but it’s a powerful approach for specific algorithms. It complements other tools like lower bounds (proving a classical lower bound and matching it to quantum upper bound to see a gap or not).

H. Re-evaluating Quantum Speedups: Complexity theory also deals in asymptotic. Tang’s result emphasizes that asymptotically, for large n, the classical algorithm catches up. But one might ask: for realistic sizes, what if the quantum constant factors or lower-order terms are better? Theoretical implications aside, an exponential vs polynomial difference asymptotically is huge, but polynomial vs polynomial might still allow quantum to have a smaller power. However, complexity usually ignores constant factors and lower-order terms. In that sense, by bringing these QML tasks from “exponential gap” to “polynomial parity,” Tang’s work is like converting them from being evidence for BQP > BPP to evidence for BQP = BPP (for those tasks). It nudges our belief that maybe quantum doesn’t give exponentially more power broadly, just different power.

I. Open Problems: Theoretically, a big question remains: Are there any problems in NP (or some outside BPP) that quantum can solve but classical cannot? Factoring is the candidate that quantum can do (Shor’s algorithm) but we don’t know if classical cannot (no proof that factoring is outside BPP or even P). QML had candidates like recommendation, but those fell. So we’re left with factoring, discrete log, maybe quantum simulation problems, and oracle problems like forrelation as clear quantum advantages. Tang’s work indirectly prunes the list of candidate natural problems for which one might have believed an exponential quantum-classical separation. This sharpens the focus: factoring and certain algebraic problems, or problems involving periodicity structure, remain central. On the flip side, it suggests maybe new complexity classes relevant to learning or data might be defined that capture what quantum can do vs classical under certain input models. There’s a concept called QSamples vs PSamples in literature (quantum vs classical sampling). Tang effectively showed PSamples (classical sampling) can do what QSamples (quantum sampling) can, for low-rank linear algebra.

In sum, while Tang’s breakthrough was not framed as a complexity theory result, its implications weave into the tapestry of how we compare quantum and classical power. It provides a compelling case study supporting the notion that quantum advantages are subtle and often circumventable when scrutinized. It encourages complexity theorists to refine their conjectures about quantum speedups — distinguishing between those rooted in genuine complexity class separations and those that were artifacts of comparing apples to oranges. It’s fair to say Tang’s result, along with a handful of others, has become part of the evidence base that shapes our understanding of the quantum-classical boundary in computation.

10. Future Outlook

Having journeyed through the past and present of Ewin Tang’s work and its impact, we now turn to the future. What comes next? How will these insights shape the trajectory of both quantum computing and classical algorithm design? We outline several key directions and possibilities:

A. Further Quantum-Inspired Algorithm Development: The wave of quantum-inspired algorithms is likely to continue. Researchers will keep examining new quantum algorithms through a dequantization lens. As quantum computing research churns out innovative algorithms (for example, algorithms for differential equations, machine learning on quantum data, etc.), there will be a parallel effort to find classical analogues. This doesn’t mean all quantum algorithms will be copied classically — but the mindset is now established. In fact, Tang’s approach could extend beyond linear algebra. One could ask, for instance, about quantum machine learning algorithms using variational circuits or quantum neural networks — are there classical surrogate models that perform similarly? Already, some work in 2020s has looked at whether classical tensor networks can mimic certain quantum neural networks. This is analogous in spirit: find the classical equivalent structure.

B. Identifying Quantum-Only Zones: On the flip side, quantum algorithm designers will refine their focus on problems that resist dequantization. What might those be? — Tasks where data size is not the bottleneck but computational complexity is — e.g., factoring a large number has a small input (just the number) but quantum does it faster. Those remain prime territory (though not ML). — Tasks involving genuine quantum phenomena — like simulating quantum physics or chemistry. If the problem itself is quantum (like finding ground state energies of molecules), classical algorithms struggle because the state space is exponentially large. Quantum computers are naturally suited to such problems. We expect continued emphasis on quantum simulation as a “killer app” category that classical cannot catch up to easily. — Within machine learning: possibly generative modeling or sampling from complex probability distributions. There are quantum algorithms that sample from distributions that might be hard to sample classically (like certain quantum state outputs). If those distributions lack a concise classical description, classical sampling might fail. Quantum machine learning might find niches in, say, creating data (quantum-generated data) or in reinforcement learning with quantum environments.

Essentially, the frontier might shift to tasks like those in QMA (Quantum Merlin-Arthur) or sampling problems in #P (number of solutions type problems) where quantum might offer quadratic or more advantage.

C. Integration of Quantum and Classical (“Best of Both”): A likely scenario in the coming decade is hybrid quantum-classical algorithms. Instead of asking which is better, many are exploring how to use small or medium-sized quantum computers as subroutines inside classical algorithms. For example, a quantum computer could quickly estimate a difficult quantity (like a certain inner product or a property of data) that is hard for classical to get, and then a classical algorithm uses that information to proceed. If quantum devices become available but not large enough for, say, Shor’s algorithm on huge numbers, they might still accelerate specific parts of an algorithm. Tang’s work suggests that for tasks like recommendations, quantum doesn’t add much if classical is doing well. But there might be tasks where a bit of quantum help could reduce a polynomial exponent or constant. Hybrid approaches are already studied in variational algorithms (like the quantum approximate optimization algorithm, QAOA, which has classical outer loops and quantum inner loops). For machine learning, one could imagine a pipeline where a quantum subroutine finds a rough global pattern and a classical algorithm fine-tunes locally (or vice versa). The optimal use of quantum resources in a classical workflow will be a design question for future algorithm engineers.

D. NISQ Era Caution and Strategy: We are currently in the NISQ (Noisy Intermediate-Scale Quantum) era — quantum computers with tens to hundreds of qubits that are noisy and not error-corrected. Tang’s findings give one more reason to be cautious about expecting dramatic ML applications from NISQ devices. If a purported advantage needed even an ideal quantum machine to surpass classical, a noisy smaller machine certainly won’t beat the well-optimized classical algorithms we now have. Therefore, at least in the near term, industries might not deploy quantum for things like recommendation engines or kernel-based classifiers. Instead, they’ll probably stick to classical solutions, possibly quantum-inspired ones. This buys time for quantum hardware to improve and for researchers to find genuinely hard tasks for classical machines where even small quantum devices can show something useful (for example, quantum random circuits for certified random numbers, which Google’s experiment touched on, or small molecule simulations that push classical to the edge).

E. Education and Skill Development: There’s a silver lining in Tang’s narrative for workforce development: skills in classical computer science and mathematics remain extremely relevant even as quantum computing rises. Tang herself excelled by knowing classical linear algebra techniques and computational theory. The next generation of researchers are likely to be quantum-classical bilingual — fluent in quantum algorithm concepts but also deep in classical algorithmic techniques. Universities are already integrating quantum computing into curricula, but Tang’s example suggests they should equally emphasize randomized algorithms, linear algebra, and complexity theory. The interplay means a well-rounded computational theorist can contribute either way.

F. Potential New Algorithmic Paradigms: Tang’s work bridged quantum algorithms and classical random algorithms in a novel way. This makes one wonder: are there other computational paradigms out there that we can draw inspiration from? For instance: — Could biological computing paradigms inspire classical algorithms? (Not directly related, but an analogy — just as quantum inspired classical, maybe other unconventional models could too.) — Could analog physics processes (like simulated annealing or dynamics) inspire new algorithms or conversely be de-analogized? There’s already a field of physics-inspired algorithms (e.g., using Ising model heuristics, etc.), but rigorous analogies could be drawn just as Tang did rigorously for quantum vs classical. — Cross-pollination with AI: Perhaps techniques from deep learning (which is largely empirical and heuristic) could be given rigorous classical algorithms analogues that guarantee similar results. This is speculative, but the spirit of Tang’s work — take something that seems like magic (quantum speedup, or here deep learning’s uncanny success) and explain/replicate it with classical computation — could be a guiding star in other subfields.

G. Complexity Theory Developments: Theoretically, one future direction is to formalize Tang’s hypothesis and potentially prove theorems about it. For example, a conjecture could be: “Any quantum machine learning algorithm operating on a low-rank data matrix with quantum query access can be simulated by a classical algorithm with sample/query access with at most polynomial loss.” A formal proof of that would be a big result in complexity (some pieces of it are essentially proved by the QSVT dequantization framework). Alternatively, complexity theorists might try to identify an oracle relative to which BQP ≠ BPP still, even for some linear algebra tasks. If none can be found for a broad set of tasks, it strengthens the case that quantum advantage in those areas is elusive. Also, exploring intermediate classes like QNC (quantum NC circuits) vs classical NC might benefit from such insights (NC = problems solvable in polylog time on parallel computers — quantum circuits might have parity with classical if similar resources given, etc.).

H. Quantum Hardware Evolution — Will it Loop Back? Suppose a decade from now we have large quantum computers with quantum RAM. Would we revisit these algorithms? Possibly yes. If one can load data into a quantum machine extremely fast (maybe via some photonic parallel input or something), then the quantum algorithm can run and give an answer quickly. The classical algorithm might still require linear preprocessing. So in a scenario where data is fed in a streaming quantum manner, quantum could reclaim an advantage. This is to say, technological advances in hardware could tip the balance practically even if asymptotically they’re similar. It’s a bit sci-fi, but imagine sensors that directly record data into quantum states — then quantum ML algorithms could run on that without ever converting data to classical form. In that pipeline, Tang’s classical approach might not apply because the data never sits in a classical accessible memory in full. It’s an edge case, but worth considering for the far future: when our interface to information might be more quantum (e.g., quantum internet sensors, etc.), QML could find a native playground.

I. Applications of Quantum-Inspired Methods: In the near term, one future direction is simply applying Tang’s algorithms (and their successors) to real-world problems and seeing if they outperform existing methods. This includes: — Big matrix computations in science and engineering (maybe low-rank matrix inversion for large systems of equations, like in climate modeling or engineering simulations). — Recommender systems at companies: will someone implement a variant of Tang’s algorithm in a production recommender for, say, e-commerce? If successful, it’d be a win for quantum-inspired methods. — Healthcare or genomics data analysis, where data matrices can be huge but low-rank structure exists (genetic expression data, etc.).

The more success stories emerge of quantum-inspired algorithms giving speedups in practice, the more it validates Tang’s impact beyond theory.

J. Broadening “Quantum Without Quantum”: Tang’s cheeky hypothesis title could be generalized: What other “Quantum X Without Quantum” might we achieve? For example, “Quantum Cryptography without Quantum” — can we devise classical protocols with similar security to quantum key distribution? Or “Quantum Sensing without Quantum” — using clever classical sensors to mimic quantum-enhanced sensing. In some cases, quantum really offers unique advantages (like unbreakable security from QKD or very high precision in sensing beyond classical limits due to entanglement). But Tang’s work emboldens one to check if the gap is as wide as believed. In cryptography, for instance, some quantum crypto advantages (like certain randomization tasks) have classical counterparts but others (like based on Bell’s inequality) do not. The point is a philosophical one: quantum technologies often challenge us to think differently, and sometimes we find out classical physics or computation could do a surprising amount when we reimagine the problem.

In conclusion, the future likely holds a balanced co-evolution of quantum and classical computing: — Quantum computing will push into domains where classical cannot easily go (ensuring it finds genuine niches of advantage). — Classical computing will keep absorbing lessons from quantum breakthroughs (ensuring we elevate classical capabilities and set higher bars for quantum to clear). — Rather than one replacing the other, we’ll see a rich interplay — much as Tang’s journey exemplified: a quantum algorithm begat a classical algorithm, which in turn forced better understanding of quantum limits, which now informs future quantum algorithm design.

This symbiosis is a win-win for science. If quantum wins in some domain, we get a new tool beyond classical’s reach. If classical catches up, we have improved our classical arsenal and learned more about why quantum didn’t win there. Ewin Tang’s work has become a landmark case of the latter scenario, and it primes researchers to be both optimistic and realistic. Optimistic that there are incredible algorithms yet to be discovered (maybe hiding in quantum proposals), and realistic that quantum advantage must be proven, not just assumed. The status quo in early 2025 is that quantum computers are still mostly experimental, while classical algorithms are in production doing amazing things on big data. Tang’s hypothesis and results encourage a thoughtful approach to bridging that gap: squeeze all we can from classical methods inspired by quantum, and reserve quantum for where it truly shines.

The coming years will test this ethos in new contexts, and either way — whether through new classical algorithms or genuine quantum supremacy demonstrations — we’ll end up with deeper knowledge of computation’s ultimate capabilities.

Executive Summary

Key Findings: Ewin Tang’s research fundamentally altered our understanding of quantum vs. classical performance in machine learning tasks. At just 18, she discovered a “quantum-inspired” classical algorithm that can solve the recommendation problem as fast as a quantum algorithm, upending a flagship example of quantum advantage [1]. Her subsequent work and Ph.D. dissertation expanded this dequantization approach into a general framework, demonstrating that many proposed quantum machine learning (QML) speedups disappear when one grants classical algorithms similar data access (sample-based access) [4]. In essence, Tang’s “Quantum Machine Learning Without Any Quantum” hypothesis posits that if input data is classical, quantum computers offer at best polynomial speedups for a broad class of linear-algebra-based ML tasks — any exponential quantum advantage can likely be matched by a clever classical algorithm without quantum hardware. This dramatically narrows the gap where quantum supremacy can be claimed in data analysis. Her work dequantized quantum algorithms for recommendation systems, clustering, principal component analysis, support vector machines, regression, and more, by leveraging classical randomized linear algebra techniques (notably ℓ₂-norm importance sampling and sketching) that mirror quantum operations [3].

Strategic Implications for Research: Tang’s breakthroughs serve as a reality check for the quantum computing field. Researchers are now more cautious in asserting quantum speedups — any new QML algorithm is scrutinized for dequantization: Can a classical sampler do the same? The bar for claiming a true quantum advantage has been raised, prompting quantum algorithm designers to identify problems that resist all known classical techniques. This has refocused quantum research onto domains with more inherent quantum structure (e.g. quantum simulation, cryptography) rather than generic big-data processing. At the same time, Tang’s work has invigorated classical algorithm research: it highlighted that classical computers still have untapped potential for improvement by importing ideas from quantum computing. A new subfield of quantum-inspired classical algorithms has emerged, fostering collaboration between quantum physicists and classical computer scientists. In complexity theory, Tang’s results reinforce the Extended Church-Turing Thesis for practical data problems — they hint that quantum and classical computers are often on equal footing when given comparable access to data, aligning with the notion that reading input is a fundamental cost no computer can dramatically shortcut (barring special structure).

Impact on Industry and Quantum Tech Roadmaps: For industry players investing in quantum computing, especially for machine learning and AI applications, Tang’s findings counsel a more measured outlook. Near-term quantum computers (which are limited in size and prone to noise) are unlikely to outperform classical ML algorithms on typical enterprise datasets, because classical algorithms — now improved by Tang’s techniques — can handle those tasks efficiently on conventional hardware [5]. Companies like Amazon, Netflix, Google, and Microsoft can confidently continue using classical recommender systems and other ML tools, potentially augmented by Tang’s quantum-inspired algorithms for extra efficiency, without fear of missing out on a quantum leap in those areas [2]. This may temporarily channel quantum R&D investment towards applications with clearer quantum-only value (e.g. materials simulation, optimization problems with fewer classical heuristics). That said, Tang’s work also gave industry a gift in the present: new algorithms that reduce computational costs for big data tasks. If implemented, these could cut down resource usage in large-scale systems (like reducing the time to generate recommendations or analyze patterns), translating to cost savings and performance gains with current technology.

Limitations and Balanced Perspective: It’s important to note the scope of Tang’s hypothesis. The classical algorithms require special data access (ability to sample and query data efficiently) and work best when data have a favorable structure (e.g. low effective rank) [3]. If data are unstructured or too large to even hold in memory, quantum models that process data in superposition could still hold an edge in some scenarios. Moreover, Tang’s results don’t negate all quantum advantages — famous examples like Shor’s algorithm for factoring still stand (there’s no known comparable classical algorithm). What her work ensures is that the “low-hanging fruit” of QML speedups has been largely picked; naive quantum algorithms that simply assume fast data loading no longer guarantee a win over classical. True quantum advantage will likely come from leveraging quantum phenomena (entanglement, interference) in ways that classical randomness cannot easily mimic, or from working on inherently quantum data.

Future Outlook: Moving forward, we foresee a continued convergence of quantum and classical algorithm design. Tang’s story exemplifies how quantum insights can catalyze classical breakthroughs, suggesting a virtuous cycle: any time quantum researchers propose a powerful new method, it doubles as a challenge for classical researchers to match it. This dynamic will refine our understanding of which problems are truly “quantum-hard.” Quantum computing efforts will be directed at niche supremacy — finding problems where even with Tang-style assumptions, classical algorithms slog exponentially while quantum ones thrive. Simultaneously, classical computing will integrate more “quantum-inspired” strategies, leading to faster algorithms in machine learning, optimization, and beyond that work on today’s hardware. In practical terms, data science pipelines might incorporate sampling-based sketching methods (descended from Tang’s work) as standard practice for handling massive datasets.

For quantum computing to make a dent in machine learning, future algorithms may need to operate in regimes outside Tang’s dequantization framework — for instance, learning directly from quantum mechanical data (where classical algorithms can’t even begin without lossy measurements), or achieving polynomial (rather than exponential) yet meaningful speedups that are safe from classical emulation. Those directions are being actively explored as the community digests the lessons from Tang’s results.

Ewin Tang’s “Quantum Machine Learning Without Any Quantum” hypothesis and her pioneering classical algorithms have reshaped the landscape of quantum vs. classical computing. They remind us that innovation can come from unexpected places — even a college student can redraw boundaries held by experts — and that science progresses by continually challenging its assumptions.

The immediate legacy is a more sober, rigorous approach to quantum algorithm claims and a new arsenal of classical techniques for big data. The long-term legacy will be seen in how we chart the course of quantum computing: with clearer eyes on what it can and cannot do. In the end, whether a task is done by qubits or bits, the goal remains the same — to compute efficiently and unlock new capabilities. Tang’s work brought us closer to that goal on the classical side, and set a high bar for the quantum side to aim for, ultimately accelerating our journey toward understanding when and where quantum computing will revolutionize computing, and when classical computing is “good enough” with a bit of inspiration from quantum.

References & Further Readings

[1] N. Wolchover, “Major Quantum Computing Advance Made Obsolete by Teenager,” Quanta Magazine, Jul. 31, 2018. [Online]. Available: https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/

[2] “Ph.D. student Ewin Tang recognized in Forbes’ ’30 Under 30' in science for taking the ‘quantum’ out of quantum computing,” Allen School News, Dec. 21, 2018. [Online]. Available: https://news.cs.washington.edu/2018/12/21/ph-d-student-ewin-tang-recognized-in-forbes-30-under-30-in-science-for-taking-the-quantum-out-of-quantum-computing/

[3] F. A. Mian, “Dequantizing the Quantum: Ewin Tang’s Classical Algorithms for Quantum Speedups,” Medium | Quantum Engineering, Nov. 2, 2018. [Online]. Available: https://medium.com/quantum-engineering/dequantizing-the-quantum-how-classical-algorithms-can-match-quantum-speedups-559c5d6b682e

[4] E. Tang, “Quantum Machine Learning Without Any Quantum,” Ph.D. dissertation, University of Washington, 2021. [Online]. Available: https://ewintang.com/assets/tang_thesis.pdf

[5] A. Boyle, “How this UW grad student, researching quantum computing, proved that classical computers are better than we thought,” GeekWire, Jul. 31, 2018. [Online]. Available: https://www.geekwire.com/2018/uw-grad-student-researching-quantum-computing-proved-classical-computers-better-thought/

[6] E. Tang, “An overview of quantum-inspired classical sampling,” ewintang.com, Jan. 28, 2019. [Online]. Available: https://ewintang.com/blog/2019/01/28/an-overview-of-quantum-inspired-sampling/

[7] C.-Y. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang, and C. Wang, “Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning,” arXiv preprint arXiv:1910.06151, Oct. 15, 2019. [Online]. Available: https://arxiv.org/abs/1910.06151

[8] S. Aaronson, “Customers who liked this quantum recommendation engine might …,” Shtetl-Optimized, Jul. 31, 2018. [Online]. Available: https://scottaaronson.blog/?p=3880