Google has been coming up with a strategy to demonstrate quantum supremacy, using their experimental quantum computer that they have been working on for quite some time.
What is Quantum Supremacy?
Quantum supremacy is the claim that quantum computers can perform tasks that no current computers can handle. It is widely assumed that we will eventually reach quantum supremacy, but nobody has done it yet because the few experimental quantum computers that currently exist can only run a small number of specialised algorithms.
What is Google’s Plan?
Google’s plan is based on simulating coin flips. For an ordinary computer, this is simple – it just stores two numbers, and chooses one of them at random, and to simulate 50 coin tosses, it just selects a number at random 50 times in a row. This is simple for regular coins, and works perfectly fine, but if the coins were to be made to behave like particles obeying the laws of quantum mechanics, it becomes much more complicated.
Due to quantum entanglement, we cannot know whether any individual coin turned up heads or tails without knowing about the outcome of all the other coins. This problem of simulating coin tosses with quantum entanglement is known as quantum sampling. Classical computers work sequentially, so choosing 50 numbers at the exact same time is not possible for them. For this reason, Google argues that quantum sampling would require storing all possible configurations of all 50 coin tosses, so that all of the coins can be thrown simultaneously.
Since one bit in a regular computer can only store one of two states, covering all possible outcomes for 50 coins would take an extremely large amount of data storage. To work out how many possible outcomes there are is very simple. When working out the number of outcomes for any fair die, coin, spinner, etc., you can use the formula, where a is the number of outcomes from 1 roll (this is 2 on a coin – heads or tails), and b is the number of times that it is rolled. For 50 coin flips, this comes out as 1,125,899,906,842,624 – a very large number indeed. This is equivalent to 128 petabytes, which is a ridiculously large amount of storage.
For a quantum computer, however, this may not be a problem. Quantum computers are based on qubits, which can be either 1, or 0, or both at the same time. This means that, if a quantum computer had 50 qubits, it would be able to easily simulate these 50 coin flips.
To read more, turn to page 2 below.