课程主页:

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频:

https://www.bilibili.com/video/BV1wK411g7ck

参考资料:

https://blogs.asarkar.com/assets/docs/algorithms-curated/Maximum%20Independent%20Set%20Problem%20-%20Chekuri.pdf

https://cs170.org/assets/pdf/dis10-sol.pdf

这次回顾HW14。

3. Entanglement

(a)

等式$1,4$说明$\alpha_i,\beta_j$都不为$0$,这与等式$2,3$相矛盾。

(b)

如果第一个量子位元为$0$,则

否则为

(c)

如果第一个量子位元为$0$,则第二个量子位元为$0$;如果第一个量子位元为$1$,则第二个量子位元为$1$。

(d)

说明可以将第一个量子位元的状态传递到第二个量子位元。

4. Quantum Gates

(a)

注意到

所以等概率。

(b)

注意到

所以矩阵为

(c)

矩阵为

5. Multiplicative Weights

(a)

等号成立当且仅当

(b)

选择$1$的概率为

6. Experts Alternatives

参考资料:

https://cs170.org/assets/pdf/dis10-sol.pdf

对原始公式进行改造

其中$p_i^t$表示在时间$t$选择$i$的概率。

(a)

此时

那么

在如下条件满足时等号成立

(b)

此时

不妨设$t$时刻选择$t(i)$,那么

将$t$视为行号,$i$视为列号,考虑矩阵

那么$\sum_{t=1}^{T} c_{t(i)}^{t}$表示从每一行中挑选一项得到的和,$\sum_{t=1}^{T} c_{i}^{t}$表示第$i$列的和。

如果存在$i\neq j$,满足$t(i)=t(j)$,那么必然存在一列,其所有元素均不包含在第一项中,不妨设为$j$,那么此时取

可得

否则,每列都存在元素包含在第一项中,即

假设

那么

从而

因此

(c)

此时

对于第一项,

对于第二项,

所以