一句话：冻结问题图中的热点节点并划分子空间，减少 QAOA 子电路的 CNOT 数，从而提升解质量。
QAOA 是近期量子计算机展示量子优势的重要候选，但高设备错误率严重限制了其可处理的问题规模。在 QAOA 中，问题图的每条边在每一层对应两个双量子比特 CNOT 操作，而 CNOT 极易出错，因此电路保真度主要由问题图边数决定。作者观察到真实应用中的多数图服从幂律分布，少数热点节点拥有异常高的连接度。基于此，论文提出 FrozenQubits：冻结这些热点节点或量子比特，并将原问题状态空间智能地划分为多个较小子空间，分别独立求解。由此生成的 QAOA 子电路包含更少 CNOT，对门错误和退相干错误更鲁棒，且不同于已有电路切割方法，不需要指数级复杂的后处理。作者在 IBM 八台不同量子计算机上评估了 5,300 个 QAOA 电路，结果显示解质量平均提升 8.73 倍，最高提升 57 倍，代价是约 2 倍的量子资源开销。
Quantum Approximate Optimization Algorithm (QAOA) is one of the leading candidates for demonstrating the quantum advantage using near-term quantum computers. Unfortunately, high device error rates limit us from reliably running QAOA circuits for problems with more than a few qubits. In QAOA, the problem graph is translated into a quantum circuit such that every edge corresponds to two 2-qubit CNOT operations in each layer of the circuit. As CNOTs are extremely error-prone, the fidelity of QAOA circuits is dictated by the number of edges in the problem graph. We observe that the majority of graphs corresponding to real-world applications follow a “power-law” distribution, where some hotspot nodes have significantly higher number of connections. We leverage this insight and propose “FrozenQubits” that freezes the hotspot nodes or qubits and intelligently partitions the state-space of the given problem into several smaller sub-spaces, which are then solved independently. The corresponding QAOA sub-circuits are significantly less vulnerable to gate and decoherence errors due to the reduced number of CNOT operations in each sub-circuit. Unlike prior circuit-cutting approaches, FrozenQubits does not require any exponentially complex postprocessing step. Our evaluations with 5,300 QAOA circuits on eight different quantum computers from IBM show that FrozenQubits can improve the quality of solutions by 8.73x on average (and by up to 57x), albeit while utilizing 2x more quantum resources.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{abs-2210-17037,
title = {FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot Nodes},
author = {Ramin Ayanzadeh and Narges Alavisamani and Poulami Das and Moinuddin Qureshi},
booktitle = {ASPLOS},
year = {2023},
doi = {10.1145/3575693.3575741}
}