量子计算结果的真实性问题——量子计算验证协议

导读 量子计算已初步显现出强大的计算潜力，成为学界与业界关注的热点。随着量子技术研发工作的不断推进与技术难题的逐个攻破，量子计算终有一天会走进大众视野，帮助解决现实科技与生活中的重要问题。假设你用量子计算解决药物分子在不同条件下的演化过程研究问题，从而得知该药物分子的一些性质。当量子计算机利用其优异的计算能力得出一系列数据后，带着对量子计算美好的期望，你顺理成章的将这些数据带入下一阶段的实验。然而当我们欣然于量子计算可以解决庞大的数据与计算问题的同时，却也不得不对数据的真实性产生怀疑。于是，关于量子计算的真实性问题的研究也开始提上议程。本文将从经典计算的验证话题着手，阐述量子计算的验证方法和技术。

1.直观的经典计算验证

诚然量子计算机的并行计算潜力有望解决金融、化学等行业的大量计算难题，经量子计算机处理后输出的数据结果的真实性如何，还需设计一些技术方案进行验证。在计算机相关领域，“验证”（verification）是为检验经典计算结果的真实性和准确性而提出的一个概念。计算机的验证问题也是计算机最基本的问题之一。在经典计算的验证问题中，当服务器运行后输出了一个结果，用户端希望不需要从头执行计算任务就能验证结果的真实性。不同场景中的验证问题研究已有很长一段历史，如NP、IP、MIP、PCP等。

如何解决量子计算机中的验证问题，首先需要回顾经典计算机中的验证方法。设计经典计算机的验证协议时，如果用户需要使用自己的笔记本电脑去验证一个来自于大型计算机的计算，一种常见的思路是要求服务器提供计算过程。经典计算设计验证协议的前提条件是服务器的验证步骤可以被直观的记录和展现。

首先给经典计算中的验证问题设置一个情景：现有一个“用户”和一个“服务器”（服务器拥有远强大于用户的计算能力），用户现需要以较低的代价判断服务器结果的真实性；于是，当用户拿到服务器输出的计算结果之后，可以交互式的询问服务器一些问题并要求其作出相应回答。这样运行在两个或多个成员上的交互计算过程被称之为协议（protocal）。计算验证协议需满足以下两个条件：1.（正确性）当计算结果是正确的时候，如果服务器遵循协议回答所有问题，用户则能够确信计算结果为真；2.（可验证性）当计算结果错误时，无论服务器如何欺骗，用户总能够知晓服务器在作假。

IP协议.png

图1 IP协议（来源于网络）

理论层面上，关于计算的验证问题只需要重点关注计算结果是否可验证；而现实层面中，在云计算或者网络中，验证计算的结果还需要考虑既使他人信任计算结果又不需要从头开始执行整个计算过程。此外，一份实用的验证协议还要求当用户只具有比较有限的计算资源时，服务器在不作假的前提下消耗掉的计算资源越小越好。

在计算机科学中，当我们描述一个计算过程所消耗的时间或空间资源时，通常采用渐近复杂度来描述。通常情况下，时间函数的渐近复杂度为对数时间<多项式时间<指数时间，时间复杂度函数仅仅关注时间函数的增长速度而忽略常熟大小的差别。在研究各种计算机问题时，往往会尝试在多项式时间内解决这些问题。经典计算机在多项式时间内解决问题被称为P类复杂度(P为polynomial的首字母，译为多项式)。对多数而言，线性或者接近线性时间的复杂度已经是极限，比如用户将所需要计算的数据完全读入计算机已经达到了线性时间。

时间复杂度.png

图2 常见的时间复杂度曲线

