CS170 Efficient Algorithms and Intractable Problems HW14

课程主页：

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)

$$\begin{aligned} \alpha_0 \beta_0 &=\frac 1 {\sqrt 2}\\ \alpha_0 \beta_1 &=0\\ \alpha_1 \beta_0 &=0\\ \alpha_1 \beta_1 &=\frac 1 {\sqrt 2}\\ \end{aligned}$$

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

(b)

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

$$|\psi\rangle=|00\rangle$$

否则为

$$|\psi\rangle=|11\rangle$$

(c)

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

(d)

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

4. Quantum Gates

(a)

$$\begin{aligned} \frac{1}{\sqrt{2}}\left[\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}\right] \left[\begin{array}{cc} 1\\ 0 \end{array}\right]&=\left[\begin{array}{cc} \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} \end{array}\right]\\ \frac{1}{\sqrt{2}}\left[\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}\right] \left[\begin{array}{cc} 0\\ 1 \end{array}\right]&=\left[\begin{array}{cc} \frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}} \end{array}\right] \end{aligned}$$

注意到

$$\left|\frac 1 {\sqrt 2 }\right|^2=\frac 12$$

所以等概率。

(b)

注意到

$$\begin{aligned} \left[\begin{array}{cc} 0& 1 \\ 1 & 0 \end{array}\right] \left[\begin{array}{cc} 1\\ 0 \end{array}\right]&=\left[\begin{array}{cc} 0\\ 1 \end{array}\right]\\ \left[\begin{array}{cc} 0& 1 \\ 1 & 0 \end{array}\right] \left[\begin{array}{cc} 0\\ 1 \end{array}\right]&=\left[\begin{array}{cc} 1\\ 0 \end{array}\right] \end{aligned}$$

所以矩阵为

$$\left[\begin{array}{cc} 0& 1 \\ 1 & 0 \end{array}\right]$$

(c)

矩阵为

$$\left[\begin{array}{cc} 1& 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 &0 & 0 & 1 \end{array}\right]$$

5. Multiplicative Weights

(a)

$$\begin{aligned} f(\epsilon) &=10000(1+\epsilon) + \frac{\ln 2}{\epsilon}\\ &= 10000+ 10000\epsilon + \frac{\ln 2}{\epsilon}\\ &\ge 10000+ 2\times 100 \times \sqrt{\ln 2} \end{aligned}$$

等号成立当且仅当

$$\epsilon =\frac{\sqrt{\ln 2}}{100}$$

(b)

选择$1$的概率为

$$\begin{aligned} \frac{1}{1 + (1-0.01)^{140}} &\approx\frac{1}{ 1 +\frac 1 2 \times \frac 1 2}\\ &=\frac{4}{5} \end{aligned}$$

6. Experts Alternatives

参考资料：

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

对原始公式进行改造

$$R=\frac{1}{T}\left(\sum_{t=1}^{T}\sum_{i=1}^n p_i^tc_{i}^{t}-\min _{1 \leq i \leq n} \sum_{t=1}^{T} c_{i}^{t}\right)$$

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

(a)

此时

$$\begin{aligned} p_1^t &= 1\\ p_i^t &=0, i\neq 1 \end{aligned}$$

那么

$$R=\frac{1}{T}\left(\sum_{t=1}^{T}c_{1}^{t}-\min _{1 \leq i \leq n} \sum_{t=1}^{T} c_{i}^{t}\right)\le \frac 1 T\sum_{t=1}^{T} 1 =1$$

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

$$c_1^t=1, c_i^t =0,i\neq 1$$

(b)

此时

$$\forall t ,\exists i, p_{i}^{t}=1$$

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

$$R=\frac{1}{T}\left(\sum_{t=1}^{T} c_{t(i)}^{t}-\min _{1 \leq i \leq n} \sum_{t=1}^{T} c_{i}^{t}\right)$$

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

$$C= \left[\begin{array}{cc} c^t_i \end{array}\right]_{T\times n}$$

那么$\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_j^t=0,t=1,\ldots, T$$

可得

$$R= \frac{1}{T}\left(\sum_{t=1}^{T} c_{t(i)}^{t}\right) \le 1$$

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

$$\{t(1),\ldots, t(n)\}=\{1,\ldots, n\}$$

假设

$$t(a_i) = i,i=1,\ldots, n$$

那么

$$\sum_{t=1}^{T} c_{a(i)}^{t} \ge c^t_{t(a_i)} = c^t_i$$

从而

$$\min _{1 \leq i \leq n} \sum_{t=1}^{T} c_{i}^{t} \ge \min _{1 \leq i \leq n} c^t_i =\min _{1 \leq i \leq n}c_{t(i)}^{t}$$

因此

$$\begin{aligned} R &=\frac{1}{T}\left(\sum_{t=1}^{T} c_{t(i)}^{t}-\min _{1 \leq i \leq n} \sum_{t=1}^{T} c_{i}^{t}\right)\\ &\le \frac{1}{T}\left(\sum_{t=1}^{T} c_{t(i)}^{t}-\min _{1 \leq i \leq n}c_{t(i)}^{t}\right)\\ &\le \frac{T-1}{T} \end{aligned}$$

(c)

此时

$$\begin{aligned} \mathbb E[R] &=\frac{1}{T}\left(\sum_{t=1}^{T}\sum_{i=1}^n p_ic_{i}^{t}-\min _{1 \leq i \leq n} \sum_{t=1}^{T} c_{i}^{t}\right)\\ &=\frac{1}{T}\left(\sum_{i=1}^n p_i\sum_{t=1}^{T}c_{i}^{t}-\min _{1 \leq i \leq n} \sum_{t=1}^{T} c_{i}^{t}\right)\\ &= \max _{1 \leq j \leq n} \frac{1}{T}\left(\sum_{i=1}^n p_i\sum_{t=1}^{T}c_{i}^{t}-\sum_{t=1}^{T} c_{j}^{t}\right)\\ &=\max _{1 \leq j \leq n} \frac{1}{T}\left(\sum_{i\neq j} p_i\sum_{t=1}^{T}c_{i}^{t}-(1-p_j)\sum_{t=1}^{T} c_{j}^{t}\right) \end{aligned}$$

对于第一项，

$$\sum_{i\neq j} p_i\sum_{t=1}^{T}c_{i}^{t} \le T\sum_{i\neq j} p_i = T(1-p_j)$$

对于第二项，

$$-(1-p_j)\sum_{t=1}^{T} c_{j}^{t} \le 0$$

所以

$$\begin{aligned} \mathbb E[R] &=\max _{1 \leq j \leq n} \frac{1}{T}\left(\sum_{i\neq j} p_i\sum_{t=1}^{T}c_{i}^{t}-(1-p_j)\sum_{t=1}^{T} c_{j}^{t}\right)\\ &\le \max _{1 \leq j \leq n}\frac 1 T \left(T(1-p_j)\right)\\ &=\max _{1 \leq j \leq n}( 1- p_j)\\ &=1 -\min _{1 \leq j \leq n} p_j\\ &\le 1 \end{aligned}$$