Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2311.12867 · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics

Amplitude-Ensemble Quantum-Inspired Tabu Search Algorithm for Solving 0/1 Knapsack Problems

Kuo-Chun Tseng, Wei-Chieh Lai, I-Chia Chen, Yun-Hsiang Hsiao, Jr-Yu Chiue, Wei-Chun Huang

Published Oct 6, 2024• 4 citations
arXivHTMLPDF

Abstract

In this study, we learned more about quantum properties from quantum and metaheuristic algorithms after conducting many experiments. We then propose an improved version of Quantum-inspired Tabu Search (QTS), which en-hances the utilization of population information. The new version is called “Amplitude-Ensemble” QTS (AE-QTS). This makes AE-QTS more similar to the real quantum search algorithm, Grover Search Algorithm, in abstract concept, while keeping the simplicity of the algorithm. Later, we demonstrate the AE-QTS on the classical combinatorial optimization 0/1 knapsack problem. Experimental results show that the AE-QTS outperforms other algorithms, including the QTS, by at least an average increase of nearly 20% in all cases and even by 30% in some cases. Even as the problem complexity increases, the quality of the solutions found by our method remains superior to that of the QTS. These results confirm that our method has better search performance.

DOI
10.1109/smc54092.2024.10831250

Related papers

Amplitude-Ensemble Quantum-Inspired Tabu Search Algorithm for Quantum Boolean Circuit Synthesis

Kuo-Chun Tseng, Ziyi Sun, Pei-Lun Ho +5 more

Quantum circuit synthesis is a key technique in quantum computing. Traditional methods often generate circuits with high cost, making it crucial to produce correct and low-cost circuits efficiently. This study proposes the Amplitude-Ensemble Quantum-inspired Tabu Search (AE-QTS) algorithm for quantum Boolean circuit synthesis. AE-QTS demonstrates strong search capability with fewer parameters. Experimental results show that it outperforms other algorithms on low-bit problems and retains a certain level of synthesis ability on high-bit ones. However, the results also reveal that if the encoding frequently produces infeasible solutions, all algorithms will eventually fail, regardless of design. Therefore, future work should focus on developing encoding methods that consistently generate feasible solutions, which is essential for effectively applying metaheuristics to quantum Boolean circuit synthesis.

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics•Oct 5, 2025•0 citations

Entanglement-Enhanced Quantum-Inspired Tabu Search Algorithm for Function Optimization

Shu–Yu Kuo, Yao–Hsin Chou

Many metaheuristic algorithms have been proposed to solve combinatorial and numerical optimization problems. Most optimization problems have high dependence, meaning that variables are strongly dependent on one another. If a method were to attempt to optimize each variable independently, its performance would suffer significantly. When traditional optimization techniques are applied to highdependence problems, they experience difficulty in finding the global optimum. To address this problem, this paper proposes a novel metaheuristic algorithm, the entanglement-enhanced quantum-inspired tabu search algorithm (Entanglement-QTS), which is based on the quantum-inspired tabu search (QTS) algorithm and the feature of quantum entanglement. Entanglement-QTS differs from other quantum-inspired evolutionary algorithms in that its Q-bits have entangled states, which can express a high degree of correlation, rendering the variables more intertwined. Entangled Q-bits represent a state-of-the-art idea that can significantly improve the treatment of multimodal and high-dependence problems. Entanglement-QTS can discover optimal solutions, balance diversification and intensification, escape numerous local optimal solutions by using the quantum not gate, reinforce the intensification effect by local search and entanglement local search, and manage strong-dependence problems and accelerate the optimization process by using entangled states. This paper uses nine benchmark functions to test the search ability of the entanglement-QTS algorithm. The results demonstrate that Entanglement-QTS outperforms QTS and other metaheuristic algorithms in both its effectiveness at finding the global optimum and its computational efficiency.

IEEE Access•Jan 1, 2017•64 citations

A Quantum Global Optimization Algorithm: Application to the Knapsack Problem

