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

IEEE Conference on Nanotechnology (IEEE NANO)

Improving Boolean Circuit Testing by using Quantum Search

Yao–Hsin Chou, Sy‐Yen Kuo

Published Aug 1, 2008• 4 citations
Publisher

Abstract

Given any classical circuit, a minimum input quantum version of boolean circuit can be constructed with general CCN gates. Any quantum boolean circuit can be easily tested with one test pattern under stuck-at fault model. In this paper, we apply quantum search algorithm to boolean logic testing problem and drastically decrease not only the number of test patterns but also the time and the number of bits we needed to find out the faulty wires.

DOI
10.1109/nano.2008.185

Related papers

Quantum boolean circuit is 1-testable

Yao–Hsin Chou, I-Ming Tsai, Sy‐Yen Kuo

Recently, a systematic procedure is proposed to derive a minimum space quantum circuit for a given classical logic with the generalized quantum Toffoli gate which is universal in classical boolean logic. Since quantum computation is reversible, we can use this property to build Quantum Iterative Logic Array (QILA). QILA can be easily tested in constant time (C-testable) if stuck-at fault model is assumed. In this paper, we apply Hadamard and general CCN gates on QILA circuits to make them 1-testable. As a result, for quantum boolean circuits, the number of test patterns is independent of both the size of the array and the length of the inputs.

IEEE Conference on Nanotechnology (IEEE NANO)•Aug 1, 2007•4 citations

Quantum Boolean Circuits are 1-Testable

Yao–Hsin Chou, I-Ming Tsai, Sy‐Yen Kuo

Recently, a systematic procedure was proposed to derive a minimum input quantum circuit for any given classical logic with the generalized quantum Toffoli gate, which is universal in Boolean logic. Since quantum Boolean circuits are reversible, we can apply this property to build quantum iterative logic array (QILA). QILA can be easily tested in constant time (C-testable) if stuck-at fault model is assumed. In this paper, we use Hadamard and general controlled-controlled not gates to make QILA 1-testable. That is, for any quantum Boolean circuit, the number of test patterns is independent of both the size of the array and the length of the inputs.

IEEE Transactions on Nanotechnology•Jul 1, 2008•12 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

On Finding Sensitivity of Quantum and Classical Gates

Debajyoti Bera, Steven Homer

We consider a fault model of Boolean gates, both classical and quantum, where some of the inputs may not be connected to the actual gate hardware. This model is somewhat similar to the stuck-at model which is a very popular model in testing Boolean circuits. We consider the problem of detecting such faults; the detection algorithm can query the faulty gate and its complexity is the number of such queries. This problem is related to determining the sensitivity of Boolean functions. We show how quantum parallelism can be used to detect such faults. Specifically, we show that a quantum algorithm can detect such faults more efficiently than a classical algorithm for a Parity gate and an AND gate. We give explicit constructions of quantum detector algorithms and show lower bounds for classical algorithms. We show that the model for detecting such faults is similar to algebraic decision trees and extend some known results from quantum query complexity to prove some of our results. 1

•Jun 5, 2009•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

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
Given any classical circuit, a minimum input quantum version of boolean circuit can be constructed with general CCN gates. Any quantum boolean circuit can be easily tested with one test pattern under stuck-at fault model. In this paper, we apply quantum search algorithm to boolean logic testing problem and drastically decrease not only the number of test patterns but also the time and the number of bits we needed to find out the faulty wires.
Recently, a systematic procedure is proposed to derive a minimum space quantum circuit for a given classical logic with the generalized quantum Toffoli gate which is universal in classical boolean logic. Since quantum computation is reversible, we can use this property to build Quantum Iterative Logic Array (QILA). QILA can be easily tested in constant time (C-testable) if stuck-at fault model is assumed. In this paper, we apply Hadamard and general CCN gates on QILA circuits to make them 1-testable. As a result, for quantum boolean circuits, the number of test patterns is independent of both the size of the array and the length of the inputs.
Recently, a systematic procedure was proposed to derive a minimum input quantum circuit for any given classical logic with the generalized quantum Toffoli gate, which is universal in Boolean logic. Since quantum Boolean circuits are reversible, we can apply this property to build quantum iterative logic array (QILA). QILA can be easily tested in constant time (C-testable) if stuck-at fault model is assumed. In this paper, we use Hadamard and general controlled-controlled not gates to make QILA 1-testable. That is, for any quantum Boolean circuit, the number of test patterns is independent of both the size of the array and the length of the inputs.
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.
We consider a fault model of Boolean gates, both classical and quantum, where some of the inputs may not be connected to the actual gate hardware. This model is somewhat similar to the stuck-at model which is a very popular model in testing Boolean circuits. We consider the problem of detecting such faults; the detection algorithm can query the faulty gate and its complexity is the number of such queries. This problem is related to determining the sensitivity of Boolean functions. We show how quantum parallelism can be used to detect such faults. Specifically, we show that a quantum algorithm can detect such faults more efficiently than a classical algorithm for a Parity gate and an AND gate. We give explicit constructions of quantum detector algorithms and show lower bounds for classical algorithms. We show that the model for detecting such faults is similar to algebraic decision trees and extend some known results from quantum query complexity to prove some of our results. 1
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.
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.