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

Cogent Engineering

Quantum algorithm for solving the test suite minimization problem

Hager Hussein, Ahmed Younes, Walid Abdelmoez

Published Jan 1, 2021• 10 citations
Publisher

Abstract

Test-suite minimization problem is an essential problem in software engineering as its application helps to improve the software quality. This paper proposes a quantum algorithm to solve the test-suite minimization problem with high probability in O2n, where n is the number of test cases. It generates an incomplete superposition to find the best solution. It also handles the non-uniform amplitudes’ distribution case for the system with multisolutions. The proposed algorithm uses amplitude amplification techniques to search for the minimum number of test cases required to test all the requirements. The proposed algorithm employs two quantum search algorithms, Younes et al. algorithm for quantum searching via entanglement and partial diffusion to prepare incomplete superpositions that represent different search spaces such that the number of test cases is incremented in each search space, and updated Arima’s algorithm to handle the multisolutions case. The updated Arima’s algorithm searches for a quantum state that satisfies an oracle that represent the instance of the test-suite minimization problem.

DOI
10.1080/23311916.2021.1882116

Related papers

Efficient Quantum Answer Set Programming Solver Using Partial Diffusion and Entanglement

Esraa Ebdelrehime, Ahmed Younes, Islam Elkabani

The relation between answer set programming (ASP) and combinatorial problems, especially the satisfiability problem (SAT) has attracted significant interest in academic literature. The aim of this paper is to introduce an efficient quantum answer set programming solver (QSAT) that can handle NP-hard combinatorial search problems by reducing the problem to MAX-3-SAT problem. The paper proposes a quantum algorithm that solves the MAX-3-SAT problem using amplification techniques that exploits entanglement and partial diffusion operator to find a solution with high probability inO(√2n/l), where n is the number of variables and l denotes the number of literals. The proposed algorithm shows a speed-up in solving ASP problems compared to classical approaches.

IEEE Access•Jan 1, 2025•0 citations

Efficient quantum algorithms for set operations

Rehab Elgendy, Ahmed Younes, H.M. Abu-Donia +1 more

Abstract Analyzing the relations between Boolean functions has many applications in many fields, such as database systems, cryptography, and collision problems. This paper proposes four quantum algorithms that use amplitude amplification techniques to perform set operations, including Intersection, Difference, and Union, on two Boolean functions in $$\mathcal {O}(\sqrt{\mathcal {N}} )$$ O ( N ) time complexity. The proposed algorithms employ two quantum amplitude amplification techniques divided into two stages. The first stage uses the Younes et al. algorithm for quantum searching via entanglement and partial diffusion to prepare incomplete superpositions of the truth set of the first Boolean function. In the second stage, a modified version of Arima’s algorithm, along with an oracle that represent the second Boolean function, is employed to handle the set operations. The proposed algorithms have a higher probability of success in more general and comprehensive applications when compared with relevant techniques in literature.

Scientific Reports•Mar 25, 2024•2 citations

Applying quantum search to automated test pattern generation for VLSI circuits

Sarbjeet Singh, Amardeep S. G. Singh

We present a quantum search algorithm for automated test pattern generation (ATPG) of combinatorial VLSI circuits. This problem can be viewed as an optimization problem because digital circuits can be modeled as a neural network and the problem become to minimize the energy function of this neural network. The solution of the equation gives us the test vector. Here specific aspects of quantum theory like superposition and quantum parallelism are applied to this problem. In quantum search algorithm this problem is viewed as a searching problem where the search function (also called oracle) f(x)=1 if the value of the energy function of the neural network is 0 otherwise f(x)=0. Quantum mechanics help us to search a group of items simultaneously from the search space rather than one item at a time. The algorithm is so efficient that it requires only, on average, roughly /spl radic/N (where N is the total number of vectors) searches to find the desired test vector, as opposed to a search in classical computing, which on average needs N/2 searches. A comparison is made between exhaustive, simulated annealing and quantum based search techniques. Experimental results show that the quantum search algorithms are more efficient than classical algorithms and can be applied with more efficiency on a quantum computer.

International Scientific and Practical Conference of Students, Post-graduates and Young Scientists: Modern Techniques and Technology (MTT)•Mar 1, 2004•4 citations

