Quantum Gates

In classical Boolean circuits, $\{\land,\lor,\neg\},\{\neg\land\}$ are sets of universal gates.

In quantum setting, for any unitary matrix $U$, $\exists$ approximation of $U$ that can be obtained by using only gates from small sets.

CNOT

Operation on $2$ qubits.

Flip the second qubit iff the first qubit is $1$:

$\vert00\rangle\stackrel{M}\rightarrow\vert00\rangle$
$\vert01\rangle\stackrel{M}\rightarrow\vert01\rangle$
$\vert10\rangle\stackrel{M}\rightarrow\vert11\rangle$
$\vert11\rangle\stackrel{M}\rightarrow\vert10\rangle$

\[ M=\begin{pmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0\\ \end{pmatrix} \]

TOFFOLI

Some $8\times 8$ matrix that implements CCNOT.

Operation on $3$ qubits.

Flip the third qubit iff the first two qubits are $1$s:

$\vert110\rangle\stackrel{M}\rightarrow\vert111\rangle$
$\vert111\rangle\stackrel{M}\rightarrow\vert110\rangle$

\[ M=\begin{pmatrix} 1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0\\ 0&0&0&1&0&0&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&0&1\\ 0&0&0&0&0&0&1&0\\ \end{pmatrix} \]

HADAMARD

Operation on $1$ bit.

After this gate, we get $\vert1\rangle$ with probability $1/2$, $\vert0\rangle$ with probability $1/2$. $$ M=\frac{1}{\sqrt2}\begin{pmatrix} 1&1\ 1&-1 \end{pmatrix} $$ Claim: TOFFOLI and HADAMARD form a set of universal quantum gates.

Quantum algorithm: apply quantum gates to qubits

Quantum Problems

A quantum problem must be:

well-defined: Input qubit size must equal to output size.
reversible: given an output, one can always compute the input.

NAND

Input $2$ qubits, output the NAND results of the two.

To make the problem well-defined, we need to make input size = output size.

To make the problem reversible, we need extra qubits (ancilla qubits).

Input: $q_1,q_2,\vert0\rangle$. Output: $q_1,q_2,q_1\mathsf{NAND}q_2$.

Deutsch's Problem

Given a function $f:\{0,1\}\mapsto\{0,1\}$ as a black box. Question: $f(0)=f(1)$?

In classical way, compute $f(0)$, compute $f(1)$, then compare. ($2$ calls of $f$)

In quantum way, we need only $1$ call of $f$.

We need an extra ancilla qubit to make the problem reversible:

$f'(x,y)=(x,f(x)\mathsf{XOR}y)$.

GHZ Game

$3$ players, A, B, C.

Each player gets the input a qubit s.t. the number of $1$s is even.

Task: Each player outputs a bit s.t. the XOR of all bits = the OR of all bits. No communication allowed!

The classical way: No strategy with shared randomness can win with probability $>3/4$.

In quantum way, there is a strategy can win with probability $100\%$: Each player does the same

If the input is $0$, apply HADAMARD gates on it and output.
If the input is $1$, 1. apply $S^+$ gates on it; 2. apply HADAMARD gates on it; 3. measure and output.

$S^+$ is S dagger gates: $$ \begin{pmatrix} 1&0\ 0&-i \end{pmatrix}. $$

Quantum Teleportation

Alice and Bob share a Bell state.

Alice takes another qubit $\vert\psi\rangle=\alpha\vert0\rangle+\beta\vert1\rangle$ as input.

Task: Bob needs to learn $\vert\psi\rangle$.

Requirement: Alice can send only $2$ classical bits to Bob. (instead of sending the qubit $\vert\phi\rangle$)

Theorem: pre-shared Bell state + $2$ classical bits is equivalent to $1$ qubit.

Solution

We give solution in a classical way, it is not hard to convert it into quantum version.

Assume that Alice and Bob share a randomness coin.

Assume that Alice has the classical random bit $v=(\alpha,\beta)$ (which is equivalent to qubit $\vert\psi\rangle$).

Task: Bob must learn $v$.

Requirements: Alice can only send $1$ bit with probability $(1/2,1/2)$

Alice and Bob get bits $X_a,X_b$ from the shared coin ($X_a=X_b$)
Alice applies CNOT on $(V,X_a)$.
Alice sends $X_a$ to Bob. (Satisfying $(1/2,1/2)$ property)
Bob applies CNOT on $(X_a,X_b)$. The we get $\Pr\{X_b=0\}=\alpha,\Pr\{X_b=1\}=\beta$