Harry Buhrman谈量子算法和密码学

卢克·穆罕沃斯： 理论上，基于位置的量子密码术可以确保某些任务只能在某些位置执行：

例如，一个国家可以以这样的方式发送消息，即它只能在另一个国家的大使馆的位置解密。

在Buhrman等人。（2011），你和你的共同作者表明

如果合作的对手被允许预先共享任意大的纠缠量子态，那么……基于位置的密码学……在量子设置中……是不可能的。

在积极的方面，我们表明，对于限制不共享任何纠缠量子状态的对手，可以实现安全的位置核实。联合，这些结果提出了有趣的问题是否可以在有界纠缠的有界案例中进行安全定位验证。

在给定有限纠缠量的情况下，安全位置验证是否可能，我们目前的知识状态是什么?

哈利布尔曼经典的，这样的方案总是不安全的，如果一个限制了对手的运行时间或其他资源。量子的情况更加复杂，尽管我们和其他人已经证明，在指数级纠缠量的情况下，量子方案也可以被打破，是不安全的。因此，我们的任务就是寻找以下方案:1)诚实的一方可以轻松实施2)需要不合理数量的纠缠以便对手打破计划。我们已经看到在这方面取得了一些部分进展。例如,一个纸通过Beigi和Koenig表明存在有必要纠缠的方案来打破它们。事实证明，这个问题是否存在，如果他们这样做，如果他们这样做，则证明他们是安全的某些方案，是我们目前正在努力的难题。事实证明，我们采取的方法暗示，如果成功，导致古典复杂性理论，因此非常努力。另一方面，仍有可能在这种意义上简单地存在安全性的方案。

卢基：根据您对当前量子计算和量子算法设计的知识，您可以制作哪些关于政府或公民的建议？

例如。Ronald de Wolf推荐我们切换到后量子密码学对于敏感的数据，特别是“即使没有QC，安全服务即使是安全服务......可能会呼吸他们暂时存储的RSA加密通信，等待QC允许它们稍后解密这些消息。”

哈利是的，我完全同意罗纳德的观点。尽快切换到量子证明安全性(尽管我们不知道什么是量子证明，见下一段)。事实上，我们所有的电子加密通信，如电子邮件、电话交谈等，都是用类似rsa的技术加密的，目前还无法解密，但美国国家安全局和其他机构收集这些加密数据，直到有一天他们可以破译它们。例如，当建立一个足够大的量子计算机时，这样的数据可以很容易地被解密。因此，如果我们想在合理的时间内保证数据的安全，我们就应该改用其他加密技术和标准。这更适用于政府、银行和大公司，而不是普通用户，但我仍然觉得很多人没有意识到这一点。常见的错误做法是这样的:这台量子计算机，如果建造的话，仍然比我们先进15年，到那个时候，我们就会转向更安全的加密技术。这种推理当然是不正确的。

那么我们应该使用哪种加密？有问题的是，这需要更多的研究。金宝博娱乐然而，已经提出了一些加密方案出现作为量子证据。我建议我们使用那些与好的老RSA结合的方法。所以双重加密。这样，加密安全性至少和现在一样，但很可能也是量子证明。这种方法的一个警告是加密和解密变得(非常)低效，因为类似RSA的技术非常方便快速。这是一个人为了未来的安全而必须付出的代价。所以加密的时候必须做出决定。是否只需要确保明年的安全，例如，当传输一个信用卡号码时，如果它只在一两年内安全就可以了，还是我们需要安全到未来?对于后一种情况，我建议尽快切换。

卢基：根据您对量子计算和量子算法设计的当前状态的了解，您是否有额外的建议您可以向各国政府或公民达成额外的建议？

哈利密码的含义是那些直接与社会有关的。大多数人没有意识到的是，在科学和技术的相关领域，如化学，生物，物理和医学设计，有许多问题是计算非常苛刻的，往往不可能实现，即使是最强大的超级计算机。量子计算机将有助于更有效地解决这些问题，特别是当它们涉及量子力学系统和性质的模拟时。金宝博官方所以Q金宝博娱乐C方面的研究可能也会有影响。

卢基：从您的角度来看，在量子计算研究的理论一半（不是实验一半）的大量进展中，最重要的因素最重要的因素是什么？金宝博娱乐换句话说，对字段（或相关领域）的最可行但困难的变化将大多数加速理论量子计算研究？金宝博娱乐

哈利：这是一个难以回答的问题。如果我知道改变什么我会立即做到。其中一个问题是我们希望拥有更多的量子算法，证明量子计算的力量。社区开发了几种技术，如Quantum Theier采样和量子随机散步。我们希望拥有更多这些技术和想法。也许更重要的是，我们还需要隔离适合量子加速的计算问题或任务。也就是说Quantum Computers优于经典计算机的位置。

另一个可以改进的领域是容错和纠错代码。虽然已经取得了很大的进展，但我们仍然不知道算法设计可以容忍多少硬件错误的确切值。这个值称为容错阈值。在实现量子位并在其上运行量子算法和协议时，知道确切的值是很重要的。我们将需要执行错误纠正和容错计算，以对抗由于不完善和噪声弹出的错误。但是，如果出现的误差太大，这种计算校正是不可能的。另外，保持开销尽可能小也很重要。

第三个问题是几个Qubit应用程序中的问题。我们开始看到实验室中几个Qubbit计算机的示范，但没有良好的问题可以用来展示在30-100 Qubits上操作的小量子计算机的有用性。

卢基： 在Buhrman等人。（1997），您和您的共同作者在计算复杂性理论中列出了6个打开问题。在中间时间内有任何待解决，也许至少具有相对的结果？

哈利：在那篇文章中，我们列出了6个假设，所有这些都可能是假的。目标是并且仍然表明它们相当于p = np。我们还列出了6个打开的问题解决了明年由D. Sivakumar（来自该名单的＃2和5）。据我所知，已经对这些问题进行了多大进展，或者表明所有假设相当于P = NP。我认为这表明P与NP问题有多困难。目前有一种解决这个问题的新方法，而不是六个假设，而是P与NP问题本身。这种方法称为几何复杂性，并且涉及代数几何形状和表示理论。数学中的困难主题。

实际上是量子信息与这些类型的经典问题之间的联系。量子信息的语言允许一个人以不同的语言说明一些问题，该问题允许人们从不同的角度接近问题。一般来说，这一切都非常成功。例如Ronald de Wolf and Co-authors的结果它的核心是量子通信，还是我有的论文Jop Briet, Troy Lee和Thomas Vidick他们通过解决量子信息中的问题解决了巴拿赫空间理论中的问题。也有一项调查关于其他这样的结果。

也许我们应该通过量子技术重新审视6个假设纸张，看看我们是否可以进展。虽然目前我没有看到明确的攻击计划。

卢基:谢谢,哈里!