Lecture 2 - Sep 3, 2020

C C^dag = \tilde{C} \tilde(C)^dag
U D^2 U^dag = \tilde{U} \tidle{D}^2 \tilde{U}^dag
--> D = \tilde{D}

U = \tilde{U} R
for some R that [R,D] =0

thm: given states |psi>_AB and |gamma>_AB
psi_A = gamma_A <===>
there exists a unitary W s.t. (I otimes W) |psi> = |gamma>

<==   easy

==> |psi> = vec(X), |gamma> = vec(Y) = sum_ij Y_ij |i> otimes |j>
XX^dag = YY^dag
X = U_1 D_1 V_1^dag
Y = U_2 D_2 V_2^dag
U_1 D_1^2 U_1^dag = U_2 D_2^2 U_2^dag
--> D_1 = D_2
U_2 = U_1 R, for some R that [R, D_1] =0

(I otimes W) |psi> =
(I otimes W) sum_ij X_ij |i> otimes |j> =
sum_ij X_ij |i> otimes W |j> =
sum_ijk X_ij W_jk |i> otimes |k> =
vec(XW)

(applying unitary to the 1st system <--> left-multiplication)
W = V_1 R V_2^dag
XW = (U_1 D_1 V_1^dag) (V_1 R V_2^dag) = U_2 D_2 V_2^dag = Y

corollary: |psi>_{AB}, |gamma>_{AB'}
psi_A = gamma_A  <==>  either there is an isometry V:B-->B', or V:B'-->B that relates them

Detour -> cryptography.
---------------------
BB84 cryptosystem: = QKD, quantum key distribution
Alice chooses a random bit r, and a random basis b in {X,Z}
Z basis: |0>, |1>      X basis: |+>, |->   = (|0> +- |1>) / sqrt(2)
send this to Bob, and he measures in a random basis m in {X,Z}
tells Alice he's measured, then both reveal bases, discard if b != m, otherwise keep answer.
repeat N times, get about N/2 bits.
If Eve measures, she will introduce errors, which Alice and Bob can detect.
--> "key" = shared secret random string

coin flipping
QM -> strong coinflipping is impossible, weak coinflipping with any bias eps>0 is possible
Alice can choose any bias between  0 and 1/2+eps, Bob can choose anything in [1/2-eps, 1]

bit commitment.
two phases: commit and reveal
commit phase, Alice commits to a bit b
reveal phase, Bob learns b
properties:
1. valid - if both players are honest, Bob learns b and doesn't abort
2. hiding - after commit phase, Bob can't learn b
3. binding - during reveal phase, Alice can convince Bob to accept only one value of b

oblivious transfer (OT) - stronger than BC, equivalent to secure multiparty computation
Alice inputs bits (x_0, x_1).  Bob inputs b, learns x_b, Alice learns nothing

OT > BC > strong coin flipping

many of these things are possible quantumly with computational assumptions
Urmila Mahadev + others...  LWE = learning with errors

Thm: information-theoretically secure quantum bit commitment is impossible

detour - quantum channels, noisy q operation
rho_A --> N(rho)_B
which N are allowed?  (analogous to unitary or stochastic matrices for pure-state QM or probability)
1. tpcp maps = trace-preserving, completely positive linear maps
2. Kraus decomposition.  N(rho) = sum_k E_k rho E_k^dag, where {E_k} are Kraus operators
3. N(rho) = tr_E [ V rho V^dag], where V : A -> B otimes E is isometry

BC protocol.
Alice  --->  Bob
        <---
	 --->
	 <---
	commit phase: state is rho_0 or rho_1
	<---
	 --->
	 <---
	 --->
	 reveal phase

WLOG modify this to make players "honest but curious"
whenever Alice or Bob does a noisy operation, just do the isometry, skip the partial trace
now, global state of AB is always pure
@ commit phase, state is |psi_b>_{AB} for b in {0,1}

suppose that protocol is perfectly hiding  --> psi_0^B = psi_1^B
|psi_0>_AB = (W otimes I) |psi_1>_AB   --> not at all binding
---
Can I have protocol that is eps-hiding, delta-binding, valid?
Bob only can learn eps information, Alice gets caught with prob 1-delta.

need robust version of purification uniqueness:
If psi_A ≈ gamma_A does there exist W s.t. <psi| (I otimes W) |gamma> ≈ 1?

----
norms

function x --> ||x||
||cv|| = |c| ||v|| for scalar c
|| v+w || <= ||v|| + ||w||
separating: ||v||=0 <--> v=0

l_p norms
||x||_{l_p} = (sum_i |x_i|^p)^{1/p}
l_2 = Euclidean
l_1 = Manhattan
l_infty = max_i |x_i|

S_p = Schatten-p norms
||X||_{S_p} = || svals(X) ||_{l_p}
||X||_{S_1} = sum of svals = "trace norm"
||X||_{S_infty} = biggest singular value

pure-state QM: l_2 unit sphere
probabilities: nonnegative vectors in l_1 unit sphere
density matrices: psd matrices in S_1 unit sphere
measurement operators: live in S_infty