Quantum Supremacy: What is it and what does it mean?

Later this year we will probably see Google’s first demonstration of “quantum supremacy”.
This is when a quantum computer outperforms a conventional computer.
In this video I will explain what that means.
But before we get to quantum supremacy, I have to tell you what a quantum computer is.
All conventional computers work with quantum mechanics because their components rely on
quantum behavior like electron bands.
But the operations that a conventional computer performs are not quantum.
Conventional computers store and handle information in form of bits that can take on two values,
say 1 or 0 or up and down.
A quantum computer, on the other hand, stores information in form of quantum-bits or q-bits
that can take on any combination of 0 and 1.
Operations on a quantum computer can then entangle the q-bits, which allows a quantum
computer to solve certain problems much faster than a conventional computer.
Calculating the properties of molecules or materials, for example, is one of those problem
that quantum computers can help with.
In principle, properties like conductivity or rigidity, or even color, can be calculated
from the atomic build-up of a molecule.
We know the equations.
But we cannot solve these equations with conventional computers.
It would just take too long.
To give you an idea of how much more a quantum computer can do, think about this.
One can simulate a quantum computer on a conventional computer
just by numerically solving the equations
of quantum mechanics.
If you do that, then the computational burden on the conventional computer increases exponentially
with the number of q-bits that you try to simulate.
You can do 2 or 4 q-bits on a personal computer.
But already with 50 q-bits you need a cluster of supercomputers.
Anything beyond 50 or so q-bits cannot presently be calculated, at least not in any reasonable
amount of time.
So what is quantum supremacy?
Quantum supremacy is the event in which a quantum computer outperforms the best conventional
It needs to be a specific task because quantum computers are really special-purpose machines
whose powers help with particular calculations.
However, to come back to the earlier example, if you want to know what a molecule does,
you need millions of q-bits and we are far away from that.
So how then do you test quantum supremacy?
You let a quantum computer do what it does best, that is being a quantum computer.
This is an idea proposed by Scott Aaronson.
If you set up a quantum computer in a suitable way, it will produce probabilistic distributions
of measurable variables.
You can try and simulate those measurement outcomes on a conventional computer but this
would take a very long time.
So by letting a conventional computer compete with a quantum computer on this task, you
can demonstrate that the quantum computer does something a classical computer just is
not able to do.
Exactly at which point someone will declare quantum supremacy is a little ambiguous because
you can always argue that maybe one could have used better conventional computers or
a better algorithm.
But for practical purposes this really doesn’t matter all that much.
The point is that it will show quantum computers really do things that are difficult to calculate
with a conventional computer.
But what does that mean?
Quantum supremacy sounds very impressive until you realize that most molecules have quantum
processes that also exceed the computational capacities of present-day supercomputers.
That is, after all, the reason we want quantum computers.
And the generation of random variables that can be used to check quantum supremacy is
not good to actually calculate anything useful.
So that makes it sound as if the existing quantum computers are really just new toys
for scientists.
What would it take to calculate anything useful with a quantum computer?
you think is “useful” and how optimistic you are that algorithms for quantum computers
will improve.
So let us say, realistically it would take a few million q-bits.
When will we get to see a quantum computer with a few million q-bits?
No one knows.
The problem is that the presently most dominant approaches are unlikely to scale.
These approaches are superconducting q-bits and ion traps.
In neither case does anyone have any idea how to get beyond a few hundred.
This is both an engineering problem and a cost-problem.
And this is why, in recent years, there has been a lot of talk in the community about
NISQ computers, that are the “noisy intermediate scale quantum computers”.
This is really a term invented to make investors believe that quantum computing will have practical
applications in the next decades or so.
The trouble with NISQs is that while it is plausible that they soon will be practically
feasible, no one knows how to calculate something useful with them.
As you have probably noticed, I am not very optimistic that quantum computers will have
practical applications any time soon.
In fact, I am presently quite worried that quantum computing will go the same way as
nuclear fusion, that it will remain forever promising but never quite work.
Nevertheless, quantum supremacy is definitely going to be a super-exciting event.