Mohamed Yassine Cherif, Wided Lejouad Chaari, Olfa Belkahla Driss

Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm for solving combinatorial optimization problems with improved performance and runtime approaching Grover’s optimal time of quantum search. The algorithm determines the global optimum of the objective function defining the addressed problem using an enhanced application of Grover’s search by simultaneously exploring all comparison cases of possible solutions without requiring iterative operations, unlike previous approaches, which affect performance and runtime. The paper also introduces a version of the proposed algorithm for solving the knapsack problem, along with its execution results and a comparison with other competing algorithms.

•Jan 12, 2026•0 citations

A Quantum Global Optimization Algorithm: Application to the Knapsack Problem

Mohamed Yassine Cherif, Wided Lejouad Chaari, Olfa Belkahla Driss

Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm to solve combinatorial optimization problems intended to provide an improved performance. The proposed algorithm aims to amplify the probability of selecting the global optimum of the objective function defining the addressed problem using a specific variant of Grover’s search based on simultaneously exploring all comparison cases of possible solutions to recognize the right one. The paper also includes the study of precision and runtime of the presented concept and introduces a version of the proposed algorithm addressing the knapsack problem, along with its execution results and a comparison with other competing algorithms.

•Jun 15, 2026•0 citations

A Quantum Global Optimization Algorithm: Application to the Knapsack Problem

Mohamed Yassine Cherif, Wided Lejouad Chaari, Olfa Belkahla Driss

Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm to solve combinatorial optimization problems intended to provide an improved performance. The proposed algorithm aims to amplify the probability of selecting the global optimum of the objective function defining the addressed problem using a specific variant of Grover’s search based on simultaneously exploring all comparison cases of possible solutions to recognize the global optimum. The paper also includes the study of precision and runtime of the presented concept and introduces a version of the proposed algorithm addressing the knapsack problem, along with its execution results and a comparison with other competing algorithms

•Mar 23, 2026•0 citations

Quantum-Inspired Tabu Search Algorithm for reversible logic circuit synthesis

Wen-Hsin Wang, Chia-Hui Chiu, Shu–Yu Kuo +2 more

