TCS-TR-A-07-33

Date: Sun Dec 30 11:38:38 2007

Title: An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction

Authors: Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller

Contact:

First name: Shin-ichi
Last name: Minato
Address: Division of Computer Science, Hokkaido University, Sapporo 060-0814, Japan
Email: minato@ist.hokudai.ac.jp

Abstract. Recently much attentions have been paid to quantum circuit design to prepare for the future ``quantum computation era.'' Like the conventional logic synthesis, it should be important to verify and analyze the functionalities of generated quantum circuits. Therefore, we propose an efficient verification method for quantum circuits under a practical restriction. Thanks to the restriction, we can introduce an efficient verification scheme based on decision diagrams called Decision Diagrams for Matrix Functions (DDMFs). Then, we show analytically what are the advantages of our approach based on DDMFs over the previous techniques. In order to introduce DDMFs, we also introduce new concepts, quantum functions and matrix functions, which may also be interesting and useful on their own for designing quantum circuits.