이상적인 양자 오라클 모델에서 N개의 후보 중 조건을 만족하는 항목 하나를 찾는 Grover 알고리즘에 대한 설명으로 옳지 않은 것은?

1. 1

   비정렬 검색에 필요한 오라클 질의 수를 Θ(√N) 수준으로 줄인다.

   오답 이유Grover 알고리즘은 구조가 없는 N개 후보 검색에 약 √N회의 오라클 질의를 사용하므로 고전적 선형 검색보다 제곱근 가속을 제공한다.
2. 2

   일반적인 비정렬 검색을 Θ(log N)번의 오라클 질의만으로 해결한다.

   정답 근거Grover 알고리즘은 일반적인 비정렬 검색을 로그 수준으로 줄이지 않는다. 알려진 일반적 이득은 Θ(√N) 질의이므로 이 설명이 틀렸다.
3. 3

   이상적 모델에서 k비트 대칭키 전수 탐색의 작업 지수를 대략 k/2로 낮춘다.

   오답 이유키 공간 크기가 2^k이면 Grover 탐색의 이상적 질의 수는 대략 2^(k/2)이므로 대칭키의 전수 탐색 보안 지수를 절반 수준으로 본다.
4. 4

   같은 전수 탐색 보안 수준을 목표로 하면 대칭키 길이를 늘리는 대응을 고려할 수 있다.

   오답 이유이상적 Grover 위협만 비교하면 키 길이를 두 배로 늘려 기존의 고전적 전수 탐색 지수에 대응하는 식으로 보안 여유를 잡을 수 있다. 실제 비용은 회로·오류정정·병렬화 조건도 함께 봐야 한다.