在所有可能的相应阶的二进制矩阵中找到一个Hadamard矩阵（H-matrix）是一个可以用量子计算机解决的难题。由于当前量子处理器中量子比特数和连接数的限制，以前的方法只能实现 2 阶和 4 阶的低阶 H 矩阵搜索。在本文中，研究人员表明，通过采用 H 矩阵的经典搜索技术，可以制定新的量子计算方法来寻找高阶矩阵。研究人员展示了一些发现超过 100 阶 H 矩阵的结果，以及经典量子资源平衡方法的原型实验，该方法产生了一个 92 阶 H 矩阵，该矩阵之前由喷气推进实验室研究人员在1961年使用大型计算机发现。由于解的准确性可以通过在多项式时间内执行的正交性测试来验证；这对于困难问题的优化来说是不典型的，所提出的方法有可能在不久的将来用于证明实际的量子霸权。

研究背景

Hadamard 矩阵 (H-matrix) 是一个具有$\{-1,+1\}$ 元素的二元正交矩阵，其任何不同的列（或行）对彼此正交。这样的矩阵只有当它是正方形并且其列（行）的长度等于1、2或4的倍数时才存在；即，对于一个$M\times M$ 维 H 矩阵，则$M=1,2$ 或者$M=4k$ 表示正整数$kk$ 。对任何正整数$kk$ 都有一个 H 矩阵的反向陈述也被认为是正确的，尽管既不存在数学证明也不存在反证。这是Hadamard矩阵猜想的一个长期存在的问题。

H-矩阵一直是科学和实际兴趣的主题。1867 年由 Sylverster 首次发现和描述，Hadamard 进一步研究了它与行列式问题的关系。其元素的正交性和二进制性使其在信息处理和数字通信中得到广泛应用。CDMA（码分多址）系统采用 Hadamard-Walsh 码来减少用户之间的干扰，因此通信系统的容量不会因用户数量的增加而严重恶化。 H 矩阵还被水手 9 号航天器用作其 ECC（纠错码），用于将火星图像发送到位于地球上的接收站，这要归功于其长纠错能力。

一些特定类型的H矩阵可以很容易地找到（构建），而其他H矩阵需要大量的计算资源来做。大小为$M\times MM\backslash times\; M$ 的 H 矩阵也称为$MM$ 阶 H 矩阵。当 M 遵循$M=2^{n}M=2^n$ 的特定模式，其中$nn$ 是正整数时，矩阵可以很容易地通过Sylvester’s张量积方法构造。Hadamard构造了 12 和 20 阶的 H 矩阵，其阶不遵循$2^{n}2^n$ 模式。它表明，除了Sylvester方法所规定的之外，还存在其他顺序。Paley构造了$M=4kM=4k$ 阶的H矩阵，其中$k\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\hspace{0.17em}\hspace{0.17em}4k\equiv 1\backslash mod4$ ,$k\equiv 3\mathrm{m}\mathrm{o}\mathrm{d}\hspace{0.17em}\hspace{0.17em}4k\equiv 3\backslash mod4$ ，分别被称为Paley Type I和Type II h矩阵。在公式中，他在伽罗瓦域GF(q)中采用了二次残差的方法，其中$qq$ 是奇数素数的幂。

各种实施方法也被提出。De Launey和horadam提出了一种共环技术，该技术基于一个有限群$GG$ 上的群发展，这个群是由$G\times GG\times G$ 上定义的一个共循环的作用所修改的。当它应用于二进制矩阵时，可以通过该方案生成 Hadamard 矩阵。本文简要介绍了Horadam的共环方法，并介绍了近年来的研究进展;在开发一种基于量子计算的h矩阵搜索方法时，研究人员发现一种简单而直接的方法将是一个很好的起点。本文中描述的方法是基于Williamson、Baumert-Hall和Turyn提出的较早的技术，适合于此目的。这三种方法都把对特定二进序列的搜索作为一个基本步骤。在本文中，将这些方法称为经典的 H 矩阵搜索方法。

