What is Quantum Computer: explained in 5 mins

• Quantum computers already exist
• Quantum Physics 101
• Quantum Computer is run on qubits
• Quantum Computing
• How Quantum Computer can solve RSA?
• What are Quantum Computers good for?
• Links

Quantum computers already exist

If we think that classical computer is a car, then Quantum Computer is not a faster car, it's a boat. It is meant for other tasks [1].

Several Quantum Computers already exist (e.g. China, Google, IBM). Some quantum computers can work only when cooled down to almost absolute zero, other work given the room temperature, but have huge size. It's not clear yet which implementation will win [2].

Quantum Physics 101

Particles (electrons, etc) are not tiny little balls of stuff [3]. That works for lots of thought experiments, but in fact they are superbizarre little fluctuations in fields that permeate the entire universe.

Here is my own understanding. Particles can be like waves in the water, but when you catch them to perform measurements, for a glimpse of time they turn into a little ball with some labels. When you set them free, they are waves again. They are like some magical shapeshifters.

Quantum Computer is run on qubits

Qubits are like waves. A qubit could really likely to be 0 which means a lower energy wave. A qubit could be more likely to be 1 which means a higher energy wave [1].

Each qubit has a probability of being each. When a quantum computer is working, the probabilities of multiple qubits interact. They add constructively or desctructively.

What is the job of software engineer here? She/he will alter the probabilities while the algorithm is running. Quantum computers don't try all the options. A Quantum Computer more like watches the pond, how the wave interacts, and then helps to find the most likely answer.

Quantum Computing

Mathematically [4], a qubit is a linear combination (a chance being 0 + a chance being a 1):

Similar to classical computers, specialists string together qubits, using construct called gates that can alter the states of qubits into circuits. E.g. we can have a qubit that's at the state of 0. We can use Hadamard gate to put it into superposition between 0 and 1. We can have multiple qubits with multiple gates in a circuit:

For the circuit to be useful, at some point you need to read about its outputs = measure it. When a qubit is measured, it loses its superposition and collapses into just a simple 0 or 1. To make sure the collapsed answer we got is a correct one, quantum gates need to be arranged in a way so that it would amplify the correct answer and cancel all the incorrect ones. This process is called interference.

We can also entangle two qubits so that their states have 50% chance of measuring 00 and 50% of measuring 11, but never a 01 or a 10.

How Quantum Computer can solve RSA?

RSA algorithm depends on the difficulty of finding factors of a very large number. Here is an example of factors: for 15 it's 3 and 5, because they are both primes and 3x5 = 15. It's easy to find the factors of 15 by trial and error, but the difficulty grows exponentially as the size of the number increases.

Peter Shor from Bell labs came up with an algorithm, its main idea is that long strings of numbers contain periodicities - patterns of repetition - which may not be obvious at first sight but may be teased out by mathematical analysis. Periodic patterns can be probed using Fourier analysis, which unpacks complicated wave patterns into their component parts. E.g. the complicated sound wave corresponding to the sound of a group of a musical instruments playing a chord together could be unravelled by Fourier analysis into a wave corresponding to a violin note, or to the cello, etc. A quantum computer using Shor's algorithm could set up a superposition with all the possible periods (waves), and select the one that actually fitted number in question. The periodicity found could then be used by a classical computer to reveal the factors of that number.

What are Quantum Computers good for?

They are good for finding structure in tons of data [1]. As for me, I expect that they will at least help to advance ML (especially not-supervised or semi-supervised learning).

Links

1. Cleo Abram. Quantum Computers, explained with MKBHD. Youtube
2. Michi Kaku | Quantum Supremacy | Talks at Google. Youtube
3. Jorge Cham & Daniel Whiteson. We Have No Idea. A Guide to the Unknown Universe.
4. What is Quantum Computing? IBM Technology. Youtube
5. John Gribbin. Computing with Quantum Cats. From Alan Turing to teleportation