抄録

A-013
1-CNOT回路内の縮退故障を検出する検査入力集合生成アルゴリズム

可逆回路の製造時に回路内の故障を見つけることは重要であるが，可逆回路内の縮退故障を検出する検査入力集合を生成するアルゴリズムはあまり知られていない．Patelらは，任意の可逆回路C に対して|T| = O(log |W(C)|) であるような完全な検査入力集合T が存在することを証明した．ここで，W(C) は回路C に対する配線の集合である．Tabeiらは任意の可逆回路に対して|T| = O(log |W(C)|) であるような完全な検査入力集合T を期待多項式時間で生成するような乱択アルゴリズムを提案した．本研究では，0-CNOT，1-CNOT ゲートで構成された回路のあらゆる縮退故障を検出するような検査入力集合を生成する決定性多項式時間アルゴリズムを提案する．