Implementation of Efficient Quantum Computing Algorithm for Searching

Nirhali Atharva, Malwade Rohit, P. Akshay +2 more

The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.

International Research Journal on Advanced Engineering Hub (IRJAEH)•May 21, 2025•0 citations

Quantum Approximate Optimization Algorithm for Test Case Optimization

Xinyi Wang, Shaukat Ali, Tao Yue +1 more

Test case optimization (TCO) reduces the software testing cost while preserving its effectiveness. However, to solve TCO problems for large-scale and complex software systems, substantial computational resources are required. Quantum approximate optimization algorithms (QAOAs) are promising combinatorial optimization algorithms that rely on quantum computational resources, with the potential to offer increased efficiency compared to classical approaches. Several proof-of-concept applications of QAOAs for solving combinatorial problems, such as portfolio optimization, energy optimization in power systems, and job scheduling, have been proposed. Given the lack of investigation into QAOA's application for TCO problems, and motivated by the computational challenges of TCO problems and the potential of QAOAs, we present IGDec-QAOA to formulate a TCO problem as a QAOA problem and solve it on both ideal and noisy quantum computer simulators, as well as on a real quantum computer. To solve bigger TCO problems that require many qubits, which are unavailable these days, we integrate a problem decomposition strategy with the QAOA. We performed an empirical evaluation with five TCO problems and four publicly available industrial datasets from ABB, Google, and Orona to compare various configurations of IGDec-QAOA, assess its decomposition strategy of handling large datasets, and compare its performance with classical algorithms (i.e., Genetic Algorithm (GA) and Random Search). Based on the evaluation results achieved on an ideal simulator, we recommend the best configuration of our approach for TCO problems. Also, we demonstrate that our approach can reach the same effectiveness as GA and outperform GA in two out of five test case optimization problems we conducted. In addition, we observe that, on the noisy simulator, IGDec-QAOA achieved similar performance to that from the ideal simulator. Finally, we also demonstrate the feasibility of IGDec-QAOA on a real quantum computer in the presence of noise.

arXiv:2312.15547•IEEE Transactions on Software Engineering•Oct 14, 2024•23 citations

Quantum algorithm for minimum dominating set problem with circuit design

Haoying 皓颖 Zhang 张, Shaoxuan 绍轩 Wang 王, Xinjian 新建 Liu 刘 +2 more

Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing. Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems. This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs. To expedite the search process, a quantum algorithm employing Grover’s search is proposed. However, a challenge arises from the unknown number of solutions for the minimum dominating set, rendering direct usage of original Grover’s search impossible. Thus, a swap test method is introduced to ascertain the number of iterations required. The oracle, diffusion operators, and swap test are designed with achievable quantum gates. The query complexity is O(1.414 n ) and the space complexity is O(n). To validate the proposed approach, qiskit software package is employed to simulate the quantum circuit, yielding the anticipated results.

