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

International Scientific and Practical Conference of Students, Post-graduates and Young Scientists: Modern Techniques and Technology (MTT)

Applying quantum search to automated test pattern generation for VLSI circuits

Sarbjeet Singh, Amardeep S. G. Singh

Published Mar 1, 2004• 4 citations
Publisher

Abstract

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.

DOI
10.1109/pdcat.2003.1236383

Related papers

APPLYING QUANTUM SEARCH TO AUTOMATED TEST PATTERN GENERATION FOR VLSI CIRCUITS

Amardeep S. G. Singh, Sarbjeet Singh

This paper presents a quantum search algorithm for Automated Test Pattern Generation (ATPG) of VLSI circuits. For given digital circuits, a neural network is created that represents the digital gates with their interconnections as neurons. This neural network is characterized by an energy function E, which is the mathematics representation of neural network. The solution of the energy function gives us the test vector. The test vector is a combination of input values of digital circuits that detects a particular fault. In this paper, specific aspects of quantum theory like superposition and quantum parallelism are applied to find the solution of this energy function. The algorithm developed is so efficient that it requires only [Formula: see text] (where N is the total number of vectors) iterations to find the desired test vector whereas in classical computing, it takes N/2 iterations. At the end, a comparison is made between exhaustive, simulated annealing and quantum based techniques. Experimental results show that the quantum search algorithms are more efficient than classical algorithms and can be applied with more efficiency.

International Journal of Quantum Information•Mar 1, 2003•5 citations

Quantum generation of neural networks

H. De Garisi, Ravichandra Sriram, Zijun Zhang

This paper shows how the new field of quantum computing can be applied to the creation of neural network circuits. Quantum computing is capable of processing huge numbers of quantum states simultaneously, in parallel, ("quantum parallelism"). In theory, QC ought to be able to process all possible points in a 2/sup N/ search space (of N bit bit-strings). If N is large, 2/sup N/ is gigantic, making a systematic search with a classical computer impossible. This paper presents an extended example of a simple QC algorithm applied to the generation of neural network circuits.

International Joint Conference on Neural Networks (IJCNN)•Jun 22, 2004•4 citations

Automatic Test Pattern Generation using Grover’s Algorithm

Nishant Agrawal

Quantum computing is an exciting new field in the intersection of computer science, physics and mathematics. It refines the central concepts from Quantum mechanics into its least difficult structures, peeling away the complications from the physical world. Any combinational circuit that has only one stuck at fault can be tested by applying a set of inputs that drive the circuit to verify the output response. The outputs of that circuit will be different from the one desired if the faults exist. This project describes a method of generating test patterns using the Boolean satisfaction method. First, the Boolean formula is constructed to express the Boolean difference between a fault-free circuit and a faulty circuit. Second, the Boolean satisfaction algorithm is applied to the formula in the previous step. The Grover algorithm is used to solve the Boolean satisfaction problem. The Boolean Satisfiability problem for Automatic Test Pattern Generation(ATPG) is implemented on IBM Quantum Experience. The Python program initially generates the boolean expression from the file and converts it into Conjunctive Normal Form(CNF) which is passed on to Grover Oracle and runs on IBM simulator and produces excellent results on combinational circuits for test pattern generation with a quadratic speedup. Grover’s Algorithm on this problem has a run time of O(√N).

International Journal for Research in Applied Science and Engineering Technology•Jun 14, 2021•0 citations

EXPLORING QUANTUM COMPUTING ALGORITHMS FOR OPTIMIZING VLSI CIRCUIT DESIGN AND FABRICATION PROCESSES

Umamaheswari P, Suneel Kumar Asileti

