Quantum Computing

The theory of computation has traditionally been studied almost entirely in the abstract, as a topic in pure mathematics. This is to miss the point of it. Computers are physical objects, and computations are physical processes. What computers can or cannot compute is determined by the laws of physics alone, and not by pure mathematics.

— David Deutsch

Dirac Notation #

• \braa=\keta\dag

\dag is called the dagger operation, or Hermitian conjugation, or just the conjugation operation.

• \braketb|a: inner product

Qubits #

Computational Basis States #

\ket0:=[10]

\ket1:=[01]

Quantum State #

The quantum state of a qubit is a vector of unit length in a two-dimensional complex vector space known as state space.

• Normalisation Constraint: |α|2+|β|2=1 for α\ket0+β\ket1

Quantum Logic Gates #

NOT Gate #

X(α\ket0+β\ket1)=α\ket1+β\ket0

• Function application is just matrix multiplication.

X=[0110]

• Notation originated from Pauli’s σx operation to describe rotations around x-axis
• XX=I

Quantum wire #

• If input \ketψ then output is also \ketψ
• Hard to implement; quantum states are fragile.
• If state is stored in a neutrino then state will be well preserved; can easily pass through a mile of lead without disturbance
  • But quantum gates can’t be implemented with them as they won’t interact

Hadamard Gate #

H\ket0=\ket0+\ket1√2

H(\ket0+β\ket1)=α−β√2\ket0+α−β√2\ket1

H=1√2[111−1]

• HH=I
• Many algorithms first use Hadamard gates to “spread out” in quantum states, i.e., in superpositions of multiple computational basis states, which makes it possible to take computational shortcuts. At the end of the algorithm they use clever patterns of cancellation and reinforcement to bring things back together again into one (or possibly a few, in the many-qubit case) computational basis state, containing the desired answer

Measurement #

• If you measure a qubit is in the state α\ket0+β\ket1 in the computational basis it gives you a classical bit of information: either 0 with probability |α|2, or 1 with probability |β|2
• A fundamental fact about this measurement process is that it disturbs the state of the quantum system. After the measurement, if you get the outcome 0 then the state of the qubit afterwards (the “posterior state”) is the computational basis state \ket0 and vice-versa.
  • No matter what the outcome, α and β are gone. And so you can’t get any more information about them.

General single-qubit gates #

• A matrix U is unitary if U\dagU=I where U\dag is the adjoint of U: U\dag:=(UT)∗
  Unitary matrices preserve the length of their inputs

Controlled-NOT gate #

• The wire with the small filled dot is the control qubit and the one with the larger unfilled circle is the target qubit.

• For a two-qubit system, the general state is a superposition of the four computational basis states: α\ket00+β\ket01+γ\ket10+δ\ket11
  • Normalisation condition: |α|2+|β|2+|γ|2+|δ|2=1
• If control bit is set to 1, then the target qubit is flipped (NOT’d), else no change. \ketx,y→\ketx,y⊕x
  • ⊕: XOR, addition modulo 2