Reduction of Quantum Cost by Making Temporary Changes to the Function

Nurul AIN BINTI ADNAN  Shigeru YAMASHITA  Alan MISHCHENKO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.7   pp.1393-1402
Publication Date: 2017/07/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016EDP7397
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
quantum cost,  changing functionality,  Mixed Polarity Multiple Control Toffoli gates,  ESOP,  

Full Text: PDF(1.7MB)>>
Buy this Article




Summary: 
This paper presents a technique to reduce the quantum cost by making temporary changes to the functionality of a given Boolean function. This technique is one of the very few known methods based on manipulating Exclusive-or Sum-Of-Products (ESOP) expressions to reduce the quantum cost of the corresponding circuit. The idea involves adding Mixed Polarity Multiple-Control Toffoli (MPMCT) gates to temporarily change the functionality of the given function, so that the modified function has a smaller quantum cost. To compensate for the temporary change, additional gates are inserted into the circuit. The proposed method finds a small ESOP expression for the given function, and then finds a good pair of product terms in the ESOP expression so that the quantum cost can be reduced by applying the transformation. The proposed approach is likely to produce a better quantum cost reduction than the existing methods, and indeed experimental results confirm this expectation.