在本文中, 我会简要解释 randomness extractor 的定义, 再以有限空间中退随机化的例子来引出 classical-proof (seeded) extractor 的定义, 此后以有限空间量子计算中消除中间测量为例引出 quantum-proof (seeded) extractor 的定义. 最后我会列举一些有代表性的 seeded extractor 构造, 并指出哪些可以证明是 quantum-proof 的.

Extractor 是什么

先解释一下什么是 randomness extractor, 它想做的是从 weak random source 中提取随机比特. 譬如说你手上有若干枚硬币, 它们中一部分有正反面, 但是另一部分正反面相同 (都是正面图案或者反面图案), 尽管你不知道每枚硬币属于哪部分. 尽管如此, 你仍然可以通过看着硬币一边旋转一边落地, 根据落地后硬币的正反面来得到"随机"比特串, 虽然它好像不是完全随机的. 或者你手上有个正二十面体, 不过每一面的重量不尽相同, 你同样可以通过抛掷-落地来得到某种"随机"串.

对于任何 weak random source, 如果你还有少量正常的硬币们辅助的话 (可以证明这在一般情况下是必要的), 那么你可以提取这些 weak random source 中绝大部分随机比特. 形式化一些, 那就是 Ext:{0,1}n×{0,1}d→{0,1}m{\rm Ext}:\{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m, 其中 weak random source XX 对应的概率分布是在 {0,1}n\{0,1\}^n 上的, 而正常的硬币们对应的概率分布是在 {0,1}d\{0,1\}^d 上的, 你最后可以得到的 mm 个随机比特, 即均匀随机分布 UmU_m. 怎么衡量 weak random source XX 的随机性呢? 如果 XX 越难猜, 我们认为它越随机, 所以这里的度量就是 H_\min(X)=-\log \min_{x \sim X}\Pr[X=x], 称作最小熵 (min-entropy). 换而言之, 最小熵刻画的是最小的 guessing probability. 而 extractor 的输出也未必完全是随机比特, 它们很可能只是非常接近随机比特:

定义 1 (extractor). 对于任何满足 H_\min(X) \geq k 的 nn-比特 weak random source, 在 dd-随机比特的帮助下, Extractor Ext:{0,1}n×{0,1}d→{0,1}m{\rm Ext}: \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m 可以做到 $ {\rm Ext}(X,U_d) \approx_{\epsilon} U_m$.

建议不熟悉最小熵定义的读者, 停下来思考一下如何从 guessing probability 的角度理解定义 1.

Quantum-proof extractor 是什么

那什么是 quantum-proof extractor 呢? 字面上理解, quantum-proof 就像 water-proof (即防水) 一样, 说的是 against quantum adversary. 我们先给出一个关于退随机化 (derandomization) 的具体例子 [1], 再给出定义.

考虑需要空间 SS 和时间 TT 的随机算法 A\mathcal{A}, 自然在计算过程中每一步都满足 s0,s1,⋯,sT∈{0,1}Ss_0,s_1,\cdots,s_T \in \{0,1\}^S: 从 sis_i 到 si+1s_{i+1} 我们可以应用简单的逻辑门 gi∈{AND,OR,NOT}g_i\in\{\text{AND}, \text{OR}, \text{NOT}\}; 或者以 1/21/2 概率应用 AND, 再以 1/21/2 概率应用 OR, 如 gi(yi)={gi(0) if yi=0gi(1) if yi=1g_i(y_i)=\begin{cases}g_i^{(0)}~\text{if }y_i=0\\ g_i^{(1)}~\text{if }y_i=1\end{cases}. 并且由于每一步都可以使用随机比特, 所以我们需要 TT 比特随机串 y∼UTy \sim U_T, 即

s0→g1(y1)s1→g2(y2)⋯→gT/2(yT/2)sT/2→gT/2+1(yT/2+1)sT/2+1→gT/2+2(yT/2+2)⋯→gT(yT)sT∈{0,1}S.s_0 \overset{g_1(y_1)}{\rightarrow} s_1 \overset{g_2(y_2)}{\rightarrow} \cdots \overset{g_{T/2}(y_{T/2})}{\rightarrow} s_{T/2}\overset{g_{T/2+1}(y_{T/2+1})}{\rightarrow} s_{T/2+1} \overset{g_{T/2+2}(y_{T/2+2})}{\rightarrow} \cdots \overset{g_T(y_T)}{\rightarrow} s_T\in \{0,1\}^S.

鉴于我们想用更少的随机比特来模拟 A\mathcal{A}, 于是就把上面的计算历史, 以 sT/2s_{T/2} 为界分成两部分, 左边用到的随机串是 y(L):=y1y2⋯yT/2∼UT/2y^{(L)}:=y_1y_2\cdots y_{T/2} \sim U_{T/2}, 右边用到的随机串是 y(R):=yT/2+1yT/2+2⋯yT∼UT/2y^{(R)}:=y_{T/2+1}y_{T/2+2}\cdots y_T\sim U_{T/2}. 怎么用 extractor 呢? 一个办法是重复利用左半边的随机串, 在很短的新随机串 zz 的帮助下, 得到 y(R)≈ϵExt(y(L),z)y^{(R)}\approx_{\epsilon}{\rm Ext}(y^{(L)},z), 然后再保证对应的计算过程 BR(BL(0S,y(L)),y(R))≈ϵBR(BL(0S,y(L)),Ext(y(L),z))B_R\left(B_L(0^S,y^{(L)}),y^{(R)}\right)\approx_{\epsilon}B_R\left(B_L(0^S,y^{(L)}),{\rm Ext}(y^{(L)},z)\right) 成立, 这里新随机串 z∼Utz \sim U_t 并且 t≪Tt \ll T. 用上述过程我们可以把需要的随机比特数从 TT 减少到 T/2+Θ(S)T/2+\Theta(S), 而如果我们递归地作用上述过程 Θ(log⁡n)\Theta(\log n) 次, 那么我们最终只需要 Θ(Slog⁡T)\Theta(S \log T) 个随机比特!

这里唯一的问题是, 伪随机串 Ext(y(L),z){\rm Ext}(y^{(L)},z) 和真随机串 y(R)y^{(R)} 不可区分, 并不能导出对应的计算结果 (即 side information) 也是不可区分的. 所以令 Bi(s,r)B_i(s,r) 表示以 s∈{0,1}Ss\in\{0,1\}^S 为输入, r∼UT/2r\sim U_{T/2} 为所用随机比特串的计算过程 BiB_i 的输出, 我们需要 extractor 保证

y(R)∘BR(BL(0S,y(L)),y(R))≈ϵExt(y(L),z)∘BR(BL(0S,y(L)),Ext(y(L),z)),y^{(R)} \circ B_R\left(B_L(0^S,y^{(L)}),y^{(R)}\right)\approx_{\epsilon} {\rm Ext}(y^{(L)},z) \circ B_R\left(B_L(0^S,y^{(L)}),{\rm Ext}(y^{(L)},z)\right),

上式中 ∘\circ 表示连接两个比特串, 其实就是集合的直积 (Cartesian product). 而这样的 extractor 称作 classical-proof extractor; 并且此时刻画 weak random source 的度量是条件最小熵 H_\min(X|E), 其中 EE 即 side information.

类似地, 我们可以定义 quantum-proof extractor. 在上面的例子中, 就是考虑 SS-量子比特的计算, 但是中间可以用中间测量 (intermediate measurement), 譬如说 M(ρ)=∣0⟩⟨0∣ρ∣0⟩⟨0∣+∣1⟩⟨1∣ρ∣1⟩⟨1∣M(\rho)=|0\rangle\langle 0| \rho |0\rangle\langle 0| + |1\rangle\langle 1| \rho |1\rangle\langle 1|, 即在 {∣0⟩,∣1⟩}\{|0\rangle,|1\rangle\} 基上做投影测量. 有趣的是, M(ρ)M(\rho) 也可以被写作随机比特控制的 unitary channel, 即以 1/2 概率作用 ∣1⟩⟨1∣−∣0⟩⟨0∣|1\rangle\langle 1|-|0\rangle\langle 0|, 或以 1/2 概率作用 II. 于是我们可以用上面退随机化的例子, 来消除有限空间量子计算过程的中间测量[2]. 并且我们需要使用 quantum-proof extractor, 即保证

∣y(R)⟩⟨y(R)∣⊗BR(BL(∣0S⟩,y(L)),y(R))≈ϵ∣Ext(y(L),z)⟩⟨Ext(y(L),z)∣⊗BR(BL(∣0S⟩,y(L)),Ext(y(L),z)),|y^{(R)}\rangle\langle y^{(R)}| \otimes \mathcal{B}_R\left(\mathcal{B}_L(|0^S\rangle,y^{(L)}),y^{(R)}\right)\approx_{\epsilon} |{\rm Ext}(y^{(L)},z)\rangle\langle {\rm Ext}(y^{(L)},z)| \otimes \mathcal{B}_R\left(\mathcal{B}_L(|0^S\rangle,y^{(L)}),{\rm Ext}(y^{(L)},z)\right),

这里 BL(⋅)\mathcal{B}_L(\cdot) 和 BR(⋅)\mathcal{B}_R(\cdot) 是给定输入态和 (伪) 随机比特串后对应量子线路的输出态, 也是这里的 quantum side information.

到此为止, 我们简单讨论了 seeded (weak) extractor, 以及它的 classical-proof 和 quantum-proof 变种. 而市面上常见的 seeded extractor 介绍都会提到的例子是 privacy amplification, 这里需要 strong extractor 的不可区分性满足 Ext(X,Ud)∘Ud≈ϵUm∘Ud{\rm Ext}(X,U_d)\circ U_d \approx_{\epsilon} U_m\circ U_d (注意观察和定义 1 中的区别).

我们可以构造哪些 extractor

下面我们就可以讨论已知的 (quantum-proof) seeded extractor 的构造了. 我们通常希望做到 seed length d=O(log⁡/ϵ)d=O(\log/\epsilon), 而 output length m=k−Ω(log⁡1/ϵ)m=k-\Omega(\log 1/\epsilon), 其中误差会造成不可避免的 entropy loss log⁡1/ϵ\log 1/\epsilon.

尽管 seeded extractor 的概念是由 Nisan 和 Zuckerman 在 1996 年提出 [3], 但是 Impagliazzo, Levin, Luby 早在 1989 年证明的 leftover hash lemma[4] 已经给出了非平凡构造, 即 pairwise-independent hash function family H=h:{0,1}n→{0,1}k−2t\mathcal{H}={h:\{0,1\}^n \rightarrow \{0,1\}^{k-2t}} 对应于 strong extractor Ext(X,h)=h(X){\rm Ext}(X,h)=h(X), 此时 output length m=k−Ω(log⁡1/ϵ)m=k-\Omega(\log 1/\epsilon), 但 seed length 是 d=O(n)d=O(n). 尽管如此, 由于 leftover hash lemma 的 entropy loss 是最优的, 因而可以通过与其他构造组合得到 seed length 更短的构造. 譬如 Zuckerman 在 1997 年[5] 给出 seed length d=O(log⁡n)d=O(\log n), output length m=Ω(k)m=\Omega(k) 的构造, 不过此时需要输入满足 high-entropy k=Ω(n)k=\Omega(n).

而 Guruswami, Umas, Vadhan (2009) 终于给出了参数最优的 seeded extractor 的构造[6]. 此外值得一提的是 Luca Trevisan 在 1999 年的工作[7], 他先用 list-decodable error-correction codes 给出了 seed length O(log⁡n)O(\log n) 的 single output-bit strong extractor 的构造. 又用 Nisan-Wigderson 的 pseudorandom generator 给出了一般性规约, 进而给出构造使得 seed length O(log⁡2n/log⁡k)O(\log^2 n/\log k) 且 output length m=k1−k/nm=k^{1-k/n}.

那我们可以证明哪些 seeded extractor 是 quantum proof 的呢?

  • Tomamichel, Schaffner, Smith, Renner 在 2011 年证明[8] 了基于 leftover hash lemma (或者说 almost pairwise independence) 的构造是 quantum-proof 的.
  • König 和 Terhal 在 2008 年证明[9] 了任何 single output-bit strong extractor 都是 quantum-proof 的.
  • De, Portmann, Vidick, Renner 在 2012 年证明[10] 了 Trevisan’s extractor 是 quantum-proof 的.
  • Chung, Cohen, Vidick, Wu 在 2016 年一度声称证明[11] 了 Zuckerman (1997) 是 quantum-proof 的, 不过几个月后撤稿.

上述 quantum-proof 证明得到的 seed length 和 output length 和原有构造基本一致. Gavinsky, Kempe, Kerenidis, Raz 和 de Wolf 找到了反例 [12], 证明了在某些参数范围下, classical extractor 不是 quantum-proof 的.

最近的进展则是 Berta, Fawzi, Scholz 在 2015 年的工作 [13], 他们用算子代数 (和线性代数) 给出了 seeded extractor 和 quantum-proof seeded extractor 的 completely-bounded norm 描述, 进而用它的 SDP relaxation 证明了 extractor 产生的概率分布和均匀分布间距离的上界 O(2m/2ϵ)O(2^{m/2}\epsilon) 和 O(2n−kϵ)O(2^{n-k} \epsilon), 前者的输出很短 (特例是 [9:1]), 后者有 high-entropy 输入 (特例是 [10:1]).

在本文中, 笔者并未涉及 two-source extractor, 即第二个 source 不一定是 seed, 或者说均匀分布, 以及更一般的 multi-source extractor. 值得一提的是它们的 quantum-proof 版本从定义开始已经有了一些困难, 另外也并没有太多的已知应用, 不但进展寥寥, 而且关注度也非常有限.

参考文献

  1. Impagliazzo, Russell, Noam Nisan, and Avi Wigderson. “Pseudorandomness for network algorithms.” In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 356-364. 1994. ↩︎

  2. Girish, Uma, and Ran Raz. “Eliminating Intermediate Measurements Using Pseudorandom Generators.” In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. ↩︎

  3. Nisan, Noam, and David Zuckerman. “Randomness is linear in space.” Journal of Computer and System Sciences 52, no. 1 (1996): 43-52. ↩︎

  4. Impagliazzo, Russell, Leonid A. Levin, and Michael Luby. “Pseudo-random generation from one-way functions.” In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 12-24. 1989. ↩︎

  5. Zuckerman, David. “Randomness‐optimal oblivious sampling.” Random Structures & Algorithms 11, no. 4 (1997): 345-367. ↩︎

  6. Guruswami, Venkatesan, Christopher Umans, and Salil Vadhan. “Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes.” *Journal of the ACM (JACM)*56, no. 4 (2009): 1-34. ↩︎

  7. Trevisan, Luca. “Extractors and pseudorandom generators.” Journal of the ACM 48, no. 4 (2001): 860-879. ↩︎

  8. Konig, Robert T., and Barbara M. Terhal. “The bounded-storage model in the presence of a quantum adversary.” IEEE Transactions on Information Theory 54, no. 2 (2008): 749-762. ↩︎

  9. Konig, Robert T., and Barbara M. Terhal. “The bounded-storage model in the presence of a quantum adversary.” IEEE Transactions on Information Theory 54, no. 2 (2008): 749-762. ↩︎ ↩︎

  10. De, Anindya, Christopher Portmann, Thomas Vidick, and Renato Renner. “Trevisan’s extractor in the presence of quantum side information.” SIAM Journal on Computing 41, no. 4 (2012): 915-940. ↩︎ ↩︎

  11. Chung, Kai-Min, Gil Cohen, Thomas Vidick, and Xiaodi Wu. “Quantum-Proof Extractors: Optimal up to Constant Factors.” arXiv (2016). ↩︎

  12. Gavinsky, Dmitry, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald De Wolf. “Exponential separations for one-way quantum communication complexity, with applications to cryptography.” In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 516-525. 2007. ↩︎

  13. Berta, Mario, Omar Fawzi, and Volkher B. Scholz. “Quantum-proof randomness extractors via operator space theory.” IEEE Transactions on Information Theory 63, no. 4 (2016): 2480-2503. ↩︎