A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation

技术摘要：一种用于离散优化的量子无结构搜索算法

问题陈述
本文探讨了解决离散优化问题（特别是组合优化问题）的挑战，这类问题的变量为二进制且无法定义导数。虽然基于梯度的算法在连续变量方面非常有效，但在离散空间中往往会失效，而这些空间通常是 NP-hard 的。现有的量子方法（如二次无约束二进制优化，QUBO 框架）仅限于包含一阶和二阶项的目标函数。此外，许多当前的量子优化算法（例如变分量子算法）依赖于混合经典-量子回路，这些回路可能会受到噪声影响或需要深层电路。作者提出了一种寻找一般离散函数 $f(x)$ 的极值或根的方法，该函数可能包含超出 QUBO 二次限制的高阶项。

方法论：QSERA 算法
作者引入了量子极值与根搜索算法（QSERA），它是基于 Grover 算法的量子搜索算法（QSA）家族的一员。该方法论分为两个主要步骤：

1. 算子构建 ($f(x) \to u(z)$)：
   第一步涉及将寻找极值（或根）的条件 $f(x^*) \approx f^*$ 映射为对二进制字符串 $z^*$ 的无结构搜索问题。

   • 重缩放（Rescaling）： 将目标函数 $f(x)$ 重缩放为函数 $g(x) \in [0, 1]$。对于最大化问题，$g(x) = (f(x) - f_{min}) / (f_{max} - f_{min})$；对于最小化问题，$g(x) = (f_{max} - f(x)) / (f_{max} - f_{min})$；对于求根问题，则应用特定的变换。这需要先验知识或对全局最小值 ($f_{min}$) 和最大值 ($f_{max}$) 的估计。
   • 放大（Amplification）： 为了创建一个满足 $u(z^*) = 1$ 且 $u(z \neq z^*) = 0$ 的二进制算子 $u(z)$，将 $g(x)$ 提升至高次幂 $n$（即 $u_n(z) \equiv g(x)^n$）。当 $n \to \infty$ 时，$u_n(z)$ 趋于理想的算子。
   • 泛化（Generalization）： 文中指出，$f(x)$ 可以是最高达 $K$ 阶的通用多项式（公式 10），这使得目标函数可以比标准的 QUBO 形式更复杂。
   • 门实现（Gate Implementation）： 作者推导了算子的量子电路。他们定义了对应于二进制变量的自伴算子 $B_k$，并构建了一个酉算子 $G$，使得 $G|z\rangle = g(x)|z\rangle$。随后定义算子 $Q^*$ 为 $e^{i\pi G^n}$。该算子被分解为每个阶数项（零阶、一阶、二阶等）的酉算子 $Q^*_j$ 的乘积，并通过辅助比特和相位移动门来实现。

2. 搜索执行：
   一旦构建好算子 $Q^*$，算法便采用 Grover 扩散算子 ($Q_+$) 和算子 ($Q^*$) 进行迭代循环。系统初始化在均匀叠加态中，并通过重复应用算子 $(Q_+ Q^*)$ $m_{opt} \approx (\pi\sqrt{N} - 2)/4$ 次，以放大目标态 $|z^*\rangle$ 的振幅。

核心贡献

• 超越 QUBO 的泛化能力： 与许多受限于二次形式的量子优化方法不同，QSERA 可以处理包含高阶项（三次、四次等）的目标函数，使其适用于更广泛的组合优化问题。
• 显式的电路构建： 本文提供了用于构建任意多项式阶数的量子算子门的详细数学推导，包括用于电路参数的系数递归计算。
• 处理近似边界： 作者分析了 $f_{min}$ 和 $f_{max}$ 未能精确知晓的情况。他们证明，虽然算法仍能运行，但找到精确最优解的概率取决于幂参数 $n$ 的选择。如果 $n$ 过大，算子信号可能会消失；如果 $n$ 过小，信号则不够显著。存在一个最优的 $n$ 来平衡这些因素。

结果：投资组合优化案例研究
作者使用一个包含 $N_a = 4$ 个资产、产生 $N=16$ 种可能投资组合的投资组合优化问题验证了 QSERA。

• 设置： 目标是找到一个包含 2 个资产的投资组合，以最小化与基准收益率和波动率的距离。目标函数包含了最高至四阶的项。
• 实现： 使用 4 个用于投资组合状态的量子比特、2 个用于 AND 操作的辅助量子比特以及 1 个用于相位追踪的辅助量子比特组装了量子电路。
• 性能：
  • 通过最优的 Grover 迭代次数 ($m_{opt} = 2$) 和精心选择的幂次 $n \approx 24$，算法成功识别出了具有最高概率的最优投资组合（状态 $|1001\rangle$）。
  • 第二优的投资组合（$|0101\rangle$）也显示出相对较高的概率，这反映了算法找到了最接近估计边界的解。
  • 研究证实，如果 $f_{min}$ 和 $f_{max}$ 是估计值而非精确值，测量到真实最优解的概率小于 1，因此需要多次“采样”（多次执行）以从近优解中区分出真正的最优解。
  • 文中可视化了幂次 $n$ 与成功概率之间的关系，显示出在中间 $n$ 值处存在概率峰值；若 $n$ 过大（信号抑制）或过小（辨别力不足），性能都会下降。

意义与主张
本文声称 QSERA 在寻找离散函数的极值或根方面，相对于经典的暴力搜索提供了二次加速 ($O(\sqrt{N})$)。其主要意义在于能够：

1. 解决与标准 QUBO 形式不兼容的高阶目标函数优化问题。
2. 无需像 VQA 那样依赖混合经典-量子参数优化回路，而是依靠单次量子执行（尽管如果边界是近似的，可能需要多次采样以获得统计置信度）。
3. 潜在地解决“嘈杂”或梯度陡峭的连续函数（经离散化后）问题，在这些情况下基于梯度的算法可能会失效，尽管作者指出，对于连续变量，结构化搜索通常更高效。

作者总结道，虽然算法需要已知函数边界才能保证成功，但它仍然是离散优化的强大工具，特别是当目标函数的结构超出了当前基于 QUBO 方法的能力范围时。