Quantum Computing - Conceptual Introduction

Preliminaries - What Is QC?

Building Blocks

Qubits

Short for quantum bits.
Just like classical bits they need a well-defined physical representation, of which there are many (e.g. photonic polarization, electron spin, nuclear spin, Josephson junction, ion trap, etc.)
Unlike classical bits, they exist in a quantum superposition of available basis states (more on this later)
On the computational level we operate on logical qubits, which can comprise up to 1000 physical qubits (depending on the quantum error correction scheme)
An array of qubits is typically referred to as a quantum register

Quantum Gates

QC analogues of logic gates
Mathematically they are represented by unitary matrices (more on this later)
Unlike logic gates in classical computing, they are reversible (cf. Feynman’s and Fredkin’s remarks on classical reversibility)
n-qubit gate is represented by a $2^n × 2^n$ unitary matrix (this dimensionality results from the properties of tensor products)
Quantum gates can transform single or multiple qubits, conflate several qubits with each other (quantum entanglement), conditionalize certain actions, etc.

Measurement

Irreversible operation on a qubit or quantum register
Measurements are performed relative to a basis of base vectors
Measurement can only yield one of the constituent pure states (i.e. in the case of an already pure state the result will be known in advance)
The probability of arriving at a pure state is proportional to the squared modulus of its (complex) amplitude (more on this later)

Ancillary qubits

Because reversibility sometimes requires outputting additional information, it may be necessary to use additional, so called ancillary qubits, which will store this information and can later be discarded.
Because sometimes the ancillary qubits get entangled with the main thread of computation, it is not always possible to just discard them. In such cases one might need to perform uncomputation, which is a unitary way to undo the entanglement.

Decoherence

Unwanted, but unavoidable (?) interference between computational elements (qubits) and their (quantum-mechanical) surroundings
Decoherence boils down to physical qubits getting entangled with the environment
Attempts to limit decoherence involve cryogenic environments, shielding, quantum error correction, etc.

Mathematics of QC

Preliminaries

Complex Numbers

Complex numbers (commonly denoted as $\mathbb{C}$) are a generalization of real numbers ($\mathbb{R}$) but with the inclusion of the so-called imaginary unit ($i = \sqrt{-1}$).
Historically they stemmed from research into the solvability of quadratic equations (particularly, with negative discriminants). Pioneering the concept were Italian mathematicians Cardano, Bombelli and Tartaglia.
Initially, complex numbers were viewed as a purely mathematical trick, but over the next couple centuries their intimate relationship to geometry and physics was discovered (culminating in the central part they play in quantum mechanics).
The most general form of a complex number is: $z = a + ib$ (called a cartesian form). $a$ and $b$ are called real and imaginary part, respectively (we can say that $\Re{z} ≡ Re\ z = a$ and $\Im{z} ≡ Im\ z = b$).
An important concept is complex conjugation, which boils down to negation of the imaginary part and is frequently denoted as $z^*$ or $\bar{z}$ ($z^* ≡ \bar{z} = a - ib$).
An alternative way to represent a complex number is called polar form: $z = (r, \varphi)$, where $r = \sqrt{|a|^2 + |b|^2}$ and $\varphi = arctan(\frac{b}{a})$.
We have: $zz^* = (a + ib)(a - ib) = a^2 - (ib)^2 = a^2 + b^2 = |z|^2$. $|z|$ is called the modulus. This relation is important and will be lurking all throughout quantum mechanics.
Complex numbers can be visualized on a 2-dimensional complex plane as if they were 2D vectors. In this picture the real and imaginary parts correspond to $x$ and $y$ coordinates, polar components of a complex number correspond to polar coordinates of a vector, modulus is the distance from origin and complex conjugation is reflection about the real axis.
An interactive review of complex arithmetic is available here.

Linear Algebra

Nice interactive introduction/review available here

Mathematical concepts

Ket (vector)

An ordinary vector can be represented sybolically as a ket (after Dirac)
Notational equivalence:

$$|a\rangle ≡ \begin{bmatrix} a_1 a_2\\ \vdots\\ a_n\\ \end{bmatrix} $$

Bra (covector)

An object dual to a vector (a covector or differential form) can be represented sybolically as a bra
Hermitian conjugate is the conversion operation between bras and kets
Notational equivalence:

$$\langle a| ≡ {|a\rangle}^† ≡ \begin{bmatrix} a_1 a_2\\ \vdots\\ a_n\\ \end{bmatrix}^† ≡ \begin{bmatrix} a_1^* & a_2^* & \cdots & a_n^*\end{bmatrix} $$

Hermitian adjoint (or conjugate)

A combination of matrix transposition and taking complex conjugates of all its elements: $A^† = (A^T)^* = (A^*)^T$

Unitarity

