变体布尔函数学习的经典和量子复杂性分析

1C{} → {}|C|√γ-γC√γ-γC利用Adjacent界亚历山大·别洛夫斯摘要在本文中，我们研究了军政府学习问题的以下变体我们被赋予了对n个变量的布尔函数f的oracle访问权限，该函数只依赖于k个变量，并且，当被限制为k个变量时，等于某个预定义的函数h。任务是识别函数所依赖的变量当h是XOR或OR函数时，这分别给出了Bernstein-Vazirani或组合群测试问题的受限变体我 们 分 析 了 一 般 情 况 下 使 用 的 对 手 界 ， 并 给 出 了 一 个 替 代 的 公 式 的quantumuerymplexityfhisprblem。我们将继续为您提供最优质的服务，当h是OR函数（复杂度为Θ，k））或正半函数（复杂度为Θ（k1/4））。第一个算法解决了[4]中的一个公开问题对于h是多数函数的情况，我们证明了一个O（k1/4）的上界。所有这些算法都可以精确。我们得到一个四次的改进相比，随机化的复杂性（如果h是确切的一半或多数函数），和二次相比，非自适应量子复杂性（在本文中考虑的所有功能）。1引言学习理论从不同的角度研究了从函数值重构函数的问题。在本文中，我们研究的问题，精确学习的成员资格查询。在这个问题中，一个给定的oracle（黑盒）访问函数f：0， 1n 0， 1属于某个固定的函数类（通常称为概念类）。任务是使用对oracle的尽可能少的查询要求给出函数的精确描述，而不是近似值（虽然，允许以1/ 3的小概率出错）。这是一个广泛的研究领域，无论是经典的还是量子的。我们将重点介绍一些结果。经典上，这个问题是由Angluin定义的[5]。 Bshouty等人 [16]获得了精确使用组合参数学习概念类C的随机查询复杂度的上界和下界0<γ≤C≤1的类。更具体地说，如果i为零，则q的复杂度Xi ty为O。 洛格|C|ΣandΩ. 1+l og|C|Σ量子，这个问题进行了分析（在量子甲骨文审讯或识别的名称如果icati on）byvanDam[40]和dAmbai n是etal。 [3]的文件。VanDamconsidedecas eees e e e e se d ed e deeconsts对于所有的布尔运算，当n/2+O（n）时间复杂度满足一定的条件时，需要经典的查询。 Ambainis等人构造了一个时间复杂度为O（n log |C|log n log log |C|）-查询一般情况下的算法。最后，Kothari[28]给出了这个问题的量子查询复杂度的完整表征，用n和。Servedio和Gortler[37]证明了[16]中结果的一些量子类似物。特别是，th。Ey表示，对于任何概念类C，学习C的量子查询复杂度正好是Ω1γ-γC +log |C|n. 利用这个结果，他们得出了同一问题的确定性复杂性是. 时间复杂度O（nQ3）其中nQ是它的量子查询复杂度。[6]阿提哈德和塞尔维迪奥构建了一个量子Olog| C| loglog| C|γ-γC详细说明：同一问题的查询算法本文研究了Ambainis和Montanaro [4]提出的学习问题。 设h：{0，1}k → {0，1}是固定对称布尔函数。我们麻省理工学院，abelov@csail.mit.eduarXiv：1311.6777v3 [quant-ph] 2014年10.2≫K|C|⊆⊆⌊⌋| ⟩|⟩给定oracle访问满足以下性质的nk个变量上的布尔函数f。 函数f仅依赖于k个输入变量的子集A，并且当限制为这些变量时，函数等于h。因此，学习问题简化为识别集合A。只依赖于少量输入变量的函数称为junta。因此，我们的问题与学习和测试juntas的问题有关，这已经在经典（见[13]和其中的参考文献）和量子[7]两方面进行了研究然而，请注意，我们的设置与通常的军政府学习不同。首先，我们有一个额外的承诺，即函数f等于函数h。其次，我们允许自适应成员查询，而不仅仅是样本。第三，我们必须精确地找到函数f，而不是近似值。最后两个方面使我们的设置不同于量子PAC模型[17]。一个简单的信息理论论证表明，经典地解决这个问题需要<$（log）=<$（klogn）个随机查询。在数量上，像往常一样，人们可以做得更好。其中一个开创性的量子算法，伯恩斯坦-瓦齐拉尼算法[12]，可以在这些设置中陈述。该算法解决了h是XOR函数时的问题。它在一个查询中这样做，没有错误，而且，同时对所有k值。另一个例子是组合群测试问题（尽管名称，它是一个学习问题）。在这个问题中，给定一个n个元素的集合X，已知其中至多k个元素被标记。对于任何子集S X，可以在一个查询中检测S是否包含标记元素。任务是识别所有标记的元素，尽可能少地进行查询它对应于h是OR函数的情况（如果我们另外要求恰好有k个标记元素）。这是一个经典的研究问题[22]。Ambainis和Montanaro[4]研究了这个问题的量子已完成带wildcardsproblem的搜索，但无法快速地对合并存储组的合并执行Xity（2）在两种情况下，（ 时间复杂度O（k）Iwama等人研究的量子假币问题。 [26]这与我们的工作密切相关。 在这个问题中，给一个人n个硬币，并且知道其中正好有k个是伪造的。 所有真币的重量都一样，所有假币的重量都一样，而且假币严格来说比真币轻。一个人也被赋予了完美的秤，任务是使用尽可能少的称重操作来找到所有的假币更正式地说，oracle接受两个不相交的相等大小的子集S，T[n]作为其输入。如果S和T包含相同数量的假币，则它以0回答，否则以1回答。(I.e.、人们只知道天平是否平衡。Iwama等人构造了一个量子算法，解决了这个问题，在O（k1/4）查询的oracle。没有一般的下限是已知的这个问题。我们的合作伙伴 在这个时候，我们会把它摔下来。在第3项中，我们将通过以下方式解决问题1998年，张晓波和张晓波（ k）-查询算法组测试问题（在其完全的一般性中，即，允许少于k个标记的元素）。在第4节中，我们使用敌手界和表示理论来制定我们的学习问题的量子查询复杂度的优化问题，对于任何对称函数h。在第5节中，我们解决了这个优化问题时，h是正半函数（函数的评估为1，当恰好k/2的输入变量等于1）。学习问题的量子查询复杂度为Θ（k1/4）。在第6节中，我们描述了当h是多数函数时的一些部分结果最后，在第7节中，我们证明了上述大多数算法可以在不增加复杂度的情况下精确化，并证明了非自适应量子算法的一些不可行结果在讨论我们的技术之前，让我们描述一些以前使用的技术。一种可能性是应用Grover搜索（如Ambainis等人的论文[3]，以及Atıc和Servedio[6]）。这最多给出二次加速。然而，大多数论文都使用了以下的测量和测量策略：|ψ⟩已完成，输入或操作系统的一个端口或一个新的操作系统对该数据是一个程序，并且已完成。这种策略通常有两种变体之一第一个是傅立叶采样。在这在T= 1的情况下，λ是均匀叠加。所得的状态，Ox π，在傅立叶基中测量。这个过程被重复多次，当收集到足够的样本时，它们被一个经典的子程序处理以重建f。值得注意的例子是Bshouty和Jackson[17]的DNF学习算法以及Atıctillo和Servedio[7]的junta学习算法，其中，3/| ⟩|⟩|C|∈ C公司简介∩∩∩∅|\|⊆⊆| ∩|≥方法被明确地提到（在第一篇论文中以量子实例Oracle的名义，在第二篇论文中以傅立叶采样Oracle的名义一个更好的方法是如何使所有x=y的情况下的最大值Ox最小值和Oy最小值都小于最大值，然后应用PrettyGood Measurement[24]来区分它们。这里的例子是参考文献[20，23]。无论哪种方式，测量和测量策略通常都是非自适应的（定义见第2节）。这是一个限制。例如，Zalka[41]表明，与Grover搜索相比，非自适应量子算法需要<$（n）个查询来求解OR函数Childs等人在[20]中解释了为什么他们的隐藏移位算法使用此参数对delta函数执行次优所有这些方法都不能满足我们的问题。首先，本节开始时提到的一般结果在这里是无用的，因为我们的问题的量子查询复杂度小于k，这比n或log小得多。接下来，我们在随机算法上实现了超二次加速，这是仅使用Grover搜索不可能实现的。最后，在第7节中，我们证明了任何非自适应量子算法都需要比我们的算法多二次方的查询。这并不完全排除测量和测量策略，但表明其最简单和最常见的一次性变体在这里不起作用。将我们的正半函数算法与Iwama等人 [26]的假币问题算法进行比较也很有趣。毕竟，这两个算法都达到了O（k1/4）的复杂度，这是随机复杂度的四倍改进。我们不知道在两个方向中的Iwama等人 将伪造问题简化为Bernstein-Vazirani问题实际上，如果偶数大小的子集S包含偶数数量的伪造硬币，则存在将S分割成具有相等数量的伪造硬币的两个相等大小的子集这些解剖可以使用量子振幅放大来检测[15]。类似的方法似乎不太可能应用于正半函数。我们的技术，而不是这些技术，我们使用的双重对手界。 攻击者界限是量子查询复杂度的下限，首先由Ambainis [2]以现在被称为正加权攻击者的形式开发。后来，它得到了Høyer等人的加强。[25]到负加权或一般对手界限。 Reichardt等人 证明了这个下界是紧的，如何将对偶的对手界限转换为量子查询算法[33，31]。他们的算法是基于量子行走。因此，一个量子查询算法可以通过提出一个可行的解决方案的双重对手界。在这方面已经做了一些工作。公式评估算法提供了一个例子[34，42]。另一个发展方向是学习图[9]。它们被应用于改进三角形和其他子图检测的量子查询复杂度[30，10]，以及k-独特性问题[8]。一般来说，学习图对于具有小1-证书的布尔函数工作得很好。显然，这两种一般方法在这里都不起作用。事实上，我们的问题没有一个很好的公式描述，也没有布尔输出，也没有小证书。相反，我们从头开始构建一个可行的解决方案的双重对手。让我们简要介绍一下我们的建设。关于敌手界限的精确表述，读者可以参考第2节。非正式地，对偶对手界限（3）归结为使用查询（3b）区分输入A、B在下面的非正式说明中，我们分析了使用通常的随机算法和对手界区分A和B的复杂性，并比较了两者。虽然在（3b）中获得相等，而不是像（3d）中那样的下限，很重要，但我们现在忽略这个问题我们从组合群测试开始，这对应于h是OR函数的情况假设我们想要区分k个子集A，B[n]。此外，我们想这样做，而不管距离<$A =B A。一个简单的策略是通过随机独立地包含[n]的每个元素来获取子集S[n]，并希望SA和SB中恰好有一个是空的。通常，最坏的情况是距离= 1。在这种情况下，以SA=为条件，S区分A和B的概率（即，SB =）是p。 但是取p1/k并没有太大意义，因为这样S不与A相交的概率就太小了。然而，双重对手允许额外的技巧。特别地，我们可以也就是说，具有SA1的查询S既不计入复杂度，也不计入区分A和B。(The当然，这也适用于B）。因此，在本发明中，4∈| ∩||∩|∩∅--⟨⟩⟨⟩ǁ ǁ| ⟩| ⟩ | ⟩ ›→ |⟩ |⟩在这种情况下，我们甚至可以取p= 1/ 2，这增加了A和B被区分的机会但是当k是k时，p= 1/ 2的选择就不起作用了。事实上，在A S=的条件下，S B= 1的 （请记住，如果SB>1，则我们不使用S代替B 在这种情况下，p= 1/k是一个更好的选择。在最终的解中，我们随机均匀地取p（0，1），令人惊讶的是，它适用于所有的值。因此，我们的解决方案的组合组测试问题是有点特设。分析是如此简单，因为我们可以假设S与A相交于0或1个元素。 如果h是择多函数，则它是在h上进行选择的 |SA|是k/2−1或rk/2。 在此，assumeAB=。你好，不管A是什么，概率最多为O（1 /2）。（k），|SB| ∈ {}。 因此，为了解决在这种情况下，我们将不得不采取其他交叉口的大小，以及，这将使分析更加复杂。我们使用一种保证严格的方法，而不是坚持这种特殊的在不失一般性的情况下，我们可以假设对手下界（2）的最优解Γ关于置换[n]的元素然后，矩阵Γ可以由k+ 1个实数唯一我们利用对称群的表示理论，得到了这些数必须满足的充要条件对偶问题的一个可行解再次给出了一个量子查询算法。不幸的是，由此产生的优化问题仍然非常复杂。我们能够得到一个可行的解决方案，当h是大多数或正半函数时，使用这些函数关于权重k/2对称。但是，将这些方案应用于OR函数，例如，将比我们以前的特别解决方案复杂得多我们的多数解和正半解本质上是等价的，但对于正半解，解是紧的。将此解推广到精确的阈值函数或阈值函数是一个公开的问题。2预赛我们用[n]表示集合1，2，.。. .，n和2 A来表示A的子集的集合。一个k-子集是一个大小为k的子集。文中所有矩阵都有实数项。 A是A的伴随（转置）矩阵。 如果A是一个矩阵，通过A [[i，j]]，我们表示第i行和第j列的交点上的元素。我们用A表示A的谱范数（最大奇异值）， 一个tr我们表示迹范数A（奇异值之和通过A，B，我们表示矩阵之间的内积A，B= tr（A<$B）.我们假设熟悉基本的概率论，我们重复使用下面关于二项式系数的著名结果：引理1. 如果n和k都是正整数，满足k = O（n），则。nn/2θ= Θ（2 n/θn）。量子查询复杂度现在我们定义量子查询复杂度的标准和非自适应变量。对于查询复杂度的更完整的处理，请参阅[18]和[32]非自适应查询复杂度。量子查询算法被定义为与oracle调用交替的酉变换序列：U0→ Ox→ U1→ Ox→···→ U T−1→ Ox→ U T。（一）这里Uis是与输入无关的任意酉变换。 OracleOx是相同的在所有的地方，它取决于输入字符串x=（xi）作为iibviib+xiv，其中加法是模2执行的。除了i和v之外的其他寄存器保持不变。计算开始于预定义状态0。在执行了（1）中的所有操作之后，测量某个预定义的输出寄存器。我们说算法评估函数f，如果对于域中的任何x，测量的结果是f（x），概率至少为2/ 3。数字T是算法的查询复杂度。在所有计算f的算法中，T的最小值是f的量子查询复杂度，记为Q（f）。因此，我们看到量子算法可以根据先前Oracle调用的结果准备下一个Oracle查询的输入在许多情况下，这对于获得好的算法至关重要但是，在某些情况下，oracle的输入并不依赖于其先前执行的输出这5HHCHHHHH{∈ C|}ΣC× CHHHn被非自适应量子查询复杂度的概念所捕获在这样的算法中，我们假设所有的oracle调用同时并行发生更正式地说，非自适应量子查询一个几何体是U0→OxT→U1。该非常规和非常规问题非常复杂，其中f为Xity定义类似于自适应情况。问题的公式化让我们严格定义我们的学习问题版本。 设h：{0， 1}k→ { 0， 1}是一个对称布尔函数。它由子集W h∈ {0，. . . ，k}使得h（x）= 1当且仅当|X|∈ W h，其中|X|表示x的汉明重量。设n≥k为正数，整数，C表示[n]的所有k-子集的集合 如果A ∈ C，我们定义函数f A：{0，1} → {0，1}为f A（x）= h（x A），其中x A是输入字符串x对A中位置的限制。用定义为i∈S当且仅当xi= 1的子集S∈ [n]来标识输入字符串x更为方便因此，在本发明中，f A（S）= 1当且仅当|一个人|∈ W h.n学习问题L n：{0，1}{0，1} →2[n]定义为Ln（f A）= A。因此，h是固定的和已知的对于事先学习者，输入是函数fA（可以用以下元素识别：），并且输入变量是fA的输入字符串（可以用[n]的子集标识）。很容易看出，量子查询复杂度Q（Ln）是n中的非减函数。 Q（Ln）也存在一个与n无关的上界.例如，可以采用类似于[7]中的傅立叶采样算法的复杂度，因为其行为不依赖于n。因此，存在limn→∞Q（Ln），记为Q（Lh），这是我们最感兴趣的问题。接着，我们定义了针对我们的特殊情况Ln的对手界。 攻击矩阵Γ是一个C× C实对称矩阵，其对角线上有零。引入一个记法的错误，设Γ_（？）S表示由{ A ∈ C}中的行构成的Γ的子矩阵|f A（S）= 0}和B中的列f B（S）= 1。敌手界ADV±（Ln）等于以下两个最优解的（公共）最优misation问题：和最大化最大值（2a）受rS≤1的对于所有S[n];（2b）对于所有的A∈ C，Γ[[A，A]]= 0。（2c）最小化最大A∈CΣS[n]XS[[A，A]]（3a）受S：fA（S）/=fB（S）X S[[A，B]]=1 对于C中的所有A/=B;（3b）XS≥0 for allS [n]，（3c）其中XS是半正定矩阵（参见[33，定理6.2]证明两个问题的等价性由于以下结果，敌手界限非常有用定理2（[25，31]）. 函数f的量子查询复杂度等于Θ（ADV ±（f））。利用这个定理，我们可以估计ADV±（Lh）而不是Q（Lh）。这里我们记ADV±（Lh）= limn→∞ ADV±（Ln）.极限存在是因为ADV±（Ln）是n中的非减函数。对手界的一个重要特例是正加权对手，我们用ADV（Ln）表示。这是对Ambainis的原始版本的轻微修改[2]。它严格地弱于一般的界限，但它通常更容易应用。正加权对手的定义如（2）和（3）中所述，但有以下修改。在（2）中，我们要求所有的元素都是非负的。在（3）中，我们用下面的条件[38，等式（3）]代替条件（3b）（3.7）]：ΣS：fA（S）/=fB（S）XS[[A，B]]≥1 for allAB在C中;（3d）6.≥√| △|−−−13组合群测试在本节中，我们将描述一个用于组合组测试问题的量子查询算法我们以原始形式解决问题，这与我们的学习问题版本略有不同让我们重新表述这个问题。设k n<是固定的正整数，C由[n]的所有大小不超过k的子集组成.对于每个A∈ C，函数fA：2[n]→ {0，1}定义为：fA（S）=1，如果A≤S/=0;否则为0。我们被赋予对fA的oracle访问权限，任务是检测A。与LOR问题的区别在于，我们允许A的大小小于k。在本节中，我们证明了以下结果：定理3. 组合群测试问题的量子查询复杂度为Θ（k）。下界可以通过从无序搜索的约化来证明，更多细节参见[4]这里我们证明了上界。我们通过构造（3）的可行解来实现这是通过两个步骤完成的：首先，我们定义秩为1的矩阵YS（p），然后从它们构建矩阵XS设P是[n]上的二项概率分布，概率为p。 回想一下，它是[ n ]的子集上的概率分布，其中[ n ]的每个元素独立地包含在子集中。 通过P（S），我们可以从P中得到S的可积性：P（S）=p|S|（1−p）n−|S|.最后，设△表示集合的对称差。我们定义Y（p）=（YS（p））S<$[n]为：哪里Y（p）=P（S）=0，S2P√4kp/（1−p），如果|一个人|=0;[[A]]=对所有的A∈ C。 在这个符号中，（1− p）|一|/2个×4（1−p）/（kp），如果|一个人|= 1; 0，否则;.Σ YS（p）[[A，A]]=1.一、|一|ΣΣPR |=零|= 0KP+ PR Σ|=1个|= 1.Σ1 −pS[n]2p（1−p）SP1−pSPKP1=2 p（1 −p）|一|..（1−p）|一|KP1−p+的|一|p（1−p）|一|−1.Σ1 −pKP.K.p（1−p）现在我们固定两个不同的元素A，B和C。元素A仅在以下情况下才用于Y S|SA|≤ 1。所以，我们只对S [n]感兴趣，|一个人|+的|B组|= 1。因此，在本发明中，ΣY（p）[[A，B]] =PrSPΣ Σ|+的|B组|=1个|= 1S：fA（S）SfB（S）2 p（1 − p）（|一|+|B|）/2个AB p（1 p）|AB| −12.2.1-2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2|一|+|B|）/2=|（1名p）|(1p)2|A △ B|二、现在，对于每个S[n]，令XS=∫1Y S（p）d p.0首先，每个XS是半正定的，因为半正定矩阵形成凸锥。接下来，1≤7−1S对于任何A∈ C：XS[[A，A]]≤∫1Dpk= π好吧S[n]最后，对于C中的所有A/=B：Σ0X[[A，B]] = |A△B|2p（1−p）∫1|A△ B|（1− p）2d p = 1。S：fA（S） fB（S）0√8≤不不k−iκm，p（d）其他事项H−{}›→{}∈不不−不4表示理论在上一节中，我们描述了当h是OR函数时（3）的可行解的特殊构造。在本节中，我们使用表示论来给出ADV±（Lh）的另一种描述，它适用于任何函数h。我们使用下界（2），因为它具有非常简单的结构。在接下来的两节中，我们使用对偶性来证明新的公式，量子查询的复杂度L多数k时间复杂度为O（k1/4）令h：{0， 1}k→ { 0， 1}是由权重的子集Wh定义的对称函数，即，h（x）= 1森林论坛|X| ∈W h.对函数L h的攻击矩阵的搜索结果等价于对realnbersd=（d0，. . . ，dk）这是一个非常复杂的问题，因为它是一个非常复杂的问题。设mk为正整数，0时，卷积是一致的。在这种情况下，如果满足条件limc →0εc=0，则x是一个约束εc，条件是A（t）−et− t−t≤如果n1小于cn，则ε c并且-ek−tek−t如果n1大于（1 −c）n，则ε ≤ εc。t0，t101t−t0−t1我们在本节的最后证明了引理。现在，让我们展示如何使用引理来证明定理4。假设ADV±（Lh）=Q。如第2节所述，Q<∞。然后，对于每个n，设Γ（n）是（2）的最优解。我们可以假设<$r（n）<$r是r（n）的特征值，否则用y−r（n）代替r（n）。因为你的年龄很小，所以我们都知道克r（n）=t=0时d（n）k（N，t）.（十三）C〇nsi deteterd（n）=（d（n））。由于所有由Q生成的d（n）的值都是随机的，因此，t t我们将这两个变量定义为等式d（n1），d（n2），我们发现d=（dt）是.....这是一个非常重要的问题。 Clearly. ，max.tdt=Q.接下来，当n→ ∞时，trk（N，t）= in（13）不 −t−1. 因此，trk（N，k）表示所有其他投影仪. （2）（ C）（D（个）trΓ（ni）dk= limd我=lim. - 是的= 0。（十四）i→∞i→∞ninik k−1这证明了定理4中的第一个约束。第二个约束由引理6和（11）得出。现在假设d是定理4中的优化问题的最优解，并且令Q= maxtdt。在（13）中，当d（n）=dtf（0，使得εc≤1/（2（k+1）Q），其中εc与引理6相同。 如果|S|/n 1 − c，则对任何满足max tdt≤ Q的d的选择，S ≤ 1 / 2。 如果|S|/n → p，且c

下载后可阅读完整内容，剩余1页未读，立即下载