在计算验证协议的问题中，关于服务器的运行时间也有不同的设定。当不限制服务器的运行时间，意味着服务器有可能需要指数时间运行协议，这类协议被称为交互式证明系统（interactive proof system）。出于实用性的考量，服务器的运行协议的时间需要控制在多项式时间之下，这就为协议设计提出了更高的要求。服务器在多项式时间下运行协议时，只需要满足协议运行在多项式时间内对攻击者保持安全性即可，不需要协议对任何不可信服务器都保持安全性。这种问题的设定可借助密码学工具和思想来实现协议的设计工作，如RSA加密技术的安全性思想就是利用了解密时间与解密信息的价值不对等关系的思路使信息安全性得到有效保障。

验证的思想已发展五十年之久，早已成为计算理论、算法与密码学研究的基石，而经典计算的验证协议已成为如零知识证明、多方安全计算等问题的基础构件。那么经典计算验证的协议是否也适用于验证量子计算的结果呢？如果了解了量子的一些基本特性就知道答案一定是否定的。不同于经典计算，量子计算的运行过程会受到观测行为的影响，会导致运行结果被破坏。《Classical Verification of Quantum Computations in Linear Time》研究给出了如何对验证量子计算结果进行验证的答案。

关于量子计算的验证问题，2017年Mahadev在一篇论文中针对量子计算构造了一个“全同态加密”的加密方案，利用经典世界中的密码技巧建立起与量子计算之间的桥梁。Mahadev的论文中并没有直接解决量子计算的验证问题，而是通过“全同态加密”的加密方案，实现了仅靠经典用户端计算支持服务器端的全同态量子计算。在Mahadev研究的基础上，衍生了一系列关于量子密码的研究。然而真正设计量子计算安全协议，还需要考虑时间复杂度的因素。

《Classical Verification of Quantum Computations in Linear Time》放弃了量子计算验证中常用的哈密顿量方法，将远程态制备作为中间步骤，最终构造出了能在线性时间的量子计算验证协议。下文将主要介绍该研究中构造线性时间的量子计算验证协议所采用的技术路线。

2.量子计算验证技术

当量子计算逐步成为现实，我们也开始思考量子计算是否是可验证的、量子计算如何在实践中执行等问题。该如何定义量子计算验证协议呢？类比经典计算的验证问题，我们认为当一个协议满足以下两个条件时，被称之为量子计算验证协议。定义如下：1.（正确性）当计算结果正确时，如果服务器遵循该协议回答所有问题，则用户能够确信计算结果为真。具体可表示为(C,O)当

，验证者可接受概率≥c； 2.（可验证性）当计算结果错误时，无论服务器如何欺骗用户，用户总能知晓服务器作假行为。具体表示为(C,O)当

，验证者拒绝的概率≥1-s。 除此之外，以上两个条件只是确定了什么是量子计算验证协议，真正可以使用的量子计算验证协议还需在实践中应用，即我们希望协议是有效的，也就是说用户端和服务器运行时间应该是线性时间。

2.1常用的几种量子计算验证方法

以往研究中有以下几种量子计算验证方法：

• • 一种常用的方法是使用单量子服务器和带有有限量子存储器的用户端完成验证。这些协议包括基于Clifford的认证协议、基于多项式代码的协议、基于测量的量子计算和陷阱量子位的协议、基于Hamiltonians的接收和测量协议等。这些协议通常需要在客户端有一个小的（例如，单量子位）量子设备，并在理论上(IT-)是安全的。这种验证方法的用户端仍然需要做量子计算，对于现有的所有可实现理论信息安全性的验证协议而言，用户端的量子计算（也是总复杂度）在电路规模中至少是线性的（甚至更多）。
• • 使用多个纠缠的量子服务器和一个完全经典的用户端进行计算验证也是一种常用的验证方法。假设服务器之间不存在通信，因此用户端可以利用这些服务器的联合行为来进行相互测试。这类协议通常可以实现理论上的信息安全性；但如果保证在实际的实践过程中，使一定范围内的多个无通信的服务器产生纠缠将耗费高昂的成本代价。
• • 一种相对较新的方法是基于计算假设性协议。早期的研究并不能实现经典验证，而Mahadev构造了CVQC中的第一个经典验证协议。该协议基于一种新的原语，称为有噪声的量子陷门无爪函数，它可以由容错学习假设构造而成。后来的学者在此研究的基础上开发了一系列新的CVQC协议。

对于一个中等规模的问题，尤其是对量子计算而言，三次复杂度已经大到无法在实际中运行。（以上列出的所有协议，总时间复杂度等于服务器量子计算的复杂度；我们将简单地使用“复杂性”来表示两者。）这就引出了一个的问题：量子计算的经典验证的复杂度可以更小吗？

2.2 远程态制备

上文提到了Mahadev仅利用经典用户端计算去支持服务器端的全同态量子计算的研究方案。对于验证协议而言，时间复杂度是评价一个协议可用性和有效性的重要指标。量子计算问题中的输入是要验证的量子线路及其计算结果，计算结果的输入规模大致等同于要验证的线路的规模（即量子逻辑门的数目）。我们希望手中协议的时间复杂度尽可能地小，最好是线性（以用户与服务器的总时间计算，由于要验证的线路总是需要被全部读入，我们至少需要线性时间）。Mahadev给出的协议时间复杂度是——线路规模的立方，这就意味着Mahadev仅利用经典用户端计算去支持服务器端的全同态量子计算的研究方案并不是一个可用性极强的验证办法。

量子计算的验证问题具有重要的理论意义与现实意义。我们希望量子服务器最终能让用户相信量子电路C输出结果的真实性。在量子计算结果验证的用户端，我们认为用户端受到经典计算能力的限制，从而引出量子计算的经典验证问题（CVQC）。量子计算服务端的时间复杂性通常主导总的用户端与服务器的时间复杂性，Mahadev提出最快的单服务器CVQC协议目前的时间复杂度为O（

），其中|C|为待验证电路的大小、k为安全参数。这导致许多现有协议的立方时间放大，包括多方量子计算、零知识和混淆。鉴于量子计算资源非常宝贵，这种立方复杂性可能会成为一些量子计算验证协议落地应用的一个巨大阻碍。

通过开发新技术，《Classical Verification of Quantum Computations in Linear Time》研究对Mahadev提出的单服务器CVQC协议进行改进，改进后的CVQC协议复杂度O(

)（就客户端和服务器的总时间复杂度而言）为线性时间，解决了时间复杂度为线路规模立方的问题。新的CVQC协议假设存在噪声活板门函数，在量子随机先验模型中具有安全性。

同时，研究还给出了一种可验证性(RSPV)的远程态制备。远程态制备在量子密码学中是最基本的概念，其实用性也较高。研究发现到许多现有的量子密码协议具有以下结构：1.客户端首先准备一些量子工具（小尺寸的秘密状态），并将它们发送到服务器；2.双方通过经典的交互来完成一些任务，这一步被称为小工具辅助协议。这些协议有一个不可取的特性，即客户端仍然需要在第一步中准备和发送（可能有很多）量子小工具。RSPV可以近似地代替第一个步骤；如果RSPV协议只依赖于经典信道，那么我们将得到一个编译器，该编译器可以将量子信道协议编译为具有类似功能的经典信道协议。

理想情况下，RSPV协议中希望用户端从一个状态族发送一个统一的随机状态，用户端使用协议与服务器发生交互。当协议完成时，如果服务器对验证问题没有欺骗，服务器应该保持理想状态。这个属性被称为远程状态准备的可验证性。理解远程态制备（remote state preparation）问题，可以假设在用户和服务器之间架设一条量子通信信道，并给予用户足够的量子计算能力，用户可以给服务器端传递他想制备的量子态。根据量子态测量坍缩原理（测量行为会干扰量子态从而导致最终结果无法测量）:制备这一量子态的用户，可以通过状态的制备过程，准确地知道用户端所传送态的完整信息；而服务器端虽然能拿到这一量子态，却无法通过测量这一状态知晓其完整信息。

