Mosca和Stebila（2010）提出了aquantum硬币的概念，这是量子货币的一种形式，其中所有量子货币状态都是彼此的精确副本，因此无法追踪。Tokunaga等人（2003年）提出的方案也实现了不可追踪性，但通过不同的底层机制实现。请注意，从概念上讲，构造一个硬币方案比比尔方案更难：无克隆定理（见第2.6节）指出，如果量子态只有一个副本，就不可能克隆它。为了证明量子硬币的不可伪造性，我们需要这个定理的一个强化版本，在这个定理中，伪造者可以获得状态的多项式多个副本。3.2.2公共量子货币在威斯纳的方案中，量子票据被传输到中央银行进行验证。这类似于信用卡交易，支付终端将信息发送给受信任的第三方进行验证。与私钥加密类似，Aaronson（2009）将此类方案称为“私钥”量子货币，因为验证需要银行的私钥。请注意，私钥必须保密，因为它允许铸造新的货币。钞票/硬币/闪电（第3.2.1-3.2.3节）安全（第3.2.4节）公共（第3.2.2节）不需要甲骨文（第3.2.5节）效率（第3.2.6节）经典可验证（第3.2.7节）经典可铸造（第3.2.7节）噪音容忍（第3.2.8节）未损坏（第3.2.4节）威斯纳（1983）$IT 7 Nagaj等人（2016）Bennett等人（1982）$C 3.3.7.7肖尔（1994）Tokunaga等人（2003）、IT 7.7 Aronson（2009）N3.7 Lutomirski等人（2010）Mosca和Stebila（2010年，第4节）、IT 7.7 Osca和Stebila（2010年，第5节）、IT 7.7 Gavinsky（2012）IT 7.3 Aronson和Christiano（2012年，第5节）$IT 3.3.7 Aronson和Christiano（2012年，第6节）Conden等人。

（2019）Farhi等人（2012）N 3 3 7 3 3 3 3 3 3 3莫利纳等（2012年，第4节）$IT 7 3 3 3 3 7 3阿斯塔夫斯基等（2012年）（CV qticket，第2页）$IT 7 3 3 3 3 3 3乔治奥和凯雷尼迪斯（2015年，第4节）$IT 7 3 3 3 3 3 3 3 3 3 3 3本·大卫和萨塔斯（2016年，第7节）$N 3 37 37米里和阿拉佐拉（2017年）$IT 7 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3吉等（2018年）$C 7 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3詹3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 33詹德里（2019年，第4节）N37詹德里（2019年，第6节）N 3 3 7 Roberts（2019）Radian and Sattath（2019a）$C 7 3 3 7 Radian and Sattath（2019b，第2节）N33337阿莫斯等人（2020年）科拉丹杰洛和萨塔斯（2020年）+  N 3 3 7贝赫拉和萨塔斯（2020）×C 罗伯茨和詹德里（2020年）C 3表2：上表根据九个属性对量子货币方案进行了分类。如果一篇论文介绍了多重主题，我们会包含单独的条目，并提供章节参考。脚注中提供了有关各物业分类系统的其他信息。信息技术：信息理论安全；C：标准假设下的计算安全性；N：没有基于非标准假设的安全性证明或计算安全性。: 不提供完整的公开验证。3：不间断；7：破损；: 在某些情况下会破裂。用户无法追踪，但银行无法追踪。将威斯纳（1983）与经典的可验证性相结合。将Aaronson和Christiano（2012）与经典验证相结合。向银行提供经典验证，但不向其他用户提供。詹德利（2019）讲述了对阿伦森和克里斯蒂亚诺（2012）的袭击。安全性证明是基于后量子不可分辨性模糊的存在，没有基于标准假设的构造。该结构基于抗碰撞的非折叠散列函数。

