補助ビット

可逆コンピューティングでは、補助ビットは不可逆な論理演算を実装するために使用される追加ビットです。古典的コンピューティングでは、メモリ ビットは自由にオンまたはオフにすることができ、事前の知識や追加の複雑さは必要ありません。 ただし、これは量子コンピューティングや古典的可逆コンピューティングには当てはまりません。 これらのコンピューティング モデルでは、コンピュータ メモリに対するすべての操作は可逆的でなければならず、ビットのオン/オフを切り替えるとそのビットの初期値に関する情報が失われます。 このため、量子アルゴリズムでは、元の状態が事前にわかっているビットにアクセスできない限り、ビットを特定の規定された状態に決定論的に設定する方法はありません。 値が事前にわかっているこのようなビットは、量子コンピューティング タスクまたは可逆コンピューティング タスクでは補助ビットと呼ばれます。

補助ビットの簡単な使い方は、複雑な量子ゲートを単純なゲートにダウングレードすることです。たとえば、補助ビットに制御を配置することで、トフォリゲートを制御NOTゲートまたはNOTゲートとして使用できます。^{[1] : 29}

古典的な可逆計算では、定数 O(1) の補助ビットが普遍的な計算に必要かつ十分であることが知られています。^{[2]補助ビットの追加は必須ではありませんが、余分な作業領域により、より少ないゲートを使用するより単純な}回路構成 が可能になります。^{[1] : 131}

補助ビットの概念は、補助量子ビットの観点から量子コンピューティングに拡張することができ、これは例えば量子エラー訂正に使用できます。^{[3]量子コンピューティングにおける補助量子ビットの使用の注目すべき例の1つは}、Deutsch-Jozsaアルゴリズム です。

量子触媒は補助量子ビットを使用してエンタングルメント状態を保存し、通常は局所操作と古典通信（LOCC）では不可能なタスクを可能にします。^[4]