Applying Quantum Search to Automated Test Pattern Generation for VLSI Circuits
This paper presents 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. In this paper 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 algorithmisso efficient that it requires only,on average, roughly √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.
ATPG Neural Network Quantum Computer Quantum Search Algorithms Simulated Annealing and VLSI
Sarbjeet Singh Amardeep Singh
Department of Computer Science & Engineering,Thapar Institute of Engineering & Technology,Deemed University, Patiala, Punjab, INDIA
国际会议
成都
英文
648-651
2003-08-27（万方平台首次上网日期，不代表论文的发表时间）