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 0s, 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.
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.
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:
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:
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
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.
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}})
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.
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
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.
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:
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
PP: quantum computer can get 0.5 + \gamma probability, but classical can get 0.5 + \gamma / 2^n probability.
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:
Table of Content