对于远程态制备有几种不同的安全概念，包括盲目性和可验证性等；《Classical Verification of Quantum Computations in Linear Time》研究主要关注具有可验证性(RSPV)的远程态制备。在远程态制备问题中，理想情况是用户端从一个状态族发送相同的随机状态。用户端希望使用协议与服务器之间进行交互。因此如果当协议完成时发现服务器没有欺骗行为，服务器应该近似地保持理想态，这个属性被称为远程态制备的可验证性。必然地，这个可验证性的概念被定义为服务器端等距法：服务器可以自由地选择基，并将此基用于服务器的所有操作，他人无法从外部检测这种基的变化。

Mahadev技术的成功引发了一系列关于将这些相似态构造成经典信道RSPV协议的可能性。通常，RSPV是在一个小的状态族上定义的（例如，上面讨论的|+θi），而小工具辅助协议通常需要大量这样的小工具。为方便起见，我们定义了一个RSPV变量，该变量将小工具编号L作为输入：定义1.2 （非正式的）工具数为L的RSPV的形式为

，将

作为输入并满足以下条件：

• • （完备性）如果服务器是可信的，最终会得到

，其中

均在

中一致随机独立的。客户端最后得到的是

。

• • （可验证性）对任何恶意服务器而言，如果它可以以很大的概率传递协议，那么用户端和服务器在通过空间上的联合状态几乎与诚实状态无法区分，直到服务器端等距。

有研究对仅使用经典信道的RSPV协议问题给出了积极的回答。还有一些研究提供了一个候选协议，其安全性可以抵抗攻击者的一些限制形式。然而，前述研究中协议的时间复杂性尚不清楚。虽然这两个协议都是多项式时间，但其复杂性要么是完全隐式的，要么不是完全计算的（反卷积计算显示多项式的阶数是几十或数百个）。考虑到经典通道RSPV的广泛应用，《Classical Verification of Quantum Computations in Linear Time》研究提出以下问题：L小工具的经典通道RSPV是否可以{|+θi，θ∈ {0，1···7}}更快吗？这个问题的答案也可以为更多一般状态族的RSPV协议研究开路。

2.3 “8态量子工厂”

数十年来，远程态制备协议已成为无数量子协议（比如一部分量子密钥分发协议）研究的基石。从实际角度考虑，远程态制备有一个前提条件，即用户需要具有量子通信和量子计算的能力，显然这个前提不太符合实际情况。那么是否存在一种方法允许用户使用比较容易实现的技术，利用经典计算与经典通信在服务器端创造一个“信息魔盒”呢？综合而言，量子计算的验证问题的本质是研究下面这类状态的远程制备问题。这在前人的研究中被形象地称为“8态量子工厂”：

对应于θ等于0, π/4到7π/4，上式对应于八个量子态。上式中｜0〉和｜1〉代表二维复向量空间中的两个基向量，系数也是复数。我们可以将两个基向量理解成平面x轴和y轴上的单位向量，而θ是某个单位向量从x轴出发转过的⻆度。

通过“8态量子工厂”，我们希望能创造出这样的信息魔盒：用户知晓θ⻆的具体数值，服务器端能获得上面的量子态，却无法完整准确获知θ的具体数值。信息魔盒的奇妙之处在于，如果实现大量的8态量子工厂，把每一个逻辑门都对应于这样的一些状态，我们就可以实现量子计算验证，并且协议所需的状态数量依然是线性复杂度，与要验证的计算问题规模在同一量级，这就解决了Mahadev研究中从“量子线路”到“哈密顿量”转化所付出的额外代价问题，即立方时间复杂度问题，以在8态量子工厂为基础，基于一些密码学工具，后续学者们构造出一系列8态量子工厂协议（八种状态的远程态制备协议）。该量子计算验证协议的复杂度就是运行大量8态量子工厂的复杂度，也就是——状态数量的50~100次方（估计量）。

《Classical Verification of Quantum Computations in Linear Time》研究放弃了大家在量子计算验证及后续工作中常使用的哈密顿量方法，而采用远程态制备作为中间步骤，研究了8种量子态的远程态制备问题。最终通过发展新技术，克服了现有技术的种种限制，构造出了能够在线性时间内制造大量这样的量子态的协议。进一步与现有工作结合，得到了一个线性时间的量子计算验证协议。其中研究中的“线性时间”指使用我们的协议制备L个量子态所需总时间与L成线性。

