IBM was able to simulate a 56 qubit quantum computer using only 3 TB of memory

Question

Recently it's been in the headlines that IBM was able to simulate a 56 qubit quantum computer using only 3 TB of memory. This is several thousand times smaller than one would expect the memory requirements of such a simulation to be. How were they able to do this? Did their simulation run correspondingly faster? Does the capacity to simulate quantum computers this way using conventional algorithms have any impact on our current understanding of the capabilities of quantum computers when compared to classical ones?

Answer 1

This blog post by Scott Aaronson gives a overview of why this simulation does not change anything about our understanding of quantum computers.

Maybe the best way to understand why is to understand what computer scientist are trying to prove at the moment: "quantum supremacy". The idea is to show that quantum computers can solve some problems much faster than classical computer (I insist on some because we know quantum computer only provide a speedup for some classes of problems but not all.) Now in theory we already have strong evidence that this the case because of Shor's algorithm:

• a quantum computer can factor a $b$-bit integer in time roughly $O(b^3)$
• the best known classical algorithm to factor $b$-bit integer runs in time $e^{kb}$ for some constant $k$
• one can verify if a factorization is correct with a classical computer in time $O(b^3)$

From this one can derive a "practical proof" that quantum computers provide a speedup of classical computers as follows:

• generate a random integer with $b=10000$ bits
• run Shor's algorithm to factor it: this takes maybe a few seconds (or minutes)
• verify answer with a classical computer: takes a few seconds (or minutes)
• factorize the number with a classical computer: takes a millions of years or more

The important fact in this example is that the incredible difference between the quantum and classical computers: a few seconds vs a few million years.

There is one major problem though: to factor an integer that size with a quantum computer, we need to build a quantum computer with many thousands of qubits. At the moment, the largest quantum computer ever built does not even have a hundred. Thus we cannot run the above experience (yet).

This is where Scott Aaronson and the IBM experiment enters the picture. Instead of trying to factor numbers, we want to find another problem as above but where the quantum computer is much smaller so that we can actually build it. One such problem is quantum simulations:

• simulating a quantum system with a quantum computer is very easy (polynomial time)
• simulating a quantum system with a classical computer is very hard (exponential)

So we go ahead and redo our experiment:

• pick a quantum system at random of size $b=100$ qubits
• simulate it with a quantum computer: takes a few seconds/minutes
• simulate it with a classical computer: takes a few million year

Since we can build a quantum computer of that size (~100 qubits), we are done right? Well no because how do we know the simulation with the quantum computer was correct? Sure it's fast, but maybe it's wrong! In this case we have not proven anything. You see with factorization, verifying the result is easy, but for simulation it is as hard as the simulation itself... This is the crucial issue.

In order to fix this, we want to find a value of $b$ such that the classical computer can still find the answer so that we can verify it but it has to be long enough to demonstrate that the gap between quantum and classical is huge. Researcher are trying to find this sweet spot, and think it is around $b=50$ where a supercomputer will take may a few months or year. The IBM paper shows that $50$ is too small. But remember that the simulation for $b=100$ is trillions of times harder than for $b=50$ (exponential), thus may the sweet spot is at $b=60$, but it is unlikely that we can ever reach $b=100$.

NOTES: I simplified most of the actual complexity bounds. I ignored the fact that quantum computations only give the correct answer with high probability, one may have to re-run the algorithm several times.