- 选题背景和意义：
过去几年内出现了许多新的计算机技术，量子计算可以说是要求开发人员进行最重大范式转换的技术。 量子计算机由 Richard Feynman 和 Yuri Manin 于二十世纪八十年代提出。 量子计算背后的直觉源自于重大物理学困惑之一：卓越的科学进展面临无法为极其简单的系统创建模型的难题。 量子力学是在 1900 年和 1925 年之间开发的，它一直是化学、凝聚态物理学和各种技术（从计算机芯片到 LED 照明）的基石。 尽管取得了上述成就，但人们似乎无法使用量子力学为某些最简单的系统创建模型。 这是因为模拟包含几十个相互作用粒子的系统所需的计算能力多于传统计算机在过去数千年内可提供的计算能力！
可以通过多种方法来了解量子力学难以模拟的原因。 最简单的方法可能是了解量子理论可以解释为该物质在量子级别同时位于不同的可能配置（称为“状态” ）中。 与传统概率论不同，量子状态的许多配置（可能会被观察到）可能会相互干扰，就像潮汐中的波浪一样。 此干扰会阻止使用统计采样来获取量子状态配置。 如果我们想要了解量子演变，则必须跟踪量子系统可能拥有的每个可能配置 。
假设有一个包含电子的系统，其中电子可以位于 $40$ 个位置中的任意一个。 因此，电子可以位于 $2^{40}$ 个配置中的任意一个（因为每个位置可以包含电子，也可以不包含电子）。 若要在传统计算机中存储电子的量子状态，需要超过 $130$ GB 的内存！ 这是相当大的内存，但在某些计算机的范围内。 如果我们允许粒子位于 $41$ 个位置中的任意一个，则配置数 $2^{41}$ 是其两倍，因而需要超过 $260$ GB 的内存才能存储量子状态。 如果我们想要按传统方式存储状态，则无法无限期地增加位置数，因为我们很快超出了世界上功能最强大的计算机的内存容量。 内存用来存储系统所需的数百个电子超出了宇宙中的粒子数；因此，传统计算机没有希望模拟其量子动力学。 但实质上，此类系统根据量子力学定律及时演变，丝毫不知道无法通过传统计算能力来设计和模拟其演变。
这番观察使量子计算的早期构想提出了一个简单而强有力的问题：我们是否可以将这一困难转变为机会？ 具体来说，如果量子动力学难以模拟，则在构建将量子效应作为基本运算的硬件时，会发生什么情况？ 我们是否可以通过利用自然管理相互作用粒子所用的定律的系统来模拟包含这些粒子的系统？ 我们是否可以调查完全脱离自然的任务，但遵循或受益于量子力学定律？ 这些问题引出了量子计算的起源。
量子计算的基础核心是将信息存储在物质的量子状态中，并使用量子门操作来计算该信息，方法是通过利用和学习来“计划”量子干扰。 针对称为“因式分解”的问题，编程干扰以解决被视为传统计算机难以解决的问题的早期示例已由 Peter Shor 于 1994 年完成。 因式分解可以在确保当今电子商务安全的同时分解多个公钥密码体制，包括 RSA 和椭圆曲线加密。 自那时起，已为许多困难的传统任务开发了快速且高效的量子计算机算法：在化学、物理学和材料科学方面模拟物理系统、搜索无序数据库、求解线性方程组和机器学习。
- 课题关键问题及难点：
考察何种量子计算系统可以被经典计算系统有效模拟，是理解量子计算系统与经典计算系统的关系的重要环节，也是深入理解量子计算系统核心特征的重要内容。当前，已经有相当丰富的从不同角度针对对这个问题研究成果，但是还缺乏一个有效的框架来将这些不同侧面的视角进行统一描述。尝试从量子计算系统构建的时空结构的角度来考察这两种计算系统的特征，通过考察可被经典系统有效模拟的量子计算系统对应的时空结构，探讨是否时空结构可以作为刻画经典与量子计算系统之间相互关系的合理框架。
- 文献综述（或调研报告）：
文献[Quantum Computers that can be Simulated Classically in Polynomial Time.2001][2]证明了一类重要的量子计算可以在p多项式时间内进行经典模拟。特别地，证明了以4*4矩阵为特征的2位运算，其中16个元素遵循一组5个p多项式关系，可以根据一定的规则组合成一类可以在多项式时间内进行经典模拟的电路。并证明了有限类的高效全周期计算与多项式时间图灵迭代是一致的。所介绍的方法将量子计算模型引入了代数复指数理论的范畴。将量子物理的一种观点以一种一致的方式，对波函数进行确定性的模拟，只在测量过程中产生随机化。所有的结果都是基于门的使用，这些门在图匹配支柱方面是不同的。文献[Simulating quantum computation by contracting tensor network.2005][3]证明了一个具有T门的量子电路，其底层图具有树宽d，可以在时间内确定地进行模拟，特别是当d=O(logT)时，它是T的多项式。还证明了Raussendorf和Briegel (Physical Review Letters, 86:5188-5191, 2001)的单向量子计算是一种具有良好物理实现前景的通用量子计算方案，如果它的量子资源来自于一个小树宽图，那么随机化算法可以有效地对其进行模拟。文献[The quantum FFT can be classically simulate.2007][4]观察到，QFT可以由一个多对数路径宽度的电路来执行，如果这个电路不仅可以应用幺正门，而且还可以应用一般的线性门。回顾Markov和Shi[9]和Jozsa[7]的结果，它们提供了这种电路在树宽时间指数上的经典模拟，这意味着标题中所述的结果。经典的FFT模拟当然是没有意义的，当应用到经典的输入字符串，其结果是已知的;我们的观察可能只有在QFT用作子程序并应用于更有趣的叠加的情况下才有效。另一个证明是基于与琼斯多项式的联系;它是非常短的，如果一个愿意依赖几个已知的结果。文献[Quantum Hamiltonian Complexity.2014][5]综述了量子哈密顿复杂性的发展领域，包括量子约束满足的研究。目标是为这门学科提供一个以计算机科学为导向的介绍，以帮助消除计算机科学家和该领域物理学家之间的语言障碍。本文中包括以下:(1)的基本思想,动机,和历史的领域,(2)多体的物理专业术语解释计算机科学友好的语言,(3)概述多体的物理的核心观点,如平均场理论和张量网络,和(4)简短的博览会选择计算机科学结果。文献[The Heisenberg Representation of Quantum computers.1998][6]描述了操作符而不是状态的演化的形式主义在理解量子运算的一个重要类别方面被证明是非常有成效的。在误差校正和某些通信协议中使用的状态可以用它们的稳定器——泡利矩阵的一组张量积来描述。即使是这种简单的群结构也足以产生丰富的量子效应，尽管它还没有达到量子计算的全部能力。文献[A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States.2013][7]这是部分基于张量网络方法的选定主题的非技术性介绍，基于有关该主题的几次讲座和入门研讨会。 对于新手来说，应该是熟悉该领域的一些关键思想的好地方，特别是关于数字的思想。 在非常概括的介绍之后，我们激发了张量网络的概念并提供了一些示例。 然后，我们继续解释有关矩阵乘积状态（MPS）和投影纠缠对状态（PEPS）的一些基础知识。 还讨论了一些有关1d和2d量子晶格系统的关联数值方法的详细信息。
- 方案（设计方案、或研究方案、研制方案）论证：
（1）对量子计算系统的经典可模拟性问题的已有研究成果进行整理和总结。
（2）考察现有的量子计算系统可模拟性条件与时空结构的关系。
（3）尝试建立从时空结构角度来理解量子计算系统的框架。
