A parallel global optimization algorithm inspired by quantum physics

Yipeng Liu, Gary J. Kœhler

Anna Ouskova Leonteva, Ulviya Abdulkarimova, T. M. Wintermantel +3 more

This paper presents a novel multi-threaded quantum inspired optimization algorithm targeted at global search in continuous domains. The proposed approach is based on a Diffusion Monte Carlo (DMC) physical model and is characterized by a set of parallel quantum walk processes. The effectiveness of the proposed algorithm is demonstrated by experimental results on the 24 noiseless functions from the Black Box Optimization Benchmark of the Comparing Continuous Optimization benchmarking platform (COCO).

Kuk-Hyun Han, Kui-Hong Park, Ci-Ho Lee +1 more

This paper proposes a new parallel evolutionary algorithm called parallel quantum-inspired genetic algorithm (PQGA). Quantum-inspired genetic algorithm (QGA) is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. QGA is suitable for parallel structures because of rapid convergence and good global search capability. That is, QGA is able to possess the two characteristics of exploration and exploitation simultaneously. The effectiveness and the applicability of PQGA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that PQGA is superior to QGA as well as other conventional genetic algorithms.

V. Protopopescu, J. Barhen

Kyo Kuroki, Satoru Jimbo, Thiem Van Chu +2 more

In recent years, quantum annealing has triggered active research on annealing methods for solving various combinatorial optimization problems (COPs) by mapping them to the Ising model based on spin glass theory. In particular, parallel annealing algorithms (PAAs) that can update all variables simultaneously attract attention due to fast optimization using parallel computers, either as an extension of Simulated Annealing rooted in classical thermodynamics or as a quantum-inspired algorithm. However, both types of PAAs face their own challenges. The classical thermodynamics-based PAAs (c-PAAs) perform inferior to the quantum-inspired PAAs (q-PAAs), whereas the q-PAAs require more parameters to be tuned than the c-PAAs. This paper proposes a new c-PAA based on Mean Field Annealing, which has the unique feature of updating analog variables deterministically. The proposed PAA achieves high speed and robustness despite fewer parameters than the q-PAAs, which means the proposed PAA breaks through the challenges of conventional PAAs. We demonstrate its performance through experiments on four types of COPs: Maximum Cut Problem, Graph Coloring Problem, Maximum Independent Set Problem, and Traveling Salesman Problem. These results imply that unless a real physical phenomenon is used, quantum-inspired algorithms cannot be considered superior to classical thermodynamics-based algorithms.

Bin Cao, Shanshan Fan, Jianwei Zhao +3 more