量子计算机模拟器：SQRAM架构与编译器研究

理论计算机科学电子笔记170（2007）101-124www.elsevier.com/locate/entcs顺序量子随机存取机Rajagopal Nagarajan2，4Nikolaos Papanikolaou3，4华威大学计算机科学系Coventry CV4 7AL英国大卫·威廉姆斯1伦敦城市大学信息学院EC1V 0HB英国摘要我们提出了量子计算的SQRAM架构，它是基于Knill的QRAM模型。我们详细介绍了一个合适的指令集，它实现了一个通用的量子门，并演示了操作的SQRAM与Deutsch 被认为是编译的SQRAM机的高级量子程序，我们提出了量子汇编代码的模板和一种方法，用于分解复杂的量子操作的矩阵SQRAM模拟器和编译器进行了讨论，以及未来的工作方向关键词：量子计算，量子编程，量子模拟器，QRAM，编译器。1电子邮件：d. p. city.ac.uk2电子邮件：biju@dcs.warwick.ac.uk3 电子邮件地址：nikos@dcs.warwick.ac.uk4R。Nagarajan和N. Papanikolaou部分得到EPSRC赠款GR/S34090和欧盟第六框架计划（项目SecoQC）的支持。1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.12.014102R. Nagarajan等人理论计算机科学电子笔记170（2007）1011引言快速增长的量子计算和量子信息领域仍处于起步阶段，主要是由于缺乏实质性的实用量子计算设备。然而，这种装置的理论潜力得到广泛承认。目前，对于感兴趣的计算机科学家来说，唯一现实的研究途径是使用量子计算机模拟器。由于量子力学系统的状态空间很大，在经典计算机上很难实现对亚原子现象的完全模拟。诺贝尔奖得主理查德·费曼在1985年指出：“. . .如果用N个粒子来描述自然界的一个孤立部分需要N个变量的一般函数，如果计算机通过实际计算或存储这个函数来模拟这个函数，那么自然界的大小（N→2N）将需要模拟计算机的大小呈指数级爆炸性增长。（摘自[7]）费曼特别关注量子力学，他指出：“。. .具有R粒子由函数f（x1，x2，.，x R，t），我们称之为振幅，以找到x1，x2，.，x R，因此，因为它有太多的变量，它不能用普通的计算机模拟，与R成比例的元素数[。. . ]。”我们在本文中的目标要温和得多;我们感兴趣的是有限数量量子比特（qubit）上的局域量子计算。特别是，我们将讨论混合经典量子计算机架构的设计SQRAM设计基于Knill此外，我们还将定义一个SQRAM的虚拟实现的指令集，并说明这种操作。当运行Deutsch的算法来确定布尔函数的平衡性时的设备我们已经使用OpenQubit库实现了SQRAM机器的模拟器[14];这在D.威廉姆斯根据最近对量子语言的提议，包括，例如，QPL [15]，QCL [12]，CQP[8]和qSpec [13]，我们认为这是为了考虑高级量子程序的编译;我们讨论了这方面的技术，并提出了我们首先总结基本的量子计算概念。然后，我们将继续描述所提出的SQRAM架构和指令集;为了说明指令集，我们展示了Deutsch的算法如何R. Nagarajan等人理论计算机科学电子笔记170（2007）101103α22用汇编语言实现SQRAM。最后，我们将转向用QPL（一种函数式量子编程语言）编译2相关工作目前有几种量子模拟器可用，包括分析量子电路的工具和量子编程语言的解释器[3，12]。这里介绍的工作也与[2，12，15]中描述的工作密切相关，该工作涉及量子编程语言设计所涉及的问题。我们的工作开发了一套更完整的工具，包括单独的（但相互作用的）部分编译和模拟;它还允许编译代码被存储。在[16]中，定义了一个多层框架，它为量子计算机模拟器的不同抽象层次建模;然而，作者考虑了物理实现的具体方面;相反，我们仅仅依赖于假设所提出的系统架构可以用当今的硬件实现3量子计算基础有几个要点是有序的;我们假设没有量子计算的先验知识。量子位或量子位是具有两个基本状态的物理系统，常规地写为|0>和|1位，对应于一位经典值。例如，这些可以是电子的自旋态或光子的偏振态，但我们不考虑物理细节。根据量子理论，量子系统的一般态是基态的叠加或线性组合。一个量子比特有状态α| 0>+ β|其中α和β是复数，使得|α| +的|β| = 1;仅通过一个（复数）标量因子与mo_du_lux1区分的状态是不可区分的。状态可以用列向量表示：β = α| 0>+ β| 1.形式上，量子态是希尔伯特空间中的单位向量，即复向量空间，满足某些公理的内积。基础{|0，|1}被称为标准基础。其他的基有时也很有趣，特别是由向量组成的对角（或对偶，或Hadamard1 1|0+|（1）和|2016 - 02 - 22 00：00：00（|0⟩− |1）|1 ⟩)104R. Nagarajan等人理论计算机科学电子笔记170（2007）10122联系我们22⎦2封闭量子系统的演化可以用幺正变换来描述。如果量子位的状态由列向量表示，则酉变换U可以用复值矩阵（u ij）表示，使得U −1= U，其中U是U的共轭转置（即U的元素ij是u<$ji）。U通过y矩阵乘法作用：⎡ ⎤⎡αJ⎣ ⎦= ⎣βJ⎤ ⎡⎤u00u01⎦⎣αu10u11β幺正变换也可以通过它对基态的效应来定义，它线性扩展到整个空间。例如，Hadamard算子定义为：|+= 1|0分+1分|1⟩ |1⟩|−= 1|0⟩− √ 1|1⟩ |1⟩2 2⎡ ⎤它对应于矩阵H=用σ0、σ1、σ2、σ3表示，定义如下：1 1100万。泡利算子，21− 1⎡ ⎤ ⎡ ⎤1 0 0 1σ0=σσ1=0 1⎤σ=0−iσi0⎡1 0⎤1 0=0− 1测量在量子物理学中起着关键作用。如果一个量子比特处于状态α|0>+ β|然后测量它的值，结果有可能是0 |α|2（保持状态|结果1与概率|β|2（保持状态|《明史》（卷1）。例如，如果一个量子位处于|+则测量（相对于标准基准）给出结果0（并声明|概率为1，结果为1（和状态|概率为1。如果一个量子位处于|0则测量结果为0（并表示|概率为1。为了超越单量子比特系统，我们考虑空间的张量积（与经典系统中使用的笛卡尔积相反）。 如果空间U和V有基ui和vj，则U V有基ui vj。 特别地，由n个量子比特组成的系统具有2n维空间，其√⎡3R. Nagarajan等人理论计算机科学电子笔记170（2007）101105|⟩|⟩22222|⟩|⟩112标准的基础是00…0个...... 十一... 1 .一、 我们现在可以考虑测量单个量子比特或多个量子比特的集体测量。 例如，一个2量子比特系统具有基|00，|01>，|10分钟，|11 π，一般状态为α| 00 + β| 01 + γ| 10 + δ| 11、与|α|2个以上|β|2个以上|γ|2个以上|δ|2 = 1。测量第一个量子比特的概 率 为0|α|2个 以上|β|2（使系统处于状态√|α|+ 的|β|2（α| 00 + β| 01））和结果1的概率|γ|2个以上|δ|2.离开系统状态√|γ| +的|δ|2（γ| 10 + δ| 11.）;在每种情况下，我们重新规范化通过乘以适当的标量因子来计算状态测量两个量子位同时以概率给出结果0 |α|2（使系统处于状态|β |β| （使系统处于状态|01）等等;基态联合|00，|01>，|10分钟，|结果为0、1、2、3的11位数只是一个常规选择。量子计算的能力，在算法意义上，来自于状态叠加的计算;叠加中的所有状态同时变换（量子并行），并且效果随着状态空间的维度呈指数增长。量子算法设计中的挑战是进行测量，使这种并行性得到利用;一般来说，这是非常困难的。量子位对上的受控非（CNOT）运算符执行映射：|00 ⟩ |00 ⟩|01 ⟩ |01 ⟩|11 ⟩| 11 ⟩|10 ⟩| 10 ⟩这可以被理解为当且仅当第一个量子位（控制）被设置时反转第二个量子位（目标）。对一般状态的作用是通过线性得到的。两个或多个量子位的系统可以处于纠缠态，这意味着量子位的状态是相关的。例如，考虑状态1的第一个q比特的测量（|00+|11日）。结果为0（并且结果状态为00），概率为1，或者1（结果状态为11），概率为 1。在任一情况下，第二量子位的后续测量给出了与第二量子位的测量结果相同的确定的第一次测量。即使纠缠的量子比特在物理上是分离的，这也是正确的。纠缠说明了张量积（在量子系统中）和笛卡尔积（在经典系统中）之间的关键区别：两个量子比特的纠缠态不能表示为单量子比特态的张量积。Hadamard和CNOT运算符106R. Nagarajan等人理论计算机科学电子笔记170（2007）101可以结合起来创造纠缠态：1CNOT（（H I）|00）=2（|00 + |11）4SQRAM机器在本节中，我们提出了一个混合经典量子计算机的系统架构，由一个经典计算机器控制一个纯粹的量子力学组件。这样的设备，称为QRAM机，由Knill在[9]中提出。经典组件包括中央处理单元（CPU）、经典数据存储器（DS）和程序存储器（PS）。量子力学组件分为量子硬件接口（QHI），量子存储器寄存器和操纵其内容的方法;请注意，我们的讨论仍然独立于特定的硬件实现和相关的图1展示了SQRAM机器的总体设计，包括经典组件和量子组件。我们现在将描述这个设计的细节，包括它的操作周期和指令集。4.1经典成分经典组件有两个不同的内存位置，一个用于程序，一个用于数据。我们选择稍微偏离传统的冯·诺依曼模型，其中程序被以相同的方式处理，并且在相同的位置，作为他们操纵的数据。CPU通过程序计数器跟踪程序中的当前指令，程序计数器索引程序存储中的位置。CPU还包含一个CPU不包含任何寄存器，因为所有操作都在数据存储中执行。数据存储操作全局数据（如果适用）从地址0x 0000开始存储，而局部基点指向当前函数的局部数据的开头（这是修改的当函数被进入和离开时）。堆栈顶部点刚好在有效数据区。表1详细说明了用于控制经典COM的主要指令R. Nagarajan等人理论计算机科学电子笔记170（2007）101107经典组件Quantum组件的测量操作指令与量子态的相互作用0x0F读/写栈顶0x0000数据存储局部基 0x000F局部基0xFFF0 StackTop0xFFFF0x00Quantum硬件接口中央处理单元程序计数器控制单元算术逻辑单元程序存储器SQRAM的一个组成部分，并描述了每个指令的后果，在一个al-租记法。该符号包括符号st（栈顶）、lb（局部基址）、pc（程序计数器的值）、DS[i]（数据存储中位置i的内容）和PS[i]（程序存储中位置iSQRAM的操作周期如下。程序执行开始时，程序计数器、局部基址和栈顶都初始化为0。从程序计数器给定的位置检索指令并执行，然后重复该过程。大多数指令导致程序计数器递增，但有些指令（如跳转和停止指令）对可用经典指令的列表有不同的影响一旦程序计数器超过程序存储的末尾，程序执行就结束了关键字：数据存储超出范围数据存储正在使用数据存储尚未分配Fig. 1. SQRAM机器量子寄存器108R. Nagarajan等人理论计算机科学电子笔记170（2007）101指令E. E.添加st← st−1DS[ st−1]← DS[ st−1]+ DS[ st]pc← pc+1停止PC←大小（PS）JUMPZ地址st← st−1如果（DS[st-1]=0）：pc←地址否则：pc← pc+1LOADo setDS[ st]← DS[ lb+o set]st← st+1pc← pc+1LOADL值DS[ st] ←valuest← st+1pc← pc+1SAVEo setst← st−1DS[ lb+o set]← DS[ st]pc← pc+1减去st← st−1DS[ st−1]← DS[ st−1]− DS[ st]pc← pc+1表1SQRAM机器经典指令集4.2量子组件SQRAM的量子组件由一个量子寄存器和一个量子硬件接口（QHI）组成，QHI接收来自CPU的指令并相应地操纵量子位。图2示出了一个R. Nagarajan等人理论计算机科学电子笔记170（2007）101109--初始化和加载量子态演化状态的测量检查必要时重复图二. SQRAM操作周期典型的量子算法在图2的第一阶段，硬件将量子位重置为|0的初始状态，然后应用一些转换将它们置于所需的初始状态。第二阶段是量子态的操纵实际发生的地方。计算完成后，测量结果;每个测量的量子位产生一个二进制值0， 1，传递给CPU，然后可以用于条件控制目的。最后阶段检查结果的有效性，并在必要时重复计算。可能会出现不正确的结果，或者是由于硬件问题，如破坏量子态的退相干，或者是由于量子算法的概率性质正如第3节所解释的，通过对状态施加一系列操作来变换状态;这些操作可以对任意数量的量子比特进行操作，唯一的限制是它们必须是幺正的。虽然从理论的角度来看这是准确的，但目前很难在任意数量的量子位上实现任意操作。幸运的是，我们知道有一个小的运算集合（实际上是无限多个这样的集合），它是通用的，因为它能够近似任意运算到任何给定的精度。现在我们介绍构成这些泛集之一（称为标准集）的运算。第一个操作是受控非（CNOT），我们之前已经描述过。该操作可以与任意单个量子比特操作相结合，以在任意数量的量子比特上精确地为了完成标准集，有必要近似任意单个量子比特操作。在标准集合中，这是用Hadamard算子（用H表示），相位算子（S）和π/8算子来完成的。 我们使用标准集作为SQRAM指令集的基础，以及测量和初始化指令，以及用于控制目的的经典指令集。我们还包括一个指令，用于对单个量子位执行任意操作。SQRAM的本表中使用的特殊符号包括符号target（用于目标量子位）、control（用于控制量子位）和invert（表示当控制处于状态时，CNOT处于活动状态|0、宁110R. Nagarajan等人理论计算机科学电子笔记170（2007）101指令E. E.AQBITQR [qst] ←|0⟩qst← qst+1pc← pc+1CNOT目标控制逆变器QR[ target]← target× cnot（ control，invert，.. ）pc← pc+1浇口目标a b c dQR[ target]← target× gate（ a，b，c，d）pc← pc+1HDMD靶1 1 1 1QR[ target]← target× gate（2，2，2，−2）pc← pc+1MSRE目标DS[ st]<$ measure（ target）st<$st+1pc← pc+1阶段目标QR[ target]← target× gate（1，0，0，i）pc← pc+1PI目标iπ/4QR[ target]← target× gate（1，0，0，e）pc← pc+1表2SQRAM机器量子指令集比|1）;否则，符号大多是不 言 自 明 的 。4.3SQRAM机上的Deutsch我们现在给出一个为SQRAM机器编写的程序的例子。我们将使用[ 5 ]中给出的Deutsch我们有一个有四种可能的函数f（x）可以执行，这些是f（x）=0，f（x）=1，f（x）=NOT（x），和f（x）=x。其中前两个称为常数，因为它们总是给出相同的结果，而后两个称为平衡的，因为一半的输入结果为0，一半的输入结果为0。R. Nagarajan等人理论计算机科学电子笔记170（2007）101111⊕⊕| ⟩| ⟩结果为1。问题是使用尽可能少的函数求值来确定f（x）是常数还是平衡的。如果以经典方式执行，则需要两个函数求值，一个输入为0，另一个输入为1，并对结果进行比较然而，在量子计算机上使用Deutsch 注意，如果函数是常数，那么f（0）f（1）= 0，而如果它是平衡的，那么f（0）f（1）=1。使用图3中的电路，可以计算f（0）f（1），而无需找出f（0）和f（1）的值。|0>|1>图三. 实现Deutsch算法的电路图4中给出了用于SQRAM机器的Deutsch算法的实现，该算法用于测试NOT门的平衡性。非门是平衡的，所以计算f（0）<$f（1）的结果应为1。与电路表示相比，该代码涉及额外的初始化，因为所有量子位自动置于状态0。 第二 量子位实际上需要被置于状态1 ;这是使用NOT操作实现的。注意，NOT操作是使用GATE指令实现的;它也可以使用不带控件的CNOT来实现。操作U f是f（x）-controlled-NOT的可逆形式;它执行映射|X轴|关于我们|x，y<$f（x）<$.在我们的示例中，f（x）-|0 ⟩.这个例子主要说明量子指令;大多数读者应该熟悉经典指令所执行的功能。本例中使用的唯一经典指令是SAVE，它将测量结果存储在经典堆栈的顶部。进一步的代码可以基于该值有条件地跳转以向用户提供反馈4.4模拟SQRAM为了评估和分析的SQRAM的设计，我们已经开发了一个软件模拟器。量子力学系统的模拟是一个非常复杂的问题（如引言中所讨论的），因此我们的模拟器只处理相对少量的量子位。当然，有几种已知的量子算法只使用了几个HXHUfHy112R. Nagarajan等人理论计算机科学电子笔记170（2007）1010x10xESQRAM10xF0x0Qnqn−1qn−2年q4年q3Q2年q1q0AQBITAQBIT;分配初始量子位栅极0x01 0.0 0.0 1.0 0.0 1.0 0.0 0.0 0.00.0;将第二个量子位初始化为1HDMD0x00应用阿达玛HDMD0x01CNOT0x01 1 0 1;应用CNOT门HDMD0x00最后的阿达玛MSRE0x00测量结果拯救0x00;保存到地址0x 00以供以后使用见图4。 实现非门Deutsch算法的SQRAM汇编程序量子比特;我们已经成功地模拟了这些。模拟器使用OpenQubit库[14]。这是一个开源C++库，旨在用于涉及量子系统建模的项目。它提供了用于表示量子系统（存储大型我们的模拟器直接实现了经典组件和模拟的SQRAM机器的体系结构尽可能与前面介绍的相匹配。模拟器和图1所示设计之间的一个关键区别是在量子寄存器和处理器之间放置了一个额外的抽象层。模拟器提供了一个量子比特的宇宙图五. SQRAM机器通过引用R. Nagarajan等人理论计算机科学电子笔记170（2007）1011135为SQRAM使用前一节中介绍的汇编语言指令手工编写大型程序是不切实际的;这既耗时又容易出错。量子编程语言的出现，可以自动编译成相应的机器代码，大大促进了“量子编程”的任务量子编程语言提供了经典控制结构和量子操作的优雅混合量子编程语言的使用非常适合我们的SQRAM机器（以及大多数量子算法）使用的计算模型。这种计算模型比电路模型更熟悉计算机科学家，我们预计它将大大简化新量子算法的开发。在本节中，我们将考虑我们首先确定这些语言的某些理想特征和特殊性，然后我们继续讨论Selinger我们已经实现了从QPL的一个子集到SQRAM汇编代码的翻译，这也是简要描述。5.1Quantum编程语言要求根据[2，9，15]，高级量子编程语言的期望特征经典特征：多年来对经典语言的研究已经确定了一些属性，如清晰的语法和直观的关键词集完整性：量子编程语言应该是通用的，这样它就可以代表所有的量子算法。这使它具有与量子电路模型相同的表达性：语言应该为程序员提供足够的原语和构造集，以允许轻松构建量子程序。可分离性：将程序中量子力学性质的部分与经典部分分开应该很简单硬件独立性：量子编程语言应该是114R. Nagarajan等人理论计算机科学电子笔记170（2007）101便携式，即，独立于特定的硬件平台。一种语言应该尽可能地保持通用性，甚至可以使用量子图灵机作为其目标平台。经典语言的扩展：扩展了已知经典语言的量子编程语言可能会比全新的语言找到更广泛的用户群。5.2量子系统的特殊性及其实现语言设计克隆未知量子态的能力对涉及赋值的语句的行为有直接影响;这些语句包括直接赋值和向函数传递值。因为实际上不可能复制值，所以许多语言使用引用，因此有许多变量指向同一个量子位。其他语言可能禁止量子变量的直接赋值。尽管如前所述，不可能将一个量子位分配给另一个量子位，但可以将一个量子位分配给经典位;这涉及隐式测量。与经典编程不同，这将修改赋值右侧的变量，并且不可能恢复以前的值。两个量子位由不同的变量名标识，它们可能会纠缠在一起，因此对一个变量的操作会对另一个变量产生影响。在经典编程中没有类似的东西，但这对程序员来说比对语言设计者来说5.3函数式量子程序设计语言QPL有几种语言在不同程度上满足了以前提出的要求[2，9，12]。我们的工作特别关注Peter Selinger塞林格将静态类型系统确定为QPL的关键特性之一;这允许语法强制执行量子理论的某些要求，例如不可克隆定理。与通常的控制结构一样，如循环和条件语句，QPL允许递归函数的定义。这在对列表和树进行操作时很有用，在QPL中，这些列表和树可能包含量子和经典数据。QPL的语法从图6中的[15R. Nagarajan等人理论计算机科学电子笔记170（2007）101115QPLTermsP，Q：：=新位b：= 0| new qbit q := 0|b：=0|b：= 1 |b := 1| q1,...，q n = S|skip|P; Q| 如果b那么P否则Q| measureqthenPelse Q| 而b做P| proc X : Γ → Γ J{P } in Q| y1,...，y m= X（x1，.，x n）见图6。 彼得·塞林格的QPL的语法5.4Quantum操作代码生成，对于我们的目的，是产生机器指令的过程中的每个节点的抽象语法树对应于一个高级程序。我们设计了QPL语言中量子结构的代码模板，并且我们还考虑了大型操作的分解，因此它们可以直接使用有限数量的可用指令来实现。代码模板在编译器中用于提供一组汇编指令，这些指令对应于源程序中的特定构造，例如表达式、循环或变量声明。我们现在将为那些本质上是量子的构造定义代码模板;我们在这里不会给出经典构造的细节。具体来说，我们将涵盖量子数据的声明，其操作和最终测量。 高级QPL构造到相应SQRAM汇编代码的映射翻译：QPLTerms›→ SQRAMTrms在QPL中，一个新的量子位使用以下语句声明（新qbitq：= 0）这将分配一个新的量子位，由变量名q表示，并将其分配给状态|0分。为了实现这一点，我们简单地使用AQBIT指令：转换[（新qbitq：=0）] =AQBIT116R. Nagarajan等人理论计算机科学电子笔记170（2007）101∗∗| ⟩使用=运算符将转换应用于量程数据类型。例如，内置的酉变换U可以应用于q如下：（q=U）。这里有两种情况需要考虑。 首先，U可能是我们希望直接使用GATE指令实现的单个量子位操作。这就变成：平移[（q=U）]=门q U或者，U可能是无论哪种方式，我们都将进入5.5节讨论的分解过程。度量是最复杂的代码模板（假设我们在操作量子类型时不涉及分解）。QPL通过以下声明进行测量：measureq thenP elseQ对量子位q执行测量。如果测量结果为1，则执行对应于P的命令，否则执行对应于Q的命令。 代码模板如下所示：转换[测量q，然后 P，否则 Q]=MSREQ;执行测量Jumpz其他 ;如果result为0，跳转到ELSEP;如果结果不为0，则执行命令P。LOADL0;无条件跳转到结尾，Jumpz端;通过加载0并跳转到0。否则：Q;执行命令Q。结束语：;结束。如果q的测量值为1，则忽略JUMPZ指令，程序在无条件地跳过代码以执行Q之前继续执行P。另一方面，如果q被测量为0，则第一个JUMPZ跳过P的执行，直接跳到Q被执行的点。R. Nagarajan等人理论计算机科学电子笔记170（2007）101117U1nU2nUnn生成原始操作以近似单个量子位操作。用单量子比特操作和CNOT生成CNOT门序列，以允许受控单量子比特操作实现生成一组两级酉矩阵输入U11U12U21U22Un1Un2阶段1阶段2X第3阶段第4阶段输出见图7。 任意酉矩阵5.5算子矩阵在4.2节中，我们讨论了普适性原理，指出任何量子操作都可以分解并以一小组普适门的形式实现。因此，我们的SQRAM机只提供相应于这些通用门的操作，编译器的工作是执行分解。这种分解是一个复杂的过程，各种不同的人和研究小组已经完成了这项工作。我们把这些工作放在一起，形成一个完整的编译过程，并提供其效率的分析。5.5.1概述将矩阵分解为原语操作是一个多阶段的过程（如图7所示）;下面的部分将描述每个阶段。该过程的每个阶段的有效性的数学证明已经很好地建立，并且之前已经完成了可以用于近似给定酉矩阵的最佳门数的工作[11]。因此，本工作的重点是设计算法来实现该过程，并对这些算法进行经典的效率分析据我们所知，它已经实现了一个工作编译器来测试下面几节中提出的概念，但我们不会在这里讨论它的实现有关详细信息，包括设计方法、示例和样本输出，请参见[18]。118R. Nagarajan等人理论计算机科学电子笔记170（2007）101=2⎥5.5.2二级酉矩阵的两级酉矩阵是那些只对系统状态的2个向量分量起非平凡作用的矩阵;也就是说，当向量乘以矩阵时，只有两个元素改变，因为矩阵中的大多数元素是单位的。这种矩阵具有如下结构：- 是的. . . .⎢⎢⎤. . .⎥⎥⎢··· 1 0 0··· 0 0 0···⎥⎢ ⎥⎢ ⎥⎢···0α 0··· 0γ 0···⎥⎢ ⎥⎢ ⎥⎢··· 0 0 1··· 0 0 0···⎥⎢⎢Rk⎢⎢. . .⎥. . . . . .⎥⎥⎥（一）⎢··· 0 0 0··· 1 0 0···⎥⎢ ⎥⎢ ⎥⎢··· 0 β 0··· 0δ 0···⎥⎢ ⎥⎢ ⎥⎢··· 0 0 0··· 0 0 1···⎥⎣. . .. . .⎦. . .初始步骤是将边长为s的原始矩阵U分解为一系列二级酉矩阵（也是边长为s）。这个序列中矩阵的乘积必须等于输入矩阵U，因此以正确的顺序将它们应用于系统与应用U具有相同的效果。执行这种分解不仅是下一阶段所必需的，它本身也是一个结果在[ 20 ]中描述了一种用分束器设备实现这种变换的技术，其结果是，简单地我们将不深入研究所涉及的数学，因为它可能变得相当复杂;关于这一点的报道见[20，18，11]。已经观察到[11]，这样的过程将把原始矩阵分解成至少mosts（s−1）两级矩阵。 然而，没有分析这种方法提供了一种算法，并且确定这一点是有用的结果。在[18]中，我们对变分的效率做了一些假设，并证明了复杂度近似为Θ（n5）。这显然不是一个快速的算法，并且应该注意的是，前面的分析是关于矩阵的大小的（其在系统的大小中是指数的）。因此，该算法总体上需要指数时间，但也应该记住.R. Nagarajan等人理论计算机科学电子笔记170（2007）101119⎢|⟩|⟩|⟩|⟩⎢⎣⎥⎢⎥⎥|⟩|⟩它通常将在小的n值上操作，对应于少量的量子比特。此外，执行这种分解的困难清楚地表明，有必要具有可以存储的量子5.5.3产生受控酉门和CNOT门我们从前一阶段获得一组两级酉矩阵，例如以下形式的矩阵：⎡ ⎤⎢α0 0γ⎥⎢ ⎥⎢0 1 0 0⎥U=0（二）⎢0 0 1 0⎥⎣ ⎦β0 0δ这样的矩阵作用于系统的两个分量（在这种特殊情况下，它作用于00和11），并使其他分量不被考虑，如下所示：⎡ ⎤ ⎡ ⎤⎢|00 ⟩ ⎥⎢ α |00 + γ |11 ⟩ ⎥⎢ ⎥ ⎢ ⎥⎢|01 |01 ⟩⎥（三）⎢ ⎥−→⎢ ⎥⎢10⎥⎣⎦|11 ⟩⎢10⎥⎣ ⎦β|00+ δ |11⟩我们希望用受控的单量子位操作或受控U门来实现这个矩阵 因此我们使用一系列CNOT门（在这个简单的情况下，该系列仅包含一个门）来交换状态，使得目标状态彼此相邻。然后将受控U应用于仍在发生变化的1位，并使用反向系列的CNOT门将状态排列回其原始位置。为了阐明该过程，等式2给出的运算由图8中的电路实现，其中T是U的⎡ ⎤α γT=100 （4）β δ120R. Nagarajan等人理论计算机科学电子笔记170（2007）101| ⟩| ⟩不见图8。实现等式2的电路。注意，当控制量子位为0时，CNOT门是有效的，而不是更传统的1。接下来的问题是如何生成一系列CNOT门，以适当的方式重新排列计算状态。涉及使用格雷码的解决方案由[11]覆盖，并且在我们的编译器的上下文中的描述由[18]提供。5.5.4实现受控的单一门第5.5.3节中描述的过程的输出由两种类型的门组成：受控非门和受控U门。我们的SQRAM机能够直接实现受控非门通过CNOT指令，但受控U门需要进一步的分解。本节简要介绍了如何在Barenco等人 [1]的工作基础上实现这一点。请注意，我们将只考虑Barenco等人观察到，对于边长为2的任何酉矩阵U（即在单个量子比特上操作），可以找到3个以上的酉矩阵A，B和C，使得：A×B×C=I以及：S×A×NOT×B×NOT×C=U其中S定义为：⎡S=⎤eiδ0 ⎦0eiδA 对于由多个量子比特控制的酉门，过程是类似的;我们找到一组酉，它们可以实现原始酉矩阵，也可以实现单位矩阵，这取决于在两者之间使用CNOT门。然而