출처 검증됨레벨 3
도이치-조사 알고리즘
도이치-조사 알고리즘은 불리안 함수가 상수인지 균형인지를 단 한 번의 쿼리로 결정하며, 고전적 결정론적 알고리즘에 비해 지수적 속도향상을 제공합니다.
무슨 뜻인가요
도이치-조사 알고리즘(1992)은 블랙박스 함수가 상수(모든 입력에 같은 출력)인지 균형(절반은 0, 절반은 1)인지 결정합니다.고전적으로 최악의 경우 2^(n-1)+1 쿼리가 필요하지만 양자 알고리즘은 단 한 번의 쿼리만 사용합니다.양자 병렬성과 간섭을 활용합니다.일상 비유
동전이 공정한지 양면이 같은지 확인하는 것을 상상하세요.
봉인된 투표함이 모두 같은 표인지 완벽한 분할인지 검사하는 것으로 생각하세요.
흔한 오해
- 속도향상은 결정론적 고전 알고리즘에 대한 것입니다.
- 알고리즘은 함수가 무엇을 계산하는지 알려주지 않습니다.
핵심 정리
- 단 한 번의 오라클 쿼리로 상수 vs 균형 결정.
- 양자 우위를 증명한 최초의 알고리즘.
- 중첩, 위상 킥백, 간섭을 핵심 기법으로 사용.
이해했는지 확인해 보세요
도이치-조사 알고리즘에 필요한 오라클 쿼리 수는?
- A.n
- B.2^n
- C.1
- D.log(n)
정답 보기
정답: C. 1
이유: 도이치-조사 알고리즘은 정확히 1번의 오라클 쿼리가 필요합니다.
먼저 알아야 할 개념
원 출처: Deutsch & Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. A 439, 553 (1992), doi:10.1098/rspa.1992.0167