The growing complexity of Very Large Scale Integration (VLSI) circuit designs has significantly increased the demand for innovative approaches to enhance design efficiency and fabrication accuracy. Traditional computational methods face limitations in terms of scalability and optimization for complex VLSI systems. The advent of quantum computing presents a promising paradigm shift, offering exponential speedup in solving computationally intensive problems such as optimization, simulation, and data analysis in VLSI design and fabrication. This research investigates the potential of quantum computing algorithms to optimize VLSI circuit design and fabrication processes, addressing key challenges such as layout optimization, routing, and process variation. The problem lies in the increasing complexity and size of VLSI circuits, which often lead to inefficient designs, longer manufacturing times, and increased cost. Current methods such as classical algorithms and heuristic techniques struggle to achieve optimal solutions within reasonable time frames. Quantum algorithms, particularly those based on quantum annealing and variational quantum eigensolvers (VQE), have shown promise in solving combinatorial optimization problems with much higher efficiency. By leveraging quantum computing, the goal is to improve the optimization of circuit layouts, minimize power consumption, and reduce production costs in VLSI systems. The proposed method utilizes quantum computing techniques to model and solve optimization problems related to VLSI circuit design and fabrication. Simulations and comparisons with classical methods show significant improvements in design efficiency, reduced error rates, and faster optimization cycles. The outcomes of this study could transform the future of VLSI design and fabrication, leading to more efficient, cost-effective, and scalable solutions for semiconductor manufacturing.

ICTACT Journal on Microelectronics•Jan 1, 2025•0 citations

Fault Testing Quantum Switching Circuits

Marek A. Perkowski, Jacob Biamonte

Test pattern generation is an electronic design automation tool that attempts to find an input (or test) sequence that, when applied to a digital circuit, enables one to distinguish between the correct circuit behavior and the faulty behavior caused by particular faults. The effectiveness of this classical method is measured by the fault coverage achieved for the fault model and the number of generated vectors, which should be directly proportional to test application time. This work address the quantum process validation problem by considering the quantum mechanical adaptation of test pattern generation methods used to test classical circuits. We found that quantum mechanics allows one to execute multiple test vectors concurrently, making each gate realized in the process act on a complete set of characteristic states in space/time complexity that breaks classical testability lower bounds.

•Jan 1, 2010•0 citations

Neural networks with quantum architecture and quantum learning

Massimo Panella, Giuseppe Martinelli

Abstract A method is proposed for solving the two key problems facing quantum neural networks: introduction of nonlinearity in the neuron operation and efficient use of quantum superposition in the learning algorithm. The former is indirectly solved by using suitable Boolean functions. The latter is based on the use of a suitable nonlinear quantum circuit. The resulting learning procedure does not apply any optimization method. The optimal neural network is obtained by applying an exhaustive search among all the possible solutions. The exhaustive search is carried out by the proposed quantum circuit composed of both linear and nonlinear components. Copyright © 2009 John Wiley & Sons, Ltd.

