写像

各入力にちょうど 1 つの出力を対応させる関係。 関数と同義。

$$f:A\to B$$

3 つの分類#

種類	条件	意味
単射	$f(a)=f(a^{\prime })\Rightarrow a=a^{\prime }$	潰さない
全射	$\forall b\in B,\exists a:f(a)=b$	全部覆う
全単射	単射かつ全射	1 対 1 対応。逆写像が存在

情報の保存#

単射は情報を失わない。 線形写像で言えば フルランク、核が $\{0\}$ の状態。 逆行列が存在する条件と対応する。

量子計算の量子ゲートは 必ずユニタリ、 すなわち全単射でなければならない。 量子計算は可逆であり、情報を捨てられない。 古典の AND ゲート（2 入力 1 出力）がそのままでは使えないのはこのため。

参考文献#

• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html
• Michael A. Nielsen, Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511976667