When classical computers are just too boring.

Computers, theoretically, have two things: states (like the memory of the computer) and computations (moving from one state to another, like the CPU).

State

As said before, a Qubit in state ∣ψ⟩\ket{\psi} is the quantum mechanics analog of a bit. It is often represented by spin-1/2 particles. It's In the Hilbert Space HH.

∣ψ⟩∈H\ket{\psi}\in H

Let there be nn qubits. It's a Span of all basis states

∣ψ⟩∈H=span{∣0⟩,∣1⟩}⊗n\ket{\psi} \in \mathcal{H} = \mathrm{span}\{\ket{0},\ket{1}\}^{\otimes n}

The state is a superposition over all 2n2^n basis strings. ana_n are all probability amplitudes. See Composite System for how to deal with multiple qunatum systems.

∣ψ⟩=α1∣0,0,…,0⟩+α2∣1,0,…,0⟩+⋯+α2n∣1,1,1,…,1⟩\ket{\psi} = \alpha_1\ket{0,0,\ldots,0} + \alpha_2\ket{1,0,\ldots,0} + \cdots + \alpha_{2^n}\ket{1,1,1,\ldots,1}

Computation

Computation is a unitary operator UU applied to the input state

∣ψout⟩=U∣ψin⟩\ket{\psi_\text{out}} = U\ket{\psi_\text{in}}

In computers, we measure zz basis collapses the output and returns a bit string zz with probability given by the Born Rule

P(z)=∣⟨z∣ψout⟩∣2,z∈{0,1}nP(z) = \big|\braket{z | \psi_\text{out}}\big|^2, \qquad z \in \{0,1\}^n

We use Interference makes wrong answers destructively cancel and right ones add up.

We use entanglement to create correlations that classical registers can't hold.

Gates

What can unitary operator UU be?

One qubit gates

Two qubit gates