10th IEEE High Assurance Systems Engineering Symposium Advances in Quantum Computing Fault

Advances in Quantum Computing Fault Tolerance and Testing

David Y. Feinstein, V.S.S. Nair, and Mitchell A. Thornton

Department of Computer Science and Engineering, Southern Methodist University

{dfeinste, nair, mitch}@engr.smu.edu

Abstract

We study recent developments in quantum computing (QC) testing and fault tolerance (FT) techniques and discuss several attempts to formalize quantum logic fault models. We illustrate the inherent need for fault tolerance in QC due to the decoherence problem. Further, we examine several ideas regarding random testing and examine the viability of built-in-system- test (BIST) in future QC circuits.

Quantum computing (QC) attracts much interest in view of its promise of extensive computational parallelism and its potential to overcome the power wall problem [1]. While quantum computing is still in its embryonic development stages, several papers discussing the testing strategy for future quantum logic (QL) circuits appeared in recent years. This fast abstract relates to our ongoing research in quantum logic testing. It further surveys QC fault models, fault tolerance and various other test strategies.

In general, only a few of the many fault models of conventional logic can be immediately extended to quantum logic. Quantum logic has not reached the real technological level that allows the use of behavioral faults that deal with the highest level of design. Similarly, conventional logic’s hot topics of delay faults and defect faults currently do not have real equivalence within the QL domain. On the other hand, logic-level fault models (or register transfer level RTL) that deal with the netlist of quantum gate interconnections can be readily adapted to QC.

The most popular RTL fault model is the stuck-at-fault. In conventional logic, it is modeled by assigning a fixed logic value to an I/O of the circuit. Perkowski et al. [4] proposed two fault models, the first for binary permutative QC, and the second for the general quantum gates. In the first model, they define multiple-valued states for the wires, including {|0〉, |1〉, |V0〉, and |V1〉} which are observed for the conventional “stuck at” problems. The main difference between their two

fault models is the need for probabilistic tests whenever the outputs use complex values.

Conventional logic often defines stuck-at faults using the particular gate fault models. Polian et al. promoted the use of a gate fault model for QC over the stuck-at model [5]. They derived a family of logical fault models for reversible circuits composed of k-CNOT (k-input controlled-NOT) gates. Their model relates to the single missing-gate fault model (MGF). We are also working on a MGF-like fault model [1]. Leakage faults, which are very important in conventional digital logic, have been treated sparsely in the QC literature. We assume that each qubit lives “happily” in a two dimensional Hilbert space so that in response to an error, the qubit can either become entangled with the environment or rotated unpredictably within the two dimensional space. The leakage in quantum circuits occurs when the qubit leaks out of this two-dimensional Hilbert space into a larger space. The testing of QC leakage faults is a difficult open issue. We note that faults manifested as rotations can be modeled as the unintentional insertion of a single qubit Pauli rotation gate and that faults causing only phase changes in the qubit may be ignored since the only information carrying portion of the qubit is the direction it points to in the Hilbert space.

In the real world, more than one fault (single-fault model) can materialize at the same time, thus leading to the multiple-fault model.

The test generation problem for irreversible, classical circuits is an NP-complete problem. Agrawal noted in the early 80s that fault detection is improved when the output content of the tested circuit is maximized. Since reversible logic like QC circuits have maximized outputs, it suggests that it should be easier to detect faults in QC reversible logic circuits compared to conventional logic.

Patel et al. indeed showed that reversible circuits require fewer test vectors for multiple faults based on the stuck-at model compared to classical circuits [3]. They found that in reversible logic, the number of test vectors grows logarithmically in both the number of inputs/outputs and the number of gates!

Moreover, they demonstrated a critical and unique feature for reversible logic testing – any test-set that

1. Introduction

2. Fault models for quantum logic

1530-2059/07 $25.00 © 2007 IEEEDOI 10.1109/HASE.2007.53

367369

can detect all single faults in a reversible logic circuit will also detect all multiple stuck-at faults. This feat cannot be achieved in conventional (irreversible) circuits where multiple stuck-at faults are significantly more difficult to cover than single stuck-at faults. On the other hand, Biamonte and Perkowski demonstrated that quantum circuits can use only some of the test methods developed for reversible circuits [4].

