【引入】

计算不可区分性，是基于概率多项式时间算法来定义的，即如果不存在任何 PPT 区分器能够有效区分两个概率系综，就称它们是计算不可区分的。

考虑一个更强的不可区分性概念：多项式规模电路意义下的不可区分性（Indistinguishability by Polynomial-Size Circuits）。其不只考虑统一的多项式时间算法，而是允许对每个输入长度 $n$，都有一个专门设计的电路 $C_n$ 作为区分器。

具体来说，PPT 算法是均匀的，它必须由一个统一的算法描述，并且能够处理所有输入长度；而电路族是非均匀的，它允许每个输入长度 $n$ 都有一个单独设计的电路 $C_n$。

也就是说：

PPT 区分器：一个通用程序，输入任意长度样本后尝试区分
电路族区分器：每个长度 $n$ 都有一个专门的区分电路 $C_n$

因此，电路族模型可能比 PPT 模型更强，因为它允许针对每个长度提前硬编码一些信息，而这些信息未必能由统一算法高效生成。

所以，如果两个概率系综连所有多项式规模电路族都无法区分，那么它们当然也无法被 PPT 算法区分。

【多项式规模电路族】

一个电路族 $\{C_n\}_{n\in\mathbb N}$ 是指对每个输入长度 $n$，都有一个对应的布尔电路 $C_n$。其中，$C_n$ 只处理长度为 $n$ 的输入，输出一个比特 $0$ 或 $1$。

如果 $C_n$ 的规模被某个多项式 $\mathrm{poly}’(n)$ 上界控制，即：

$|C_n|\leq \mathrm{poly}'(n)$

则称 $\{C_n\}_{n\in\mathbb N}$ 是一个多项式规模电路族（Polynomial-Size Circuit Family）。其中的规模，通常指电路中门的数量。

【多项式规模电路的不可区分性】

自然数索引形式

设两个概率系综分别为 $X=\{X_n\}_{n\in\mathbb N}$ 和 $Y=\{Y_n\}_{n\in\mathbb N}$，如果对于任意多项式规模电路族 $\{C_n\}_{n\in\mathbb N}$，任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有：

$\left| P[C_n(X_n)=1] - P[C_n(Y_n)=1] \right| < \frac{1}{\mathrm{poly}(n)}$

则称 $X$ 和 $Y$ 是多项式规模电路意义下不可区分的（Indistinguishable by Polynomial-Size Circuits）。

直观来看，这个定义的含义是：即使允许每个长度 $n$ 都有一个专门设计的多项式规模电路 $C_n$，该电路仍然无法以不可忽略的优势区分 $X_n$ 和 $Y_n$。

字符串索引形式

弱形式

设 $S$ 是一个字符串集合，两个概率系综分别为 $X=\{X_w\}_{w\in S}$ 和 $Y=\{Y_w\}_{w\in S}$，如果对于任意多项式规模电路族 $\{C_n\}_{n\in\mathbb N}$，任意正多项式 $\mathrm{poly}(\cdot)$，以及所有长度充分大的 $w\in S$，都有：

$\left| P[C_{|w|}(X_w)=1] - P[C_{|w|}(Y_w)=1] \right| < \frac{1}{\mathrm{poly}(|w|)}$

则称 $X$ 和 $Y$ 是多项式规模电路意义下不可区分的。

这里电路使用的是 $C_{|w|}$，电路只依赖于索引字符串 $w$ 的长度 $|w|$，而不是依赖于具体的 $w$。

强形式

对于上述由字符串索引定义的不可区分性，还可以提出一个更强的条件，即不再只允许电路依赖于长度 $|w|$，而是允许每个具体的字符串 $w$ 都有一个专门电路 $C_w$。

形式上，要求对于任意多项式 $\mathrm{poly}’(\cdot)$、任意满足 $|C_w|\leq \mathrm{poly}’(|w|)$ 的电路集合 $\{C_w\}_{w\in S}$，任意正多项式 $\mathrm{poly}(\cdot)$，以及所有长度充分大的 $w\in S$，都有：

$\left| P[C_w(X_w)=1] - P[C_w(Y_w)=1] \right| < \frac{1}{\mathrm{poly}(|w|)}$

这个条件看起来更强，因为它允许电路不仅依赖输入长度，还可以依赖具体索引 $w$。

也就是说，原定义中，所有长度相同的 $w$ 共用同一个电路 $C_{|w|}$，而新条件中，每个具体的 $w$ 都可以有自己的电路 $C_w$。

等价性

强形式相比于弱形式有一个更强的条件，但实际上两种定义形式是等价的。

假设存在某些多项式 $\mathrm{poly}’(\cdot)$ 和 $\mathrm{poly}(\cdot)$，以及无穷多个字符串 $w$，使得：

$\left| P[C_w(X_w)=1] - P[C_w(Y_w)=1] \right| \geq \frac{1}{\mathrm{poly}(|w|)}$

也就是说，针对这些 $w$，存在电路 $C_w$ 能够明显区分 $X_w$ 和 $Y_w$。

由于这样的 $w$ 有无穷多个，所以可以找到一个无限的长度集合 $N$，使得对于每个 $n\in N$，都存在某个长度为 $n$ 的字符串 $w_n\in\{0,1\}^n$ 违反上述条件。也就是说，对于每个 $n\in N$，都有一个具体字符串 $w_n$，以及对应电路 $C_{w_n}$，能够明显区分 $X_{w_n}$ 和 $Y_{w_n}$。

现在定义一个新的电路族 $C’_n\overset{\mathrm{def}}{=}C_{w_n}$，由于 $C_{w_n}$ 的规模至多为：

$\mathrm{poly}'(|w_n|)=\mathrm{poly}'(n)$

所以 $\{C’_n\}$ 是一个多项式规模电路族。

但这个电路族 $C’_n$ 对无穷多个 $n$ 都能明显区分对应的 $X_{w_n}$ 和 $Y_{w_n}$，从而违反弱形式的定义。

因此，如果弱形式的定义成立，那么这个强形式的定义也必须成立，这说明二者等价。

【概率电路的去随机化】

在上述定义中，即使允许电路是概率电路，也不会增强区分能力。也就是说，允许电路内部随机性、使用算法随机选择，并不会使它比确定性电路族更强。

这是因为，如果一个概率电路能够以某个不可忽略优势区分 $X_n$ 和 $Y_n$，那么它的区分优势是对内部随机性的平均结果。既然平均区分优势不可忽略，就必然存在某一种固定随机选择，使得对应的确定性电路也能够达到至少同样的区分效果。

因此，可以把这组内部随机性固定下来，将概率电路转化为确定性电路。

所以，在多项式规模电路意义下，考虑确定性电路族已经足够。

【重复实验的保持性】

多项式规模电路意义下的不可区分性在重复实验下仍然保持，而且这一次不需要假设两个概率系综是多项式时间可构造的。

也就是说，如果 $X$ 和 $Y$ 在多项式规模电路意义下不可区分，那么即使区分器拿到多项式多个独立样本，也仍然无法区分它们。

在 PPT 情形下，为了证明重复采样下仍然不可区分，需要假设 $X$ 和 $Y$ 都是多项式时间可构造的，而在电路模型中，电路族是非均匀的，可以把某些辅助信息硬编码进电路中，因此重复实验下的保持性可以在不要求分布可高效构造的情况下成立。

Alex_McAvoy

多项式规模电路的计算不可区分性