虽然乍一看看起来很简单，但找到一个 H 矩阵实际上是一项具有挑战性的任务。为了找到一个 92 阶的 H 矩阵，1961 年，三位 JPL（喷气推进实验室）研究人员使用了当时最先进的计算机，即 IBM/7090 Mainframe 。对于 1000 阶以下的矩阵，最近成功找到的未知 H 矩阵是 428 阶的矩阵，它是 2005 年通过计算机搜索特定二进制序列发现的。论文中描述的方法特别有趣，因为下一个未知的 H 矩阵，例如阶数为 668 的 H 矩阵，可能可以使用相同的方法找到。目前还没有找到它们的主要原因是因为找到这样的矩阵需要巨大的计算资源，它按矩阵的阶数呈指数增长。

在所有的$O\left(2^{M^2}\right)O\backslash left(2^\{M^2\}\backslash right)$ 二元矩阵中找到一个$MM$ 阶的H 矩阵是一个难题。考虑到量子计算机解决困难问题的能力，我们提出用量子计算机来找到这样一个矩阵。理论上，量子计算机需要$O\left(M^2\right)O\backslash left(M^2\backslash right)$ 个量子比特叠加才能解决这样的问题。然而，在现有的量子退火处理器中，需要$O\left(M^3\right)O\backslash left(M^3\backslash right)$ 个量子比特，因为需要额外的辅助量子比特来将$kk$ 体项转化为2体Ising哈密顿模型。在本文中，证明了通过采用经典的搜索方法，可以减少所需的计算资源，对于实现Ising模型的量子退火处理器，其所需的计算资源将变为$O\left(M^2\right)O\backslash left(M^2\backslash right)$ 。本文描述了如何建立与经典方法相关的相应的哈密顿量，并给出了一些阶数超过100的结果。还描述了如何通过管理经典计算资源和量子计算资源，进一步开发这种技术来寻找高阶矩阵。在这种经典量子杂交算法中，经典部分的复杂度仍然呈指数增长，而量子部分则呈多项式增长。研究表明，与目前量子计算机无法实现的纯量子方法相比，该算法扩展了纯量子方法在有限量子比特数量下的能力，从而可以找到几个高阶的H矩阵。

通常，通过退火或启发式方法解决优化问题只能得到一个近似解，即我们不能确定它实际上是最佳点，除非枚举所有可能的解决方案。然而，枚举一个难题的所有可能解决方案是一项极其费力的任务。相比之下，H-SEARCH 中解的正确性可以在多项式时间内轻松验证；即，通过评估找到的矩阵（解）的正交性。如果我们将解决方案视为证书，H-SEARCH 的行为就像一个 NP 完全问题，因为找到解决方案很困难，但检查其正确性很容易。从这个特定的角度来看，H-SEARCH 是一个有趣的难题，在解决实际量子霸权问题时值得考虑。

使用量子计算机查找 H 矩阵

量子计算机被认为具有超越经典计算机的计算能力;这一特性被称为量子加速，甚至是量子霸权。关于这个问题的一个重要进展是谷歌研究人员在 2019 年取得的成就，他们声称他们的 Sycamore 量子处理器只需要大约 200 秒即可完成特定的计算任务；在这种情况下，对随机量子电路进行采样，其中经典超级计算机需要大约10，000年才能执行这项任务。下一步，需要具有解决现实问题的能力，而传统计算机无法在合理的时间内解决这些问题。需要创造性的思维来构建能够证明这种实用优势的算法。