这种函数没有候选构造，因此无法实例化。施工可基于詹德里（2019年，第4节）或詹德里（2019年，第6节）。施工可基于Farhi等人（2012年）、詹德里（2019年，第4节）或詹德里（2019年，第6节）。只有在弱对抗模式下才能进行安全性证明。在“公钥”量子货币方案中，银行同时生成私钥和公钥。私钥是用来造币的。公钥将发送给所有用户。公钥允许用户有效地验证量子货币的真实性。这消除了用户与中央银行通信以执行验证的需要，就像威斯纳方案中所做的那样。相反，验证可以在“本地”进行需要强调的是，任何公钥方案都不能实现信息安全。也就是说，与Wiesner（1983）和其他私钥方案不同，公钥方案不能仅使用不克隆定理来排除伪造的可能性，而是必须基于计算的硬假设来保证其安全性（Aaronson，2009）。自Aaronson（2009）最初引入该概念以来，已经提出了几个公共量子货币方案。如表II所示，这些模式都不是基于标准硬度假设的安全证明，我们在第3.2.4节中讨论了这一点。构建这样一个方案被认为是一个重要的开放性问题。3.2.3量子光在公共量子货币计划中，中央银行可以准备与给定序列号相关的量子态的多个实例。量子照明方案具有公共量子货币的所有属性，但也保证即使中央银行本身无法生成具有相同序列号的多张票据。“量子闪电”的概念在詹德里（2019）首次定义；然而，Farhi等人。

（2012年），它比詹德里（2019年）早，也提供了一个满足定义的建筑。我们在附录A.6中强调了Farhi et al.（2012）的构造，该构造要求使用纽结理论中的概念。詹德里（2019）的详细概述超出了本文的范围。从透明度的角度来看，不可能用同一序列号构建多个账单，这可以用来为流通中的货币数量提供可证明的保证。如果需要验证票据的序列号，并且所有序列号的列表都是公开的，那么任何人都有可能验证流通金额的上限。当然，实物现金的情况并非如此，因为一个无赖的央行可能会产生多张具有相同序列号的票据。这种属性消除了对中央银行的一种信任的需要，而这种信任在最近有高通货膨胀历史的国家可能是有价值的。3.2.4安全性正如我们将在本小节中看到的，“不可伪造性”定义的微小变化可能对量子货币方案的安全性产生重要影响。我们将通过一系列例子来检验不可伪造性的概念来证明这一点，其中对手试图以央行无意的方式进行验证。然后，我们将对公共量子资金的安全性进行全面定义。我们首先将伪造定义为一种行为，通过这种行为，对手可以在不通过银行验证方案的情况下成功地从银行接收资金。这一简单的定义似乎足够宽泛，但它实际上无法捕获某些形式的伪造。例如，考虑一个对手，他从银行获得了一个量子货币状态，并通过了两次验证。显然，这也是伪造的。

或者，一个对手需要n个货币状态才能生成n+1个通过验证的状态，我们也会将其定义为不受欢迎的伪造形式。我们还可以说，如果对手从nmoney states开始，并生成m个严格超过n个通过验证的状态，那么她就会进行伪造。请注意，这些类型的赝品按硬度的降序排列。当然，我们希望所有这些对对手来说都是不可能的，所以我们通常会尝试排除最简单的形式。我们可能还想考虑这样一种情况，即对手成功地进行了尝试，但概率很小，例如。我们也希望避免这种情况。不幸的是，不可能保证成功概率为0，因为暴力攻击的成功概率非零。在密码学中，将其形式化的标准方法是使用“可忽略”函数的概念。如果函数的衰减速度比逆多项式快，则可以忽略不计。形式上，函数f:N→ 如果对于每一个c，R+可以忽略不计∈ N所有x都存在这样的情况≥ Nc，f（x）≤xc。因此，如果一个冒险家的成功概率可以忽略不计，我们认为该方案是安全的。另一个需要说明的问题是，对手是否可以在尝试验证后要求返还资金。如果该方案在这种情况下是安全的，我们说它对自适应攻击是安全的（见附录A.5节）。这种定义并不保证某些计划的安全，这意味着新资金必须在成功验证后铸造和交付。例如，Wiesner的方案可以抵御非自适应攻击（Pastawski等人，2012年；Molina等人，2012年），但需要进行修改才能抵御自适应攻击（Aaronson，2009年；Lutomirski，2010年；Nagaj等人，2016年）。

