[양자컴퓨팅] Deutsch's Algorithm 정리

어떤 함수 f가 constant하다 라는 말은 함수 f가 f(0)=0, f(1)=0 을 만족하거나 f(0)=1, f(1)=1을 만족함을 의미하며, f(0), f(1)이 각각 0과 1의 값을 가질 때 함수 f가 balance하다 라고 말한다. 

 

 

어떤함수 f가 있을 때 우리는 함수 f가 constant인지 balance인지를 파악하고 싶다. 단순히 생각해보면 먼저 f(0)이 무엇인지 찾고, f(1)이 무엇인지 찾아서 그 결과가 동일하면 constant, 다르면(큐빗이 2개임을 가정) balance하다라고 할 수 있으며, 총 2번의 확인으로 알 수 있다. 여기서 양자컴퓨팅으로 더 빠르게 알 수 있지 않을까 해서 나오게 된것이 도이치 알고리즘(Deutsch's algorithm)이다.

 

Deutsch's Algorithm

일단 주어진 함수 f를 Uf로 변환하는 과정이 필요하다. Uf란 함수 f를 Unitary matrix로 만들겠다는 말인데, 이전에 양자상태의 변환에 있어서 어떤 quantum state에서 다른 state로 변환할 때는 unitary matrix를 이용한다는 것을 배웠다. 따라서 함수 f를 일반적인 matrix가 아닌 가역성을 갖는 unitary matrix로 만들어야 한다. 

 

 

만든 Uf를 위 그림과 같은 양자회로에 넣고 input이 0state, 1state임을 인지하고 계산을 해본다. 측정 직전의 상태인 Ψ3을 살펴보면 계산을 통해서 밑의 식이 도출됨을 알 수 있다. f가 constant이면 첫번째 측정값으로 0state이 나올것이며(phase는 +1, -1) f가 balance라면 첫번째 측정값으로 1이 나올것이다!!(마찬가지로 phase는 +1,-1)

 

즉, 함수 f가 무엇이 되었건 간에 위의 양자회로에 Uf로 변환하여 집어넣으면, 첫번째 측정값만으로 이 함수가 constant인지 balance인지 알 수 있는 것이다. 기존의 방법에서는 2번의 확인으로 f를 알 수 있었다면, 도이치 알고리즘을 사용한다면 1번만으로 가능하게 된다.