Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization

Understand

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.