Gavinsky（2012）提出了替代私钥方案，该方案也实现了无条件安全性，甚至可以抵御自适应攻击。现在，我们已经研究了对手可能进行的不同类型的攻击，我们将为公共量子资金构建一个完整的安全定义。像许多加密方案一样，不可伪造性由挑战者和对手之间的安全博弈来定义。挑战者生成公钥和私钥，并将公钥发送给对手。对手要求获得n个国家的货币。然后银行应用造币算法生成|$i|$尼昂把这些钱送给对手。对手准备m（可能纠缠）量子态并将其发送给挑战者。挑战者使用验证算法验证m状态。我们说，如果成功验证的数量严格大于n，那么对手就赢了。此外，如果赢得这场比赛的概率可以忽略不计，那么该方案对于所有在多项式时间内运行的对手来说都是安全的。请注意，所有公钥方案，包括那些早于现代文献（Bennett等人，1982年）的公钥方案，都依赖于复杂性理论的安全概念（Aaronsonand Christiano，2012年），必须对对手可用的资源做出明确的假设。例如，在上述安全定义中，我们假设对手在多项式时间内运作。这与某些私有密钥方案不同，比如Wiesner（1983），它们实现了信息理论上的安全性，并且对对手无条件安全。Farhi等人（2012年）提出了一个利用复杂性理论安全概念构建公钥量子货币的显著尝试，该尝试使用指数大叠加和结理论来生成量子票据状态。

该方案的安全性取决于产生有效量子比尔态的计算困难性，以及复制未知量子态的不可能性。不幸的是，如果不首先实现纽结理论的进步，就不可能充分分析该方案的安全性。有关该方案的完整说明，请参见附录A.6节。3.2.5 oracle确定公共资金计划，如Mosca和Stebila（2010年，第4节），依赖于oracle的使用。正如第2.5节所讨论的，oracle是一个黑匣子函数，我们假设在本节中，用户普遍可以使用它。甲骨文的主要优点是用户无法“查看”它的内部。相反，访问它的唯一途径是通过函数的输入输出行为。如果不是这样，潜在的伪造者可以通过分析实现oracle的电路而不是其输入输出行为来获取信息。因此，用甲骨文构建公共资金计划要比没有甲骨文构建方案简单得多。在这里，我们的意思是“安全参数”中可以忽略不计在大多数情况下，它意味着量子货币状态的量子比特数，这是一个可以由中央银行选择的参数：随着安全参数的增加，伪造变得越来越困难。有两种方法可以解释基于神谕的量子货币构造。首先，甲骨文的建设可能是迈向全面公共量子货币计划的中间步骤。例如，Aaronson和Christiano（2012）从一个基于甲骨文的方案（第5节）开始，然后展示如何移动甲骨文（第6节）。或者，甲骨文可以被解释为一种技术，比如中央银行向外部用户提供的应用程序编程接口（API）。

当然，使用甲骨文需要与央行进行量子通信，这将使使用公共量子货币的主要优势无效。3.2.5.1复杂性理论无克隆理论我们现在将简要概述神谕如何促成公共量子货币计划的构建。我们将通过讨论文中证明的两个有用定理来解决这个问题，这两个定理为构造某些公钥量子货币方案提供了基础。第一个是神谕的存在声明，神谕是阴谋论的基础。定理1（Aaronson（2009））。存在一个量子甲骨文U，与之相关的是可公开验证的量子货币。第二个定理被Aaronson（2009）称为“复杂性理论无克隆定理”，它解释了甲骨文U的属性，并提供了关于不可伪造性的严格保证。在这个定理中，造假者被赋予用于验证的量子预言符Uψ和k量子票据|ψik、 每一个都由一个n量子位纯态|ψi组成。然后，造假者试图使用k个量子比尔态来生成k+δ有效量子比尔态。Aaronson（2009）证明这需要Ohmδ√nlklogk-L对Uψ的质疑。即使对于δ=1，随着量子比特数n的增加，这个问题也很快变得棘手。定理2（复杂性理论不可克隆（Aaronson，2009），Aaronson和Christiano（2012）定理B.1中的证明）。设|ψi为n量子位纯态随机抽样（根据哈尔测度）。假设我们得到初始状态，ψK, 为了一些k≥ 1，以及一个预言，Uψ，使得Uψ|ψi=-|ψi和Uψ|φi=|φi表示与|ψi正交的所有|φi。

