Introduction to QC, with Grover's Search

\[ \newcommand{\<}{\langle} \renewcommand{\>}{\rangle} \]

Introduction to Quantum Computing¶

0712238 Yan-Tong Lin

Motivation¶

:::success

One might state the main goal of theoretical computer science as "study the power and limitations of the strongest-possible computational devices that Nature allows us." Since our current understanding of Nature is quantum mechanical, theoretical computer science should arguably be studying the power of quantum computers, not classical ones. --- Ronald de Wolf

:::

The Big Picture¶

- Introduction to Quantum Computating - Postulates of QM - Basics of QC - Grover's Search

Postulates of QM¶

Quantum State¶

Superposition¶

- $|0\rangle + |1\rangle$ - linear combinations of states are allowed

Measurement¶

- $|\psi\rangle = \alpha|0\rangle + \beta |1\rangle \ni \alpha, \beta \in \mathbb{C}$ - when we try to "measure" the state - $Pr(M(|\psi\rangle) \to |0\rangle) = |\alpha|^2$ - $|\psi\rangle=\sum a_i |i\rangle \implies \sum |a_i|^2 =1$ - called normalization

Note: - sometime ignore normalization if we do not care

Entanglement¶

- $|00\rangle + |11\rangle$ - mutaul information

Note: - not a postulate actually, more like a property discovered by the definitions - Superposition and - Formal definition of Entanglement is

Unitary Evolution¶

- norm perserviation is desired - $\langle Ux, Uy \rangle = \langle x, y \rangle \implies UU^{\dagger}=I$

Basics of QC¶

Quantum Gates¶

- like gates on classical bits - $X= \begin{pmatrix} 0 && 1 \\ 1 && 0 \\\end{pmatrix}$, $Y= \begin{pmatrix} 0 && -i \\ i && 0 \\\end{pmatrix}$, $Z= \begin{pmatrix} 1 && 0 \\ 0 && -1 \\\end{pmatrix}$ - $CNOT$: $|x\rangle|y\rangle \to |x\rangle|x \oplus y\rangle$ - $H= \frac{1}{\sqrt{2}} \begin{pmatrix} 1 && -1 \\ 1 && 1 \\\end{pmatrix}$

Note: - X is not, Y, Z is upto change of basis - H is like sqrt ok identity, to uniform - (Mention Universality) There exist universal quantum gate set that permits arbitrarily small error.

Oracles¶

- quantum version of a certain function $f$ - $O_f(|x, y\>) = |x, y\oplus f(x)\>$

Note: - if we know $f$, it should be easy to construct the corresponding $O_f$

Quantum Parallelism¶

- $f:\{0,1\}^n \to \{0,1\}$ is either balanced or constant - It requires $O(N=2^n)$ query of $f$ for a classical circuit to judge - quantum: $O(1)$ query

Note: - can briefly introducethe concept of complexity here (asymptotic time as function of n)

Deutsch-Jozsa Algorithm¶

Grover's Search¶

Gover's search is a quantum algorithm for the "unstructured search" problem. The core idea is to see the input space as a combination of "Good" and "Bad" subspaces and do reflections (Grover's iteration) to make the probability of observing the "Good" part higher. To achieve a probability close to 1, about $O(\sqrt{n})$ iterations are required.

The Problem - Unstructured Search¶

Assumption - has a query oracle¶

View Uniform Superposition as l.c. of $|G\rangle, |B\rangle$¶

- $|G\rangle = \sum |\omega\rangle$ - $|B\rangle = \sum |\omega\rangle$ - $|U\rangle = \sin(\theta)|G\rangle + \cos(\theta)|B\rangle$ - here $\sin(\theta) = \sqrt{\frac{M}{N}}$

References¶

https://homepages.cwi.nl/~rdewolf/qcnotes.pdf
Quantum Computation and Quantum Information, Michael Nielsen, Isaac Chuang
https://qiskit.org/textbook/preface.html

Last update: 2023-09-15