文献

J-GLOBAL ID：201202207639332676   整理番号：12A1240816

最適4ビット可逆Toffoli回路とそれらの合成に関する研究

A Study of Optimal 4-Bit Reversible Toffoli Circuits and Their Synthesis

著者 (2件)： GOLUBITSKY Oleg (Google, Inc., ON, CAN) ,  MASLOV Dmitri (Univ. Waterloo, ON, CAN)
資料名： IEEE Transactions on Computers  (IEEE Transactions on Computers)
巻： 61  号： 9  ページ： 1341-1353  発行年： 2012年09月 
JST資料番号： C0233A  ISSN： 0018-9340  CODEN： ICTOB4  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 可逆回路は効率的量子計算のために効率的実行が必要な,重要な計算クラスである。可逆関数の最適合成は大きな問題で,回路計算における制限因子の1つに可逆関数の純粋な数がある。4ビット可逆関数への限定合成すら巨大な探索空間をもたらし,各関数用Toffoliゲートに必要な出力空間のみで記憶容量が100テラバイトを越える。関数実装に必要なゲート数の最小化を目的に,2つのアルゴリズム,FINDOPT:4ビット可逆関数用最適回路の発見,SEARCALL:すべての最適4ビット可逆関数の発見,について記述した。FINDOPT実装では,最大9ゲート必要なすべての最適実装の計算に約3時間,4ビット可逆関数の最適回路の探索に平均で約0.00756秒かかった。FINDOPTの実装に約13日必要だが,全ての関連する統計とデータの収集は1回だけ完結すればよい。複数の実験により,両計算方式が所与の探索空間サイズにおいて驚くほど高速なことを示した。

シソーラス用語： *論理合成 ,  論理回路 ,  *可逆回路 ,  量子論 ,  *量子計算 ,  最適回路 ,  発見的方法 ,  近傍探索法 ,  *計算機アルゴリズム ,  性能試験
準シソーラス用語： 量子回路 ,  可逆Toffoli回路 ,  論理ゲート

分類 (2件)： 計算理論  (JB02000A) ,  回路理論一般  (NA02010M)

タイトルに関連する用語 (2件)： 4ビット ,  研究