顺序优化

准备好飞跃了吗（通过共同设计）？加入量子硬件上的顺序优化

利用量子现象实现计算加速的前景使得量子处理单元 (QPU) 对于许多算法数据库问题具有吸引力。查询优化涉及通常需要探索大型搜索空间的问题，似乎是量子算法的理想匹配。我们提出了连接排序的第一个量子实现，这是最受研究和最基本的查询优化问题之一，基于对二次二元无约束优化问题的重新表述。我们在两种最先进的方法（基于门的量子计算和量子退火）上对我们的方法进行了经验描述，并确定了与最知名的经典连接排序方法相比的加速，这些方法的输入大小符合当前的量子退火器。然而，我们也证实，早期技术的极限很快就会达到。当前的 QPU 被归类为嘈杂的中型量子计算机 (NISQ)，并且受到各种限制的限制，与理想的未来 QPU 相比，这些限制降低了它们的能力，这阻止了我们扩大问题维度并实现实用性。为了克服这些挑战，我们的公式考虑了特定的 QPU 属性和限制，并允许我们在可实现的解决方案质量和问题规模之间进行权衡。与所有针对查询优化和数据库相关挑战的量子计算的先前工作相比，我们超越了当前可用的 QPU，并明确针对可扩展性限制：利用从数值模拟和实验分析中获得的见解，我们确定了共同设计 QPU 以提高其连接排序实用性的关键标准，并展示了即使相对较小的物理架构改进也能带来显着的增强。最后，我们概述了定制设计 QPU 的实际实用性之路。