Due to the no-cloning theorem of QC, quantum computers can be modeled as physically moving the qubits from the storage area to the quantum processing area and back to storage during every computation cycle. A suitable QC transmission channel fault model assumes the same probability p for a qubit to flip from |0〉 to |1〉 or from |1〉 to |0〉 [2].

Random pattern generation for conventional digital logic was researched extensively in the last 40 years. It was found that most logic circuits respond well to random pattern generation in the sense that 80% coverage may be achieved even after only 10 random patterns. However, some circuits such as PLAs do not perform so well.

The use of random pattern testing in QC is a very interesting open question. Our expectation is that random testing for QC may prove to be very useful, with good fault coverage even for a low number of tests. This is because quantum circuits are reversible, and we have noted that reversible circuits have maximized outputs which generally make them easier to test. Further, the lack of don’t care states in QC circuits increases the chance that few patterns will tend to have wider fault coverage. We are currently researching random gate replacements in our design verification technique for detecting redundant QC logic using QMDD equivalence checking [1].

3. Random testing for quantum logic

QC reliance on extensive data communication is further impacted by the decoherence problem. Decoherence is the tendency of a quantum state held at superposition to “decay” into the basis states, resulting in a loss of the quantum state information (like noise in classical computing). Isailovic et al. showed that decoherence causes an extremely large error rate of single quantum gate of 10-3 [1]. While near future enhancements are projected to improve this failure rate to 10-8, it is still many orders of magnitude below the standard CMOS gate’s error rate of 10-19. Therefore, QC must rely extensively on quantum error correction codes (QECC) for proper operation. All current and proposed implementations for quantum computing typically use [n,k,d] quantum error correcting codes, where a total of n qubits are used to encode k qubits of data, with distance d. This code is capable of correcting the error set {Ei} iff

5. Fault Tolerant circuits for QC

PEiEjP=αijP (1)

where α is an Hermitian matrix with complex elements and P is a projector into the code [2].

After an error is detected, a properly designed fault-tolerant QC circuit must activate its error recovery means. Such a QC circuit can tolerate a single-fault failure probability p in the circuit’s gates provided the measurement result reported has probability of error of O(p2).

The important threshold theorem for quantum computation states that an arbitrarily complex QC circuit can work reliably, provided the error probability p of each individual gate is below a certain threshold [2]. While the QC circuit still requires some reasonable overhead in size for QECC and other noise avoidance circuits, this theorem is heralded by QC researchers as the light at the end of the tunnel that leads to the emergence of real quantum computers.

+

4. Built-in-self-test (BIST) for QC

The built-in-self-test (BIST) paradigm emerged with the increased complexity of conventional digital circuits. We believe that future quantum computers must rely heavily on BIST due to the projected complexity of the proposed implementations. While the development of BIST for conventional logic had to survive repeated economical challenges, particularly in those circuits that offered poor fault coverage by the BIST, QC BIST may be able to rely on smaller and well designed pattern sets which provide better coverage. It should also be noted that BIST (for conventional logic) often employs a random pattern generator.

References

[1] D. Y. Feinstein, Ph.D. Qualifier Examination Report,

SMU, School of Engineering April 12, 2007.

[2] M.A. Nielsen and I.L. Chuang, Quantum Computation

and Qunatum Information, Cambridge University Press, 2000.

[3] K.N. Patel, J.P. Hayes, and I.L. Markov, “Fault testing for

reversible logic”, In IEEE Trans. on CAD of IC and Systems, Vol. 23, No. 8, pp. 1220-1230, August 2004. [4] M.A. Perkowski, J. Biamonte, and M. Lukac, “Test

generation and fault localization for quantum circuits”, In ISMVL’05 , pp 146-153, May 2005.

[5] I. Polian, T. Fiehn, B. Becker, J. P. Hayes, “A Family of

Logical Fault Models for Reversible Circuits” Proceedings 14th Asian Test Symposium, pp. 422-427, Dec. 2005.

370368