We introduce a quantum divide and conquer algorithm that enables the use of distributed computing for constrained combinatorial optimization problems. The algorithm consists of three major components: classical partitioning of a target graph into multiple subgraphs, variational optimization over these subgraphs, and a quantum circuit cutting procedure that allows the optimization to take place independently on separate quantum processors. We simulate the execution of the quantum divide and conquer algorithm to find approximate solutions to instances of the Maximum Independent Set problem which have nearly twice as many nodes than the number of qubits available on a single quantum processor.
We introduce a quantum divide and conquer algorithm that enables the use of distributed computing for constrained combinatorial optimization problems. The algorithm consists of three major components: classical partitioning of a target graph into multiple subgraphs, variational optimization over these subgraphs, and a quantum circuit cutting procedure that allows the optimization to take place independently on separate quantum processors. We simulate the execution of the quantum divide and conquer algorithm to find approximate solutions to instances of the Maximum Independent Set problem which have nearly twice as many nodes than the number of qubits available on a single quantum processor.
Scaling the size of monolithic quantum computer systems is a difficult task. As the number of qubits within a device increases, a number of factors contribute to decreases in yield and performance. To meet this challenge, distributed architectures composed of many networked quantum computers have been proposed as a viable path to scalability. Such systems will need algorithms and compilers that are tailored to their distributed architectures. In this work we introduce the Quantum Divide and Conquer Algorithm (QDCA), a hybrid variational approach to mapping large combinatorial optimization problems onto distributed quantum architectures. This is achieved through the combined use of graph partitioning and quantum circuit cutting. The QDCA, an example of application-compiler co-design, alters the structure of the variational ansatz to tame the exponential compilation overhead incurred by quantum circuit cutting. The result of this cross-layer co-design is a highly flexible algorithm which can be tuned to the amount of classical or quantum computational resources that are available, and can be applied to both near- and long-term distributed quantum ar-chitectures. We simulate the QDCA on instances of the Maximum Independent Set problem and find that it is able to outperform similar classical algorithms. We also evaluate an 8-qubit QDCA ansatz on a superconducting quantum computer and show that circuit cutting can help to mitigate the effects of noise. Our work demonstrates how many small-scale quantum computers canwork together to solve problems 85 % larger than their own qubit count, motivating the development and potential of large-scale distributed quantum computing.
Combinatorial optimization is considered a promising class of problems in which quantum computers can show significant advantages. However, problems of practical relevance typically have more variables than current or foreseeable quantum computers have qubits. Here we introduce a divide and conquer approach that partitions the optimization problem into subgraphs that can be represented on smaller quantum processors. We then find all states of the subgraphs that can possibly be part of the solution to the entire problem by determining the cost or energy ranges in which the local subgraph energies of these states must be contained. This allows us to reduce the problem by only considering the subspace spanned by these states. We then recombine the system using a binary encoding for each subgraph with a local energy ordering. This process can be iterated until no further reduction is possible. We also find that the number of necessary qubits can be reduced further when only retaining states in a fraction of the relevant energy range at very little expense in terms of approximation ratio to the global ground state. In numerical simulations, we find that our approach allows us to solve combinatorial optimization problems on weighted random 3-regular graphs with ∣V∣=40 discrete variables on ∼∣V∣/4 qubits while retaining a possible approximation ratio of ∼99.9%. We also observe an increasing reduction with larger system sizes.
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.
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.
Noisy Intermediate-Scale Quantum (NISQ) computers currently available have a few thousand qubits, and could potentially solve combinatorial optimization problems efficiently. However, the sizes of the problems that could be solved are limited by the number of qubits, their connectivity, high noise, and short coherence times. In this work, we propose hybrid quantum-classical algorithms based on the divide and conquer paradigm for solving larger Maximum Independent Set (MIS) and Maximum Weighted Independent Set (MWIS) problems on graphs than would otherwise be possible on NISQ devices. The machines include D-Wave Quantum Annealers and QuEra Quantum Computers with Neutral Atoms. Our algorithms are designed for separable graphs, which are classes of graphs with good vertex separators; these include planar graphs, finite element meshes with good aspect ratios, nearest neighbor graphs, and certain classes of geometrically defined graphs. The algorithms recursively employ vertex separators to create a collection of small subgraphs, from which NISQ computers obtain disjoint maximal independent sets, which are then augmented by independent vertices from the separators. We demonstrate competitive results compared to the classical Luby's algorithm, and KaMIS, a state-of-the-art classical MIS solver, on graphs with several thousand vertices. These divide and conquer-based algorithms are also well-suited for distributed quantum computer architectures.
Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm for solving combinatorial optimization problems. However, it cannot overcome qubit limitation for large-scale problems. Furthermore, the simulation time of QAOA scales poorly with the problem size. We propose a divide-and-conquer QAOA (DC-QAOA) to address the above challenges for graph maximum cut (MaxCut) problem. The algorithm works by recursively partitioning a larger graph into smaller ones whose MaxCut solutions are obtained with small-size noisy intermediate-scale quantum computers. The overall solution is retrieved from the subsolutions by applying the combination policy of measurement distribution reconstruction (MDR). The solution quality depends on the graph partitioning algorithm and MDR policy. Multiple partitioning and reconstruction methods are proposed and compared. Results are evaluated by metrics, such as quantum program runtime, measurement expectation value (EV), and approximation ratio (AR). The results show that DC-QAOA achieves 97.14% AR (20.32% higher than classical counterpart), and 94.79% EV (15.80% higher than quantum annealing). DC-QAOA solves large-scale graph instances with a polynomial rate or returns unsuccessful partition if graph connectivity requirement is not fulfilled otherwise.