图1：2 阶和 4 阶二进制矩阵的势能图 (PEL)。二进制$BB$ 的能量由$DD$ 矩阵的非对角线的平方和计算而来，其中$D=B^{T}BD=B^TB$ 。在(a)中，生成了 2 阶二进制矩阵，并根据它们的索引绘制了它们的能量。在二进制到自旋变量变换之后，索引被转换为矩阵。例如，对于索引为 1 的第二个矩阵，则过程如下：$1\to 0001\to [1,1,1,-1]\to \left(\genfrac{}{}{0px}{}{1}{1}\genfrac{}{}{0px}{}{1}{-1}\right)1\to 0001\to \backslash left[1,1,1,-1\backslash right]\to \backslash left(\{1\backslash atop\; 1\}\{1\backslash atop\; -1\}\backslash right)$ 。零能量矩阵，例如索引为1,2,4，…的矩阵表示正交/Hadamard矩阵。在(b)中绘制了几个相邻(根据Hamming距离)到一个正交矩阵的四阶二进制矩阵。索引为 6 和 10 的矩阵是 Hadamard，因此它们处于全局最小值，而其他矩阵则不是。在索引为 3 的矩阵中给出了局部最小值的示例。我们可以观察到这 2 个和 4 个二进制矩阵中的能量退化。

QAM 计算机的工作原理基于量子退火 (QA)，它是经典（热）退火 (CA) 的量子模拟。CA 通过逐渐降低温度来工作，有时允许系统跳过更高的能量，而 QA 则通过量子隧穿穿过能垒来寻求解决方案。H-SEARCH 问题的哈密顿量的能量分布是退化的；即，有许多具有相同能量的等效二进制矩阵。图1给出了 2 阶和 4 阶二进制矩阵的势能图 (PEL) 说明。考虑到 PEL，量子退火方法适用于找到解决方案。预计加速来自通过量子隧穿找到最小能量的过程。Farhi 和 Gutmann 描述了关于量子计算如何加速搜索算法的进一步分析。Das 和 Chakrabarti 对量子退火和模拟量子计算进行了全面回顾。

总的来说，现有的量子计算机可以分为通用量子门（QGM-Quantum Gate Machine）和量子退火器（QAM-Quantum Annealing Machine）。抛开一些与噪声和其他非理想条件相关的问题，这两种类型的量子处理器都已经被制造出来，并且公众用户可以通过互联网访问。这两种量子计算机所提出的方法的实现方案如图2所示。直接法：适用于QAM。三种主要的量子计算方法源自非量子计算/经典 H 矩阵构造/搜索方法，我们将其称为 Williamson、Baumert-Hall 和 Turyn 方法。

图2：求解H矩阵问题的量子计算方法是由经典方法发展而来的。在之前的直接方法中，研究人员用$M\times MM\backslash times\; M$ 的二进制变量表示一个$MM$ 阶的H矩阵，该矩阵变成了$O\left(M^2\right)O\backslash left(M^2\backslash right)$ 逻辑量子比特和$O\left(M^3\right)O\backslash left(M^3\backslash right)$ 物理量子比特(包括附属)，并在一个具有Ising模型的量子处理器上实现。本文采用三种经典方法;即Williamson、Baumert Hall和Turyn，通过构造它们对应的量子哈密顿量，转化为量子计算算法。本文提出的每一种相应的量子计算方法都需要$O\left(M\right)O\backslash left(M\backslash right)$ 个逻辑量子位，当它们在QAM(量子退火机)类型的处理器上实现时，逻辑量子位转换为$O\left(M^2\right)O\backslash left(M^2\backslash right)$ 个物理量子位。在QGM（量子门机器）处理器中，所需的量子位数量将与哈密顿量中的逻辑量子位数量成正比，即$O\left(M\right)O\backslash left(M\backslash right)$ 。可以利用量子近似优化算法(QAOA)在QGM处理器中实现所提出的方法。

研究结果

根据研究获得的 10,000 个结果中，研究人员确定了两个正确的解决方案。其中一个解被构造成H矩阵;其对应的指标矩阵、解的统计数据如图3所示。这个TT(8)序列产生了一个92阶的Hadamard矩阵，1961年JPL实验室的研究人员在使用IBM/7090大型计算机进行搜索时也发现了这个矩阵。

