Quantum Bayesian Networks

November 17, 2018

18 Year Old Girl shows that Seth Lloyd’s quantum machine learning algorithm is junk

Filed under: Uncategorized — rrtucci @ 6:15 pm

On July, 2013, Seth Lloyd, together with 2 of his minions, unveiled with much fanfare and self-admiration, a quantum machine learning (QML) algorithm based on an earlier algorithm called HHL (which stands for Harrow, Hassidim, Lloyd). HHL allows one to use a quantum computer to solve a sparse system of linear equations. Lloyd has been enhancing his QML algorithm since its inception 5 years ago. He added to it, Topology in 2014 and GANs in 2018 .

Hundreds of news articles have been written extolling the power of Lloyd’s QML algorithm and the brilliance of its inventor. And now, an 18 year old girl named Ewin Tang has shown (see https://arxiv.org/abs/1811.00414 , https://arxiv.org/abs/1811.04852 , https://arxiv.org/abs/1811.04909 ) that Lloyd’s algo is junk. By the technical term “junk”, I mean that Tang proposed a classical algorithm that does the same thing and is almost as efficient as the quantum one ( i.e., both have very similar time complexity) plus the classical one doesn’t require a quantum computer with QRAM whereas HHL does. (QRAM is a mythological resource that will be much harder to achieve than fault tolerant quantum computing, which itself is a distant dream.)

Before showing that Seth Lloyd’s QML algo is junk, Tang also showed (see https://arxiv.org/abs/1807.04271) that Kerenidis’s quantum algo for recommendation systems is also junk (same def of the word junk as before).

If you think that Ewin Tang might be wrong, think again. Her emperor deflation algorithms have been vetted by respected members of the theoretical computer science community, including Tang’s teacher and advisor for this project, Prof. Scott Aaronson, a famous figure in quantum computing.

3 related topics come to my mind, Hans Christian Andersen’s tale “The Emperor’s new clothes”, this Macbeth quote about the futility of life:

Out, out, brief candle!
Life’s but a walking shadow, a poor player
That struts and frets his hour upon the stage
And then is heard no more: it is a tale
Told by an idiot, full of sound and fury,
Signifying nothing.

and a scene from the reality TV show Survivor that is sometimes given as an illustration of the phenomenon of Schadenfreude.


  1. Soon enough, they will all have much more serious issues to worry about!

    “The Heaven and Earth are impartial
    They move the 10.000 things
    as if they were straw dogs.”

    Comment by technofeudalism — November 18, 2018 @ 4:48 pm

  2. technofeudalism, we definitely live in scary times

    Comment by rrtucci — November 18, 2018 @ 7:05 pm

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: