量子計算における操作は、古典的なコンピュータの論理ゲートに似ていますが、根本的な違いがあります。量子ビットの状態はベクトルで表されるため、その状態を変化させる操作は行列で記述されます。具体的には、ユニタリ行列と呼ばれる特殊な行列が使われます。これは、操作が可逆的であり、確率の総和が常に1に保たれることを保証するためです。

例えば、古典的なNOTゲートに相当するパウリXゲートは、以下の行列で表されます。

同様に、重ね合わせ状態を作り出すために不可欠なアダマールゲート（Hゲート）もユニタリ行列です。

古典計算では、NANDゲートさえあれば他の全ての論理ゲートを構成できることが知られています。同様に、量子計算にも「ユニバーサルゲートセット」が存在します。これは、いくつかの基本的なゲートを組み合わせることで、任意の量子計算を望みの精度で近似できるゲートの集合です。

最も一般的なユニバーサルゲートセットの一つは、クリフォードゲート（H、S、CNOTゲートなど）と、非クリフォードゲートであるTゲートの組み合わせです。Tゲートは「$\\/8$ゲート」とも呼ばれ、ブロッホ球のZ軸周りに$\pi/4$ラジアン回転させる操作に対応します。

これらの基本的なゲートを配列したものが、量子回路です。量子アルゴリズムは、この量子回路図として表現されます。

実用的な計算には複数の量子ビットが必要です。複数の量子ビットを扱うゲートの代表格が、制御NOTゲート（CNOTゲート）です。これは2つの量子ビットに作用し、1つを「制御ビット」、もう1つを「ターゲットビット」とします。制御ビットが$|1\rangle$のときのみ、ターゲットビットを反転（NOT操作）させます。

CNOTゲートの動作は、4x4のユニタリ行列で記述されます。入力状態が$|00\rangle, |01\rangle, |10\rangle, |11\rangle$の順に並んだ基底ベクトルに作用します。

CNOTゲートと単一量子ビットゲートを組み合わせることで、エンタングルメントと呼ばれる、古典的にはありえない相関を持つ量子状態を作り出すことができます。これは量子アルゴリズムが古典アルゴリズムを超える能力を持つ源泉の一つです。

量子アルゴリズムを評価する際、その効率は重要です。量子回路の複雑さを測る指標として「回路の深さ」と「回路の幅」があります。

• 回路の幅: 回路で使用される量子ビットの総数です。
• 回路の深さ: アルゴリズムを実行するために必要な時間ステップの数です。同時に（並列に）実行できるゲートは1ステップと数えられます。

現在の量子コンピュータはノイズに弱く、量子状態を維持できる時間が限られています（コヒーレンス時間が短い）。そのため、回路の深さが浅い（つまり、計算ステップが少ない）アルゴリズムほど、エラーの影響を受けにくく、実行しやすくなります。量子プログラマは、ゲートを並列に実行できる箇所を見つけ、回路の深さを最小限に抑えるように工夫します。

ここまでの重要な概念を理解できたか、クイズで確認してみましょう。

これらのゲート操作の組み合わせが、複雑な量子アルゴリズムの根幹をなしています。