A matrix is unitary when $AA^† = A^† A = I$
Unitary matrices preserve vector lengths and are thus generalizations of rotations $\langle a A|A a\rangle = \langle a|A^† A|a\rangle = \langle a|I|a\rangle = \langle a|a\rangle$
All quantum gates satisfy this property
Unitary matrices have eigenvalues of modulus $1$ (shown here)

Hermiticity (self-adjointedness)

A Hermitian (self-adjoint) matrix is identical to its Hermitian conjugate
All eigenvalues of a Hermitian matrix are real
Because of the above, physical observables (i.e. measurable properties of a system) are represented as Hermitian operators

Basic postulates of Quantum Mechanics

Each physical state is associated with a Hilbert space $H$ (vector space, where calculus can be applied) with an inner product $\langle a|b\rangle$ (for $a$ and $b$ being vectors in $H$)
The Hilbert space of a composite system is a tensor product of constituent Hilbert spaces
Physical observables are represented by hermitian matrices operating in $H$
The expectation value of an observable $A$ for a system in state $ψ$ is $\langle ψ|A|ψ\rangle$
The spectrum of an operator (its eigenvalues) represents the possible outcomes of physical measurement
State can be alternatively represented by a density matrix

Dynamics

The dynamics of a quantum system is given by the Schrödinger equation: $i \hbar \frac{∂}{∂ t}Ψ(\mathbf{r},t) = \hat H Ψ(\mathbf{r},t)$

Examples of Quantum Circuits

[[https://algassert.com/quirk#circuit={%22cols%22:\[\[%22X%22,%22X%22\]\],%22init%22:\[0,1\]}][NOT gate]]

Acting on two separate qubits set to $|0\rangle$ and $|1\rangle$ respectively.

[[https://algassert.com/quirk#circuit={%22cols%22:\[\[%22H%22,%22H%22\]\],%22init%22:\[0,1\]}][Hadamard gate]]

Converting a pure state into a superposition

[[https://algassert.com/quirk#circuit={%22cols%22:\[\[%22H%22,%22H%22\],\[%22H%22,%22H%22\]\],%22init%22:\[0,1\]}][2 Hadamard gates]]

… and back again

[[https://algassert.com/quirk#circuit={%22cols%22:\[\[%22%E2%80%A2%22,%22X%22\],\[1,1,%22%E2%80%A2%22,%22X%22\]\],%22init%22:\[1\]}][CNOT gate]]

Controlled NOT

[[https://algassert.com/quirk#circuit={%22cols%22:\[\[%22H%22\],\[%22%E2%80%A2%22,%22X%22\]\]}][Bell state]]

Simplest instance of quantum entanglement

[[https://algassert.com/quirk#circuit={%22cols%22:\[\[%22Swap%22,%22Swap%22\],\[1,1,%22Swap%22,%22Swap%22\],\[1,1,1,1,%22Swap%22,%22Swap%22\],\[1,1,1,1,1,1,%22Swap%22,%22Swap%22\]\],%22init%22:\[1,0,0,1,0,0,1,1\]}][SWAP gate]]

Exchange two qubits connected by the gate

[[https://algassert.com/quirk#circuit={%22cols%22:\[\[%22Z%22\],\[1,%22Z%22\]\],%22init%22:\[0,1\]}][Z gate]]

Negates the $|1\rangle$ state

Useful Resources

Quantum Programming Languages

Q# and Quantum Development Kit

QPL designed by Microsoft. The QDK contains a quantum simulator and many useful debugging tools. Q# programs are embedded within C# code, which handles the non-quantum part.

Qiskit

QPL by IBM. Reasonably mature programming environment, heavy integration with Jupyter notebooks, lots of high-quality introductory material.

PyQuil and Forest SDK

QPL build by Rigetti Computing. Embeds quantum computations within ordinary Python code. Unlike Q# it’s more of a library than separate language. Facilitates experiments with

Quipper

A QPL embedded in Haskell. Aspects of quantum computation, such as measurement, are represented as monadic types (cf. our conversation at Luigi’s Lucky Leprechaun)

Circuit Visualization

Quirk

Simple and intuitive quantum circuit visualizer. Good to untangle (hehe…) conceptual confusion that sometimes arises when working on a problem.

Cheatsheets

Q# and Algebra Quick Reference

Blogs

Shtetl-Optimized

Scientific blog by Scott Aaronson. Lots of explanations, discussions and pointers to other resources.

Websites

Quantum Computing Primer

Series of introductory articles on QC by Daniel Vaughan

Miscellaneous

Quantum Koans

Half-tongue-in-cheek, half-serious musings on the nature of QM

Microsoft Quantum Katas

A koan-like approach to teaching QC and Q#. There are two ways to run them:

Natively, using Microsoft’s QDK
Embedded in a Jupyter Notebook

Files

quantum-computing.org

Latest commit

History