정렬 순서에 규칙이 없는 100만 건의 데이터에서 조건에 맞는 1건을 찾을 때, 그로버 알고리즘으로 필요한 질의(오라클 호출) 횟수의 차수로 가장 가까운 것은?

정답: B. 약 1,000회

고전 컴퓨터로 1건씩 조사하면 평균으로 절반인 약 50만 회, 최악으로 100만 회가 걸립니다. 그로버 알고리즘에서는 정답의 진폭을 조금씩 증폭함으로써 약 √N회, 정확히는 (π/4)√N ≈ 785회의 반복으로 높은 확률로 정답이 얻어지며, 차수로는 √(100만) = 1,000회 정도입니다. 빨라지는 것은 제곱만큼뿐이며, 쇼어 알고리즘 같은 지수적인 차이는 없습니다. 대칭 키 암호에서는 키의 전수 탐색 횟수가 2ⁿ에서 약 2^(n/2)이 되므로, 키의 길이를 2배로 하는(AES-128에서 AES-256으로 하는) 것으로 대응할 수 있다고 여겨집니다.