然后对于所有的l>k，准备lregistersρ。。。，ρlsuch:lXi=1hψ|ρi |ψi≥ k+δ（40）我们需要：Ohmδ√nlklogk- L（41）对Uψ的疑问。复杂性理论中的不可克隆定理包含两个要素：（1）原始不可克隆定理；（2）非结构化搜索问题中可实现的量子加速的二次上界（Grover，1996；Bennett等人，1997）。它表明，一个造假者如果能随机获得k张有效的钞票，就需要执行∝√成功伪造一张钞票。使用格罗弗算法来识别有效的票据状态，这并没有实质性的改善。因此，如果纸币有大量的量子位元n，那么成功伪造的概率将是有利的。复杂性理论的不可克隆定理也被用于后来的公钥量子货币方案，包括Aaronson和Christiano（2012）以及量子币构造Mosca和Stebila（2010）（见第3.2.1节）。这些方案在验证算法中使用了Aaronson（2009）的oracle。3.2.6效率要求所有用于创建和验证货币单位的协议都可以在量子计算机上以多项式时间执行。例如，一个具有1000个量子位的模式，以及一个具有指数级扩展的验证过程运行时间，可能需要数百万年来验证单个状态，因此，不会被认为是有效的。然而，作为高效、实用的方案，效率低下的方案可能被证明是有用的。例如，Mosca和Stebila（2010）是一种无效的方案，但为Ji等人（2018）提供了一个构建块，这是一种有效的方案，但其缺点是将不可伪造性级别降低到计算安全性。3.2.7经典验证和可铸造性假设我们有一个量子货币单位，并希望验证其有效性。例如，这可能是Bennett等人设想的量子地铁令牌。

（1982），在转门处进行验证后，允许进入地铁。或者，它可以是一种量子货币，用于在电子商务交易中进行支付。在前一种情况下，我们可以物理地存放代币；然而，在后一种情况下，我们是在远距离进行交易，需要使用通信渠道进行支付。威斯纳（1983）依靠量子通信信道来验证量子货币状态；然而，正如加文斯基（2012）在一篇介绍“经典可验证性”概念的论文中所证明的，这并不是严格必要的。经典的可验证性意味着不需要量子通信通道来验证量子货币的形式。相反，通过银行和付款人之间的交互协议进行验证。使用经典通道进行验证至少有两个优点。首先，此类方案不需要在商户和央行之间创建量子通信渠道来执行验证。相反，可以使用现有的经典通信渠道，如经典互联网。其次，攻击者将无法通过截获通信和对量子位进行转换来修改法案的基本量子态，就像他们用威斯纳的钱所做的那样。某些量子货币方案，如Farhi et al.（2012）和Radian and Sattath（2019a），包括通过使用银行和接收者之间纯粹的经典交互来铸造量子货币的程序。此类方案必然依赖于计算假设（Radian和Sattath，2020）。采用一种允许经典可铸造性的方案的好处是，不需要量子通信来铸造和分发货币。

此外，当经典造币与经典验证相结合时，不需要量子通信基础设施。3.2.8噪声耐受性实施量子技术（包括量子货币）所面临的最大挑战之一是量子系统与周围环境相互作用和退相干时产生的噪声。处理噪声最直接的方法是使用量子误差校正；然而，一些量子技术，包括某些种类的量子货币，被设计为在系统中建立噪声容忍度，而不是依赖于量子纠错。由于目前的技术难以大规模实现量子纠错，量子货币的实验工作将在第3.3节详细讨论，依靠Pastawski等人（2012年）和Amiri and Arrazola（2017年）提出的抗噪声方案。3.3实验实施当量子货币的概念最初在威斯纳（1983年）提出时，显然在可预见的未来在技术上不可行。正如所提出的，它依赖于将经典态的物理编码转化为单光子的性质，即光的基本粒子，例如它们的偏振。量子光学系统确实是一个特殊的实验平台，有关量子技术中噪声技术挑战的更多细节，请参见第4.2节。量子货币等量子密码方案的实施是因为光子操控技术的成熟，以及光子沿着光纤或自由空间等物理通信信道传输的能力。

然而，即使中央银行有能力构建此类量子票据并以较低的成本进行编码，在检索、使用和验证之前，这些状态也必须在内存中存储一段时间，而不会出现实质性的消相干。量子存储器是一项具有挑战性的技术，尽管近年来在其发展方面取得了重要进展，但其特点——即存储时间、存储后量子态的检索效率、，与初始状态相比，检索到的状态的可靠性——通常无法在单个系统内优化，目前不适合实际使用（Heshami等人，2016）。然而，在理论量子货币计划所需的资源方面已经取得了实质性进展，这使得研究人员能够部分实现某些形式的量子货币。由于公钥方案在理论和实践上都带来了额外的技术挑战，迄今为止的研究主要集中在构建私钥形式的货币上。虽然这不会影响公开验证的可能性，但它可以提供类似于CBDC的支付工具，但具有信息论安全性，这是纯数字货币无法实现的标准。我们简要回顾了两种方案的实验实施情况。3.3.1量子光学货币我们考虑的第一个方案是实现基本量子光学票据，这是Bartkiewicz等人（2017年）首次通过实验证明的。我们注意到，作者在论文中提到了钞票，但事实上，使用了需要与银行互动的验证过程，这意味着它不是一个公共密钥模式。