3.结果与讨论

《Classical Verification of Quantum Computations in Linear Time》有一些技术创新总结：研究者们开发的一套技术不同于现有的CVQC和RSPV协议，他们放弃了在现有研究中普遍使用的哈密顿函数方法，而是使用RSPV协议作为中间步骤得到了一个更快的CVQC协议，RSPV协议旨在以|+θi〉的形式制备量子态。

即使不考虑复杂性，使用RSPV协议作为中间步骤的量子计算的验证问题也不简单。现有的研究足以处理此类状态：客户端指示服务器执行一个操作，然后进行部分测量，这将为服务器端的随机θ创建|+θ〉（或类似状态）；客户端可以根据服务器的响应及其机密信息（陷门等）计算θ。然后在此状态下可能会执行一系列测试，其中客户端要求服务器测量量子位（与θ相关或与θ无关），并使用服务器的反馈来检查它是否真的按照预期准备好了|+θ〉。更重要的是有研究已经设计出一个基于量子随机访问码的测试。

下面将简要概述《Classical Verification of Quantum Computations in Linear Time》研究新的CVQC协议：

1.与现有研究不同，为了让诚实的服务器获取状态，我们利用相位表结构仅使用哈希函数委派量子计算（它来自于一个不同的量子委托问题），将乱码表构造推广到量子世界。这项技术无法直接制备单量子比特态｜+θ〉。相反，它创建了这种态的编码形式

，其中x0与x1是用户端秘密持有的长密钥，而θ0、θ1是随机取样，满足θ1− θ0 = θ。

这样做的好处是，它允许设计一系列不可能在|+θ〉状态的新测试。但这会带来巨大的成本：用户端会泄露密钥，从而允许服务器解码状态并获取|+θ〉。这种做法被证明是不安全的，因为泄露的密钥和相位表会让攻击者破坏协议。为了解决这个问题，研究中开发出助手工具法。从某种意义上说，这种方法允许客户端直接公开密钥，而不牺牲相位表的必要保密性。研究认为这一部分是我们协议的核心步骤。

2.然后，论文中设计了一系列新的测试方法，允许用户端测试服务器状态。难点在于研究者们不仅希望这些方法可以真正证明服务器的状态的可信性，同时也希望当应用于L个状态时，整个测试都在线性的时间内。如果我们希望所有这些状态的总体误差都稳定在一个常数范围内，那么获得线性时间协议就存在一个固有障碍。在《Classical Verification of Quantum Computations in Linear Time》的测试设计中，有一些测试共同作用于所有这些小工具，可以帮助跨越这个障碍。

讨论

《Classical Verification of Quantum Computations in Linear Time》指出了研究结果的一些局限性，论文并不准备解决这些问题。

• • 尽管研究中的远程状态协议不停的运行，我们并不准备构建一个不断运行的CVQC协议。底层辅助工具验证下协议在线性时间内运行意味着整个CVQC协议循环的复杂度也是线性的。
• • 我们不关注优化big-O符号中的隐藏常量。当前的持续放大不切实际，但它主要来自非常不精确的安全性分析（即使是我们工作中的基本计算可能也不够严密）。尽管安全性分析比较粗略，但在这项研究中，作者们依然对许多记录未来改进的常量给出了一个明确的界限。这些改进记录对协议的实际应用非常重要。
• • 我们的RSPV协议的安全性被定义为常数误差和可能的无界等距。这已经足以构建新的CVQC协议，但会限制RSPV的应用场景。

虽然以上这些问题将会引发一系列相对应的问题，但《Classical Verification of Quantum Computations in Linear Time》对量子计算的验证问题研究将会推动量子计算的安全性在实践中的应用。

论文原文：https://arxiv.org/abs/2202.13997v2