Deutsch Algorithm

  1985 Paper

   $U_{f}$ 를 한 번만 act해서 f가 상수함수인지 알 수 있나?
   할 수 있다.

  Mermin Fig 2.3 의 이해

  $U_{f}$ 의 연산자에

  $(H\otimes 1)U_{f}(H\otimes H)(X\otimes X)|0\rangle |0\rangle$

를 하고, 첫번째 bit를 재면, 상수 함수 여부를 알 수 있다고 했다.

  $(H\otimes H)U_{f}(H\otimes H)$

를 생각해 보자

  위와 다른 점은 아래 비트에 $H$를 더 곱하는 것인데, 이는 위 비트에는 영향을 미치지 않는다.

  이 오퍼레이터를 해석해보면, 아래 비트에 의해서 영향을 위 비트가 영향을 받을 때는 아래 비트가 $|1\rangle$

일 때 뿐이다.

  따라서 위 비트가 변화하지 않기 때문에 상수함수인 것을 판단할 수 있다는 뜻이다.

 $(H\otimes H)U_{f}(H\otimes H)(1\otimes X)|x\rangle |0\rangle$

로 하고, 위의 비트를 재면 그만이다.