DAOrayaki DAO研究奖金池：
资助地址: DAOrayaki.eth
投票进展：DAO Reviewer 1/0 通 过
赏金总量：45 USD
研究种类：Quantum Computing, Complexity, Matrix Powering
原文作者: Nick Thieme
创作者：skyh@DAOrayaki.org
审核者：wonder@DAOrayaki.org
原文: Computer Scientists Eliminate Pesky Quantum Computations
多年来，中间测量使量子算法的复杂性难以量化。新的研究表明，这些测量根本不是必要的。
NickThieme
随着量子计算机的功能越来越强大，我们对它们的理解仍然是一片混乱。两位计算机科学家的工作帮助洞悉了未来机器可计算的内容，使之用这些未来机器来进行计算。
芝加哥大学的 Bill Fefferman 和 Zachary Remscrim 在 2020 年 6 月发表的研究证明，任何量子算法都可以重新排列，将计算中间执行的测量数据移动到处理过程的最后，而不改变最终结果，也不大幅增加执行任务所需的内存量。此前，计算机科学家认为这些测量的时间会影响内存需求，对量子算法复杂性的观点存在分歧。
Fefferma 表示：“这一直让人苦恼，我们不得不考虑两种复杂性——一个带有中间测量，另一个没有。”
由于量子计算机独特的工作方式，这个问题只存在于量子计算机领域。量子计算机和我们家用计算机的根本区别在于它们存储信息的方式。量子计算机不是用0 和 1（二进制）的典型比特来编码信息，而是用称为量子比特的更高维度的比特组合来编码信息。
这种方法可以实现更密集的信息存储，以及实现更快的计算。但这也带来了一个问题。如果在计算中的任何时候，你需要访问一个量子比特中包含的信息并对其进行测量，那么这个量子比特就会从一个同时存在的可能位的微妙组合折叠成一个单一的确定位，这可能会影响到系统中的所有其他量子比特。
这可能是一个问题，因为几乎所有的算法都需要知道正在进行的计算的值。例如，一个算法可能包含这样的语句: “如果变量 x 是一个数字，将它乘以 10; 如果不是，就不要管它。”执行这些步骤似乎需要知道在计算过程中的那一刻 x 是什么，这对量子计算机来说是一个潜在的挑战，在量子计算机中，测量粒子的状态（确定 x 是什么）本质上改变了它。
但是 28 年前，计算机科学家证明了避免这种双输是可能的。他们建立了量子算法，你可以等到计算结束后再进行中间测量而不改变最终结果。
该结果的一个重要部分表明，在计算结束之后再进行中间测量，并不会大幅度增加总的运行时间。量子算法的这些特性---- 测量可以延迟而不影响答案或运行时间---- 被称为延迟测量原理。
这个原则巩固了量子算法，但也付出了一定代价。延迟测量使用了大量额外的内存空间，实际上是每次延迟测量多一个量子位。虽然对于一台拥有 4 万亿比特的传统计算机来说，每次测量一比特只需要花费很小的代价，但考虑到目前最大的量子计算机中量子比特的数量有限，这个代价实在是太高了。
Fefferman 和 Remscrim 的工作以一种“惊奇”的方式解决了这个问题。通过一个抽象的证据，他们表明在一些限制条件下，任何可以通过中间测量进行计算的东西都可以不用中间测量进行计算。他们的证明为延迟中间测量提供了一种节省内存的方法ーー避免了这种测量带来的内存问题。
“在最标准的情况下，你不需要中间测量,” Fefferman 说。
Fefferman 和 Remscrim 通过证明一个具有代表性的良态矩阵动力估计问题，在某种程度上等价于另一类具有重要性质的问题，从而得出了他们的结论。
在给定的条件下，条件良好的矩阵幂问题有效地要求您为一类矩阵(数组)中的特定条目找到值。Fefferman 和 Remscrim 证明了矩阵幂和其他允许中间测量的量子计算问题一样困难。这一系列问题被称为 BQL，团队的工作意味着矩阵幂可以作为该类中所有其他问题的代表---- 因此他们对矩阵幂估计的任何证明都将适用于所有其他涉及中间测量的问题。
在这一点上，研究人员借鉴了他们早期的一些工作。在 2016 年，Fefferman 和 Cedric Lin 证明了一个相关的问题，证明了和良态矩阵变换相关的问题，这和相似阶中最难的 BQUL 问题十分相似。这个阶乘就像 BQL 的小兄弟。它和 BQL 是一样的，除了它要求阶乘中的每个问题都必须是可逆的。
在量子计算中，可逆和不可逆测量之间有着根本的区别。如果一个计算测量了一个量子位，它将折叠量子位的状态，使得初始信息无法恢复。因此，量子算法中的所有测量都是天生不可逆的。
这意味着 BQUL 不仅仅是 BQL 的可逆版本，它也是没有任何中间测量的 BQL (因为中间测量，像所有量子测量一样，将是不可逆的，违反了阶乘的信号条件)。2016年的工作证明了矩阵求逆是一个无中间测量的典型量子计算，即 BQUL 的一个完全代表性问题。
新的论文以此为基础，将两者联系起来，证明了代表所有中间测量问题的良态矩阵能源可以简化为良态矩阵变换，它代表所有不能具有中间测量特征的问题。换句话说，任何带有中间测量的量子计算问题都可以简化为没有中间测量的量子计算问题。
这意味着，对于内存有限的量子计算机，研究人员在对不同类型的量子算法的内存需求进行分类时，不再需要担心中间测量的问题。
2020年，普林斯顿大学的一组研究人员---- Ran Raz，Uma Girish 和 Wei Zhan---- 独立地证明了一个稍微弱一些但几乎相同的结果，他们在 Fefferman 和 Rimscrim 的工作三天后发表了这个结果。Raz和Girish后来扩展了这个结果，证明了中间测量可以以一种时间有效和空间有效的方式推迟到更有限类型的计算机上。
总之，最近的工作对有限的内存量子计算如何工作提供了一个更好的理解。有了这种理论保证，研究人员就有了将他们的理论转化为应用算法的路线图。从某种意义上说，量子算法现在是免费的，可以不用支付延迟测量的高昂费用。
参考链接：
1.两位计算机科学家：
https://arxiv.org/abs/2006.03530
2.John Watrous：
https://cs.uwaterloo.ca/~watrous/
3.Bill Fefferman：
http://www.billfefferman.com/
4.Zachary Remscrim：
https://computerscience.uchicago.edu/people/profile/zachary-remscrim/
5.证明了一个相关的问题：
https://quics.umd.edu/people/cedric-lin
6.Ran Raz：
https://engineering.princeton.edu/faculty/ran-raz
7.Uma Girish：
https://www.cs.princeton.edu/~ugirish/
8.Wei Zhan：
https://www.cs.princeton.edu/~weizhan/
9.独立地证明了：
https://arxiv.org/abs/2006.04880
10.扩展了这个结果：
https://arxiv.org/abs/2106.11877
通过 DAO，研究组织和媒体可以打破地域的限制，以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式，构建一个代表社区意志并由社区控制的功能齐全的去中心化媒体。欢迎通过文末方式提交与DAO、量子计算、星际移民、DA相关的内容，瓜分10000USDC赏金池！欢迎加入DAOrayaki社区，了解去中心化自治组织（DAO），探讨最新话题！
Media：https://media.daorayaki.org
Discord server: https://discord.gg/wNUPmsGsa4
Medium: https://medium.com/@daorayaki
Email: daorayaki@dorafactory.org
Twitter: @daorayaki_
微信助手：DAOrayaki-Media
小宇宙：DAOrayaki
详情请参考：
Dora Factory支持去中心化DAO研究组织DAOrayaki
DAOrayaki ｜DAOrayaki 开启去中心化治理2.0时代
DAOrayaki ｜风险投资的范式转移：无限主义基金和无限游戏
DAOrayaki ｜DAOrayaki dGov 模型：基于Futarchy的正和游戏
更多关于DAO的文章，关注Dorafactory，查看往期文章。
