Deutsch-Jozsa 오해
Deutsch-Jozsa 알고리즘을 이해하지 못합니다. 위키피디아가 제안한대로 :${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$. 이 함수는 n 자리 이진 값을 입력으로 사용하고 각 값에 대한 출력으로 0 또는 1을 생성합니다. 함수는 상수 (모든 출력에서 0 또는 모든 출력에서 1) 또는 균형 (입력 도메인의 절반에 대해 1을 반환하고 나머지 절반에 대해 0을 반환)이라고 약속합니다. 그런 다음 작업은 oracle을 사용하여 {\ displaystyle f} f가 일정하거나 균형이 맞는지 확인하는 것입니다.
질문 1 : 일반 컴퓨터에서 확률 알고리즘을 사용하면 오라클에 0을 한 번만 입력 한 다음 하나의 1을 입력하면 안됩니다.
나는 또한 여기에서 읽었다 : http://www.diva-portal.org/smash/get/diva2:840938/FULLTEXT01.pdf: Bob이 균형 함수에서 임의의 길이 목록을 생성한다고 가정합니다. 그러면 목록에는 0과 1이 똑같이 포함되므로 Alice가 목록에 임의의 요소를 그리면 확률이 1/2 인 0 또는 1이됩니다. 그녀가 두 가지 요소를 그린다면. 그런 다음 각각 동일한 확률이 1/4 인 "00", "01", "10"및 "11"결과를 얻을 수 있습니다. Alice가 함수가 상수인지 균형인지 추측해야한다면 시간의 절반을 정확하게 추측 할 것입니다. 대신 세 번째 요소를 그리는 경우 결과는 가능한 결과”000”,”001”,”010”,”011”,”100”,”101”,”110”및”111에 대해 균일 한 확률 분포가됩니다. ”. 앨리스는 이제 8 번 중 6 번을 정확하게 추측합니다.
질문 2 : 만약 그녀가 "001"(또는 이브 "01"/ "10")을 가지고 있다면 그것은 이미 균형 잡힌 함수가 아닌가?
답변
첫 번째 질문과 관련하여 $n$ 입력 $f$ 그리고 임무는 $f$일정하거나 균형이 잡힌다 (하나 또는 다른 것임을 약속) 단일 쿼리로 양자 컴퓨터에서이 작업을 수행 할 수 있습니다.$f$. 만약$n=1$, 그런 다음 고전적으로 제안한대로 수행 할 수 있습니다. $0$ 하나의 쿼리 및 입력 $1$ 다른 쿼리의 경우 총 2 개의 쿼리에 대해하지만 양자 컴퓨터는 여전히 하나의 쿼리만으로 승리합니다.
두 번째 질문에 대해서는 맞습니다. 고전적으로 다른 두 개의 출력을 얻은 경우 (약속에 따라) 함수가 균형을 이루고 있는지 확인할 수 있습니다. 그러나 독일어 - Josza 당신이 할 수 있다고 지적 보장 이 단지와 균형있어 단일 쿼리.
일반적으로 최소 2 개, 최대 $2^{n-1}+1$, 쿼리이지만 양자 역학적으로 단일 쿼리로 충분합니다.
아직 확인하지 않았다면 현재보고있는 Deutsch-Jozsa 알고리즘의 단일 큐 비트 버전 인 Deutsch 알고리즘을 살펴 보는 것부터 시작하십시오.
여기에 몇 가지 간단한 리소스가 있습니다.
- http://www.cs.xu.edu/~kinne/quantum/deutche.html
- https://www.youtube.com/watch?v=5xsyx-aNClM
Deutsch-Jozsa보다 간단하고 좋은 디딤돌입니다.