非自适应学习图的量子查询复杂性证书结构及其对证书大小的限制

1关于非自适应学习图亚历山大·别洛夫斯·安西斯·罗斯曼尼斯摘要我们引入了一个概念的量子查询复杂性的证书结构。这是一个众所周知的观察的形式化，许多量子查询算法只需要输入字符串中可能的证书的处置的知识，而不是其中的精确值。接下来，我们推导出非自适应学习图的复杂性的对偶公式，并使用它来表明非自适应学习图对于所有证书结构都是紧通过这一点，我们的意思是存在一个函数拥有证书结构，并且学习图为其提供了最佳量子查询算法。对于一个特殊的情况下产生的证书结构的证书的大小有界，我们构造了一个相对一般的类具有此属性的该构造基于正交表，并且推广了最近导出的k和问题的量子查询下界[7]。最后，我们使用这些结果表明，学习图的三角形问题，从参考。[20个]在这种情况下几乎是最佳的这也给出了三角和问题的量子查询下界1介绍确定解决计算问题所需的计算资源量是理论计算机科学中的主要问题之一然而，在目前的知识阶段，这一任务似乎对许多问题来说遥不可及在这种情况下，可以在一些简化的假设下分析问题的复杂性查询模型展示了这样的假设之一。在这个模型中，假设除了访问输入字符串之外的所有计算资源都是免费的。（有关模型的详细描述，包括我们的兴趣量子查询复杂度的情况，请参阅[10]。在这个假设下，有可能证明一些严格的界限。特别地，构造了一个相对简单的半定规划（SDP），得到了任何函数的量子查询复杂度的严格估计这就是我们在5.1节中描述的敌手界限。不幸的是，对于许多函数，即使是这个SDP也很难解决。 在本文中，我们探讨了在进一步简化的假设下构造一个更简单的优化问题的可能性。我们的假设是基于量子行走的算法类的动机开发这种算法的一个流行框架[22]包括一个黑盒检查子例程，该子例程根据在行走过程中收集的信息发出信号，如果这些信息足以接受输入字符串。在许多情况下，收集到的信息的确切内容与量子行走的实现无关，重要的是这些信息的可能位置 我们通过下面的定义将其形 式 化 。在定义中，我们使用以下符号。 如果m和n是正整数，我们使用[n]来表示集合{1，2，. . . ，n}，以及[m，n]来表示集合{m，m +1，. . . ，n}。对于序列x=（xi）∈[q]n，而S∈[n]，设xS∈[q]S表示x在S上的投影，即，序列（x s，. . . ，x s）索引1ℓ元件S1，. . . ，S.定义1（证书结构）。n个变量的证书结构C是2 [n]的非空子集的集合，每个子集在取超集下闭合。我们说一个函数f：D → {0，1}，其中D ∈[q]n具有证书结构C，如果对于每个x∈f−1（1），可以找到M∈ C，使得<$S ∈ M <$z ∈ D：z S= x S=<$f（z）= 1。我们的目标是为客户提供高质量的产品和服务。我们的目标是为客户提供高质量的服务。Com大卫河滑铁卢大学计算机科学学院和量子计算研究所我知道你在说什么。CaarXiv：1210.3279v2 [quant-ph] 2012年122| |∈∈||∈C问题：给定x∈[q]n，检测是否存在M∈ C使得˜xj≠0（modq）。如果≥|C|j∈AM我们感兴趣的量子算法执行同样好的任何功能与一个固定的证书结构。在第2节中给出了这种算法的一些例子。更正式地说，将证书结构的量子查询复杂度定义为拥有此证书结构的所有函数的最大量子查询复杂度。最近开发的（非自适应）学习图的计算模型[5]依赖于定义函数的证书结构这建议将证书结构的学习图复杂度定义为利用该证书结构计算函数（因此，任何函数）由于学习图可以转换为具有相同复杂度的量子查询算法，因此证书结构的学习图复杂度是其量子查询复杂度的上界在本文中，我们证明了这两个复杂性实际上是相等的常数因子。定理2. 对于任何证书结构，其量子查询和学习图复杂度最多相差一个常数乘法因子。这意味着任何想要比最佳学习图表现更好的量子查询算法都必须在算法的早期阶段考虑变量的值虽然定理2是一个非常一般的结果，但在具有所需量子查询复杂度的函数是相当人为的，并且字母表的大小是天文数字的意义上，它是不令人满意的。然而，对于我们将要定义的证书结构的特殊情况，可以用具有高量子查询复杂度的中等大小的字母表来构造相对自然的问题定义3（有界生成的证书结构）。我们说证书结构C是有界生成的，如果对于任何M ∈ C，可以找到子集A M<$[n]，使得|A M|= O（1），且S∈M当且仅当S<$A M.定义4（正交数组）。假设T是[q]k的子集。我们说T是字母表[q]上的正交数组当且仅当，对于每个索引i[k]和每个序列x1，. . . ，xi −1，xi+1，. . . ，x k的元素，则存在x i [ q]的T /q k−1个选择，使得（x1，. . .，xk）T.我们称T为数组的大小，k为数组的长度。（与正交数组的标准定义相比（参见[16]），我们总是要求所谓的数组强度等于k-1。定理5. 假设证书结构C是有界地生成的，并且令A M类似于定义3。假设字母表是[q]，其中q ≥ 2 |C|，并且每个A M配备有长度为字母表[q]的正交阵列T M|A M|尺寸Q|AM|-1。 考虑函数f：[q] n→ {0，1}定义为f（x）= 1当且仅当存在M ∈ C使得xAM∈ TM. 那么，f的量子查询复杂度至少是一个常数乘以C的学习图复杂度。对于复杂性，如果存在中断C，则会导致严重的数据丢失，如果出现错误，则会导致数据丢失q2，定理5暗示这个问题的量子查询复杂度至少是一个常数学习图复杂度的两倍。定理5是文献[1]中k-和问题下界的推广[7]，并通过将其与学习图联系起来，提供了关于构造的额外直观性参考文献[7]中的许多讨论也适用于这里。让我们简要地评论一下文件的结构在第2节中，我们给出了一些受已知计算问题启发的证书结构示例 在第3节中，我们导出了非自适应学习图复杂度的对偶公式。在第4节中，我们应用这个对偶公式来给出第2节中证书结构的学习图复杂度的下界。我们证明，过渡到学习图的复杂性确实简化了问题，通过获得一个几乎最佳的n9/7下界的三角形证书结构，而没有什么比平凡的对于原始的三角形问题，已知n（n）最后，在第5节中，我们证明了定理2和定理5。2证书结构我们在引言中定义了证书结构的概念。事实上，许多现有的量子算法，隐式或显式，在这些设置工作。在本节中，我们回顾其中的一些算法32∈∈∈∈nK 元素，并且，对于每个大小为k的子集A∈[n]，存在唯一的M∈ C，使得S∈M，如果n3元素，并且，对于每个三元组1≤a b c≤n，存在唯一的M∈ C，使得并定义相应的证书结构。在第4节中，我们考虑了它们的学习图复杂性。这些算法的最著名的例子是Grover正如Childs和Eisenberg [11]首先注意到的那样，Ambainis算法可以用于找到大小为k的任何子集。换句话说，它适用于具有以下证书结构的任何函数：Defi。6.我不知道。 k=O（1）时的k -最优约束条件如下所示。It只有当一个人，在同一篇论文中，Childs和Eisenberg证明了Ambainis定理5可以被看作是这个猜想的一个强推广（因为Ambainis另一个著名的基于量子行走的算法[23]（隐式地）解决了具有以下证书结构的任何函数：定义7.n个顶点上的三角形证书结构C是上的证书结构。n个变量被定义为一个函数。W. 总之，当1≤ d，因此，或者n-3/14gi（S，M）= 0，或ν（S，M）2n3/7，此时满足条件的a的选择数为O（n3/7）因此，（7）的左手边是O（n3/7）（n−3/14）2=O（1）。如果gi（S，M）gi（Sj，M）= 0，则在前三种情况下，d的值，直到小的模糊度，可以从j的端点之一的度来确定。因此，集合K = K（S，j），如前面证明中所述，存在。自动地，我们得到了三角形和问题的量子查询复杂度是n（n9/7）。因此，任何量子查询算法，愿意改善三角形检测问题的O（n9/7）界，将不得不将三角形检测和三角形求和问题之间的差异转化为考虑.5下界在本节中，我们证明定理2和定理5。结果是强连接的：在第二个，我们证明了一个更强的声明，从更强的反。因此，证明也有许多共同的元素。本节的组织如下。在5.1节中，我们回顾了我们用来证明下界的对抗方法在证明中，我们将定义一些矩阵并讨论它们的谱性质。 为了方便起见，我们描述了矩阵的主要参数，例如它们的行和列的标签，以及它们在一个地方的相互关系，5.2节。在5.3节中，我们陈述了对定理2和定理5都很重要的中间结果。在第5.4节中，我们完成了定理5的证明。在5.5节中，我们回顾了傅立叶基的定义和主要性质，并定义了傅立叶偏置的重要概念最后，在第5.6节中，我们证明了定理2。5.1粘合剂结合敌手方法是证明量子查询复杂度下界的主要技术之一 首先由Ambainis [2]开发，后来由Høyer等人加强。[17 ]第10段。在此之后，对手界被证明是最佳的Reichardt等人。 [24、21]。在本文中，我们使用了一个变种的对手界从参考。[7]的文件。定义14. 设f是定义域D ∈ [ q ] n的函数f：D → {0，1}. 设D是一个对（x，a）的集合，每个对的第一个元素属于D，且Di={（x，a）∈ D |f（x）= i}，其中i ∈ {0，1}。函数f的敌手矩阵是非零实D1× D0矩阵Γ。并且，对于j∈[n]，让t∈jde不等于D∈1×D∈0maxdefinedyJ1、否则定理15（附着界[17，7]）. 在定义14的符号中，f的量子查询复杂度是（Adv ±（f）），其中Adv±（f）= supvΓ（九）rmaxj∈nj其中f的所有对手矩阵上的最大化，并且是谱范数。下面的结果在使用对抗方法证明下界时非常有用。·12◦ ◦◦D →{}DΓCM1战斗机^˜˜电子邮件：info@gmail.拉吉˜˜˜˜YΓ=GM2，（10）其中，a_h_G_M是n[q]n×[q]n-矩阵。 N∈t，n ∈ R，n ∈ R。而且我会一直这样做，blocksG′-是的GM2M 类似于（10）。引理16（[21]）. 设dj为定义14中的值。那么，对于任何大小相同的矩阵AA我们将用它来用矩阵Γ ′代替（9）的分母中的Γ j，使得Γ j= Γ ′ j。根据引理16，这给出了直到因子2的相同结果。我们将把这种关系表示为拉吉矩阵由Γ−→5.2纲要Γ′。让我们简单地概述定理2和定理5是如何被证明的。让C表示证书结构。设αS（M）满足（2），并且使得（2a）等于的学习图复杂度。我们定义一个显式函数f：0， 1，其中[q]n具有程序（2）的目标值（2a）量子查询的复杂性。后者是证明使用对手界，定理15。为此，我们定义了许多矩阵，如图1所示。XM1双排XM2双排GTM2XMkG˜M阿克斯GM1..GMk拉吉中文（简体）图1：第5节中使用的矩阵之间的关系。用灰色标记的部分形成左侧的矩阵Γ和右侧的矩阵Γ′注意，它们分别不是Γ和Γ′的子矩阵：它们有额外的乘法因子，如（14）和（15）中所指定的。在Martrix矩阵Atf irst，我们可以创建一个martrix矩阵Atfyi ngfol owper eties。最后，它是这样的由[q]n× C的元素标记，列由[q]n的元素标记。因此，如果我们表示C={M1，. . . ，Mk}，该矩阵矩阵具有以下形式：Geachj∈[n]，则ex是tsΓ'suchtatΓ−→Γ'anddΓ′≤1. 这一复杂的结构使我们能够因此，r具有良好的值（9）。但是，我们不能使用它，因为它不是一个对手矩阵：它使用所有可能的输入都作为行和列的标签然而，由于构造Γ的特定方式，我们将能够将Γ转换为真正的对手矩阵Γ，使得（9）的值仍然是好的。在我们描述如何做之前，让我们概述一下函数f的定义。GΓ˜′阿克斯Y^“M1G^′M2..G^′MKK10（一）S..C||˜√˜.M1N∈M˜ΣMAMM′′拉吉拉吉′我觉得你会更好。当Γ^′是一个n×[q]n-矩阵时，AsΓ ′是一个满足Γ^′和<$Γ′≤1的代数，我们满足<$Γ′=O（1）的条件. 我们不去看那块石头i>0ei ei.这些是q×q矩阵。E0的所有元素都等于1/q，E1的元素是定义函数设M为证书结构C的元素。 设A（1），. . . ，A（M））是所有M的包含式极小元。（在有界生成的证书结构中，M只有一个包含式极小元AM.）对于每个A（i），我们选择一个长度为M M|在字母表[ q ]上，并定义|over the alphabet [q], and defineXM=，x∈[q]n|x（i）∈T（i）对于所有i∈[M]，.（十一）选择正交表，使得XM非空并且满足以下正交性性质：<$S∈2[n]\M<$z∈ [q]S：{x∈X M|x S=z}= |X M|/q|S|.（十二）对于有界生成的证书结构，此属性将自动满足正输入的集合定义为f−1（1）=M∈CXM。负输入的集合定义为：f−1（0）=，x∈[q]n|对于所有M∈C和i∈[M（M）]，x（i）∈ /T.（十三）（一）AMM很容易看出，f具有其证书结构。参数的选择使得f−1（0）=<$（qn）。设X ={（x，M）∈ [q] n× C|x ∈ X M}且Y = f −1（0）。矩阵Γ是由下式定义的X×Y矩阵：r [[（x，M），y]]=Qn|XM|Γ[[（x，M），y]].（十四）因此，r由块G M组成，如在（10）中，其中G M=q n/|X M|G M[[X M，Y]]。（后一种符号表示由指定的行和列形成的子矩阵我们还表明，矩阵r这是一个非常简单的问题。ItisclearthatΓ−→Γ意味着Γ−→ Γ。我们证明了Γ^′[[（x，M），y]]=Qn|XM|[[（x，M），y]].由G^“.也就是说，.QnMMG^'为|XM|G′[[X M，[q] n]]。（十五）5.3证明的共同部分设e0，. . . ，eq-1是Cq的标准正交基，使得e0= 1/nq（1，. . . ，1）。记为E0=e0e，Σ∗0给出E[[x，y]]=.1−1/q，x=y;（十六）−1/q，x/= y。对于S[n]，设ESdentej∈[n]Esj 其中，如果j S，则sj=1 ，并且sj=0，则w是e。这些矩阵是正交投影：ESES′=我们通过以下方式从（10）中找到了矩阵GES，S= S′0，否则。（十七）..′E1=10其中αS（M）与（2）相同。GM=αS（M）ES，（18）S[n]11. . ΣΣ0||| |1∅拉吉˜∆∆˜MΣM我是17岁。 我在第5节中找到了一个问题。2，所有的XM数据都是用于执行全局操作（12）和MProof. RecaltGM=qn/|XM|GM[[XM，Y]]，hence，by（18）：你好，|XM|rwsandd|Y|在此基础上，我们还将继续努力，S1SQn1Qn∅|X| |Y|M∈Cα-环己二烯（M）2Qn∅∅〇f（18）。该结果是一个在一个矩阵中的一个公式（10），但与一个由|= n（q n），则|= Ω(q n), thenrα-环己二烯（M）2M∈C.（十九）GM= .Qnα（M）En[[XM，Y]]+ .QnS（M）E S [[X M，Y]].|X M||S/=1000|S/=∅让我们计算GM的项的和s（GM）。在第一项中，En的每一项都等于q−n。X M/qnY αn（M）。我们主张，在第二个任期内，α S（M）= 0乘（2c）。否则，. αS（M）ES[[XM，Y]]对于所有S/= 0，如果S∈M，则s（E[[X，Y]]）=[x，y]]= q|S| −nΣE⊗|S|[[x，y]]=|XM|ΣΣE⊗|S|[[z，y]]= 0.y∈Y x∈XMy∈Y x∈XMy∈Yz∈[q]S(On第三步，使用正交条件（12）在最后一步，我们使用如果k >0，则Ek的每列的项的和总结一下，s（G）=.|XM ||Y |α（M）。我们现在准备好估计r。定义两个单位向量u∈RX和v∈RY，αβ（M）1u[[（x，M）]]=|X对所有的（x，M）∈X和y∈Y.然后，|ΣM∈C α（M）2andv[[y]]=|Y|<$r_v≥u<$r_v=<$r_v∈Cα_ v（M）s（G_M）M=.|Y|α（M）2= . α（M）2μ m。M∈CM∈C在本节的内容中，我们将找出用于处理Γ−→Γ′的数据的方法，并将这些特性将在后续章节中使用使用（16），我们可以定义E0和E1上的作用，E0−→E0和e1−→−E0.我们通过将这个变换应用于张量积中第j个位置的E0和E1来定义ΓG′=βS（M）ES，（20）S[n]其中βS（M）=αS（M）−αS<${j}（M）。特别地，如果j∈S或S∈M，则βS（M）= 0。因此，在本发明中，（Γ′）<$Γ′=<$（G′0SMSSMM12）G′=0。β S（M）2βE S.（二十一）M∈C在特殊情况下，我们在式（2b）中有一个条件，即α∈R′≤1。S∈2[n]M∈C13M∈C^^ ^您的位置：N∈J00MB.G.Σ^G=M，I我我M，IM，IΣ5.4有界生成的证书结构在本节中，我们完成定理5的证明。在定理的设置中，（11）中的正交表T（i）由于每个M只有一个包含式极小元素AM，因此我们在本节中删除所有上面的索引（i）。根据定理的陈述，我们有|X M|= q n−1，特别地，它们是非空的。还有，XM满足正交性质（12），并且，通过（13），我们有|=.|=. [q]n \M[∈CX条纹鲈 ≥q n—M∈C|= q|= q—|C|Qn−1Qn.（二十二）2因此，满足引理17的条件，并且（19）成立。回想一下在5.2节中，为了估计<$r′<$，我们考虑矩阵Γ′。 矩阵Γ ′是Γ′的子矩阵，因此，它足以估计Γ′。 设k = max M∈C|A M|. 因此，时间复杂度为O（1）。固定每个A M={a M，1，. . . ，一个M，|AM|}，且令L M，i，其中M ∈ C且i∈[k]，是满足以下性质的2[n]的子集• 对于每个M，集合2[n]\M是不交并集LM，1<$··<$LM，k;• 对于每个M和每个i≤|A M|，L M，i的所有元素省略a M，i;• 对于每个M和每个i，使得|A M|

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