机构名称：
¥ 8.0
欢迎使用CS 860：量子下限。由于19日的情况，本课程将以异步形式在线教授：将没有现场讲座。每周，我打算在该一周内发布有关材料的一些课程注释，发布一些论文供所有学生阅读，并让一两个学生自愿发布这些论文的评论。然后，我们将讨论有关广场的论文和本周的材料（所有学生和审计师都应加入Piazza）。如果学生对课程有不同格式的偏好或想法，请在广场上配音。我强烈鼓励所有学生积极参加广场页面，这将是我们与教室最接近的事情。在材料方面，本课程将重点放在量子下限上：表明某些任务没有快速的量子算法的方式。我们将主要在黑匣子模型中证明这样的下限，也称为查询复杂性模型。该模型具有两个不错的属性：首先，它很简单且易于处理，证明其下限实际上是可行的（这并不会导致诸如\ sansp vs. \ sansn \ sansp之类的问题，而证明下限非常具有挑战性）。第二，大多数量子算法，例如Shor的算法和Grover的算法，具有自然的查询复杂性，并且可以有效地看作是查询复杂性算法。这意味着该模型尽管很简单，但足够丰富，可以捕获我们关心的``现实世界''量子加速的类型。本课程不需要量子背景。推荐了一些数学成熟度。在课程的后期，我们还将介绍通信复杂性模型，并研究如何在该环境中显示下限。通信复杂性下限通常更具挑战性，并且与理论计算机科学的其他部分有着深厚的联系。
量子下限
主要关键词
相关文件推荐
