Madame Lelica

Title:An algorithm for the T-count

Download PDF

概要:クリフォードゲートとTゲートからなる量子回路を考える。 このコンテキストでは、Tゲートは（古典的にシミュレート可能な）クリフォードゲートに追加された普遍的な計算を与えるので、特別なステータスを持っています。 しかし、フォールトトレランスを実装するのは非常に高価です。, したがって、このゲートを必要なときにのみ使用する必要があるソースと見なします。 N-量子ビットユニタリUweは、tゲートの最小可能数（UのTカウントと呼ばれる）を使用してそれを実装する回路を計算することに興味があります。 関連するタスクは、UのTカウントがm以下である場合に決定することであり、この問題はN=2^nとmの関数とみなされます。O(N^m poly(m,N))として時間と空間の両方を使用して解決する古典的なアルゴリズムを提供します。, 私たちはouralgorithmを実装し、ToffoliまたはFredkinゲートのClifford+T回路には少なくとも7つのTゲートが必要であることを示すために使用しました。 これは、これらのゲートの既知の7つのTgate回路がT最適であることを意味します。 また，単一量子ビット単位のＴカウントに対する単純な表現を提供した。