출처 검증됨레벨 3
양자 푸리에 변환
양자 푸리에 변환(QFT)은 이산 푸리에 변환의 양자 아날로그로, n큐비트에 대해 O(n²) 게이트만으로 계산 기저 상태를 위상 인코딩된 주파수 상태로 변환합니다.
무슨 뜻인가요
QFT는 계산 기저 상태를 주파수 성분을 인코딩하는 위상을 가진 중첩으로 매핑합니다.고전적 FFT의 O(n·2^n)과 비교하여 O(n²) 게이트만 필요합니다.쇼어 알고리즘과 양자 위상 추정의 핵심 서브루틴입니다.일상 비유
화음을 개별 음으로 변환하는 것과 같습니다.
백색광을 무지개로 분리하는 프리즘으로 생각하세요.
흔한 오해
- QFT 속도향상이 직접 신호 처리 가속화로 이어지지 않습니다.
- QFT 회로는 고전적 FFT 알고리즘과 같지 않습니다.
핵심 정리
- O(n²) 게이트로 계산 기저를 주파수 기저로 변환.
- 고전적 FFT보다 지수적으로 적은 게이트.
- 쇼어 알고리즘과 양자 위상 추정의 핵심 서브루틴.
이해했는지 확인해 보세요
n큐비트에 대한 QFT에 필요한 게이트 수는?
- A.O(n)
- B.O(n²)
- C.O(2^n)
- D.O(n·2^n)
정답 보기
정답: B. O(n²)
이유: QFT 회로는 O(n²) 게이트가 필요합니다.
먼저 알아야 할 개념
원 출처: Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172
Circuit form per Coppersmith (1994), arXiv:quant-ph/0201067.