Auxiliary-qubit-free Quantum Algorithm Solves Minimum Dominating Set Problem on NISQ Devices

Combinatorial optimisation problems, notoriously difficult for classical computers, represent a key target for emerging quantum technologies. Guanghui Li, Xiaohui Ni, and Junjian Su, along with colleagues from Beijing University of Posts and Telecommunications and elsewhere, have now developed a new approach to solving one such problem, the Minimum Dominating Set (MDS), which has applications in network design and logistics. Their research introduces a quantum algorithm that eliminates the need for auxiliary qubits, a common requirement in existing methods that significantly increases the demands on quantum hardware. This advance allows the algorithm to achieve performance comparable to current state-of-the-art techniques while dramatically reducing the number of qubits required, paving the way for more scalable solutions on near-term quantum devices and bringing practical quantum optimisation closer to reality. Further refinement of the algorithm, through independent circuit parameters, demonstrates potential for even higher quality solutions.

Quantum Diversity Optimisation via QAOA Algorithms

Scientists are exploring Quantum Approximate Optimization Algorithm (QAOA) to solve complex optimization problems, focusing on the Maximum Diversity Problem (MDP). This research aims to improve QAOA’s performance for applications such as resource allocation, scheduling, and machine learning. The method utilizes a hybrid quantum-classical approach, combining quantum computation with classical optimization techniques. A problem Hamiltonian encodes the problem’s constraints, and classical algorithms optimize the parameters of the quantum circuit. Experiments involve testing the algorithm on various instances of the MDP, evaluating solution quality, computational time, and scalability. The team implemented their algorithm using Mindspore Quantum, a quantum computing framework. This work addresses a key limitation of existing quantum approaches, which typically require a significant number of auxiliary qubits, hindering scalability on current quantum hardware. The team’s breakthrough delivers an auxiliary-qubit-free algorithm, eliminating the need for these additional qubits and simplifying circuit design. The method transforms the MDS problem using Boolean algebra, converting inequality constraints into equalities without introducing auxiliary variables.

This innovative approach allows the construction of a quantum circuit directly from the problem’s core requirements, reducing the overall qubit count. Experiments demonstrate that this new algorithm achieves performance comparable to the best existing quantum algorithms for the MDS problem, while simultaneously using fewer qubits. An ablation study using multi-angle Quantum Approximate Optimization Algorithm (QAOA) refined the algorithm’s performance, revealing that independent circuit parameters improve solution quality. The team evaluated the algorithm on both randomly generated 3-regular graphs and Erdős-Rényi random graphs, consistently achieving competitive results. The method utilizes Boolean algebra to transform the problem, significantly reducing the qubit count needed for implementation. Numerical experiments on both 3-regular and random graphs demonstrate that this algorithm achieves comparable, and in many cases superior, performance to existing QAOA methods while using fewer qubits. Further investigation revealed that independent parameter optimization for each circuit component enhances solution quality and robustness. While the resulting circuits exhibit increased depth, the substantial reduction in qubit requirements makes this approach particularly promising for implementation on current, limited-scale quantum devices. Future research will focus on addressing the increased circuit depth to enable scaling to larger, more complex problems and extending this Boolean algebra-based approach to other combinatorial optimization problems involving inequality constraints.