Part 1

What is Quantum Computing

Classical Deterministic Computing

The smallest unit of data is a bit. Each bit can either be 0 or 1.

Computation is split into a sequence of basic operations. Each operation acts on a small set of bits. → AND, OR, NOT gates, etc…

Bits are indipendent of each other. Applying an operation on a given set of bits does not affect bits outside this set.

Classic Probabilistic Computing

Some problems can be solved more efficiently using probabilistic computing than what is known with deterministic computing. Example: Plynomial Identity Testing.

Quantum Computing

The smallest unit of data is a qubit:

• Basis states: $|0\rang$, $|1\rang$;
• A qubit is a superposition $|\psi\rang = \alpha | 0\rang + \beta |1\rang$ of basis states.
• Measuring a qubit in the standard basis causes it to collapse to one of the two bases states $|0\rang$ or $|1\rang$.

Computation is split into a sequence of basic quantum operations and measurements. Each operation acts on a small set of qubits. Rotation gates, phase shift-gates, CNOT gates, etc…

Qubits may become entangled:

• Bell State: $\frac{1}{\sqrt 2} |0\rang |0\rang+\frac{1}{\sqrt 2}|1\rang |1\rang$;
• In general, a quantum state of a system with $n$ qubits is a superposition of $2^n$ basis states.