An XQDD-Based Verification Method for Quantum Circuits

Shiou-An WANG
Chin-Yung LU
Sy-Yen KUO

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A    No.2    pp.584-594
Publication Date: 2008/02/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.2.584
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
quantum computing,  quantum circuits,  verification,  decision diagram,  

Full Text: PDF(466.9KB)>>
Buy this Article

Synthesis of quantum circuits is essential for building quantum computers. It is important to verify that the circuits designed perform the correct functions. In this paper, we propose an algorithm which can be used to verify the quantum circuits synthesized by any method. The proposed algorithm is based on BDD (Binary Decision Diagram) and is called X-decomposition Quantum Decision Diagram (XQDD). In this method, quantum operations are modeled using a graphic method and the verification process is based on comparing these graphic diagrams. We also develop an algorithm to verify reversible circuits even if they have a different number of garbage qubits. In most cases, the number of nodes used in XQDD is less than that in other representations. In general, the proposed method is more efficient in terms of space and time and can be used to verify many quantum circuits in polynomial time.