有限维Hilbert空间与匕首紧闭范畴的完备性

理论计算机科学电子笔记270（1）（2011）113-119www.elsevier.com/locate/entcs有限维Hilbert空间对于Dagger紧闭范畴是完备的（延伸摘要）彼得·塞林格1加拿大新斯科舍省哈利法克斯达尔豪西大学数学与统计系摘要我们证明了一个方程由匕首紧闭范畴公理导出当且仅当它在有限维希尔伯特空间中成立。保留字：匕首紧闭范畴，希尔伯特空间，完备性。1引言Hasegawa、Hofmann和Plotkin最近证明了特征为0的任意固定域k上的有限维向量空间范畴对于可追踪对称monoidal范畴是完备的[2]。这意味着一个方程在所有可追踪的对称monoidal范畴中成立，当且仅当它在有限维向量空间中成立。通过Joyal、Street和Verity本文有两个贡献：（1）我们简化了Hasegawa，Hofmann和Plotkin结果的证明1电子邮件：selinger@mathstat.dal.ca。由NSERC支持的研究。1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.01.010114P. Selinger/Electronic Notes in Theoretical Computer Science 270（1）（2011）113U、VV、U2主要结果关于匕首紧致闭范畴的定义、它们的术语语言和它们的图形语言，见[1，4]。我们还使用了匕首跟踪monoidal范畴的概念，这是一个带有跟踪操作的匕首对称monoidal范畴[4[3]满足TrX（f）t=TrX（f）。 我们注意到每一个匕首契约相反，通过Joyal，Street和Verity我们将利用图形表示的合理性和完整性，特别是以下结果：定理2.1（[4]）Dagger紧闭范畴语言中态射之间的良型方程由Dagger紧闭范畴的公理导出当且仅当它在图形语言中直到图同构都成立。一个类似的结果也适用于匕首跟踪monoidal范畴。本文的目的是证明以下内容：定理2.2设M，N：A → B是Dagger紧闭范畴语言中的两个项.假设[[M]] = [[N]]对于有限维希尔伯特空间中的每一种可能的解释（对象变量作为空间，态射变量作为线性映射）。 则M = N在图形语言中成立（因此，在所有匕首紧闭范畴中成立）。3减少在试图证明定理2.2之前，我们把这个陈述简化为更简单的东西。通过类似于长谷川、霍夫曼和普洛特金[2]的论证，不失一般性地考虑满足某些附加条件的项M、N。附加条件是：• 我们可以假设M，N：I→I，即， M和N的定义域和上定义域都是张量单位。这些术语被称为封闭的。对闭项的限制不失一般性，因为给定一般M，N：A→B，我们可以用两个新的态射变量f：I→A和g：B→I来扩展语言，并将定理应用于项MJ=g<$M<$f和NJ=g<$N<$f。由于g、f是新符号，图形语言中的g<$M<$f=g<$N<$f意味着图形语言中的M=N• 因此，我们可以考虑匕首追踪么半群范畴语言中的项M，N。也就是说，通过Joyal，Street和Verity这是通过消除出现的“n”操作来完成的：用一个等价的新态射变量（如fJ：BD→ACE）替换每个态射变量（如f：A BC→DE），该态射变量不使用“n”操作。P. Selinger/Electronic Notes in Theoretical Computer Science 270（1）（2011）113115• 它可以考虑图形表示不包含任何“平凡圈”的项平凡圈是图中不包含任何态射变量的连通分量，例如从恒等态射的迹中获得的变量。这种限制不失一般性，因为如果M，N具有不同的平凡圈数或平凡圈类型，则它们可以在Hilbert空间中容易地分离[2]。我们说一个图是简单的，如果它不包含平凡圈。4结果的非正式概要定理2.2的形式陈述和证明需要相当数量的符号，并将在其他地方给出。尽管如此，主要思想是简单的，我们在这里非正式地说明它。4.1签名、图表和解释我们假设给定一组对象变量，记为A、B等，和一组态射变量，记为f，g等。排序A是对象变量的有限序列。我们通常会写一个字母A... n表示n元序列，I表示空序列。我们假设每个态射变量f被赋予两个固定的排序，分别称为定义域A和余域B，我们写f：A→B。我们进一步要求态射变量集合上的无定点对合（−）<$，使得当f：A →B时，f：B →A。对象变量和态射变量的集合，连同域和上域信息以及匕首操作被称为匕首monoidal范畴的签名图形上，我们表示一个态射变量f：A1. A n→B1 Bm为盒AnBm.左边的连线称为f的输入，右边的连线称为f的输出。请注意，每个框都由一个态射变量标记，每个线都由一个对象变量标记。签名上的（闭单匕首对称跟踪幺半群）图由零个或多个上述类型的盒子组成，所有这些盒子的线都是成对连接的，这样每个连接都在某个盒子的输出线和某个（可能是同一个，也可能是另一个）盒子的输入线之间。 这里是图N的一个例子，在由f：B→A<$A，g：A<$B→. . .. . .一个2FB2的1B1116P. Selinger/Electronic Notes in Theoretical Computer Science 270（1）（2011）113a，a54B.N =在图中，我们将导线编号为1到5，以帮助下面的说明;请注意，此编号不是图的正式组成部分有限维希尔伯特空间中签名的解释由以下数据组成：对于每个对象变量A，选择一个有限维希尔伯特空间[A]，对于每个态射变量f：A1≠. A n→B1 B m，achosenlinearmap[f]]：[[A1]] . [[An]]→[[B1]] . [[Bm]，suchthat[f <$]]=[[f]]<$。在给定的解释下，图M的表示是一个标量，由通常的“内部指标求和”公式定义。例如，上图N的表示为：Σ[[N]] =[[g]]a1，b2·[[f]]b3·[[f †]] a5，a4.（4.1）a1，b2，b3，a4，a5b3，a1a5，a4b2这里a1，a4，a5在[A]的某个标准正交基上的范围，b2，b3在某个标准正交基上的范围，[B]的标准正交基]，[[f]] b3代表矩阵项a5a4|[[f]]（b3）众所周知，这种表示与标准正交基的选择无关4.2校样草图通过第3节中的约化，定理2.2是下列引理的一个推论：引理4.1（相对完备性）设M是一个（闭的单匕首跟踪monoidal）图. 然后在有限维希尔伯特空间中存在一个解释[[−]] M，只依赖于M，使得对于所有N，[[N]] M=[[M]] M成立当且仅当N和M是同构图。显然，从右到左的蕴涵是平凡的，因为如果N和M是同构图，那么[N]]=[[M]在任何解释下都成立;它们对应的求和公式至多通过被和项和因子的重新排序而不同。因此，必须证明的这个引理的一般证明需要相当多的符号，以及比我们上面给出的更仔细的定义。一个完整的证据将出现在其他地方。 在这里，我们通过一个例子来说明证明技术。A 1GB 3B2F一一45F+P. Selinger/Electronic Notes in Theoretical Computer Science 270（1）（2011）113117JKy取与上面相同的签名，假设M是下面的图：M =B同样，我们已经从1到5对电线进行了编号，这次，我们还对x、y和z框进行了编号。我们现在必须构造引理所要求的解释。这是一个s follow-s。定义[A]]M是一个3-dimensionalHilbert空间，具有任意形状的基底{A1，A2，A4}。 定义[B]]M是一个二维的Hilbert空间，具有正交基{B3，B5}。注意，基向量的名称已经被选择为建议由[A]]M的向量组成的核，并且在核M中将A命名，并且对于[B]]M也类似。设x，y，z是三个代数独立的超越复数. 这意味着x，y，z不满足一个具有有理系数的多项式方程p（x，y，z，x′，y′，z′）=0，除非p ≥ 0。定义三个线性映射Fx：[[B]]M→[[A]]M <$[[A]]M，Fy：[[A]]M <$[[A]]M→[[B]]M，Fz：[[A]M <$[[B]]M→[[B]]M<$[[A]]M如下。我们给出每个映射在所选基上的⎧如果i=B5，j=A2，且k=A1，（Fx）iIJ=其他的，⎧如果i=A2，j=A1，且k=B3，（Fy）k=其他的，ij<$z 如果i=A4，j=B3，k=B5，且l=A4，（Fz）kl=1000其他希望这些线性函数中的每一个是如何从图M中导出的是显而易见的：每个矩阵精确地包含一个非零项，其位置由M中相应盒子的输入和输出线的编号确定。f和g的定义如下：[[f]] M=Fx+ F †，[[g]] M= F z.注意，我们取了矩阵Fy的伴随，因为对应的盒子被标记为f†。这是一种解释[M]的定义。对于任何图M都可以类似地进行。F的12f By+3X一5G的z4118P. Selinger/Electronic Notes in Theoretical Computer Science 270（1）（2011）113为了证明引理的条件，我们首先观察到任何图N的解释[[N]]M由类似于（4.1）的求和公式给出。更进一步地，根据[−]] M的整数定义，可以确定如下的计算公式：[N]]M可以（唯一地）表示为p（x，y，z，x′，y′，z′），其中变量x，y，z及其复共轭具有整数系数。我们还注意到这个多项式是齐次的，它的次数等于N中盒子的数量。我们证明了p在xyz处的系数非零当且仅当N同构于M。该程序是一个直接的计算机程序，使用（4. 1）和[−]]M的定义。本质上，求和公式中对xyz的任何非零贡献必须来自于对于具有AinN的连线的b as isvorA（w）of[A]]M的chochoic，以及对于具有B in N的连线的basisvorB（w）of[B]]M的chochoic，以及N的框和集合{x，y，z}之间的双射φ;此外，只有当基向量的选择与双射φ“兼容”时，贡献才能是非零的。相容性精确地等于要求映射φ和φ确定从N到M的图同构。例如，在根据等式（4.1）计算[N]]M时，p中的xyz来自赋值a1<$→A4，b2<$→B3，b3B5，A4A1，以及a5›→A2，它完全对应于（在这种情况下是唯一的）同构，N到M事实上，我们得到了一个更强的结果：p在xyz处的整数系数等于N和M之间不同同构的个数（通常为0或1，但如果M有非平凡的自同构，它可能更高）。第五章概括其他领域本文的结果（定理2.2）除复数外，还适用于其它领域。对于特征为0的任何场k，如果非平凡的i∈v∈u∈m∈x∈ →x∈ h，这是真的。 （不存在针对某个x的变量，x/=x）。在证明中使用的C的唯一特殊性质，可能在一般域k中不成立，是超越的存在 这个问题很容易解决，首先考虑分数k（x1，. ，xn），其中所需的超越量已被自由添加。引理4.1的证明不作任何改变。最后，一旦对k（x1，. ，xn）已经被发现使得[M]]=[[N]，我们使用这样一个事实，即在特征为0的域中，任何非零多项式都有非根。 因此，我们可以实例化x1，... ，xn到k的特定元素，同时保持不等式[M]]=[[N]。 注意，因此，定理2.2对k成立;然而，引理4.1仅对k（x1，.，xn）。有界维数第4节中的[−]]M。2us esHil bert空间的无边界尺寸。人们可能会问，如果希尔伯特空间的维数固定为某个n，定理2.2是否仍然成立。当n= 2时，这是假的这里是P. Selinger/Electronic Notes in Theoretical Computer Science 270（1）（2011）113119对于BobPar′e的一个推论是：等式tr（AABBAB）=tr（AABABB）对所有2 ×2-矩阵成立，但在图形语言中不成立. 事实上，根据凯莱-汉密尔顿定理，对于某些标量μ，ν，A2=μA+νI。因此tr（AABBAB）=μ tr（ABBAB）+νtr（BBAB），tr（AABABB）=μ tr（ABABB）+νtr（BABB），而右手边的迹线的周期性相等。目前还不知道作者是否定理2.2是真的，当限制空间的3维。6致谢感谢戈登·普洛特金告诉我这个问题，并讨论了它的起源。 这需要BobParoreterexaml e indim ensi on2。引用[1] Abramsky，S.和B. Coecke，A categorical semantics of quantum protocols，in：Proceedings of the 19thAnnual IEEE Symposium on Logic in Computer Science，LICS 2004，IEEE Computer Society Press，2004，pp. 415-425[2] Hasegawa ，M.，M. Hofmann和G. Plotkin，Finite dimensional vector spaces are complete for tracedsymmetric monoidal categories，in：Pillars of Computer Science：Essays Dedicated to Boris（Boaz）Trakhtenbrot on the Occasion of His 85th Birthday，Lecture Notes in Computer Science 4800（2008）.367-385[3] Joyal ， A. ， R. 街 和 D 。 Verity ， Traced monoidal categories ， Mathematical Proceedings of theCambridge Philosophical Society119（1996），pp. 447-468.[4] Selinger，P.，Dagger compact closed categories and completely positive maps，in：Proceedings ofthe 3rd International Workshop on Quantum Programming Languages ， Electronic Notes inTheoretical Computer Science 170（2007），pp. 139-163.