# Review

## Quantum Gates

Any truth table can be built by circuit

• with $n \cdot m \cdot 2^n$ gates (by brute force: use $NOT$ to make input all $0$s, combine them using $OR$, if target is $1$, then use another $NOT$, else do nothing)

• or with $m \cdot 2^n/n$ gates (C. Shannon)

Any circuit can be converted to reversible manner, except for creating zero-ed input.

Theorem: $\forall F: \{0, 1\}^n \to \{0, 1\}^m$ if it is computable with $G$ classical gates, then you can convert to reversible quantum gates with $n+m+G$ qubits and $G+n$ gates, assuming all extra $G$ bits are initialized to $0$, left in a garbage state.

## Minus Sign

H, NOT, H: turn $0^\circ$ into $0^\circ$, turn $90^\circ$ into $-90^\circ$.

NOT, H, NOT, H, NOT: turn $0^\circ$ into $180^\circ$, turn $90^\circ$ into $90^\circ$.

## Algorithms

def swap(A, B)
CNOT A B // B = A + B
CNOT B A // A = 2A + B = B
CNOT A B // B = 3A + 2B = A

def If_(A)_then_Minus(A):
H on A
H on A

@require |A> = 1|0>
def If f() then Minus(A):
Add 1 to A    // 90 degree
H on A        // -45 degree (now is parallel to NOT gate, if apply NOT now, we can't tell whether we have applied NOT)
Add f() to A  // -45 degree or 90+45 degree
H on A        // 90 degree or -90 degree
Add 1 to A    // 0 degree or 180 degree


// TODO: how about don't require?

def reflection_accross_mean():
If OR(X1, X2, ..., Xn) then Minus

@require x1, x2, ... = 0
def solve_sat(f):
// prepare uniform superposition

// repeat following two steps
If f() then Minus // reflection accross 0
reflection_accross_mean()


For $n$ variables with $T$, we need $O(T)$ instructions for if f() then minus and $O(n)$ instructions for reflection accross mean. If we repeat $k$ times, then it is $O(knT)$

For small enough $k \leq 0.01\sqrt{2^n}$, amplitude of $x^*$ is about $2k + 1$. Which is about $\frac{1}{2500}$ probability.

To get $Pr\{\text{print out } x^*\} \simeq 100\%$, we need:

k = \sqrt{N} \cdot \frac{\pi}{4} = \sqrt{2^n} \cdot \frac{\pi}{4}

## Linear Algebra

|+\rangle = \begin{bmatrix} +\sqrt{1/2}\\ +\sqrt{1/2}\\ \end{bmatrix}, -|+\rangle = \begin{bmatrix} -\sqrt{1/2}\\ -\sqrt{1/2}\\ \end{bmatrix}, |-\rangle = \begin{bmatrix} +\sqrt{1/2}\\ -\sqrt{1/2}\\ \end{bmatrix}, -|-\rangle = \begin{bmatrix} -\sqrt{1/2}\\ +\sqrt{1/2}\\ \end{bmatrix},

$NOT$: reflection accross $\pi/4$

$HAD$: reflection accross $\pi/8$

\langle f | v \rangle^\dagger = |v\rangle^\dagger \cdot \langle f|^\dagger = \langle v | f \rangle

Printing (in standard basis $|0\rangle$, $|1\rangle$) qubit in state $|v\rangle$ will output "0" with probability $|\langle 0 | v \rangle |^2$ and "1" with probability $|\langle 1 | v \rangle |^2$

If we only care about the probability of printing "0" after some transformation $T$, we can do the following:

1. apply $T^\dagger$ with $|0\rangle$: $|t\rangle = T^\dagger|0\rangle$
2. apply $T^\dagger|0\rangle$ to the state we care about: $\langle t | v \rangle = |t\rangle^\dagger |v\rangle = (T^\dagger|0\rangle)^\dagger |v\rangle = \langle 0 | T |v \rangle$

If a state $|v\rangle$ is $\theta_i$ angle with respect to its basis $|\vec{i}\rangle$, then:

• $Pr\{\vec{i}\} = \cos^2 \theta_i$

• $Pr\{\vec{j}\} = \sin^2 \theta_i$

## Filter

If you want turn the amplitude by $\delta$ degree with $n$ filters, the intensity of light getting through is:

\prod_{i=1}^{n}\left(\left(\cos\theta\right)\cos\left(\theta+\frac{\delta}{n}\right)+\left(\sin\theta\right)\sin\left(\theta+\frac{\delta}{n}\right)\right)^{2} = \left(\cos\frac{\delta}{n}\right)^{2n}

We choose to evenly distribute the angles because the function $\cos$ and $\sin$ is about linear near small angle. If the difference of angle is too big, the error will accumulate, meaning more intensity of light will be lost.

## Grover

If you want to do $k$ rotations instead of $1$, you will rotate by about $2k\sqrt{\frac{m}{N}}$. Therefore, if you want to rotate $\frac{\pi}{2}$, you need $k = \frac{\pi}{4}\sqrt{\frac{N}{m}} \in O(\frac{1}{\sqrt{p}})$

## Elitzur-Vaidman Bomb Problem

Bomb Nothing
Send 0 No Info No Info
Send 1 Explode No Bomb

Solution: send $|Rot_\frac{\pi}{n}\rangle$ $\frac{n}{2}$ many loops, measure once.

