基于对数编码的超维分解的高效量子比特量子搜索

# 基于对数编码的量子比特高效超维分解量子搜索
来源: https://arxiv.org/html/2607.11936
, Hyunwoo Oh 加州大学尔湾分校, 加州尔湾, 美国, hyunwooo@uci\.edu (https://arxiv.org/html/2607.11936v1/mailto:[email protected]), Ryozo Masukawa 加州大学尔湾分校, 加州尔湾, 美国, rmasukaw@uci\.edu (https://arxiv.org/html/2607.11936v1/mailto:[email protected]), Raheeb Hassan 加州大学尔湾分校, 加州尔湾, 美国, raheebh@uci\.edu (https://arxiv.org/html/2607.11936v1/mailto:[email protected]), Mohsen Imani 加州大学尔湾分校, 加州尔湾, 美国, m\.imani@uci\.edu (https://arxiv.org/html/2607.11936v1/mailto:[email protected])

###### 摘要

超维计算（HDC）使用维度为 D 的高维超向量来表示符号。在超向量分解中，目标是从一个绑定的目标超向量中恢复出 F 个组成超向量，每个超向量来自大小为 N 的码本。这需要搜索 N^F 个候选元组，因此在大规模下计算成本极高。最近的量子方法提供了二次搜索优势，但通常依赖于量子比特效率低下的 O(D) 量子比特超向量表示。我们提出了一种用于HDC分解的量子比特高效量子框架，将表示成本降低到 O(log D)。该框架引入了对数超向量和对数绑定编码，以及一个可逆的超向量查找算子，用于在电路级别操作密集超向量。结合改进的 Dürr–Høyer 搜索过程，该方法在显著减少量子比特使用量的同时，保持了 O(√(N^F)) 的搜索复杂度。实验结果验证了正确的相似度计算、可执行范围内的准确分解，以及相对于基于显式 D 量子比特超向量编码的基线方法，量子比特缩放性能显著提升，最多可减少 2,000 倍的量子比特数。

## 1. 引言

参见图 1 的说明。当前的量子硬件尚未能提供之前显式维度 HDC 分解方法所需的超大量子比特数（用于 D 维超向量时使用 O(D) 个量子比特）与低错误率的组合。这促使我们采用对数量子比特方法，将表示成本降低到 O(log D) 个量子比特，使其更贴合近期的硬件条件。

量子计算 (Nielsen and Chuang, 2010) (https://arxiv.org/html/2607.11936#bib.bib154) 通过利用叠加、干涉和幅度放大 (Nielsen and Chuang, 2010) (https://arxiv.org/html/2607.11936#bib.bib154); Grover, 1996 (https://arxiv.org/html/2607.11936#bib.bib147); Dalzell 等, 2023 (https://arxiv.org/html/2607.11936#bib.bib153); Boyer 等, 1998 (https://arxiv.org/html/2607.11936#bib.bib161); Brassard 等, 2000 (https://arxiv.org/html/2607.11936#bib.bib162) 提供了一种根本不同的计算模型来解决搜索和优化问题。其最重要的算法优势之一在于能够将无结构搜索的复杂度从线性降低到搜索空间大小的平方根缩放。这使得量子搜索特别适用于那些主要成本来自组合候选选择而非特征提取的机器学习问题 (Wiedemann 等, 2022) (https://arxiv.org/html/2607.11936#bib.bib157); Xu and Aggarwal, 2025 (https://arxiv.org/html/2607.11936#bib.bib158); Wiebe 等, 2015 (https://arxiv.org/html/2607.11936#bib.bib163)。

这一机会的一个典型实例出现在 *超维计算* (HDC) 中，也称为向量符号架构 (Kanerva, 2009) (https://arxiv.org/html/2607.11936#bib.bib112); Plate, 1995 (https://arxiv.org/html/2607.11936#bib.bib145)。HDC 使用高维向量（称为超向量）以及简单的代数运算（如 *绑定* 和 *捆绑*）来表示信息 (Kanerva, 2009) (https://arxiv.org/html/2607.11936#bib.bib112); Plate, 1995 (https://arxiv.org/html/2607.11936#bib.bib145)。这些操作支持对结构化信息（包括元组、序列和符号记忆）进行高效的组合表示，同时在高维空间中保持计算轻量。HDC 不仅作为一种独立的计算范式重新引起关注，还作为深度学习系统之上的结构化层而受到关注。在这种混合模型中，深度神经网络（DNN）作为强大的特征提取器，而 HDC 则在生成的表示上提供更可解释且显式组合的结构 (Rahimi 等, 2017) (https://arxiv.org/html/2607.11936#bib.bib146); Neubert and Schubert, 2021 (https://arxiv.org/html/2607.11936#bib.bib155); Yun 等, 2024 (https://arxiv.org/html/2607.11936#bib.bib139); Barkam 等, 2023 (https://arxiv.org/html/2607.11936#bib.bib156); Lee 等, 2023 (https://arxiv.org/html/2607.11936#bib.bib164)。这种集成在既需要 DNN 的表征能力，又需要 HDC 提供的符号结构和可控性的场景中尤其有吸引力。

然而，一个关键障碍在于 *分解*：从组合表示中恢复出组成超向量。这个问题在混合 DNN-HDC 系统中尤其重要，因为人们可能希望解释、操作或检索编码在学习到的超向量中的符号因子 (Memisevic and Hinton, 2010) (https://arxiv.org/html/2607.11936#bib.bib166); Frady 等, 2020 (https://arxiv.org/html/2607.11936#bib.bib167); Yun 等, 2026 (https://arxiv.org/html/2607.11936#bib.bib114); Pilligua 等, 2025 (https://arxiv.org/html/2607.11936#bib.bib168)。如果一个目标超向量是通过绑定 F 个因子形成的，且每个因子取自大小为 N 的码本，那么精确恢复就需要搜索 N^F 个可能的元组。尽管前向 HDC 操作本身仍然简单 (Kleyko 等, 2023) (https://arxiv.org/html/2607.11936#bib.bib165); Poduval 等, 2024 (https://arxiv.org/html/2607.11936#bib.bib149)，但由此产生的指数级搜索空间迅速成为主要的计算瓶颈。

最近解决这一挑战的尝试是超维量子最大值寻找 (HDQMF) (Poduval 等, 2024) (https://arxiv.org/html/2607.11936#bib.bib149)，它将 Grover 风格的量子搜索策略应用于 HDC 分解，并实现了预期的二次提升，从 O(N^F) 到 O(√(N^F)) (Grover, 1996) (https://arxiv.org/html/2607.11936#bib.bib147)。虽然很有希望，但仍然存在两个重要限制。首先，先前的表述是*量子比特效率低下*的：它使用 O(D) 个量子比特来表示 D 维超向量，这与 HDC 通常部署的高维场景（通常 D ≳ 10^4）不兼容。同时，扩展可靠可控纠缠量子比特的数量仍然是量子硬件的主要挑战 (J. Kelly (2018)) (https://arxiv.org/html/2607.11936#bib.bib159); 22 (https://arxiv.org/html/2607.11936#bib.bib169); J. Bausch, A. W. Senior, F. J. Heras, T. Edlich, A. Davies, M. Newman, C. Jones, K. Satzinger, M. Y. Niu, S. Blackwell, 等 (2024) (https://arxiv.org/html/2607.11936#bib.bib170)，当前最先进的可靠处理器仍仅运行在大约 10^2 量子比特的规模 (20) (https://arxiv.org/html/2607.11936#bib.bib160)。因此，如图 1 (https://arxiv.org/html/2607.11936#S1.F1) 所示，量子比特高效的超维方法对于实现有实际意义的量子优势至关重要。其次，先前的表述没有提供如何在电路内加载和操作密集超向量的详细门级实现，而是仅在概念层面处理超向量访问。这些限制使得评估该方法是否能在保持有意义可扩展性的同时具体实现变得困难。

在这项工作中，我们提出了一种*量子比特高效且电路可实现*的 HDC 分解量子框架，该框架解决了上述两个限制，同时保持了与先前量子工作相同的渐近搜索复杂度。为了解决量子比特效率问题，我们引入了*对数超向量编码*和*对数绑定编码*，它们仅使用 O(log D) 个量子比特而非 O(D) 个量子比特来表示和操作 D 维超向量。为了解决电路实现问题，我们引入了一个*超向量查找算子*，该算子提供了一种显式的门级机制，用于在电路内检索和应用密集超向量坐标。基于这些组件，我们为快速 HDC 分解制定了一个改进的 Dürr–Høyer 量子搜索过程 (Durr and Hoyer, 1996) (https://arxiv.org/html/2607.11936#bib.bib148)，在保持先前量子方法 O(√(N^F)) 搜索复杂度的同时，使用了显著更少的量子比特。

我们通过电路级验证和分解实验，在多种问题设置下评估了所提出的框架。结果表明，提出的电路能够正确计算预期的 HDC 相似度分数，在可执行范围内准确恢复分解，并且相对于基于显式超向量编码的量子基线，量子比特缩放性能显著提升。

我们的主要贡献总结如下：

1. (1) 我们为量子 HDC 分解引入了**对数超向量编码和对数绑定编码**，将超向量表示成本从 O(D) 个量子比特降低到 O(log D) 个量子比特。
2. (2) 我们提出了一种**超向量查找算子**，提供了密集超向量访问和操作的显式电路级实现。
3. (3) 我们开发了一个**用于 HDC 分解的改进 Dürr–Høyer 量子搜索框架**，在保持先前量子方法二次搜索改进的同时，使用显著更少的量子比特进行操作。
4. (4) 我们通过电路级正确性实验、分解准确性研究以及量子比特缩放分析，**实证验证了所提出的方法**。

## 2. 预备知识

### 2.1. 超维计算

HDC 基础。HDC 是一种使用高维分布式向量（称为*超向量*）来编码信息的表示和计算范式 (Kanerva, 2009) (https://arxiv.org/html/2607.11936#bib.bib112); Plate, 1995 (https://arxiv.org/html/2607.11936#bib.bib145)，其维度 D 通常在数千或数万。一个超向量可以表示一个符号、一个属性或一个结构化对象。HDC 的一个核心特性是，复杂结构可以通过少量代数运算构建，同时保持计算简单性。在这项工作中，我们关注标准的双极性设置，其中每个超向量由 h ∈ {-1, +1}^D 给出。两个基本的 HDC 操作是*绑定*和*捆绑*。在这项工作中，我们用 ⊙ 表示绑定。绑定将多个超向量 h_1, h_2, ... 组合成一个单一的复合超向量 h，根据：

(1) h = h_1 ⊙ h_2 ⊙ ...，在本文考虑的双极性设置中，通过逐元素乘法实现：

(2) h[u] = ∏_j h_j[u]，其中 h[u] 表示向量的第 u 个坐标，u ∈ {0, 1, ..., D-1}。捆绑将多个超向量聚合成一个类似记忆的表示 (Kanerva, 2009) (https://arxiv.org/html/2607.11936#bib.bib112); Plate, 1995 (https://arxiv.org/html/2607.11936#bib.bib145)，通常通过逐元素加法，然后进行可选的归一化或阈值化步骤。为了比较这种组合而成的超向量，我们通过归一化的双极性相关性来度量相似度：

(3) δ(a, b) = (1/D) ∑_{u=0}^{D-1} a[u] b[u]，其取值范围为 [-1, 1]，当 a=b 时等于 1，而对于无关的超向量通常接近 0。这些操作共同使得 HDC 系统能够表示元组、序列和图形等结构化对象，同时保持较低的计算成本。

HDC 分解问题。尽管 HDC 操作使得信息组合非常高效，但从组合表示中恢复潜在因子在计算上是困难的。特别是，如果一个复合超向量是通过绑定 F 个因子构建的，并且每个因子是从大小为 N 的码本中选择的，那么在最坏情况下，精确分解需要搜索 N^F 个可能的元组。因此，搜索空间随着因子数量呈指数级增长，在考虑评估每个候选相似度的成本之前，计算的复杂度为 O(N^F)。在这项工作中，我们关注绑定超向量的分解问题。

### 2.2. 量子计算

量子计算基础。量子计算 (Nielsen and Chuang, 2010) (https://arxiv.org/html/2607.11936#bib.bib154) 提供了一种基于通过幺正操作操控量子态的计算模型。量子信息的基本单位是*量子比特*，其状态处于由计算基态 |0⟩ 和 |1⟩ 张成的二维复向量空间中。一个 n 量子比特系统位于一个 2^n 维的希尔伯特空间中 (Vourdas, 2004) (https://arxiv.org/html/2607.11936#bib.bib171)，从而允许仅使用线性数量的物理量子比特就能紧凑地表示指数级大小的状态空间。计算通过应用量子门（即作用于一个或多个量子比特的幺正变换）来执行。通过利用叠加和干涉，量子电路可以放大对应理想解的振幅，同时抑制其他解。一个典型的例子是 Grover 搜索算法 (Grover, 1996) (https://arxiv.org/html/2607.11936#bib.bib147)，它为无结构搜索实现了二次加速。

量子比特可扩展性。实用量子计算中的一个核心挑战是可靠量子比特系统的有限可扩展性 (J. Kelly (2018)) (https://arxiv.org/html/2607.11936#bib.bib159); 22 (https://arxiv.org/html/2607.11936#bib.bib169); J. Bausch, A. W. Senior, F. J. Heras, T. Edlich, A. Davies, M. Newman, C. Jones, K. Satzinger, M. Y. Niu, S. Blackwell, 等 (2024) (https://arxiv.org/html/2607.11936#bib.bib170)。与经典比特不同，量子比特必须保持相干量子态，并且当纠缠时，共同占据一个张量积希尔伯特空间。保持相干性、控制多量子比特交互以及抑制噪声的难度随着系统规模的增大而迅速增加。因此，需要大量量子比特的量子算法在当前硬件上通常不实用 (J. Kelly (2018)) (https://arxiv.org/html/2607.11936#bib.bib159); 20 (https://arxiv.org/html/2607.11936#bib.bib160)。这一限制对于需要大量量子比特的算法尤其严重。

量子 HDC 分解。近期的工作引入了超维量子最大值寻找 (Poduval 等, 2024) (https://arxiv.org/html/2607.11936#bib.bib149)，它将改进的 Grover 风格量子搜索过程应用于 HDC 分解问题。虽然该方法将搜索复杂度从 O(N^F) 降低到 O(√(N^F))，但它使用了我们称之为显式超向量编码的方式，其中每个超向量维度由一个单独的量子比特表示。