图3：使用量子计算机 (D-Wave) 查找 H 矩阵的实验结果：( a ) 基于 Williamson 的方法得到一个 12 阶 H 矩阵，( b ) 基于 Baumert-Hall 的方法给出 108 阶 H 矩阵，( c ) Turyn基于的方法产生 44 阶 H 矩阵，以及 ( d ) 基于 Turyn 的方法的扩展，产生 92 阶 H 矩阵。顶部显示量子处理器的运行统计数据。底部部分在左侧显示获得的 H 矩阵，在右侧显示相应的指标矩阵。矩阵中的白色像素表示+1，而黑色的是− 1。 指标矩阵中的白色像素对应于M；这是矩阵的顺序，黑色的为零。运行统计表明，对于 12 和 44 的低阶情况，解决方案倾向于围绕低能量聚集，而对于 108 和 92 的高阶情况，它们倾向于均匀分布。

复杂性分析

本文还对所需量子位数量的复杂度进行了分析，特别是从之前的直接法到本文提出的H 矩阵搜索方法，所需的量子比特由$O\left(M^3\right)O\backslash left(M^3\backslash right)$ 减少到$O\left(M^2\right)O\backslash left(M^2\backslash right)$ 。在最坏的情况下，用蛮力的方法找到一个$M\times MM\backslash times\; M$的H 矩阵，应该检查矩阵$M^{2}M^2$ 项中的“$-1-1$ ”和“$+1+1$ ”所有可能的组合，也就是说，我们应该对所有$2^{M\times M}2^\{M\backslash times\; M\}$ 矩阵进行正交性检验。研究已经表明，如果机器能够对任意非负整数$kk$ 实现$kk$ 体交互，我们需要$M^{2}M^2$ 逻辑量子位;在这种情况下高达四体哈密顿项(Eq. (S5))。当机器只能实现2体哈密顿项时，就需要额外的辅助量子位。在高阶情况:SI符号计算的需要小节中，我们已经表明，它将进一步增加所需量子位的数量到$M^2+M\times M(M-1)\mathrm{/}2M^2+M\backslash times\; M\backslash left(M-1\backslash right)/2$ ;即从$O\left(M^2\right)O\backslash left(M^2\backslash right)$ 增加到$O\left(M^3\right)O\backslash left(M^3\backslash right)$ 。

通过使用本文提出的方法，如基于Turyn的方法，进一步减少所需的量子位。(Turyn) Hadamard矩阵可以由一个$(n,n,n,n-1)\backslash left(n,n,n,n-1\backslash right)$ Turyn型/ tt序列构造。对于给定的$(n,n,n,n-1)\backslash left(n,n,n,n-1\backslash right)$ tt序列，我们可以构造一个$4(4n-1)4\backslash left(4n-1\backslash right)$ 阶的哈达玛矩阵;例如，要找到一个$4(4n-1)4\backslash left(4n-1\backslash right)$ 阶H矩阵，我们只需要找到一个$(4n-1)\backslash left(4n-1\backslash right)$ 长度的序列。因此，在基于turyn的方法中，找到M M哈达玛矩阵所需的逻辑量子位为$O\left(M\right)O\backslash left(M\backslash right)$ 。由式(35)给出的二次能量函数意味着在哈密顿量中将有多达4体项。同样，当使用只能容纳最多2个体项的D-Wave时，需要额外的辅助量子位。相应地，所需逻辑量子位的最终数量将是$O\left(M^2\right)O\backslash left(M^2\backslash right)$ 。

结论

由于复杂性呈指数增长，通过经典计算方法找到 H 矩阵的困难可以通过基于量子计算的搜索来克服，例如将矩阵的每个元素直接表示为二进制变量，然后将其转换为量子比特。然而，量子计算资源的可用性将实现限制为只能找到低阶 H 矩阵。研究已经表明，可以采用经典的 H 矩阵搜索方法来有效地利用可用的量子计算资源来解决更大的问题，即找到比之前的直接方法更高阶的 H 矩阵。

原文链接：https://www.nature.com/articles/s41598-021-03586-0

---煤油灯科技victorlamp.com翻译整理---