8.3.1 传统机器学习问题的量子化
8.3.1.1 精确学习
在这个问题设置下，我们假设学习的目标是一个布尔函数，即要从一个已知的函数集合𝒞 （称作概念类）中学习某个未知的𝑐 ∶
{0,1}𝑛 → {0,1}。如同精确学习所表示的那样，在给定成员查询
（Membership Query）下，即当我们向系统查询𝑥时会得到𝑐(𝑥)，我们的目标是以大概率精确地确定𝑐。一般地来说，当衡量算法复杂度的方式是对系统的查询次数时，量子算法对比经典算法会有多项式时间的加速；而当衡量算法复杂度的方式是时间复杂度时，在合理的复杂
性假设下，对某些学习目标量子算法可以比经典算法指数级别地快。在经典精确学习模型下，给定成员查询𝑀𝑄(𝑐)，在查询𝑥时，
𝑀𝑄(𝑐)返回对应的标签𝑐(𝑥)。称𝒜是一个对概念类𝒞的学习者，若对任意的𝑐 ∈ 𝒞，给定𝑐对应的成员查询𝑀𝑄(𝑐)，以至少2/3的概率𝒜输出ℎ，满足ℎ(𝑥) = 𝑐(𝑥)对任意的𝑥 ∈ {0, 1}𝑛成立。这个模型也被称作谕示机确认（Oracle Identification），因为可以把概念类𝒞看作是一组谕示机的集合，而学习的目标就是在给定某个概念类中喻示机时，确定给定的谕示机是这个概念类𝒞中的哪一个。
学习者𝒜的查询复杂度是指对所有𝑐 ∈ 𝒞和所有𝒜内部的随机比特串中，学习算法需要的对成员查询𝑀𝑄(𝑐)的最多的查询次数。而对一个概念类𝒞精确学习的查询复杂度是指所有对概念类𝒞的学习者𝒜中需要的最少的查询复杂度。除此之外，由于每个概念𝑐 ∶ {0, 1}𝑛 →
{0, 1}都可以由其真值表，一个长度为𝑁 = 2𝑛的比特串唯一确定。给定正整数𝑁和𝑀，我们定义(𝑁, 𝑀)- 查询复杂度为所有概念类𝒞 ⊆
{0, 1}𝑁和|𝒞| = 𝑀中具有最大查询复杂度的概念类对应的查询复杂度。而在量子的场景下，我们允许学习者使用量子算法，并且对应访
问的成员查询从𝑀𝑄(𝑐)变为对应的量子版本𝑄𝑀𝑄(𝑐)：这个喻示机执行线性可逆变换|𝑥, 𝑏⟩ ↦ |𝑥, 𝑏 ⊕ 𝑐(𝑥)⟩。对于给定的概念类𝒞，正整数
𝑁、𝑀，我们也可以类似地定义精确学习𝒞的量子查询复杂度和(𝑁, 𝑀)-
量子查询复杂度。
为了刻画精确学习概念类𝒞的查询复杂度和量子查询复杂度，我们首先需要介绍一个由概念类𝒞决定的组合参数𝛾(𝒞)：
|{𝑐 ∈ 𝒞′ ∶ 𝑐𝑖 = 𝑏}|
𝛾(𝒞) = min max min
𝒞′⊆𝒞,|𝒞′|≥2 𝑖∈[𝑁] 𝑏∈{0,1}
|𝒞′|
这个看起来很复杂的定义事实上由这个学习程序所启发：如果学习者想要精确地从𝒞中确定𝑐，它可以每次贪心地查询真值表中最有价
值的一位𝑖 ∈ [𝑁]，即这一位可以在最坏情况下尽可能多地从目前已经确定𝑐所在的概念类子集𝒞′中去除一部分，从而缩小𝒞′并最终确定
𝑐。不难看出这个经典算法的查询复杂度是𝑂(log|𝒞| /𝛾(𝒞))。于是对任意概念类𝒞，其精确学习的查询复杂度一个上界是𝑂(log|𝒞| /𝛾(𝒞))。 2004 年，Servedio 等人在Bshouty 工作的基础上[78, 79]证明了对
于任意的概念类𝒞 ， 精确学习的查询复杂度至少为Ω(max{1/
𝛾(𝒞), log|𝒞|})。综上所述，对于精确学习某个概念类的经典查询复杂度我们得到了较紧的上下界。
2004 年，Servedio 等人[78]证明了对于任意的概念类𝒞，精确学习的量子查询复杂度至少为Ω (max{1/√𝛾(𝒞), log|𝒞| /𝑛})。一些例子表明这个下界是最优的。除此之外，2013 年，Kotthari [80]在 Servedio和Atici 等人工作[78, 81]的基础上解决了Hunziker 在 2010 年提出的一个猜想[82]，证明了精确学习概念类𝒞的量子查询复杂度一个上界是
𝑂 (√
1/𝛾(𝒞)
log|𝒞|)
log(1/𝛾(𝒞))
综上所述，我们知道量子对精确学习某个概念类这个问题上至多有多项式级别加速。更精确地，对于某个概念类𝒞，定义其精确学习的经典和量子查询复杂度分别为𝐷(𝒞)和𝑄(𝒞)，更进一步，Servedio 等人在[78]中还证明了一个推论𝐷(𝒞) = 𝑂(𝑛𝑄(𝒞)3)。
接下来关注(𝑁, 𝑀)-查询复杂度和量子查询复杂度之间的关系。经典学习理论中的一个公认的结果是(𝑁, 𝑀) - 查询复杂度是 Θ(min{𝑁, 𝑀})。至于量子的情况，在Alon 等人、Ambainis 等人和Iwama等人工作[83-85]的基础上，Kothari 在 2013 年[80]证明了(𝑁, 𝑀)-量子查询复杂度分为两类， 当𝑀 ≤ 𝑁 时是Θ(√𝑀)，而当𝑁 < 𝑀 ≤ 2𝑁 时是 Θ(√𝑁 log 𝑀 /(log(𝑁/ log 𝑀) + 1))。这说明在考虑固定参数情况下的最坏采样复杂度时，量子比经典有多项式级别的加速。
8.3.1.2 概率近似正确学习
在上面精确学习的场景里，我们可以根据自己的需要对不同样本点对应的标签进行查询，在这样非常可控的查询能力下，在查询次数足够多时总是能确定目标函数。在 PAC 学习中我们关心另一个更贴近现实的场景，在这里我们无法完全控制获得的标签对应的样本点，而只能保证每个数据都是从某个未知的分布中独立采样得到的。
在现实的场景中，通常我们收集数据，而后再对数据进行处理和学习，在大部分情况下我们无法根据学习算法的需要对数据集进行补充，只能根据已经采集到的数据尽可能地逼近目标函数。因此相较于精确学习，PAC 学习模型更能抓住这种场景的关键，从而更具有研究价值，受到研究者的广泛关注。
在经典 PAC 学习模型下，学习算法𝒜能够访问一个能够查询一个随机采样的喻示机𝑃𝐸𝑋(𝑐, 𝐷)，其中𝑐 ∈ 𝒞是要学习的目标概念，而
𝐷是一个{0,1}𝑛上的未知概率分布。每当学习算法从𝑃𝐸𝑋(𝑐, 𝐷)中查询时，喻示机会根据𝐷产生一个样本𝑥，并返回(𝑥, 𝑐(𝑥))。在这样的背景下，我们称学习算法𝒜是一个对概念类𝒞的(𝜖, 𝛿)-PAC 学习者，若对任意的概念𝑐 ∈ 𝒞和概率分布𝐷，学习算法𝒜在给定喻示机𝑃𝐸𝑋(𝑐, 𝐷)的情况下能够以至少1 − 𝛿 的概率输出一个函数ℎ ，满足Pr[ℎ(𝑥) ≠
𝑐(𝑥)] ≤ 𝜖，其中𝑥服从概率分布𝐷。此外，由于学习算法输出的函数ℎ不一定是目标概念𝑐本身，因此也不一定落在概念类𝒞中。如果学习算法输出的函数ℎ总是落在概念类𝒞中，则称这个学习算法是适当的。
学习算法𝒜的采样复杂度定义为其在任意目标概念𝑐 ∈ 𝒞、任意概率分布𝐷以及一切算法本身随机性下需要访问𝑃𝐸𝑋(𝑐, 𝐷)的最大次数。除此之外，我们定义一个概念类𝒞的(𝜖, 𝛿)-PAC 采样复杂度是所有概念类𝒞的(𝜖, 𝛿)-PAC 学习者的最小的采样复杂度。
量子 PAC 学习模型由 Bshouty 和 Jackson 在 1995 年定义[86]。在这个模型下，除了学习者可以使用量子算法外，其访问的喻示机也由
经典情况的𝑃𝐸𝑋(𝑐, 𝐷)变为对应的量子情况𝑄𝑃𝐸𝑋(𝑐, 𝐷)。每当算法访问这个喻示机，其就会恢复一个量子态
∑ √𝐷(𝑥)|𝑥, 𝑐(𝑥)⟩
𝑥∈{0,1}𝑛
这样的一个量子态是前面对经典情况的一个自然的量子拓展。很多量子过程可以产生这样的量子态，考虑在给定一些这样的量子态的情况下进行学习的模型是有意义的。一个量子 PAC 学习算法可以访问一些上述量子态的复制，在其上进行测量并返回结果。
在量子情况下，量子学习算法的采样复杂度就定义为在任意目标概念𝑐 ∈ 𝒞、任意概率分布𝐷以及一切算法本身随机性需要的最多的上述量子态的数量。与经典的情况类似，我们定义概念类𝒞的(𝜖, 𝛿)-量子 PAC 采样复杂度是所有概念类𝒞的(𝜖, 𝛿)-量子 PAC 学习者的最小的采样复杂度。
与 PAC 学习有密切联系的组合参数是 Vapnik 和Chervonenkis [87]引入的 VC 维。对一个概念类𝒞，称集合𝑆 = {𝑠1, … , 𝑠𝑡}被打乱，当且仅当{(𝑐(𝑠1), … , 𝑐(𝑠𝑡)) ∶ 𝑐 ∈ 𝒞} = {0, 1}𝑛。概念类𝒞的 VC 维就定义为能被打乱的最大集合的大小。接下来用字母𝑑表示概念类的 VC 维。 Blumer 等人在 1989 年[88]证明了概念类𝒞的(𝜖, 𝛿)-PAC 采样复杂度的
一个下界是
1
Ω (𝑑/𝜖 + log (𝛿) /𝜖)
2016 年，Hanneke[89]在 Simon 2015 年工作[90]的基础上证明了这
个下界是最优的，有了这些结论，我们就得到了概念类𝒞的 PAC 采样复杂度与其 VC 维的紧的关系，即其的(𝜖, 𝛿)-PAC 采样复杂度是
1
Θ (𝑑/𝜖 + log (𝛿) /𝜖)
一个自然的研究方向是考虑概念类𝒞的(𝜖, 𝛿)-量子 PAC 采样复杂度与其 VC 维之间的关系。令人惊讶的是，在这个学习场景里量子并不比经典情况更有优势。具体地说，在 2018 年，Arunachalam 等人[91]
在 Atici 与 Servedio 和 Zhang 等人工作[81, 92]的基础上证明了，对𝛿 ∈ (0, 1/2)和𝜖 ∈ (0, 1/20)，概念类𝒞的(𝜖, 𝛿)-量子 PAC 采样复杂度的一
个下界是
8.3.1.3 不可知学习
1
Θ ((𝑑 − 1)/𝜖 + log (
𝛿
) /𝜖)
不可知学习（Agnostic Learning）是对 PAC 学习的一个拓展。在 PAC 学习中，我们总是假设查询得到的标签是准确无误地从目标概念产生的𝑐(𝑥)，而这一点在现实中并不是一个非常合理的假设。我们无法确定收集到的数据标签总是准确无误的。算法获得的样本标签存在错误的情况是不可知学习所关注的。
经典不可知学习模型中，学习算法访问的喻示机是𝐴𝐸𝑋(𝐷)，其中𝐷是一个{0,1}𝑛+1上的未知概率分布。每次访问𝐴𝐸𝑋(𝐷)都会从𝐷中采样一个样本(𝑥, 𝑏)。对于函数ℎ，定义其错误率𝑒𝑟𝑟𝐷(ℎ) = Pr[ℎ(𝑥) ≠
𝑏]，其中(𝑥, 𝑏)服从概率分布𝐷。对于概率分布𝐷和概念类𝒞，我们可以
定义其中函数能够达到的最优错误率为𝑜𝑝𝑡𝐷(𝒞) = min{𝑒𝑟𝑟𝐷(𝑐) ∶ 𝑐 ∈
𝒞}。称一个学习算法𝒜是概念类𝒞的(𝜖, 𝛿)-不可知学习者，当且仅当对任意概率分布𝐷，算法在访问𝐴𝐸𝑋(𝐷)的情况下，以概率不低于1 − 𝛿算法输出一个函数ℎ ∈ 𝒞，满足𝑒𝑟𝑟𝐷(ℎ) ≤ 𝑜𝑝𝑡𝐷(ℎ) + 𝜖。不难发现当我们限制𝐷满足𝑜𝑝𝑡𝐷(𝒞) = 0这就是 PAC 学习模型。
与前文类似，我们可以定义算法𝒜 的采样复杂度是其访问
𝐴𝐸𝑋(𝐷)的最大可能次数。我们定义概念类𝒞的(𝜖, 𝛿)-不可知采样复杂度是其所有(𝜖, 𝛿)-不可知学习者的最小采样复杂度。
量子化版本的不可知学习问题由Arunachalam 和de Wolf 在 2017年首先研究[91]。对于概率分布𝐷，算法可以访问喻示机𝑄𝐴𝐸𝑋(𝐷)。对这个喻示机的每次查询将会返回量子态
∑ √𝐷(𝑥, 𝑏)|𝑥, 𝑏⟩
(𝑥,𝑏)∈{0,1}𝑛+1
类似地，我们可以定义量子学习者的查询复杂度和概念类𝒞的
(𝜖, 𝛿)-量子不可知采样复杂度。
经典不可知采样复杂度的下界由 Vapnik 和 Chervonenkis 在他们引入 VC 维的工作中给出[87]，也可见 Simon 的工作[93]，上界则由 Telegrand 在 1994 年给出[94]。综合这些结果我们得到，对于任意的概念类𝒞，其(𝜖, 𝛿)-不可知采样复杂度是Θ(𝑑/𝜖2 + log(1/𝛿) /𝜖2)，其中𝑑是概念类𝒞的 VC 维。这一结论与前面经典 PAC 采样复杂度的结论被 Shalev-Shwartz 和 Ben-David 在他们的著作《理解机器学习：从理论到算法》中称为 PAC 学习基本定理[95]。
在量子的情况中，Arunachalam 在 2018 年[91]证明了对于任意的概念类𝒞，𝛿 ∈ (1,1/2)和𝜖 ∈ (1,1/10)，设𝒞的 VC 维为𝑑，则其(𝜖, 𝛿)-量子不可知采样复杂度至少是Ω(𝑑/𝜖2 + log(1/𝛿) /𝜖2)。这个证明与前面 PAC 学习的情况类似。作为结论，与 PAC 学习类似，在不可知学习的模型下考虑采样复杂度，量子学习者并不比经典学习者具有显著优势。
8.3.1.4 大整数分解与高效 PAC 学习
虽然在考虑采样复杂度时，量子算法并不比经典算法具有明显优势。但当我们考虑学习算法的时间复杂度时，我们发现量子比经典具有很强的优势。Servedio 和 Gortler[78]在 2004 年的工作指出，假设不存在经典的多项式时间算法分解大整数，那么就存在概念类能够被量子算法多项式时间PAC 学习，但不能被任何经典算法多项式时间PAC学习；也存在概念类能够被量子算法多项式时间精确学习，但不能被任何经典算法多项式时间精确学习。
除此之外，他们还证明了一个更令人惊讶的结果，揭示了量子算法的神奇之处。他们证明了只需要假设经典单向函数存在，就能够找到概念类能够被量子算法多项式时间精确学习，但不能被任何景点算法多项式时间精确学习。这个结论让我们看到了在经典机器学习问题
考虑时间复杂度时的量子优越性。