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 Journal of Quantum Information

APPLYING QUANTUM SEARCH TO AUTOMATED TEST PATTERN GENERATION FOR VLSI CIRCUITS

Amardeep S. G. Singh, Sarbjeet Singh

Published Mar 1, 2003• 5 citations
Publisher

Abstract

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.

DOI
10.1142/s0219749903000097

Related papers

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

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

Detection and Diagnosis of Single Faults in Quantum Circuits

Debajyoti Bera

Detection and isolation of faults is a crucial step in the physical realization of quantum circuits. Even though quantum gates and circuits compute reversible functions, the standard techniques of automatic test pattern generation (ATPG) for classical reversible circuits are not directly applicable to quantum circuits. For faulty quantum circuits under the widely accepted single fault assumption, we show that their behavior can be fully characterized by the (single) faulty gate and the corresponding fault model. This allows us to efficiently determine test input states as well as measurement strategy for fault detection and diagnosis. Building on top of these, we design randomized algorithms which are able to detect every nontrivial single-gate fault with minimal probability of error. We also describe similar algorithms for fault diagnosis. We evaluate our algorithms by the number of output samples that needs to be collected and the probability of error. Both of these can be related to the eigenvalues of the operators corresponding to the circuit gates. We experimentally compare all our strategies with the state-of-the-art ATPG techniques for quantum circuits under the “single missing faulty gate” model and demonstrate that significant improvement is possible if we can exploit the quantum nature of circuits.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Jun 22, 2017•16 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

Automatic Test Pattern Generation for Robust Quantum Circuit Testing

Kean Chen, Mingsheng Ying

Quantum circuit testing is essential for detecting potential faults in realistic quantum devices, while the testing process itself also suffers from the inexactness and unreliability of quantum operations. This article alleviates the issue by proposing a novel framework of automatic test pattern generation (ATPG) for robust testing of logical quantum circuits. We introduce the stabilizer projector decomposition (SPD) for representing the quantum test pattern and construct the test application (i.e., state preparation and measurement) using Clifford-only circuits, which are rather robust and efficient as evidenced in the fault-tolerant quantum computation. However, it is generally hard to generate SPDs due to the exponentially growing number of the stabilizer projectors. To circumvent this difficulty, we develop an SPD generation algorithm, as well as several acceleration techniques that can exploit both locality and sparsity in generating SPDs. The effectiveness of our algorithms are validated by (1) theoretical guarantees under reasonable conditions and (2) experimental results on commonly used benchmark circuits, such as Quantum Fourier Transform (QFT), Quantum Volume (QV), and Bernstein-Vazirani (BV) in IBM Qiskit.

arXiv:2202.10697•ACM Transactions on Design Automation of Electronic Systems•Aug 20, 2024•6 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
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.
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.
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).
Detection and isolation of faults is a crucial step in the physical realization of quantum circuits. Even though quantum gates and circuits compute reversible functions, the standard techniques of automatic test pattern generation (ATPG) for classical reversible circuits are not directly applicable to quantum circuits. For faulty quantum circuits under the widely accepted single fault assumption, we show that their behavior can be fully characterized by the (single) faulty gate and the corresponding fault model. This allows us to efficiently determine test input states as well as measurement strategy for fault detection and diagnosis. Building on top of these, we design randomized algorithms which are able to detect every nontrivial single-gate fault with minimal probability of error. We also describe similar algorithms for fault diagnosis. We evaluate our algorithms by the number of output samples that needs to be collected and the probability of error. Both of these can be related to the eigenvalues of the operators corresponding to the circuit gates. We experimentally compare all our strategies with the state-of-the-art ATPG techniques for quantum circuits under the “single missing faulty gate” model and demonstrate that significant improvement is possible if we can exploit the quantum nature of circuits.
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.
Quantum circuit testing is essential for detecting potential faults in realistic quantum devices, while the testing process itself also suffers from the inexactness and unreliability of quantum operations. This article alleviates the issue by proposing a novel framework of automatic test pattern generation (ATPG) for robust testing of logical quantum circuits. We introduce the stabilizer projector decomposition (SPD) for representing the quantum test pattern and construct the test application (i.e., state preparation and measurement) using Clifford-only circuits, which are rather robust and efficient as evidenced in the fault-tolerant quantum computation. However, it is generally hard to generate SPDs due to the exponentially growing number of the stabilizer projectors. To circumvent this difficulty, we develop an SPD generation algorithm, as well as several acceleration techniques that can exploit both locality and sparsity in generating SPDs. The effectiveness of our algorithms are validated by (1) theoretical guarantees under reasonable conditions and (2) experimental results on commonly used benchmark circuits, such as Quantum Fourier Transform (QFT), Quantum Volume (QV), and Bernstein-Vazirani (BV) in IBM Qiskit.
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.