Reversible logic plays an important role in quantum computation, which is a promising research field. The reversible logic synthesis problem focuses on generating a reversible circuit automatically and finding the lowest cost when an output function is given. The synthesis of reversible logic circuits can be formulated as a combinatorial optimization problem. This paper proposes a new evolutionary algorithm for synthesizing reversible circuits based on Quantum-Inspired Tabu Search Algorithm (QTS). The proposed algorithm uses the QTS-based approach to find fewer gates and reduce the cost of reversible circuits. This method is simpler, has better performance in computational cost, and reduce the gate counts of reversible circuits. This paper also compares experimental results with other heuristic and evolutionary algorithms. The final outcome shows that the QTS-based approach performs much better than other algorithms.

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics•Oct 1, 2012•24 citations
In this study, we learned more about quantum properties from quantum and metaheuristic algorithms after conducting many experiments. We then propose an improved version of Quantum-inspired Tabu Search (QTS), which en-hances the utilization of population information. The new version is called “Amplitude-Ensemble” QTS (AE-QTS). This makes AE-QTS more similar to the real quantum search algorithm, Grover Search Algorithm, in abstract concept, while keeping the simplicity of the algorithm. Later, we demonstrate the AE-QTS on the classical combinatorial optimization 0/1 knapsack problem. Experimental results show that the AE-QTS outperforms other algorithms, including the QTS, by at least an average increase of nearly 20% in all cases and even by 30% in some cases. Even as the problem complexity increases, the quality of the solutions found by our method remains superior to that of the QTS. These results confirm that our method has better search performance.
Quantum circuit synthesis is a key technique in quantum computing. Traditional methods often generate circuits with high cost, making it crucial to produce correct and low-cost circuits efficiently. This study proposes the Amplitude-Ensemble Quantum-inspired Tabu Search (AE-QTS) algorithm for quantum Boolean circuit synthesis. AE-QTS demonstrates strong search capability with fewer parameters. Experimental results show that it outperforms other algorithms on low-bit problems and retains a certain level of synthesis ability on high-bit ones. However, the results also reveal that if the encoding frequently produces infeasible solutions, all algorithms will eventually fail, regardless of design. Therefore, future work should focus on developing encoding methods that consistently generate feasible solutions, which is essential for effectively applying metaheuristics to quantum Boolean circuit synthesis.
Many metaheuristic algorithms have been proposed to solve combinatorial and numerical optimization problems. Most optimization problems have high dependence, meaning that variables are strongly dependent on one another. If a method were to attempt to optimize each variable independently, its performance would suffer significantly. When traditional optimization techniques are applied to highdependence problems, they experience difficulty in finding the global optimum. To address this problem, this paper proposes a novel metaheuristic algorithm, the entanglement-enhanced quantum-inspired tabu search algorithm (Entanglement-QTS), which is based on the quantum-inspired tabu search (QTS) algorithm and the feature of quantum entanglement. Entanglement-QTS differs from other quantum-inspired evolutionary algorithms in that its Q-bits have entangled states, which can express a high degree of correlation, rendering the variables more intertwined. Entangled Q-bits represent a state-of-the-art idea that can significantly improve the treatment of multimodal and high-dependence problems. Entanglement-QTS can discover optimal solutions, balance diversification and intensification, escape numerous local optimal solutions by using the quantum not gate, reinforce the intensification effect by local search and entanglement local search, and manage strong-dependence problems and accelerate the optimization process by using entangled states. This paper uses nine benchmark functions to test the search ability of the entanglement-QTS algorithm. The results demonstrate that Entanglement-QTS outperforms QTS and other metaheuristic algorithms in both its effectiveness at finding the global optimum and its computational efficiency.
Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm for solving combinatorial optimization problems with improved performance and runtime approaching Grover’s optimal time of quantum search. The algorithm determines the global optimum of the objective function defining the addressed problem using an enhanced application of Grover’s search by simultaneously exploring all comparison cases of possible solutions without requiring iterative operations, unlike previous approaches, which affect performance and runtime. The paper also introduces a version of the proposed algorithm for solving the knapsack problem, along with its execution results and a comparison with other competing algorithms.
Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm to solve combinatorial optimization problems intended to provide an improved performance. The proposed algorithm aims to amplify the probability of selecting the global optimum of the objective function defining the addressed problem using a specific variant of Grover’s search based on simultaneously exploring all comparison cases of possible solutions to recognize the right one. The paper also includes the study of precision and runtime of the presented concept and introduces a version of the proposed algorithm addressing the knapsack problem, along with its execution results and a comparison with other competing algorithms.
Abstract Solving combinatorial optimization problems represents a challenge for researchers, especially hard NP-complete problems that are commonly handled through heuristic methods providing approximate solutions. The emergence of quantum computing, which enables performing parallel computation, raises hope for solving such problems within a reasonable time frame. This paper proposes a quantum global optimization algorithm to solve combinatorial optimization problems intended to provide an improved performance. The proposed algorithm aims to amplify the probability of selecting the global optimum of the objective function defining the addressed problem using a specific variant of Grover’s search based on simultaneously exploring all comparison cases of possible solutions to recognize the global optimum. The paper also includes the study of precision and runtime of the presented concept and introduces a version of the proposed algorithm addressing the knapsack problem, along with its execution results and a comparison with other competing algorithms
Reversible logic plays an important role in quantum computation, which is a promising research field. The reversible logic synthesis problem focuses on generating a reversible circuit automatically and finding the lowest cost when an output function is given. The synthesis of reversible logic circuits can be formulated as a combinatorial optimization problem. This paper proposes a new evolutionary algorithm for synthesizing reversible circuits based on Quantum-Inspired Tabu Search Algorithm (QTS). The proposed algorithm uses the QTS-based approach to find fewer gates and reduce the cost of reversible circuits. This method is simpler, has better performance in computational cost, and reduce the gate counts of reversible circuits. This paper also compares experimental results with other heuristic and evolutionary algorithms. The final outcome shows that the QTS-based approach performs much better than other algorithms.