该方案基于Wiesner（1983），但进行了以下修改：不是使用随机绘制的基对随机绘制的经典比特串进行编码，而是使用偏振光子矩阵对灰度图像进行编码。选择偏振状态以对应灰度图像中的颜色。例如，使用三组编码基将允许使用六种光偏振，每一种对应于白色和黑色之间的不同颜色。他们的原理证明实验实现是在实验室环境中使用光子偏振编码进行的。他们成功地证明了量子货币状态的创建是在他们提出的经过修改的维斯纳（1983）版本下进行的。他们还展示了如何利用最佳克隆攻击进行伪造，重点是针对单个光子的攻击，他们认为这些攻击在短期内是最合理的。3.3.2量子信用卡卡文斯基（2012年）、乔治奥（Georgiou）和凯雷尼迪斯（2015年）、阿米里（Amiri）和阿拉佐拉（Arrazola）（2017年）提出了可归类为“量子信用卡”的方案，这些方案依赖于量子检索游戏（Bar Yossef等人，2004年；阿拉佐拉等人，2016年）。Bozzio等人（2018年）是第一个实验性实施这种方案的人。他们的方法利用了光的偏振弱相干态，并允许进行经典验证，从而消除了与验证者建立量子通信通道的需要。他们还能够严格地证明不可伪造性、可接受性和对现有数字支付形式（如信用卡）的安全性。

随后，他们还在实际环境中更详细地检查了该方案的安全性，并为实际损失和噪声参数区域提供了数值界限（Bozzio等人，2019年）。与量子货币的其他实验实现一样，Bozzio等人（2018年）也受到量子内存开发进展的限制。然而，他们构建的量子货币方案要与量子内存实现的最新发展相兼容，从而在短期内提供此类基本证明。在密切相关的工作中，Guan等人（2018年）实验性地实施了基于Amiri和Arrazola（2017年）的quantummoney方案。它们展示了如何执行方案的每个部分，包括账单状态准备和验证，但也遇到了相同的量子内存瓶颈。Bozzio等人（2018年）和Guan等人（2018年）在评估其方案的安全性时都考虑了实验缺陷。3.3.3剩余挑战全面实施私钥量子货币的主要障碍是难以存储量子态。对于Bozzio等人（2018）实施的方案，如果我们假设只有存储机制负责系统中的损失，那么可以证明，如果相干态的平均光子数等于1，存储器必须达到85%的存储/检索效率，在验证时产生的错误率不到2%（Bozzio，2019）。这在实验范围内，因为已经证明，使用基于冷原子云的量子存储器可以提供高达90%的存储/检索效率（Xiao等人，2018）。此外，当平均光子数大于1时，由于状态准备而导致的错误率也可以降低，量子存储状态可靠性可以接近99%（Vernaz-Gris等人，2018）。

从长远来看，使用超导纳米线单光子探测器（可以实现90%左右的检测效率）和进一步优化存储/检索效率，可以在安全条件下充分展示该方案，而客户端是可信的。然而，请注意，目前此类量子存储器的存储时间约为微秒（尽管其他技术可能达到毫秒甚至秒），并且必须使用多路复用技术在同一存储器中同时存储多个量子位，例如使用Vernaz Gris等人（2018）中的空间模式。本讨论说明了在实践中使用量子货币作为执行金融交易的手段时需要考虑的各种交易效应。4量子算法本节概述了计量经济学家和计算经济学家近期可能会用到的量子算法。它分为两个小节。第一部分介绍了量子算法构造的理论发展，第二部分介绍了在量子计算设备上实现量子算法的实验进展。在理论部分，我们将重点介绍算法的高级检查，但也将讨论有用的低级细节。对于每一种算法，我们将尝试确定经济学中的潜在应用，确定现有算法可实现的计算加速，并确定算法是否具有不适用于经典算法的附加限制。在实验部分，我们将提供量子计算机的发展历史，包括对其发展最新进展的回顾。