International Journal of Circuit Theory and Applications•Jul 23, 2009•75 citations
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.
This paper presents a quantum search algorithm for Automated Test Pattern Generation (ATPG) of VLSI circuits. For given digital circuits, a neural network is created that represents the digital gates with their interconnections as neurons. This neural network is characterized by an energy function E, which is the mathematics representation of neural network. The solution of the energy function gives us the test vector. The test vector is a combination of input values of digital circuits that detects a particular fault. In this paper, specific aspects of quantum theory like superposition and quantum parallelism are applied to find the solution of this energy function. The algorithm developed is so efficient that it requires only [Formula: see text] (where N is the total number of vectors) iterations to find the desired test vector whereas in classical computing, it takes N/2 iterations. At the end, a comparison is made between exhaustive, simulated annealing and quantum based techniques. Experimental results show that the quantum search algorithms are more efficient than classical algorithms and can be applied with more efficiency.
This paper shows how the new field of quantum computing can be applied to the creation of neural network circuits. Quantum computing is capable of processing huge numbers of quantum states simultaneously, in parallel, ("quantum parallelism"). In theory, QC ought to be able to process all possible points in a 2/sup N/ search space (of N bit bit-strings). If N is large, 2/sup N/ is gigantic, making a systematic search with a classical computer impossible. This paper presents an extended example of a simple QC algorithm applied to the generation of neural network circuits.
Quantum computing is an exciting new field in the intersection of computer science, physics and mathematics. It refines the central concepts from Quantum mechanics into its least difficult structures, peeling away the complications from the physical world. Any combinational circuit that has only one stuck at fault can be tested by applying a set of inputs that drive the circuit to verify the output response. The outputs of that circuit will be different from the one desired if the faults exist. This project describes a method of generating test patterns using the Boolean satisfaction method. First, the Boolean formula is constructed to express the Boolean difference between a fault-free circuit and a faulty circuit. Second, the Boolean satisfaction algorithm is applied to the formula in the previous step. The Grover algorithm is used to solve the Boolean satisfaction problem. The Boolean Satisfiability problem for Automatic Test Pattern Generation(ATPG) is implemented on IBM Quantum Experience. The Python program initially generates the boolean expression from the file and converts it into Conjunctive Normal Form(CNF) which is passed on to Grover Oracle and runs on IBM simulator and produces excellent results on combinational circuits for test pattern generation with a quadratic speedup. Grover’s Algorithm on this problem has a run time of O(√N).
The growing complexity of Very Large Scale Integration (VLSI) circuit designs has significantly increased the demand for innovative approaches to enhance design efficiency and fabrication accuracy. Traditional computational methods face limitations in terms of scalability and optimization for complex VLSI systems. The advent of quantum computing presents a promising paradigm shift, offering exponential speedup in solving computationally intensive problems such as optimization, simulation, and data analysis in VLSI design and fabrication. This research investigates the potential of quantum computing algorithms to optimize VLSI circuit design and fabrication processes, addressing key challenges such as layout optimization, routing, and process variation. The problem lies in the increasing complexity and size of VLSI circuits, which often lead to inefficient designs, longer manufacturing times, and increased cost. Current methods such as classical algorithms and heuristic techniques struggle to achieve optimal solutions within reasonable time frames. Quantum algorithms, particularly those based on quantum annealing and variational quantum eigensolvers (VQE), have shown promise in solving combinatorial optimization problems with much higher efficiency. By leveraging quantum computing, the goal is to improve the optimization of circuit layouts, minimize power consumption, and reduce production costs in VLSI systems. The proposed method utilizes quantum computing techniques to model and solve optimization problems related to VLSI circuit design and fabrication. Simulations and comparisons with classical methods show significant improvements in design efficiency, reduced error rates, and faster optimization cycles. The outcomes of this study could transform the future of VLSI design and fabrication, leading to more efficient, cost-effective, and scalable solutions for semiconductor manufacturing.
Test pattern generation is an electronic design automation tool that attempts to find an input (or test) sequence that, when applied to a digital circuit, enables one to distinguish between the correct circuit behavior and the faulty behavior caused by particular faults. The effectiveness of this classical method is measured by the fault coverage achieved for the fault model and the number of generated vectors, which should be directly proportional to test application time. This work address the quantum process validation problem by considering the quantum mechanical adaptation of test pattern generation methods used to test classical circuits. We found that quantum mechanics allows one to execute multiple test vectors concurrently, making each gate realized in the process act on a complete set of characteristic states in space/time complexity that breaks classical testability lower bounds.
Abstract A method is proposed for solving the two key problems facing quantum neural networks: introduction of nonlinearity in the neuron operation and efficient use of quantum superposition in the learning algorithm. The former is indirectly solved by using suitable Boolean functions. The latter is based on the use of a suitable nonlinear quantum circuit. The resulting learning procedure does not apply any optimization method. The optimal neural network is obtained by applying an exhaustive search among all the possible solutions. The exhaustive search is carried out by the proposed quantum circuit composed of both linear and nonlinear components. Copyright © 2009 John Wiley & Sons, Ltd.