基于增量量子（受量子启发）退火技术的大规模多查询优化

《Proceedings of the ACM on Management of Data》：Large-Scale Multiple Query Optimisation with Incremental Quantum(-Inspired) Annealing

多查询优化（MQO）通过专用硬件加速器如Fujitsu数字安态器（DA），结合增量处理与动态搜索策略，有效突破NP难问题的计算规模限制，显著提升性能，并为量子加速器应用奠定基础。

　　

摘要

多查询优化（MQO）旨在减少查询批次之间的冗余工作。尽管MQO能够显著提升性能，但该问题属于NP难问题，这限制了在通用硬件上可解决的问题规模。我们提出利用专用硬件求解器（如富士通的Digital Annealer（DA））来扩展MQO的应用范围，使其能够处理以往无法解决的大规模问题。

我们提出了一种创新的增量处理方法，该方法结合了传统计算与DA加速技术。通过将MQO问题高效地划分为多个子问题，并采用动态搜索策略（该策略能够重新利用最初被丢弃的信息来逐步处理各个问题），我们的方法克服了硬件容量限制，能够处理规模极其庞大的MQO实例（最多可达νm1000个查询）。全面的实证评估表明，我们的方法显著优于现有的方法。我们的通用框架为其他基于量子技术的数据库应用奠定了基础，并为未来的量子加速器发展提供了方向。

可用格式

您可以使用以下格式查看完整内容：

PDF