アダマール変換
アダマール変換は高速アダマール変換を用いると O ( n log  n ) ( n = 2 m ) {\displaystyle O(n\operatorname {log} n)\quad (n=2^{m})} である。
H ( | 1 ⟩ ) = 1 2 | 0 ⟩ − 1 2 | 1 ⟩ {\displaystyle H(|1\rangle )={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle }
H ( | 0 ⟩ ) = 1 2 | 0 ⟩ + 1 2 | 1 ⟩ {\displaystyle H(|0\rangle )={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle }
H ( 1 2 | 0 ⟩ + 1 2 | 1 ⟩ ) = 1 2 ( | 0 ⟩ + | 1 ⟩ ) + 1 2 ( | 0 ⟩ − | 1 ⟩ ) = | 0 ⟩ {\displaystyle H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}(|0\rangle +|1\rangle )+{\frac {1}{2}}(|0\rangle -|1\rangle )=|0\rangle }