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 VLSI Test Symposium (VTS)

QBIST: Quantum Built-in Self-Test for any Boolean Circuit

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

Published Apr 1, 2008• 5 citations
Publisher

Abstract

A systematic procedure was proposed to derive a minimum space quantum circuit for any given classical logic with the generalized quantum Toffoli gate which is universal in Boolean logic. Since quantum computation is 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 CCN 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. This property can be applied to perform the quantum built-in self-test (QBIST), which makes any Boolean circuit 1-testable.

DOI
10.1109/vts.2008.49

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

Improving Boolean Circuit Testing by using Quantum Search

Yao–Hsin Chou, Sy‐Yen Kuo

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.

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

AN ALGORITHM FOR MINIMUM SPACE QUANTUM BOOLEAN CIRCUITS CONSTRUCTION

I-Ming Tsai, Sy‐Yen Kuo

Implementing a quantum computer at the circuit level has emerged as an important field of research recently. An important topic of building a general-purpose quantum computer is to implement classical Boolean logic using quantum gates and devices. Since the Toffoli gate is universal in classical Boolean logic, any classical combinational circuit can be implemented by the straightforward replacement algorithm with auxiliary qubits as intermediate storage. However, this inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, a systematic procedure is proposed to derive a minimum space quantum circuit for a given classical combinational logic. We first formulate the problem of transforming an m-to-n bit classical Boolean logic into a t-bit unitary quantum operation. The eligible solution set is then constructed such that a solution can be found simply by selecting any member from this set. Finally, we show that the algorithm is optimal in terms of the space consumption.

Journal of Circuits Systems and Computers•Oct 1, 2006•17 citations

Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates

Wim van Dam, Frédéric Magniez, Michele Mosca +1 more

We consider the design of self-testers for quantum gates. A self-tester for the gates $\boldsymbol{F}_1,\ldots, \boldsymbol{F}_m$ is a procedure that, given any gates $\boldsymbol{G}_1, \ldots, \boldsymbol{G}_m$, decides with high probability if each $\boldsymbol{G}_i$ is close to $\boldsymbol{F}_i$. This decision has to rely only on measuring in the computational basis the effect of iterating the gates on the classical states. It turns out that, instead of individual gates, we can design only procedures for families of gates. To achieve our goal we borrow some elegant ideas of the theory of program testing: We characterize the gate families by specific properties, develop a theory of robustness for them, and show that they lead to self-testers. In particular we prove that the universal and fault-tolerant set of gates consisting of a Hadamard gate, a $\mathrm{c\text{-}NOT}$ gate, and a phase rotation gate of angle $\pi/4$ is self-testable.

SIAM Journal on Computing•Jan 1, 2007•15 citations

A Systematic Algorithm for Quantum Boolean Circuits Construction

I.-M. Tsai, Sy‐Yen Kuo

To build a general-purpose quantum computer, it is crucial for the quantum devices to implement classical boolean logic. A straightforward realization of quantum boolean logic is to use auxiliary qubits as intermediate storage. This inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, we have derived a systematic way of realizing any general m-to-n bit combinational boolean logic using elementary quantum gates. Our approach transforms the m-to-n bit classical mapping into a t-bit unitary quantum operation with minimum number of auxiliary qubits, then a variation of Toffoli gate is used as the basic building block to construct the unitary operation. Finally, each of these building blocks can be decomposed into one-bit rotation and two-bit control-U gates. The efficiency of the network is taken into consideration by formulating it as a constrained set partitioning problem.

arXiv:quant-ph/0104037•Apr 9, 2001•2 citations
A systematic procedure was proposed to derive a minimum space quantum circuit for any given classical logic with the generalized quantum Toffoli gate which is universal in Boolean logic. Since quantum computation is 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 CCN 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. This property can be applied to perform the quantum built-in self-test (QBIST), which makes any Boolean circuit 1-testable.
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.
Implementing a quantum computer at the circuit level has emerged as an important field of research recently. An important topic of building a general-purpose quantum computer is to implement classical Boolean logic using quantum gates and devices. Since the Toffoli gate is universal in classical Boolean logic, any classical combinational circuit can be implemented by the straightforward replacement algorithm with auxiliary qubits as intermediate storage. However, this inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, a systematic procedure is proposed to derive a minimum space quantum circuit for a given classical combinational logic. We first formulate the problem of transforming an m-to-n bit classical Boolean logic into a t-bit unitary quantum operation. The eligible solution set is then constructed such that a solution can be found simply by selecting any member from this set. Finally, we show that the algorithm is optimal in terms of the space consumption.
We consider the design of self-testers for quantum gates. A self-tester for the gates F1,…,Fm\boldsymbol{F}_1,\ldots, \boldsymbol{F}_mF1​,…,Fm​ is a procedure that, given any gates G1,…,Gm\boldsymbol{G}_1, \ldots, \boldsymbol{G}_mG1​,…,Gm​, decides with high probability if each Gi\boldsymbol{G}_iGi​ is close to Fi\boldsymbol{F}_iFi​. This decision has to rely only on measuring in the computational basis the effect of iterating the gates on the classical states. It turns out that, instead of individual gates, we can design only procedures for families of gates. To achieve our goal we borrow some elegant ideas of the theory of program testing: We characterize the gate families by specific properties, develop a theory of robustness for them, and show that they lead to self-testers. In particular we prove that the universal and fault-tolerant set of gates consisting of a Hadamard gate, a c-NOT\mathrm{c\text{-}NOT}c-NOT gate, and a phase rotation gate of angle π/4\pi/4π/4 is self-testable.
To build a general-purpose quantum computer, it is crucial for the quantum devices to implement classical boolean logic. A straightforward realization of quantum boolean logic is to use auxiliary qubits as intermediate storage. This inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, we have derived a systematic way of realizing any general m-to-n bit combinational boolean logic using elementary quantum gates. Our approach transforms the m-to-n bit classical mapping into a t-bit unitary quantum operation with minimum number of auxiliary qubits, then a variation of Toffoli gate is used as the basic building block to construct the unitary operation. Finally, each of these building blocks can be decomposed into one-bit rotation and two-bit control-U gates. The efficiency of the network is taken into consideration by formulating it as a constrained set partitioning problem.