Satisfiability Application-Dependent Testing of FPGA using Quantum Computing

Abstract

The potential of Quantum computing has been used to solve many computationally hard problems. An algorithm for solving the Boolean satisfiability problem (SAT) or (K-SAT) on quantum computers, for testing the interconnects of an arbitrary design mapped into an FPGA. Satisfiability Application-dependent Testing of FPGA is a compute intensive problem. Existing conventional methods are unable to perform the required breakthrough in terms of complexity, time and cost. An evolutionary approach based on Quantum computing is presented, which exploits the computational power of Quantum Parallelism to solve the problem. A Boolean formula in conjunctive normal form is extracted from the FPGA under test and then the proposed algorithm based on Quantum computing is used to find the solution satisfying that formula. The test vector and configuration generation problem is systematically converted to a Quantum problem, which runs in a constant number of steps with any given number n of Boolean variables. Exploiting the massive parallelism and recombination properties of quantum, a test vectors is generated in polynomial time. Its effectiveness in terms of number of iterations is experimentally compared with some of existing approaches like simulated annealing and genetic algorithms. Using the proposed Quantum based approach it is also possible to find all the test vectors, which detect a particular fault, simultaneously.