我们还将讨论它们的局限性。我们介绍的许多算法涉及相位回退、相位估计和量子傅里叶变换（QFT）。希望了解这些子程序的详细信息的人，请参见附录中的A.2、A.3和A.4节。感兴趣的读者也可能希望看到Montanaro（2016）对量子算法的高水平调查，Childs（2017）对同一主题的详细课堂讲稿，或者量子动物园对量子算法的定期更新数据库。4.1理论进展与经典算法和经典计算机一样，量子计算的理论进展往往会引领实验实现。在本小节中，我们将概述与预测学家相关的量子算法，以及它们各自的进展状况。看见http://quantumalgorithmzoo.org，这是斯蒂芬·乔丹（Stephen Jordan）定期更新的量子算法列表。4.1.1数值微分通常用于求解经济模型和进行计量经济估算的数值方法通常依赖于计算一阶和二阶导数。例如，爬坡算法需要重复计算梯度。此外，牛顿-拉夫森法、爬山法和拟牛顿法家族，包括Davidon Fletcher-Powell（DFP）、Broyden-Fletcher-Goldfarb-Shanno（BFGS）和Berndt-Hall-Hausman（Berndt等人，1974）以及Marquardt（1963）都需要计算二阶导数的梯度矩阵和Hessian矩阵。

这些方法通常用于金融计量经济学、结构微观计量经济学、最大似然估计、动态随机一般均衡（DSGE）建模，以及中央银行和ZF机构进行的大规模宏观经济建模。对于高维模型和估计问题，如果没有封闭形式的解决方案，使用分析梯度可能是不可能的，或者如果模型是有误差的，那么使用分析梯度可能是不可能的。关于ARCH和GARCH模型的大量文献使用了数值梯度和Hessian计算（Bollerslev，1986a；Engle等人，1987；Bollerslev，1986b；Bollerslev，1987；Danielsson，1994；Zakoian，1994；Engle和Russell，1998；Gray，1996；Engle和Russell，1998；De Santisand G’erard，1998；和Engel，2000）。数值微分也被用于求解金融市场的各种不同模型（谢，1991年；希姆斯特拉和琼斯，1994年；朗斯塔夫和施瓦茨，1992年；卡罗利和斯图尔茨，1996年；德桑蒂斯和杰拉德，1997年；杜福尔和恩格尔（2000年）；Bae等人，2003年）。Aguirregabiria和Mira（2002）以及Judd和Su（2012）为利用数值导数的结构微观经济模型提供了算法。Aguirregabiria和Mira（2010）对动态离散选择模型的文献进行了综述，该模型广泛使用了基于梯度的方法。Burtless和Hausman（1978）、Lancaster（1979）和Heckman和Macurdy（1980）使用基于梯度的方法来求解结构微观经济模型。最大似然估计（MLE）用于各种不同的经济和金融问题，包括结构模型的估计（见贝尔斯利，1980年；格林，1982年；怀特，1982年；邦奇，1988年；拉贝·赫斯基等人，2005年；费尔南德斯·维拉维德和鲁比奥·拉姆i雷斯，2007年；贾德和苏，2012年）。

