量子可逆邏輯綜合算法及應(yīng)用.pdf

1、可逆邏輯綜合是指對(duì)給定的可逆函數(shù)構(gòu)造對(duì)應(yīng)的可逆邏輯電路，其是構(gòu)建量子計(jì)算機(jī)的關(guān)鍵技術(shù)之一，對(duì)于量子計(jì)算與量子信息的發(fā)展具有重要的意義。由于搜索空間隨電路規(guī)模增長成指數(shù)增長，現(xiàn)有的可逆邏輯綜合算法雖然能夠得到近似最優(yōu)解，但是都存在計(jì)算時(shí)間過長的問題。本文提出了一種類似選擇排序的可逆邏輯綜合算法，其實(shí)質(zhì)為基于變換規(guī)則的合成法。它采用一個(gè)無向無權(quán)圖表示所有可以進(jìn)行變換的路徑，在綜合的過程中，采用選擇排序思想每次從小到大的選擇需要交換的輸出項(xiàng)，

2、然后從路徑選擇圖中找到最優(yōu)的路徑進(jìn)行變換，最終使得函數(shù)的輸出序列有序即完成綜合。此外，本文還對(duì)得到的量子電路進(jìn)行了優(yōu)化。實(shí)驗(yàn)表明，相比其他綜合算法，該算法在能得到近似最優(yōu)解的前提下，效率高、易于實(shí)現(xiàn)。
　　 但是啟發(fā)式算法并不能完全求得最優(yōu)解，同時(shí)所用的擴(kuò)展Toffoli門庫代價(jià)相對(duì)非門、控制非門和Toffoli門而言過高，因此本文又提出了一種基于外存的四量子最優(yōu)電路綜合算法，通過將最優(yōu)電路的綜合問題轉(zhuǎn)換為外存上海量數(shù)據(jù)文件的排