Quantum Computing for Beginners

There are three important properties of quantum mechanics:

Superposition, Entanglement, and Interferences 

Superposition

For colors, b/w has 2 colors, gif has 256 colors, same as VGA (2^8), SVGA has 2^16=65536 colors, true color (24bit) has 2^24 = 16 million, deep color has 2^30 = 1 billon colors. Now we are using digital computer. The binary system has two numbers 0 and 1. So we are at b/w stage. 

For music, bugle has 5 notes (or may be three), march/pop songs/national anthem uses mostly 7 notes, opera/orchestra/Mozart uses 12 notes. As we know, orchestra has more details and rich melody than bugles. You can consider using a digital computer is kind of listening bugle instead of orchestra music. 

The superposition property enables quantum computers to represent more information in each unit (qubit) therefore a vast amount of data can be processed in one step. 

Entanglement

We know that twin brothers or sisters can somehow "communicate" even though they are physically apart. It seems there is something (or someone) that sends information between each other. 

Players in Matching bands synchronize with the conductor. This means, one move, all follows. 

The entanglement property "sends" information from one particle to another without delay. It seems there is a super force (God?) to control the particles' rotations with the identical angles along XYZ axes. Once entangled, one can control all qubits by just manipulating one qubit. (The others will follow). It functions like a lever. 

Interferences

Throwing two rocks in still water you will see waves and when two waves meet, they add or cancel base on the phases of the waves. 

A clock (minute hand) is a good example to explain phases. 12 o'clock is considered phase = 0, at 5 minute phase = 15 (degree), at 15 minute phase = 90. After one hour, the minute hand goes back to phase =0.

---------------

Summary

Entangled qubits have a vast number of different phases (considering distributing on a clock), most of them cancel each other (eg. 5 minute and 35 minute cancel each other). Some add up (remember waves). In the end, a few that with same phase become much larger (fit) than the rest. They are the solutions to the problem. 

If you know genetic algorithm or evolutionary computation, it functions similar, same is true comparing to the human evolution. The fit species remain and get better (more fit). Unfit species disappear.

[This explanation uses a form of story teller rather than Einstein level scientific definitions and quantum theory.]

Tensor Product

Tensor product is an outer product of two vectors. Here are some examples:

For two qubits:

For three qubits:

In "general",

CNOT Gate

 Controlled NOT gate: 

⏐x, y⟩ → ⏐x, x ⨂ y⟩

Matrix:  

The CNOT maps 

⏐0 0⟩ → ⏐0 0⟩

⏐0 1⟩ → ⏐0 1⟩ 

⏐1 0⟩ → ⏐1 1⟩

⏐1 1⟩ → ⏐1 0⟩

Proof:

⏐00⟩ = [1 0 0 0], ⏐01⟩ = [0 1 0 0], ⏐10⟩ = [0 0 1 0], ⏐11⟩ = [0 0 0 1], all vectors transposed for easy typing. 

Here ⏐0⟩ == [1 0] and ⏐1⟩ == [0 1] and ⏐ab⟩ = ⏐a⟩ ⨂ ⏐b⟩

Apply matrix multiplications: 

CNOT × ⏐00⟩ → ⏐00⟩

CNOT × ⏐01⟩ → ⏐01⟩

CNOT × ⏐10⟩ → ⏐11⟩

CNOT × ⏐11⟩ → ⏐10⟩

#

In math, left Kronecker product ⨂ is

For example: 

Qubit Operation (2)

CNOT gate: to flip iff  (if and only if) the control quit is |1>, otherwise it does nothing. 

Entanglement:

⏐+⟩ == [1/sqrt (2) * (|0> + |1>) == 0.707 |0> + 0.707 |1>

⏐-⟩ == [1/sqrt (2)] * (|0> - |1>)

X (a, b) = (b, a), NOT gate

|a, b> == |b, a>, see below qubit swap:

[a |0> + b |1>] |0> == a|00> + b|10>

|𝝍> == a |0> + b |1>

|𝝍>|𝝍> == a^2|00> + ab|01> + ab|10> + b^2|11>

Bell state (entanglement):

Linear Algebra - Qubit Operations

Vectors are commonly written in column format. Sometimes, we also use shorthand format such as (3, 4).

In quantum computing, the state |0> corresponds to vector (1, 0), and |1> corresponds to vector (0, 1). 

Commonly used quantum gates, quantum circuit symbols, and math representations: 

The Bloch sphere representation of X (NOT), H (Hadamard), and Z, S, T (phase) gates. 

We can see that 

• X gate rotates along X axis 180 degree (or less depending on the initial angle to Z axis). (NOT) 
• H gate rotates along Y  axis 90 degree (or less). 
• Z, S, T gates rotate along Z axis at certain degree. (phase)

Quantum Circuit

 A quantum circuit is a computational routine consisting of coherent quantum operations on quantum data, such as qubits, and concurrent real-time classical computation. It is an ordered sequence of quantum gates, measurements, and resets, which may be conditioned on and use data from the real-time classical computation. A set of quantum gates is said to be universal if any unitary transformation of the quantum data can be efficiently approximated arbitrarily well as a sequence of gates in the set. Any quantum program can be represented by a sequence of quantum circuits and non-concurrent classical computation.

A quantum gate is a reversible (unitary) operation applied to one or more qubits.

Electronic computer: program --> instructions (operand and data) - binary bits
Quantum computer: program --> quantum circuits (quantum gate and quantum data) - qubits

Quantum Cryptography

Quantum cryptography is to address issues in crypto key distribution by using a principle guaranteed by the fundamental laws of physics. Once a recipient receives the temper-proof key, She can then use conventional crypto method to encrypt/decrypt the message. So quantum cryptography is the hybrid approach of modern cryptography but the keys are exchanged via the quantum channel commonly called quantum key distribution (QKD). 

Fig. Quantum Cryptography

According to physics, a quantum state is unobservant. If an eavesdropper observes a quantum sate, it changes so as to cause errors at the destination. So the sending and receiving parties know the communication was compromised. Only validated keys are secure and used for further encryption/decryption. 

Image copyright: Author of this post. Free to use but reference is required. 

Quantum-safe Cryptography

The current public key encryption is mostly based on prime numbers. With the advancement of computer especial quantum computers, the threat to the existing crypto algorithms is becoming imminent. 

The need to increase the key length keeps growing. A new type of post-quantum or quantum resistant algorithms is under-development. 

Why should people worry about the existing encryption algorithms?

In WWII, German mathematicians claimed that the Enigma machine, based on simple substitution method, would require 100 years to solve. Alan Turing used less than 6 months built a Bombe at Bletchley Park. Bombe was able to crack 3,000 German encrypted message a day initially and later amounted to 2.5 million encrypted messages. 

Fig. Alan Turing's Bombe 

Today, those messages can be deciphered in a fraction of microseconds running a small program using the statistical analysis method. (The author has programmed one in Python.)

In 1977, RSA issued a challenge in an article "A new kind of cipher that would take millions of years to break". The so-called 40 quadrillion years problem (428 bit key) was solved in 1994 after a 6 months of work. 

RSA algorithm with key length 1024 bit to 4096 bit is considered strong and "unbreakable" today. Peter Shor @MIT proposed an algorithm that can solve such "unsolvable" programs on quantum computers. 

Imagine people store the encrypted data now and wait 10 years or so to decrypt when the powerful quantum computers are ready. Should you worry?

NSF Award Notice for Award - Quantum Crypto and Algorithms - May 6, 2020

This project promotes the progress of science in quantum computing algorithms and cryptologic techniques in order to improve security of encrypted information, which will have national security and defense applications.

Currently, the commonly used encryption algorithms such as RSA are considered “unbreakable” by modern digital computers due to the complexity of computation that would be required. However, this may change in the next decade or so in light of advances in quantum science.  Quantum mechanics has led to the discovery that considerable numbers of states can be manipulated at the same time thus significantly reduce the amount of time in processing. New quantum computers have shown the baseline of “quantum supremacy” in solving problems that classical digital computers practically cannot.

Efficient quantum algorithms are key to enable computer scientists to take full advantage of the next generation of practical quantum computers to efficiently solve today’s unsolvable problems. Advances in quantum science in both breaking and securing the encryptions are paramount for national security and preventing adversaries from taking advantage of critical areas of national defense.

This project seeks to discover efficient quantum cryptologic methods (i.e. the art of revealing the secret) and secure quantum cryptographic techniques (i.e. the science of making the secret more secure). This project not only exhibits the excellence in scientific research, but also supports diversity and inclusion goals for the benefit of society.