理论计算机科学电子笔记270（2）（2011）155-161www.elsevier.com/locate/entcs单向模式的可编程哈密顿量S.沙莱克河 F.赛凡A E. Kashefiba伊朗德黑兰大学数学、统计和计算机科学系b英国爱丁堡大学信息学院摘要我们构造了一族与时间无关的哈密顿量，它们能够进行普遍可编程的量子计算。该构造是通过将单向计算机汇编语言代码直接翻译成Hamilton演化来获得的。我们还介绍了如何演化的哈密顿。希望这种方法有助于进一步研究量子计算的基于测量的模型和绝热模型关键词：哈密顿演化，绝热演化，通用量子计算机，量子电路模型1介绍在Feynman提出量子计算机之后，已经最近，出现了明显不同的模型，即绝热量子计算（AQC）[2，4]和基于测量的量子计算（MBQC）[5，6]。这些新模型提出了不同的体系结构和容错方案，并为新的应用和算法提供了特定的方法，以及比较经典和量子计算的特定方法。本文的中心问题是研究MBQC和AQC之间的结构关系。已经提出了几种给定电路的绝热模拟方法[7，8]。这些方法本质上是基于将电路重写成每轮中具有很少门的计算轮，然后用于构造相应的局部哈密顿量。在另一种方法中，已利用绝热演化来使MBQC计算更鲁棒[9]。我们的构造不同于以前已知的结果，提出了一种可编程的哈密顿构造1571-0661 © 2011由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2011.01.029156S. Salek等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）155F不不 t−1不 t−1不这导致了绝热演化。可编程模型是包括“程序”和“数据”区域的模型，并且程序区域的状态确定哪些操作将被应用于数据寄存器。因此，我们可以有一个可编程的模型，而不是为每个特定的问题硬布线，并通过软件为不同的问题初始化程序区域的状态。此外，我们通过使用几何时钟实现了我们的构造的局部性。我们的方法也可以很容易地适应继承固有的并行结构的MBQC，但是会有一个权衡之间的并行性和所需的尺寸的物理系统，以实现建设。费曼哈密顿量[10]是第一个考虑计算机的两个寄存器的构造，一个用于数据，另一个用于他所谓的游标：不1H=Uσ+σ−t=1+U<$σ +σ−（一）其中T是要应用的酉变换的数量，σ+和σ−是K K在T+ 1个游标量子位中的第k个游标量子位上提升和降低运算符后来，Kitaev构造了一个类似的哈密顿量，将量子电路编码为哈密顿相互作用[11]。他考虑了一个有两个寄存器的系统，时钟寄存器和工作寄存器。KitaevHkitaev=H prop+H out+H input（2）第一项的基态是历史状态上的均匀叠加，并检查计算的正确传播，第二项确保Hkitaev仅对于在相应电路的输出上提供“是”答案的输入状态具有低本征值。最后，最后一项检查辅助量子比特的正确初始化。在Kitaev之后，其他人构造了具有不同性质的不同哈密顿量，例如作用于直线的哈密顿量[12]。虽然这些与时间无关的哈密顿量对于量子计算是通用的，但是也可以通过绝热演化来模拟具有与时间相关的哈密顿量的任何量子电路[2]。在绝热量子计算中，我们选取两个作用于我们系统的哈密顿量：Hinit和Hfinal，其中第一个哈密顿量的基态很容易构造，而最终哈密顿量的基态编码了问题的解。我们考虑含时哈密顿量为H（s）=（1−s）Hinit+sHfinal。 绝热定理指出，如果对所有s，H（s） 有一个唯一的基态，那么对于任何固定的δ>0，如果.||1+ δ||1+ δΣ[0，1]{Δ2+δ（H（s））}那么，根据H对于时间T的绝热演化的最终状态是接近于l2-norm到Hfinal的基态。[1]在[13，8]中证明了该模型与量子电路的等价性。另一方面，Raussendorf和Briegel [5，6]介绍了一种称为单向量子计算机的相对不同的模型，其中其代数结构为：1 矩阵范数是谱范数，定义为||H|| =最大w||HW||//下一页||W||.电话+1T≥Ω（三）S. Salek等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）155157我αJ我在[1]中对这一问题进行了形式化，并提供了一种简单的单向计算汇编语言。该语言的基本命令是：1-qubit preparationsNi，其准备状态中的qubit i| + i，2量子比特纠缠算子Eij：=Zij（受控-Z），1量子比特测量M α由正交投影定义|±α⟩⟨±α|i，应用于量子位i，约定是|+ α + α|i对应于结果0，而|−α⟩⟨−α|i对应于1，1-量子位泡利校正Xi，Si，其中i，j表示这些操作中的每一个所应用的量子位，并且α是[0，2 π）中的参数。量子比特最多被测量一次，因此我们可以明确地表示在量子比特j处进行的测量的结果。用于控制非确定性的偏差校正将被写为Xsjsj0 01 1i和Zi，其中Xi=Zi=I，Xi=Xi，并且Zi=Si。测量模式，或简单地说，一个模式，是由V的选择定义的一组有限的量子位，两个可能重叠的子集I和O决定模式的输入和输出，以及一个有限的命令序列作用于V。人们可以将单向量子计算的两个主要优点视为具有内在的并行结构[14]和用于算法设计的丰富的图论工具包[15，16，17]。一般来说，一个具有这些特性的模型，除了具有可编程和鲁棒的连续时间演化的优点之外，是本文的主要目标。第一步是将单向模式转换为哈密顿演化，这将在下面介绍2哈密顿构造在这里，我们希望构造一个能够进行通用量子计算的哈密顿量，该哈密顿量可以用单向汇编语言编程。我们的哈密顿量类似于[18]中的构造，但底层的汇编语言是不同的，因为它是基于单向模式的。如前所述，单向量子计算是通过纠缠算符、泡利校正和具有角度α的单量子比特测量来执行的。然而，由于测量不能连续进行，我们必须重写单向模式，其中测量是相干实施的[19]，以便能够构建哈密顿量并连续地对其进行演化。接下来，我们用状态的受控门替换测量及其相关校正，对应于测量的角度，用所需的泡利校正张量XsiMα→Xα：= |−α⟩⟨−α|iX+|+ α+α|ii最近邻交换门将被添加到我们的命令列表中，以构建最近邻哈密顿相互作用。换句话说，我们可以使用几个交换门来执行我们的命令，只对最近的邻居起作用。因此，我们有一个新的汇编语言的单向模式与命令序列是{Si，Xi，Ei，Ii}（4）其中，命令Ai作用于量子位对（i，i+1），并且Ii代表身份158S. Salek等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）155Σ†Σ操作符，该操作符将用于帮助指针按时到达其正确位置（见下文）。在[18]中，作者对构建作用于一维的哈密顿量感兴趣，因此他们必须考虑额外的数据量子位并将其准备在|0的状态，以使它们远离门的影响，在它们的构造中，门是正常控制的门或交换或身份。然而，在我们的构造中，我们使用通用的控制门，所以|0状态不适合我们的情况。因此，我们在物理上区分程序和数据寄存器，并在|+n态，就像传统单向模式中的量子位一样（我们稍后将讨论任意输入的情况）。最后，为了实现连接单向计算的离散时间步长和哈密尔顿算子的连续演化的几何时钟的概念，我们将指针符号D和空符号·添加到我们的命令序列中，其中它们的作用定义如下[18]。• 规则1：程序寄存器中的符号可以向左移动一步，如果该位置有一个空符号• 规则2：当一个命令遇到一个指针符号时，它们在程序寄存器中交换，它们下面的两个量子位被命令取代。为了给我们的计算机编程，首先我们需要初始化程序寄存器，某种风格。程序寄存器的长度是L=2M=2KN，其中K是命令序列的数量，M是除了D和·之外的命令的数量，并且N是数据量子位的数量。 我们必须初始化左半部分程序寄存器在位置kN处具有K个指针，k= 1，···，K，并且在其他地方具有空符号。右半部分包含命令序列，每个命令序列前面都有一个附录中给出了一个简单的例子现在，我们可以用费曼开始的同样的洞察力为通用量子计算构造一个哈密顿量，即一个哈密顿量，使得它的基态是历史态的叠加L−1HEMC=−（R+R）（j，j+1）（5）j=1其中R对应于上面R=A∈{S，<$Xα，E，I}|p1，p2=d1，d2+|AD DA|p1，p 2 A d 1，d 2（6）|p1,p2⊗Ad1,d2(6)其中P代表相应编程命令的编程寄存器，D代表相应编程命令的数据寄存器。最后一步是设计绝热算法来准备H EMC的基态，这是下一节的主题。最后，我们对这一部分的平行性做一个评论。在我们的构造中，为了实现单向模式的相同深度复杂度，我们可以首先使用[1]中介绍的信号移位方案处理测量的所有Z依赖性，然后使用[14]中介绍的技术并行化所得的受控门然而，这将影响程序寄存器的尺寸。局部性和排比之间的结构联系的研究超出了本文的范围，需要进一步的调查。S. Salek等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）155159好吧K你好，一.L.null.Ni−.最终的我我2不t−1t−1不2002LLnullnulli=1i=03H-EMC的绝热演化在这一部分，我们将展示如何获得绝热量子计算的基础上，on our architecture建筑.我们有兴趣在初始和最终配置之间进行插值。然而，我们的初始和最终哈密尔顿算子必须与不可编程模型不同，因为我们的哈密尔顿算子必须同时准备程序和数据寄存器的状态，而不像以前的工作那样只需要准备输入数据状态。在下文中|φi是系统在步骤i的状态。对于初始哈密顿，我们惩罚所有不希望作为初始状态的配置-是的D.D.i=1nullK−1（j+1）N−1j=0i=jN+1· - 是的·（K+1）N..-是的一个小女孩。 A.-i = KN+1。++的版本。i−i=（K+1）N+1。努尔null.我其中N，K和L与上一节中定义的相同，并且所有的量子位 编制|+100。 这确保了基态精确地|φ0 °为了定义最终的哈密顿量，如[13]中所讨论的，我们需要有一个哈密顿量，其基态是历史状态的总和与直接使用HEMC可能导致一些退化的情况不同，我们在HEMC中加入了惩罚项，它更喜欢过渡元素。L−1LH：= 0|φ ⟩⟨φ |− 1Σ|φ ⟩⟨φ|+的|φ⟩⟨φ|+1|φ⟩⟨φ|+1|φ⟩⟨φ|（八）文[13]中的证明是文[8]的改进，证明了这些哈密顿量的谱隙是命令数的逆多项式因此，我们的初始和最终哈密顿量之间的插值可以精确地执行4结论在本文中，我们构造了一个局部哈密顿量，它可以编程通过直接翻译的单向模式的相干实现的测量的基础上。我们还证明了这个哈密顿量的基态我们的哈密顿算子与以前的绝热证明不同，因为我们的构造必须在我们所需的状态下准备数据和程序寄存器，以保持我们的构造既绝热又可编程。我们的哈密顿量的局部性和对最终状态进行绝热计算的能力将使我们对退相干具有更强的鲁棒性此外，从单向模型的汇编语言的概念关于混合架构，仍有许多问题有待解决。除了保持系统处于基态，我们还将寻求使用实际测量的方法，Hinit：=I−（七）我160S. Salek等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）155似乎不兼容，但一种特殊的方法已经在[9]中进行了确认作者希望感谢Afsoon Ebrahimi的有益讨论。引用[1] V. Danos，E. Kashe fi和P. Panangelo。测量微积分。ACM杂志，54，2007。[2] E. Farhi，J. Goldstone，S. Gutmann和M.吸嘴绝热演化的量子计算。quant-ph/0001106。[3] D. 德语 量子计算网络。 罗伊检察官Lond A，425，1989年。[4] E. Farhi，J. Goldstone，S. Gutmann，J. Lapan，A. Lundgren和D.普雷达量子绝热演化算法应用于NP完全问题的随机实例Science，2001.[5] R. Raussendorf和H.J. 布里格尔单向量子计算机物理评论快报，86，2001。[6] R. Raussendorf和H. J·布里格尔 单向量子计算机的计算模型。量子信息计算，2，2002。quant-ph/0108067。[7] D. Aharonov，W. van Dam，J. Kempe，Z. Landau，S. Lloyd和O.雷格夫绝热量子计算等价于标准量子计算。《暹罗杂志》，2007年，第37期。[8] P. Deift，M. B. Ruskai和W.斯皮策绝热演化模拟量子电路的改进能隙估计。量子信息处理，2007年6月。[9] G. K. Brennen和A.三宅 基于测量的带隙基态量子计算机一个两体哈密顿量。物理评论快报，101，2008。[10] R. P. 费曼量子力学计算机。物理学基础，16，1986。[11] A. Y. Kitaev，A. H.沈，和M。N.维亚利经典与量子计算数学研究生课程美国数学学会，2002年。[12] D. Aharonov，D.Gottesman，S.Irani和J.肯普量子系统的力量在线。在FOCS '07会议录LNCS，2007年。[13] D. Aharonov，W. van Dam，J. Kempe，Z. Landau，S. Lloyd和O.雷格夫绝热量子计算等价于标准量子计算。FOCS'04 - Symposium on Foundations of Computer Science的论文集LNCS，2004年。[14] A. Broadbent和E.Kashe fi. 关于量子电路的平行化计算机科学，2009年。[15] 诉Danos和E.Kashe fi. 单向模型中的决定论物理评论A，2006年。[16] D. E. Browne，E. Kashe fil，M. Mhalla和S.珀德里克斯基于测量的量子计算中的广义量子流和决定论。新物理学杂志，2007年9月[17] N. de Beaudrap，V. Danos，E. Kashe fi和M. 罗特勒 酉的二次形式展开。量子计算、通信和密码学理论第三次研讨会，TQC 2008东京，日本，计算机科学讲义第5106期， 2008年。[18] D. Nagaj和P.Wocjan 一维哈密顿量子元胞自动机物理评论A，78，2008。[19] R. B. Gri alphths和C.妞妞。量子计算中的半经典傅里叶变换。物理评论快报，76，1996。S. Salek等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）155161附录下面的配置序列显示了如何初始化和执行从单向模式Xs1M0E12获得的程序。2 1q1q1I E ·IDX0·Dq1I E I·X0 D·Dq1I E IX0 ·D·Dq1•D•D•D··我D我·我年q1D年q1EEQ2EQ2D我的X0我的X0我的X0q1·我DE•我DX01000
我的内容管理
展开
