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
  Add 1 to 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():
  Had X1, X2, ..., Xn
  If OR(X1, X2, ..., Xn) then Minus
  Had X1, X2, ..., Xn

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

  // 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:

Linear Algebra

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

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

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

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

Adding and Deleting Qubits

MEP

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

Hadamard Test

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

$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$

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]
Bad1 = If[Mod[L, 2] == 0, "good", "bad M"]
S = PowerMod[M, L/2, F]
Bad2 = If[S == F - 1, "bad M", "good"]
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
  if all head:
    b_1 = 0
  else:
    pick y in {0, 1}^n at random
    if C(y):
      b_1 = 1
    else:
      b_1 = b_0

The steady state for satisfiable: