Source: https://rareskills.io/zh-cn/post/quadratic-arithmetic-program
二次算术程序（Quadratic Arithmetic Program）是一种 算术电路 ，具体来说是将 秩 1 约束系统 （R1CS）表示为一组多项式。它是在秩 1 约束系统上使用拉格朗日插值推导出来的。与 R1CS 不同，二次算术程序（QAP）可以通过 Schwartz-Zippel 引理在 $\mathcal{O}(1)$ 时间内进行相等性测试。
在关于 Schwartz-Zippel 引理的章节中，我们看到可以通过将两个向量转换为多项式，然后对多项式运行 Schwartz-Zippel 引理测试，从而在 $\mathcal{O}(1)$ 时间内测试它们是否相等。（需要澄清的是， 测试 本身是 $\mathcal{O}(1)$ 时间的，而将向量转换为多项式会产生额外的开销）。
因为秩 1 约束系统完全由向量运算组成，我们的目标是测试
$\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}\stackrel{?}{=}\mathbf{O}\mathbf{a}$
是否在 $\mathcal{O}(1)$ 时间而不是 $\mathcal{O}(n)$ 时间内成立（其中 $n$ 是 $\mathbf{L}$ 、 $\mathbf{R}$ 和 $\mathbf{O}$ 中的行数）。
<aside> 💡 💡 一句话理解目标：R1CS 本质就是检查三组向量是否满足 $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}$。如果向量有 100 万行，逐行核对就要比较 100 万次（这就是 $\mathcal{O}(n)$）。QAP 的野心是把这 100 万次比较压缩成只查 1 次（$\mathcal{O}(1)$）。打个比方：与其逐页核对两本一百万页的账本是否完全一样，不如给每本账本算一个『指纹』，只对比一次指纹。
</aside>
但在此之前，我们需要了解表示向量的多项式与向量之间关系的一些关键属性。
对于这里的所有数学运算，我们假设我们在 有限域 中进行，但为了简洁起见，我们省略了 $\mod p$ 符号。
如果我们取两个向量，用多项式对它们进行插值，然后将这些多项式相加，我们得到的多项式，与我们将向量相加然后再对求和后的向量进行插值得到的多项式是相同的。
用更数学化的语言来说，令 $\mathcal{L}(\mathbf{v})$ 为对向量 $\mathbf{v}$ 使用 $(1, 2, ..., n)$ 作为 $x$ 值进行拉格朗日插值所得到的多项式，其中 $n$ 是 $\mathbf{v}$ 的长度。以下等式成立：
$\mathcal{L}(\mathbf{v} + \mathbf{w}) = \mathcal{L}(\mathbf{v}) + \mathcal{L}(\mathbf{w})$
换句话说，对向量 $\mathbf{v}$ 和 $\mathbf{w}$ 进行插值后得到的多项式之和，与对向量 $\mathbf{v} + \mathbf{w}$ 进行插值得到的多项式是相同的。
<aside> 💡 💡 打个比方：把『向量』想象成一串散落的数据点，『插值成多项式』就是把这些点连成一条平滑曲线。这个等式是说——先把两组数据逐项相加、再连成一条曲线，和分别把两组数据各连成一条曲线、再把两条曲线加起来，得到的是同一条曲线。顺序无所谓、结果一样，这种『运算能穿过转换』的性质就叫同态。例如 $[1,4,9]$ 连出 $x^2$，$[1,8,27]$ 连出 $x^3$；逐项相加得 $[2,12,36]$，连出来正好是 $x^2+x^3$。
</aside>
令 $f_1(x) = x^2$ 且 $f_2(x) = x^3$ ， $f_1$ 插值 $(1, 1), (2, 4), (3, 9)$ 或向量 $[1,4,9]$ ， $f_2$ 插值 $[1,8,27]$ 。
向量之和为 $[2,12,36]$ ，很明显 $x^3 + x^2$ 对其进行了插值。令 $f_3(x) = f_1(x) + f_2(x) = x^3 + x^2$ 。