Variable Topology Quantum Circuits Enhance Performance on Set Partitioning Problems

Quantum computing offers potential solutions to complex optimisation problems, and researchers are increasingly exploring ways to harness its power with existing hardware. Bruno O. Fernandez from QuIIN, Rodrigo Bloot from the Federal University of Latin-American Integration, and Marcelo A. Moret, also from QuIIN, and their colleagues, present a new framework that uses evolving quantum circuits to tackle these challenges. Their work addresses a common problem in quantum optimisation, where algorithms can become stuck before finding the best solution, by allowing the structure of the quantum circuit itself to change during the optimisation process. Testing this approach on instances of the set partitioning problem, the team demonstrates that circuits with variable topology offer a promising alternative to traditional methods, and notably, incorporating a specifically designed “pseudo-counterdiabatic” term significantly improves performance and avoids stagnation, paving the way for efficient solutions to integer optimisation problems on larger scales.

Variational algorithms, which employ classical optimisation routines, hold particular promise for implementation on near-term quantum devices. However, convergence stagnation represents a significant challenge. This problem, computationally difficult for classical computers as its size increases, involves dividing items into groups while minimizing cost and ensuring each item belongs to only one group. The team aims to leverage quantum computing to find better or faster solutions than classical algorithms can provide. The researchers investigated several quantum algorithms, comparing them to classical approaches. This incorporation aims to improve the algorithm’s ability to escape local optima, points where the search for a solution gets stuck. The team also compared their quantum algorithms against classical methods like branch-and-cut, simulated annealing, and genetic algorithms. The idea of using evolutionary algorithms to design quantum circuits is novel, and the incorporation of the pseudo-counterdiabatic term is a clever attempt to improve performance by making the algorithm more robust to local optima.

Experiments indicate that the pseudo-counterdiabatic variant outperforms both the standard QCE and VQE on the set partitioning problem, suggesting the term effectively improves the algorithm’s ability to find good solutions. QCE appears to be a promising approach for solving combinatorial optimization problems, and the algorithms are designed for implementation on near-term quantum computers. This research demonstrates the potential of quantum computing to solve real-world optimization problems. This work addresses a key limitation of existing quantum optimization algorithms, the tendency to get stuck during the search for the best solution, known as convergence stagnation. The team proposes a framework employing circuits where the connections between quantum bits can change during the optimization process, offering greater flexibility than traditional fixed-circuit methods. Two distinct strategies were explored: a completely flexible, adaptable circuit and one incorporating the novel “pseudo-counterdiabatic” term inspired by physics, designed to guide the optimization process more effectively.

Experiments show that both approaches outperform the Variational Quantum Eigensolver (VQE) in several test cases, and the strategy incorporating the pseudo-counterdiabatic term consistently avoided getting stuck, successfully finding solutions in instances where other methods failed. The set partitioning problem, a well-known challenge in computer science, involves dividing a set of items into groups while minimizing overall cost and ensuring every item belongs to exactly one group, with practical applications in areas like airline scheduling and resource allocation. The team reformulated the problem into a QUBO (Quadratic Unconstrained Binary Optimization) format, a standard approach for implementing optimization problems on quantum computers. The results indicate that this new framework offers a significant step towards scalable quantum optimization. By circumventing the need for classical optimizers and avoiding convergence stagnation, the method holds potential for tackling larger, more complex optimization problems than previously possible. The ability to dynamically adjust the quantum circuit’s structure appears to be a key factor in its success, offering a pathway towards more robust and efficient quantum algorithms for real-world applications.

Quantum Circuits Solve Set Partitioning Problems

The research presents a new framework for tackling complex optimization problems, specifically the set partitioning problem, using quantum circuits with variable topology. The team explored two approaches: a standard evolutionary method and one incorporating the novel “pseudo-counterdiabatic” evolutionary term inspired by physics principles. Experiments demonstrate that both methods offer promising results, successfully optimizing instances of the set partitioning problem, and the pseudo-counterdiabatic approach effectively avoided the common issue of convergence stagnation. This work offers a potential pathway towards solving integer optimization problems without relying on classical optimizers, which could be beneficial for larger-scale applications. By utilizing circuits that can adapt their structure during the optimization process, the framework shows an ability to navigate complex solution spaces more effectively.