通常需要计算likelihood函数的梯度和Hessian，这会在高维问题的估计算法中造成瓶颈。用于求解和估计DSGE模型的软件包，如Dynare，通常使用数值梯度和Hessian矩阵。有关需要计算梯度或黑森分布的大规模中央银行模型的示例，请参见Christo Off el et al.（2010）和Christian et al.（2011）。非常复杂。出于这个原因，此类计算和经济计量惯例通常采用数值差异。例如，可以使用有限差分方法，通过对点的近似线性邻域执行函数计算，以数值方式计算梯度。前向差分法是最简单的方法，它近似于函数的偏导数，f（x）xj，其中x=（x，x，…，xd），并使用泰勒展开式将误差大小绑定如下：f（x，…，xj+l，…，xd）- f（x）=f（x）xjl+f（x）xjl2+f（x）xjl3！+。。。（42）然后我们可以将方程（42）重新排列如下：f（x）xj=f（x，…，xj+l，…，xd）- f（x）l-f（x）xjl2！-f（x）xjl3！- ... （43）对于较小的l，与使用前向差相关的误差为有序（l）。我们可以通过使用中心差f（x+l）将其减少到O（l）-f（x）-l） 。注意，我们必须执行d+1函数求值来计算梯度，f（x）=(f（x）十、f（x）xd），使用正向差异法。这是因为我们必须对f（x）进行一次计算，对梯度的每个d分量进行一次计算。如果我们使用中心差分法，我们必须进行二维函数计算来计算梯度。此外，Hessian矩阵的数值计算将需要O（d）函数评估。Jordan（2005）介绍了一种用于数值梯度计算的量子算法。

为了比较这种量子算法与经典梯度算法的性能，他采用了查询复杂性的概念，我们在第2.5节中讨论了这一概念。在这里，查询复杂度度量了计算梯度所需的函数求值数量，梯度由d个分量到n个精度位。正如我们之前所展示的，经典数值梯度计算的最简单方法，参见附录A.1节，了解计算复杂性和相关符号的概述。不同的是，需要d+1查询来计算带有d个分量的梯度。相反，Jordan的量子算法只需要一个查询，而不管d的大小。它还能够使用O（dn）计算N阶导数-1） 查询，而不是经典例程所需的O（dn）查询。算法1：量子数值梯度计算（Jordan，2005）1在| 0i位置用n个量子位初始化d输入寄存器。2用位在| 0i位置初始化1输出寄存器。3将H应用于所有输入寄存器。4将X应用于输出寄存器。5.应用量子傅里叶逆变换，得出：√（NdNPN）-1δ=0PN-1δ=0...PN-1δd=0 |δi |δi|δdiPN-1δa=0ei2πa/N | ai7使用oracle计算f.8将输出（模2n）添加到输出寄存器。9对每个寄存器应用量子傅里叶变换，得到：纳米FxE纳米FxE。。。纳米FxdE11计算基础上的度量，屈服f、 Jordan（2005）的伪码在算法1中给出。请注意，oracle的输入和输出是来自有界非负区间的整数，该区间由二进制字符串表示。f的输入和输出是实数。Theoracle保留输入以保持可逆性。

此外，f必须在计算梯度的点x=（x，x，…，xd）附近连续。最后，可以按照方程式（44）的规定设置辅助量子位的数量n，以确保输出在±θ区间内准确。请注意，parameterm是限制渐变各个分量的间隔大小。n=对数“最大值（f）- min（f）mlnθ2π#（44）感兴趣的读者也可能希望看到Bulger（2005）、R¨otteler（2009）和Montanaro（2011），所有这些都是关于约旦（2005）的扩展。目前，在查询复杂度方面，没有哪个量子算法能比经典算法提供更高的多项式加速比。然而，对于高维模型和估计问题，将功能评估的数量从至少d+1减少到1可能会大大减少程序运行时间。在根查找操作中尤其如此，在根查找操作中，必须反复计算梯度以找到最佳值。4.1.2插值求解动态经济模型通常需要使用函数方程，如Bellman方程和Euler方程。虽然这类问题的全局解可以用一个值的张量来表示，该张量近似于离散点集上的未知函数，但由于维数灾难，提高这类表示的准确性将带来较高的计算成本。特别是，如果我们没有连续状态，每个状态被离散成s节点，那么值函数或决策规则的张量积表示将包含k=SN节点。

这意味着，每种状态下节点密度加倍将导致状态空间的大小增加2n倍，这即使对于相对较小的模型也是禁止的。因此，高维模型的常用求解方法通常不依赖节点密度来实现对未知感兴趣函数的精确近似。例如，Krueger和Kubler（2004年）以及Judd等人（2014年）利用Smolyak方法构造稀疏网格，通过避免使用张量积网格有效地避免了维数灾难。一种更常见的方法是使用张量积网格，但在节点之间进行插值。我们将在本小节中重点介绍这种方法。参见Santos和Vigo Aguiar（1998）对值函数迭代的诱人收敛性的解释，以及Aruoba等人（2006）对动态平衡模型的求解方法的比较。经济学和金融学中的各种计算模型都在解决方法中使用插值。有关各种应用，请参见基恩和沃尔平（1994年）、阿克伯格（2003年）、鲁斯特（1997年）以及克劳福德和舒姆（2005年）。有关经常使用插值的问题类的调查，请参见赫克曼和纳瓦罗（2007年）、阿吉雷加比里亚和米拉（2010年）以及基恩（2011年）。有关插值方法的概述，请参见Judd（1998）。虽然插值通常会在给定精度水平下减少运行时间，但它仍然是许多求解方法中计算成本最高的例程之一。考虑这样一种情况，我们希望使用单项式基函数：1，xi，xi，…，用一个具有k个节点的状态变量插值一个值函数V，。。。，xdi，我∈ [k] 。我们的目标是找到系数c的d维向量，从而满足方程（45）。