Chinese Physics B•Oct 13, 2023•8 citations
Test-suite minimization problem is an essential problem in software engineering as its application helps to improve the software quality. This paper proposes a quantum algorithm to solve the test-suite minimization problem with high probability in O2n, where n is the number of test cases. It generates an incomplete superposition to find the best solution. It also handles the non-uniform amplitudes’ distribution case for the system with multisolutions. The proposed algorithm uses amplitude amplification techniques to search for the minimum number of test cases required to test all the requirements. The proposed algorithm employs two quantum search algorithms, Younes et al. algorithm for quantum searching via entanglement and partial diffusion to prepare incomplete superpositions that represent different search spaces such that the number of test cases is incremented in each search space, and updated Arima’s algorithm to handle the multisolutions case. The updated Arima’s algorithm searches for a quantum state that satisfies an oracle that represent the instance of the test-suite minimization problem.
The relation between answer set programming (ASP) and combinatorial problems, especially the satisfiability problem (SAT) has attracted significant interest in academic literature. The aim of this paper is to introduce an efficient quantum answer set programming solver (QSAT) that can handle NP-hard combinatorial search problems by reducing the problem to MAX-3-SAT problem. The paper proposes a quantum algorithm that solves the MAX-3-SAT problem using amplification techniques that exploits entanglement and partial diffusion operator to find a solution with high probability inO(√2n/l), where n is the number of variables and l denotes the number of literals. The proposed algorithm shows a speed-up in solving ASP problems compared to classical approaches.
Abstract Analyzing the relations between Boolean functions has many applications in many fields, such as database systems, cryptography, and collision problems. This paper proposes four quantum algorithms that use amplitude amplification techniques to perform set operations, including Intersection, Difference, and Union, on two Boolean functions in O(N)\mathcal {O}(\sqrt{\mathcal {N}} )O(N​) O ( N ) time complexity. The proposed algorithms employ two quantum amplitude amplification techniques divided into two stages. The first stage uses the Younes et al. algorithm for quantum searching via entanglement and partial diffusion to prepare incomplete superpositions of the truth set of the first Boolean function. In the second stage, a modified version of Arima’s algorithm, along with an oracle that represent the second Boolean function, is employed to handle the set operations. The proposed algorithms have a higher probability of success in more general and comprehensive applications when compared with relevant techniques in literature.
We present a quantum search algorithm for automated test pattern generation (ATPG) of combinatorial VLSI circuits. This problem can be viewed as an optimization problem because digital circuits can be modeled as a neural network and the problem become to minimize the energy function of this neural network. The solution of the equation gives us the test vector. Here specific aspects of quantum theory like superposition and quantum parallelism are applied to this problem. In quantum search algorithm this problem is viewed as a searching problem where the search function (also called oracle) f(x)=1 if the value of the energy function of the neural network is 0 otherwise f(x)=0. Quantum mechanics help us to search a group of items simultaneously from the search space rather than one item at a time. The algorithm is so efficient that it requires only, on average, roughly /spl radic/N (where N is the total number of vectors) searches to find the desired test vector, as opposed to a search in classical computing, which on average needs N/2 searches. A comparison is made between exhaustive, simulated annealing and quantum based search techniques. Experimental results show that the quantum search algorithms are more efficient than classical algorithms and can be applied with more efficiency on a quantum computer.
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.
Test case optimization (TCO) reduces the software testing cost while preserving its effectiveness. However, to solve TCO problems for large-scale and complex software systems, substantial computational resources are required. Quantum approximate optimization algorithms (QAOAs) are promising combinatorial optimization algorithms that rely on quantum computational resources, with the potential to offer increased efficiency compared to classical approaches. Several proof-of-concept applications of QAOAs for solving combinatorial problems, such as portfolio optimization, energy optimization in power systems, and job scheduling, have been proposed. Given the lack of investigation into QAOA's application for TCO problems, and motivated by the computational challenges of TCO problems and the potential of QAOAs, we present IGDec-QAOA to formulate a TCO problem as a QAOA problem and solve it on both ideal and noisy quantum computer simulators, as well as on a real quantum computer. To solve bigger TCO problems that require many qubits, which are unavailable these days, we integrate a problem decomposition strategy with the QAOA. We performed an empirical evaluation with five TCO problems and four publicly available industrial datasets from ABB, Google, and Orona to compare various configurations of IGDec-QAOA, assess its decomposition strategy of handling large datasets, and compare its performance with classical algorithms (i.e., Genetic Algorithm (GA) and Random Search). Based on the evaluation results achieved on an ideal simulator, we recommend the best configuration of our approach for TCO problems. Also, we demonstrate that our approach can reach the same effectiveness as GA and outperform GA in two out of five test case optimization problems we conducted. In addition, we observe that, on the noisy simulator, IGDec-QAOA achieved similar performance to that from the ideal simulator. Finally, we also demonstrate the feasibility of IGDec-QAOA on a real quantum computer in the presence of noise.
Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing. Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems. This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs. To expedite the search process, a quantum algorithm employing Grover’s search is proposed. However, a challenge arises from the unknown number of solutions for the minimum dominating set, rendering direct usage of original Grover’s search impossible. Thus, a swap test method is introduced to ascertain the number of iterations required. The oracle, diffusion operators, and swap test are designed with achievable quantum gates. The query complexity is O(1.414 n ) and the space complexity is O(n). To validate the proposed approach, qiskit software package is employed to simulate the quantum circuit, yielding the anticipated results.