Quantum Supremacy Task

Question

I’m trying to understand the task performed by Google’s Sycamore that recently achieved alleged Quantum Supremacy. I’ve read the paper in Nature but the actual task that would have taken 10,000 years to compete is over my head. Is anyone able to explain it in simpler terms?

Answer 1

First of all it seems that google has exaggerated a little bit by shooting the $10000$ years results. It seems that IBM, on his current and most powerful classic super computer, is able to perform the same task in $2.5$ days, saving the entire search space (Hilbert space) on a $250$ petabytes hard drive. This does not mean that google's result is not to be taken into consideration: it is definitely a milestone but it will not change the world as many claim, it will not provide us with stable and multipurpose quantum computers within a year or two ( to tell the truth, with current technologies it is not even practically possible to get computers with enough qbits and keep them in a consistent state).

Having made this premise, we come to the experiment:

Essentially (and in simple terms, very simple terms) what they did was to correctly sample from the possible outputs of a $53$ qbits random quantum circuit using a statistical test called linear cross-entropy benchmark and sampling about $5000000$ results in about $200$ seconds. The test was a stochastic triumph.

Some notes:

1. people (outside the discipline) are going crazy blathering of a proof of $P = NP$ or $BQP = BPP$ and then some... All these things are false, none of these important open problems have been solved by the experiment.
2. The real importance of having scalable quantum computers lies in being able to perform simulations of physical systems efficiently, which entails dramatic results in the industrial field: desig of new medicines, design of new materials, etc.
3. Quantum computers will not spell the end of cryptography: not all cryptographic methods can be efficiently cracked by a quantum computation and, in addition, we already know post-quantum cryptographic techniques: for example lattice cryptography.

Answer 2

The task performed by the Sycamore computer was meaningless. The output of the computation is essentially a random number.

So why does anyone care about it? On a very simple level, quantum computers are essentially random number generators. However, they do not generate uniform random numbers. With a properly designed algorithm, we can make certain outputs much more likely than others. The end result is usually that with high probability, the output is a useful number. For example, Shor's algorithm uses a quantum subroutine that with high probability gives a number that helps us find the prime factorization of a number.

Most quantum computations start out with a vector of qubits initialized to random, independent superpositions. This means that any bitstring is equally likely as output.

The "computation" a quantum computer does is to manipulate this random superposition, and to get certain qubits to interact with each other in certain ways, so as to manipulate the output distribution and increase the probability of getting the numbers we care about. This computation is encoded in a quantum circuit.

Now the computation Google did used a random circuit. They took some quantum gates and connected them together more-or-less arbitrarily. Why did they do this? Why did they not take a meaningful circuit (e.g. that for Shor's algorithm) and compute the outcome of that instead?

The reason is that their computer is too small to build a meaningful circuit. Had they implemented Shor's algorithm, they could only have used it to factor some very small numbers. This would not have demonstrated quantum supremacy because numbers that small could easily have been factored on a normal computer.

Instead, they chose a random circuit. Nobody understands what the circuit does, so nobody can cheat on a classical computer by exploiting knowledge about what the circuit computes. The only way to get the same output that Google did clasically, is to simulate the computation done by the quantum computer.

What Google computed is meaningless: The computation was specifically designed to be easy on a quantum computer and hard on a classical computer. The result has no intrinsic meaning, and it is purely meant to show off their quantum capabilities.

However, it is still a huge step forward: they showed, for the first time, a quantum computer able to evaluate an arbitrary quantum circuit and compute a result that cannot be computed classically. Even if the outcome of the computation is essentially meaningless, the fact they were able to obtain it at all is still very impressive.