\begin{align*} &(r|0\rangle + s|1\rangle) \otimes (x|0\rangle + y|1\rangle)\\ =&r|0\rangle \otimes (x|0\rangle + y|1\rangle) + s|1\rangle \otimes (x|0\rangle + y|1\rangle)\\ =&|0\rangle \otimes (rx|0\rangle + ry|1\rangle) + |1\rangle \otimes (sx|0\rangle + sy|1\rangle)\\ =& rx|00\rangle + ry|01\rangle + sx|10\rangle + sy|11\rangle\\ \end{align*}
(F \otimes G)(|u\rangle \otimes |w\rangle) = F|u\rangle \otimes G|w\rangle

## MEP

\begin{align*} &\sqrt{\frac{1}{2}}(|00\rangle + |11\rangle) \tag{original MEP}\\ \to&\sqrt{\frac{1}{2}}(|0\rangle \otimes |0\rangle + |1\rangle \otimes |1\rangle) \tag{separate}\\ \to&\sqrt{\frac{1}{2}}(|0\rangle \otimes Rot_{\theta}|0\rangle + |1\rangle \otimes Rot_{\theta}|1\rangle) \tag{sender rotate his qubit}\\ \end{align*}
1. If we now let the receiver measure the qubit, the receiver would not be able to know which angle we have sent $\theta$ or $\theta + 90^\circ$, which loses all meanings.
2. So we have to measure first and give instruction to receiver on how to interpret the result, since the outcome of our measurement (hence the state it actually collapse to) is random.
3. With $Pr\{A = 0\} = \frac{1}{2}$ state collapse to $|0\rangle \otimes Rot_\theta|0\rangle$. With $Pr\{A = 1\} = \frac{1}{2}$ state collapse to $|1\rangle \otimes Rot_\theta|1\rangle$
4. So we send 1 bit information to receiver let him know which one is intended.

## Sharp-SAT

def MeasureRotationOperationAgainst(Rot_theta, makeStart, d):
# for each significant digits
for i = 1, 2, 3, ..., d:
|start> = makeStart()

# measure log(d) times (to yield high probability)
for m = 1, 2, 3, ... log(d):

# rotate |start> 10^i times
for j = 1, 2, 3, ..., 10^i:
Rot_theta |start>

Measure |start>

# make one prediction
cos^2(10^i * theta) = fraction of measurements that are 0
return theta

\sum_{i = 1}^d O(\log d) \cdot O(10^{i - 1}) = O(\log d) \cdot O(10^{d - 1})

def measureAgainstMysteryStart(U, |start>)
Make T
H on T
If T then U on |start>
H on T
Measure T
return |start> # that is rotated

U|\text{start}\rangle = U\begin{bmatrix} a\\ b\\ c\\ d\\ \end{bmatrix} = \begin{bmatrix} e\\ f\\ g\\ h\\ \end{bmatrix}
Pr\{T=0\} = \left(\frac{a+e}{2}\right)^2 + \left(\frac{b+f}{2}\right)^2 + \left(\frac{c+g}{2}\right)^2 + \left(\frac{d+h}{2}\right)^2 = \langle\text{avg}|\text{avg}\rangle = \left(\cos\frac{\theta}{2}\right)^2\\ \text{and state rotate to }\frac{|\text{avg}\rangle}{\cos(\theta/2)}\\ Pr\{T=1\} = \left(\frac{a-e}{2}\right)^2 + \left(\frac{b-f}{2}\right)^2 + \left(\frac{c-g}{2}\right)^2 + \left(\frac{d-h}{2}\right)^2 = \langle\text{disp}|\text{disp}\rangle = \left(\sin\frac{\theta}{2}\right)^2\\ \text{and state rotate to }\frac{|\text{disp}\rangle}{\sin(\theta/2)}\\

$O(nd\log d + d)$ if we can efficiently power matrix, $O(10^d\log d + d)$ otherwise.

## Revolver Resolver and Factoring

Using $\gcd(42, 30) = 6$

\begin{align*} 42 = 1 \times 30 + 12\\ 30 = 2 \times 12 + 6\\ 12 = 2 \times 6 + 0\\ \end{align*}
\begin{align*} 6 = 30 - (2 \times 12)\\ 6 = 30 - (2 \times (42 - 1 \times 30))\\ 6 = 30 - (2 \times 42 - 2 \times 30)\\ 6 = -2 \times 42 + 3 \times 30\\ \end{align*}
def gcd(x, y):
while(y):
x, y = y, x % y
return abs(x)

# This simulates finding the length of cycle of
# U(x) = M * x mod F
def findL(F, M):
i = None
count = 0
while(i != 1):
if i == None:
i = 1
i = (M * i) % F
count = count + 1
return count

F = (* the thing we factor *)
M = 42 (* pick a M *)

fract = Rationalize[]; (* fraction of 2pi *)
L = Denominator[fract] (* get L from quantum *)
Solution1 =
If[GCD[M, F] == 0, M, "no easy solution"]
W = ModularInverse[M, F]
S = PowerMod[M, L/2, F]
P = GCD[S - 1, F]
Q = GCD[S + 1, F]


## Complexity Classes

Complexity Classes:

• P: polynomial with no random classical computer

• NP: polynomial verification, or, equivalently, there exists a randomized algorithm can try to find the answer with non-zero probability

• NP-complete: hardest in NP

• BPP: polynomial with random classical computer (BPP = P)

• BQP: polynomial with random quantum computer

• Quantum-Eval in BQP-hard
• BQP not in NP
• BQP in EXPTIME
• BQP in PSPACE (polynomial space: by running only one branch once)
• PP: quantum computer can get $0.5 + \gamma$ probability, but classical can get $0.5 + \gamma / 2^n$ probability.

## Time Travel

def SAT(b_0 qubit, C circuit):
Flip n^2 coins
b_1 = 0
else:
pick y in {0, 1}^n at random
if C(y):
b_1 = 1
else:
b_1 = b_0