标题： 用于组合优化的量子分治算法的扩展 显示英文标题

标题： Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization

摘要： 量子优化作为一个领域，很大程度上受到当前量子计算硬件的限制，由于规模、性能和保真度的限制，大多数非平凡的问题实例无法在量子设备上运行。 即使提出的解决方案，如分布式量子计算系统，也可能由于设备间通信的高成本而难以实现扩展。 为了解决这些问题，我们提出了延迟约束量子分治算法（DC-QDCA），这是一种构建量子电路的方法，可大大降低某些量子图优化算法的设备间通信成本。 这是通过识别一组顶点，其移除可以将输入图分割，称为分割器；通过操作与分割器中顶点相关的约束放置，我们可以大大简化优化电路的拓扑结构，减少所需的设备间操作数量。 此外，我们引入了一种迭代算法，基于这些技术来寻找可能包含数千个变量的问题的解决方案。 我们的实验结果使用量子模拟器表明，我们可以在保持相似或更高质量水平的同时，构建出比之前QDCA方法大近三倍的可行电路。 显示英文摘要

摘要： Quantum optimization as a field has largely been restricted by the constraints of current quantum computing hardware, as limitations on size, performance, and fidelity mean most non-trivial problem instances won't fit on quantum devices. Even proposed solutions such as distributed quantum computing systems may struggle to achieve scale due to the high cost of inter-device communication. To address these concerns, we propose Deferred Constraint Quantum Divide and Conquer Algorithm (DC-QDCA), a method for constructing quantum circuits which greatly reduces inter-device communication costs for some quantum graph optimization algorithms. This is achieved by identifying a set of vertices whose removal partitions the input graph, known as a separator; by manipulating the placement of constraints associated with the vertices in the separator, we can greatly simplify the topology of the optimization circuit, reducing the number of required inter-device operations. Furthermore, we introduce an iterative algorithm which builds on these techniques to find solutions for problems with potentially thousands of variables. Our experimental results using quantum simulators have shown that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.