arXiv:2212.02669

Quantum-Inspired Optimization over Permutation Groups

Rathi Munukur, Bhaskar Roy Bardhan, Devesh Kumar Upadhyay, Joydip Ghosh

Published Dec 6, 2022• 0 citations

Abstract

Quantum-inspired optimization (QIO) algorithms are computational techniques that emulate certain quantum mechanical effects on a classical hardware to tackle a class of optimization tasks. QIO methods have so far been employed to solve various binary optimization problems and a significant (polynomial) computational speedup over traditional techniques has also been reported. In this work, we develop an algorithmic framework, called Perm-QIO, to tailor QIO tools to directly solve an arbitrary optimization problem, where the domain of the underlying cost function is defined over a permutation group. Such problems are not naturally recastable to a binary optimization and, therefore, are not necessarily within the scope of direct implementation of traditional QIO tools. We demonstrate the efficacy of Perm-QIO in leveraging the structure of cost-landscape to find high-quality solutions for a class of vehicle routing problems that belong to the category of non-trivial combinatorial optimization over the space of permutations.

DOI: 10.48550/arxiv.2212.02669

Related papers

A Quantum-Inspired Optimization Framework for Engineering Decision Support Systems

Ferdi Güler, Batuhan Selamoglu

Purpose: The development of engineering decision support systems requires effective optimization techniques to deal with complex optimization problems such as energy management, logistics optimization, and resource management. The most popular classical optimization techniques, such as Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), are often less effective in terms of optimization performance and are often likely to suffer from slow optimization speed and premature convergence to local optima when dealing with highdimensional optimization search space. The quantum-inspired optimization (QIO) techniques are an emerging class of optimization techniques that attempt to mimic some principles of quantum computing on classical computers to overcome the limitations of classical optimization techniques. The purpose of this research is to develop a quantum-inspired optimization framework to overcome the limitations of classical optimization techniques in engineering decision support systems. Method: The proposed optimization framework incorporates a probabilistic amplitude representation of solutions, rotation-based evolutionary optimization, and simulated annealing acceptance criteria. The optimization framework was tested on two optimization scenarios: a highdimensional optimization problem inspired by a Rastrigin-like function representing energy management optimization and a multi-objective optimization problem inspired by logistics optimization with the goal of minimizing transportation costs and time. The optimization performance and effectiveness of the proposed optimization framework were compared with classical optimization techniques such as GA and PSO. Findings: The proposed optimization framework outperforms traditional methods such as GA and PSO in terms of speed and quality of results. In the high-dimensional problem, the proposed framework achieved an optimal value of 38.96, which is better compared to the results of PSO, which achieved 69.42, and GA, which achieved 137.22. In the multi-objective problem, the proposed framework achieved Pareto results, which show better performance and effectiveness compared to the traditional methods. Conclusion: The optimization results indicate that the quantum-inspired optimization framework is an effective optimization tool that can be used to overcome the limitations of classical optimization techniques in engineering decision support systems. The proposed optimization framework provides a link between classical optimization techniques and emerging quantum optimization techniques while being able to run on classical computers.

Apr 1, 20260 citations

Quantum-Inspired Algorithms for Optimization of Large-Scale Combinatorial Problems

Jincheng Zhang

This paper investigates the application of quantum-inspired algorithms to the optimization of large-scale combinatorial problems. Recognizing the limitations of current quantum computing hardware, this research focuses on developing classical algorithms that emulate key quantum principles – superposition and interference – to achieve significant performance improvements over traditional optimization methods. The core idea is to leverage amplitude amplification and interference cancellation techniques, inspired by quantum mechanics, to efficiently explore the solution space. We present a framework for designing such algorithms, detailing the mathematical formulations and the core mechanisms involved. The research aims to demonstrate that, without the need for actual quantum computers, these quantum-inspired approaches can offer a compelling alternative for tackling complex optimization challenges. The presented algorithms are evaluated conceptually, focusing on the mathematical foundations and design principles rather than empirical testing.

Aug 28, 20260 citations

Physics-Inspired Optimization in the QUBO Framework: Key Concepts and Approaches

Lien-Po Yu, Chin-Fu Nien

Quantum computing promises to have a tremendous advantage over its classical counterpart for solving computationally hard problems, yet remains in a relatively early stage for practical applications owing to the limited capabilities of today’s quantum computers. The approach to the special purposes of quantum computers by exploiting the special-purpose physics-inspired or quantum-inspired computers is emerging as a novel alternative to its quantum counterpart in tackling hard problems in high-performance computing. Inspired by physics, the Ising machine — a type of special-purpose computer that implements or emulates physics or quantum effects of the Ising model to speed up finding solutions to optimization problems — has recently become an active research area in the field of combinatorial optimization. This paper is to address the key enabling software and hardware technology underlying physics-inspired optimization using Ising machines in the unified quadratic unconstrained binary optimization (QUBO) framework for modeling and solving computationally hard combinatorial optimization problems, and with an aim to shed some light on the challenges and opportunities associated with the ever-growing landscape of this novel high-performance computing.

SPINAug 30, 20231 citation

An Innovative Hunting-based Quantum-inspired Jaguar Algorithm for Combinatorial Optimization

Yao–Hsin Chou, Jyun–Yi Shen, Yu-Chi Jiang +2 more

Quantum-inspired optimization (QIO) is a promising technique that simulates quantum behaviors on classical computers to leverage both classical and quantum advantages in tackling complex optimization problems. This study first proposes the quantum-inspired jaguar algorithm (QJA) to solve combinatorial optimization problems (COP). The quantum property helps address COP efficiently when the element increases in the search space. Besides, QJA extracts the crucial concept of the hunting mechanism from the jaguar algorithm (JA), which effectively addresses numerical optimization in classical computing. The featured hunting mechanism enables QJA to automatically assess the algorithm's situation and adaptively update the critical parameters in QIO, thereby performing an efficient search. QJA tackles a complex financial application: portfolio optimization, which requires an effective solution quickly. In the experimental result, this study utilizes real-world financial data to demonstrate the effectiveness of QJA and to compare it with other QIOs, facilitating advancements in quantum finance. The convergence results indicate that QJA can identify higher quality portfolios in the early stages and continue to enhance them throughout the search process. In summary, this study transfers the knowledge and insights gained from the hunting mechanism in classical computing to QIO, integrating both classical and quantum computing techniques to address COP effectively.

IEEE International Conference on Quantum Computing and Engineering (QCE)Sep 15, 20240 citations

Techniques to enhance a QUBO solver for permutation-based combinatorial optimization

Siong Thye Goh, Jianyuan Bo, Sabrish Gopalakrishnan +1 more

Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)Jul 9, 202210 citations

Quantum Illumination Optimization

Jincheng Zhang

Quantum Illumination Optimization (QIO) is a novel quantum optimization algorithm designed to achieve near-optimal solutions in a limited time frame. Traditional optimization methods often require extensive computational resources and can be slow to converge. QIO leverages the inherent randomness and adaptive nature of quantum computation to dynamically adjust the optimization process, effectively guiding the algorithm towards the optimal solution without requiring exhaustive computation. This paper details the core mechanism of QIO, explores its potential advantages, and discusses its theoretical foundations. We present a framework for applying QIO to a specific optimization problem, demonstrating its effectiveness through simulations and preliminary analysis. The core claim is that QIO can significantly reduce the computational time required for finding optimal solutions compared to conventional algorithms.

Sep 2, 20260 citations