Grover 알고리즘

이 Qiskit in Classrooms 모듈을 사용하려면, 학생들의 Python 환경에 다음 패키지가 설치되어 있어야 합니다:

• qiskit v2.1.0 이상
• qiskit-ibm-runtime v0.40.1 이상
• qiskit-aer v0.17.0 이상
• qiskit.visualization
• numpy
• pylatexenc

위 패키지의 설치 및 설정 방법은 Qiskit 설치 가이드를 참고하세요. 실제 양자 컴퓨터에서 작업을 실행하려면, IBM Cloud 계정 설정 가이드의 절차에 따라 IBM Quantum® 계정을 만들어야 합니다.

이 모듈은 테스트 결과 12초의 QPU 시간을 사용했습니다. 이는 추정치이며, 실제 사용량은 다를 수 있습니다.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

소개

Grover 알고리즘은 비구조적 탐색 문제를 다루는 기초적인 양자 알고리즘입니다. 비구조적 탐색 문제란, $N$개의 항목과 특정 항목이 원하는 것인지 확인하는 방법이 주어졌을 때, 원하는 항목을 얼마나 빠르게 찾을 수 있는지에 관한 문제입니다. 고전적인 컴퓨팅에서는 데이터가 정렬되어 있지 않고 활용할 구조도 없다면, 각 항목을 하나씩 확인하는 것이 최선입니다. 이 경우 쿼리 복잡도는 $O(N)$이며, 평균적으로 목표 항목을 찾기 전에 약 절반의 항목을 확인해야 합니다.

1996년 Lov Grover가 발표한 Grover 알고리즘은 양자 컴퓨터가 이 문제를 훨씬 효율적으로 해결할 수 있음을 보여줍니다. 표시된 항목을 높은 확률로 찾는 데 $O(\sqrt{N})$단계만 필요합니다. 이는 고전적인 방법에 비해 *이차적 속도 향상(quadratic speedup)*을 나타내며, 대규모 데이터셋에서 특히 의미 있습니다.

이 알고리즘은 다음과 같은 맥락에서 작동합니다:

• 문제 설정: 함수 $f(x)$가 있으며, $x$가 원하는 항목이면 1을, 그렇지 않으면 0을 반환합니다. 이 함수는 $f(x)$를 쿼리해야만 데이터에 대해 알 수 있기 때문에 오라클(oracle) 또는 *블랙박스(black box)*라고도 합니다.
• 양자의 유용성: 이 문제에 대한 고전적인 알고리즘은 평균적으로 $N/2$번의 쿼리가 필요하지만, Grover 알고리즘은 약 $\pi\sqrt{N}/4$번의 쿼리로 해를 찾을 수 있습니다. 큰 $N$에서 이는 훨씬 빠릅니다.
• 작동 원리 (개략적 설명):
  • 양자 컴퓨터는 먼저 모든 가능한 상태의 *중첩(superposition)*을 생성하여, 모든 가능한 항목을 동시에 표현합니다.
  • 그런 다음 올바른 답의 확률을 증폭시키고 나머지를 줄이는 양자 연산 시퀀스(Grover 반복)를 반복적으로 적용합니다.
  • 충분한 반복 후, 양자 상태를 측정하면 높은 확률로 올바른 답을 얻을 수 있습니다.

아래는 Grover 알고리즘의 기본적인 다이어그램으로, 많은 세부 사항을 생략한 것입니다. 더 자세한 다이어그램은 이 논문을 참고하세요.

Grover 알고리즘에 대해 몇 가지 주목할 사항이 있습니다:

• 비구조적 탐색에서 최적입니다. 어떤 양자 알고리즘도 $O(\sqrt{N})$보다 적은 쿼리로 이 문제를 풀 수 없습니다.
• 일부 다른 양자 알고리즘(예: 소인수분해를 위한 Shor 알고리즘)과 달리, 지수적이 아닌 이차적 속도 향상만 제공합니다.
• 암호 시스템에 대한 무차별 대입 공격의 속도를 높이는 등 실용적인 함의가 있지만, 이 속도 향상만으로는 대부분의 현대 암호화를 단독으로 깨기에 충분하지 않습니다.

기본적인 컴퓨팅 개념과 쿼리 모델에 익숙한 학부생에게 Grover 알고리즘은 양자 컴퓨팅이 특정 문제에서 고전적인 접근법을 능가할 수 있음을 명확하게 보여주는 사례입니다. 설령 그 향상이 "단지" 이차적이더라도 말입니다. 또한 더 고급 양자 알고리즘과 양자 컴퓨팅의 광범위한 잠재력을 이해하는 관문 역할도 합니다.

진폭 증폭(Amplitude amplification)은 몇몇 고전적인 알고리즘에 비해 이차적 속도 향상을 얻는 데 사용할 수 있는 범용 양자 알고리즘 또는 서브루틴입니다. Grover 알고리즘은 비구조적 탐색 문제에서 이 속도 향상을 최초로 증명한 알고리즘입니다. Grover 탐색 문제를 공식화하려면, 하나 이상의 계산 기저 상태를 찾고자 하는 상태로 표시하는 오라클 함수와, 표시된 상태의 진폭을 증가시켜 나머지 상태를 억제하는 증폭 Circuit이 필요합니다.

여기서는 Grover 오라클을 구성하는 방법과, Qiskit Circuit 라이브러리의 GroverOperator를 사용하여 Grover 탐색 인스턴스를 손쉽게 설정하는 방법을 설명합니다. 런타임 Sampler 프리미티브를 사용하면 Grover Circuit을 원활하게 실행할 수 있습니다.

수학적 배경

이진 문자열을 단일 이진 변수에 매핑하는 함수 $f$가 존재한다고 가정합니다. 즉,

$$f: \Sigma^n \rightarrow \Sigma$$

$\Sigma^6$ 위에서 정의된 한 예시는 다음과 같습니다.

$$f(x)= \begin{cases} 1 \qquad \text{if }x=\{010101\}\\ 0 \qquad \text{otherwise } \end{cases}$$

$\Sigma^{2n}$ 위에서 정의된 또 다른 예시는 다음과 같습니다.

$$f(x)= \begin{cases} 1 \qquad \text{if equal numbers of 1's and 0's in string}\\ 0 \qquad \text{otherwise } \end{cases}$$

1에 매핑되는 $f(x)$의 인수 $x$에 해당하는 양자 상태를 찾는 것이 과제입니다. 즉, $f(x_1)=1$이 되는 모든 $\{x_1\}\in \Sigma^n$을 찾는 것입니다(해가 없다면 그 사실을 보고합니다). 해가 아닌 것은 $x_0$로 표기합니다. 물론 이 작업은 양자 컴퓨터에서 양자 상태를 사용하여 수행하므로, 이진 문자열을 상태로 표현하는 것이 유용합니다:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

양자 상태(Dirac) 표기법을 사용하면, $n$개의 Qubit에서 $N=2^n$개의 가능한 상태 중 하나 이상의 특별한 상태 $\{|x_1\rangle\}$를 찾는 것이며, 해가 아닌 것은 $\{|x_0\rangle\}$로 표기합니다.

함수 $f$는 오라클로 제공된다고 생각할 수 있습니다. 오라클은 상태 $|x\rangle$에 대한 효과를 쿼리하여 결정할 수 있는 블랙박스입니다. 실제로는 함수를 알고 있는 경우가 많지만, 구현이 매우 복잡할 수 있어서 $f$의 쿼리 또는 적용 횟수를 줄이는 것이 중요할 수 있습니다. 또는 한 사람이 다른 사람이 제어하는 오라클을 쿼리하는 패러다임을 상상해볼 수 있습니다. 이 경우 오라클 함수를 알 수 없고, 쿼리를 통해 특정 상태에 대한 동작만 알 수 있습니다.

이것은 "비구조적" 탐색 문제입니다. $f$에는 탐색을 돕는 특별한 구조가 없습니다. 출력이 정렬되어 있지 않고 해가 군집을 이루는 것도 아닙니다. 유추하자면, 오래된 종이 전화번호부를 생각해보세요. 이 비구조적 탐색은 특정 __번호__를 찾기 위해 전화번호부를 훑는 것과 같습니다. 알파벳순으로 정렬된 이름 목록을 검색하는 것과는 다릅니다.

단일 해를 찾는 경우, 고전적으로는 $N$에 선형인 횟수의 쿼리가 필요합니다. 운이 좋으면 첫 번째 시도에 해를 찾을 수도 있지만, 처음 $N-1$번의 시도에서 해를 못 찾으면 $N$번째 입력을 쿼리해야 해가 있는지 알 수 있습니다. 함수에 활용할 수 있는 구조가 없으므로, 평균적으로 $N/2$번의 시도가 필요합니다. Grover 알고리즘은 $\sqrt{N}$에 비례하는 횟수의 쿼리 또는 $f$ 계산이 필요합니다.

Grover 알고리즘의 Circuit 개요

Grover 알고리즘의 완전한 수학적 설명은 IBM Quantum Learning에서 John Watrous가 진행한 강좌인 양자 알고리즘의 기초에서 찾을 수 있습니다. 간략한 내용은 이 모듈 끝 부록에 제공됩니다. 여기서는 Grover 알고리즘을 구현하는 양자 Circuit의 전반적인 구조만 살펴봅니다.

Grover 알고리즘은 다음 단계로 나눌 수 있습니다:

• 초기 중첩 준비 (모든 Qubit에 Hadamard Gate 적용)
• 목표 상태를 위상 반전으로 "표시"
• 모든 Qubit에 Hadamard Gate와 위상 반전을 적용하는 "확산(diffusion)" 단계
• 목표 상태를 측정할 확률을 최대화하기 위한 표시 및 확산 단계의 반복
• 측정

표시 Gate $Z_f$와 $H,$ $Z_{\text{OR}},$ $H$로 구성된 확산 레이어를 통틀어 "Grover 연산자"라고 부릅니다. 이 다이어그램에서는 Grover 연산자가 한 번만 반복됩니다.

Hadamard Gate $H$는 양자 컴퓨팅 전반에서 널리 사용되는 잘 알려진 Gate입니다. Hadamard Gate는 중첩 상태를 만들며, 구체적으로 다음과 같이 정의됩니다:

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

다른 상태에 대한 동작은 선형성을 통해 정의됩니다. 특히, Hadamard Gate 레이어를 통해 모든 Qubit이 $|0\rangle$인 초기 상태($|0\rangle^{\otimes n}$로 표기)에서 각 Qubit이 $|0\rangle$ 또는 $|1\rangle$로 측정될 확률을 가지는 상태로 이동할 수 있습니다. 이는 고전 컴퓨팅과는 다른 방식으로 모든 가능한 상태의 공간을 탐색할 수 있게 해줍니다.

Hadamard Gate의 중요한 부수 성질은, 두 번째 적용 시 이러한 중첩 상태를 되돌릴 수 있다는 것입니다:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

이 성질은 바로 다음에서 중요하게 사용됩니다.

이해도 확인

아래 질문을 읽고, 답을 생각해본 후 삼각형을 클릭하여 해답을 확인하세요.

Hadamard Gate의 정의에서 시작하여, 두 번째 Hadamard Gate 적용이 위에서 주장한 대로 중첩 상태를 되돌림을 증명하세요.

답:

$|+\rangle$ 상태에 X를 적용하면 +1이 나오고, $|-\rangle$ 상태에 X를 적용하면 -1이 나옵니다. 따라서 50-50 분포라면 기댓값은 0이 됩니다.

$Z_\text{OR}$ Gate는 덜 일반적이며, 다음과 같이 정의됩니다:

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{if } x = 0^n \\ -|x\rangle & \text{if } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

마지막으로, $Z_f$ Gate는 다음과 같이 정의됩니다:

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

이 정의의 효과는, $Z_f$가 $f(x) = 1$인 목표 상태의 부호를 반전시키고 다른 상태는 그대로 둔다는 것입니다.

매우 추상적인 수준에서 Circuit의 각 단계는 다음과 같이 이해할 수 있습니다:

• 첫 번째 Hadamard 레이어: Qubit을 모든 가능한 상태의 중첩에 놓습니다.
• $Z_f$: 목표 상태 앞에 "-" 부호를 추가하여 표시합니다. 이것은 즉시 측정 확률을 변경하지는 않지만, 이후 단계에서 목표 상태가 어떻게 동작할지를 바꿉니다.
• 또 다른 Hadamard 레이어: 이전 단계에서 도입된 "-" 부호가 일부 항들 사이의 상대적 부호를 변경합니다. Hadamard Gate는 계산 기저 상태의 혼합인 $(|0\rangle+|1\rangle)/\sqrt{2}$를 하나의 계산 기저 상태 $|0\rangle$으로, $(|0\rangle-|1\rangle)/\sqrt{2}$를 $|1\rangle$로 변환하므로, 이 상대적 부호 차이가 이제 측정되는 상태에 영향을 주기 시작합니다.
• 마지막 Hadamard Gate 레이어가 적용된 후 측정이 이루어집니다. 다음 섹션에서 이것이 어떻게 작동하는지 더 자세히 살펴봅니다.

예시

Grover 알고리즘의 작동 방식을 더 잘 이해하기 위해, 2개의 Qubit으로 이루어진 작은 예시를 다루어 보겠습니다. 양자역학과 Dirac 표기법에 집중하지 않는 분들에게는 선택 사항입니다. 그러나 양자 컴퓨터를 실질적으로 다루고자 하는 분들에게는 적극 권장합니다.

아래는 양자 상태가 여러 위치에 표기된 Circuit 다이어그램입니다. 2개의 Qubit만 있으므로, 어떤 경우에도 측정 가능한 상태는 $|00\rangle$, $|01\rangle$, $|10\rangle$, $|11\rangle$의 네 가지뿐입니다.

오라클($Z_f$, 우리에게는 알려지지 않음)이 상태 $|01\rangle$을 표시한다고 가정합니다. 각 양자 Gate(오라클 포함)의 동작을 단계별로 따라가며, 측정 시 어떤 상태 분포가 나타나는지 살펴봅니다. 맨 처음 상태는

$$|\psi_0\rangle = |00\rangle$$

Hadamard Gate의 정의를 사용하면:

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

이제 오라클이 목표 상태를 표시합니다:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

이 상태에서 네 가지 가능한 결과 모두 동일한 측정 확률을 가집니다. 각각 $1/2$의 가중치를 가지므로, $|1/2|^2=1/4$의 확률로 측정됩니다. 따라서 상태 $|01\rangle$이 "-" 위상으로 표시되었지만, 이것이 아직 해당 상태의 측정 확률 증가로 이어지지는 않습니다. 다음 Hadamard Gate 레이어를 적용합니다.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

동류항을 합치면:

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

이제 $Z_{\text{OR}}$이 $|00\rangle$을 제외한 모든 상태의 부호를 반전시킵니다:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

마지막으로 마지막 Hadamard Gate 레이어를 적용합니다:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

이 항들을 직접 결합해보면 결과가 실제로 다음과 같음을 확인할 수 있습니다:

$$|\psi_5\rangle =|01\rangle$$

즉, (잡음과 오류가 없는 경우) $|01\rangle$을 측정할 확률은 100%이며, 다른 상태를 측정할 확률은 0입니다.

이 2-Qubit 예시는 특히 깔끔한 경우입니다. Grover 알고리즘이 항상 목표 상태를 100% 확률로 측정하는 결과를 내지는 않습니다. 알고리즘은 목표 상태를 측정할 확률을 증폭시키는 것이며, Grover 연산자를 두 번 이상 반복해야 할 수도 있습니다.

다음 섹션에서는 실제 IBM® 양자 컴퓨터를 사용하여 이 알고리즘을 실습해 봅니다.

명백한 주의 사항

Grover 알고리즘을 적용하려면 Grover 연산자를 구성해야 하는데, 이는 곧 해답 기준을 만족하는 상태에 위상을 뒤집을 수 있어야 함을 의미합니다. 그렇다면 자연스럽게 이런 의문이 생깁니다. 해답 집합을 정확히 레이블링할 양자 회로를 설계할 만큼 해답을 잘 알고 있다면, 도대체 무엇을 탐색하는 것일까요?! 그 답은 세 가지로 나눌 수 있으며, 이 튜토리얼 전반에 걸쳐 다시 다루게 됩니다.

(1) 이러한 쿼리 알고리즘은 흔히 두 당사자를 포함합니다. 한 사람은 해답 기준을 정의하는 오라클을 보유하고, 다른 한 사람은 해답 상태를 추측하거나 찾으려 합니다. 한 사람이 오라클을 구성할 수 있다는 사실이 탐색의 필요성을 없애지는 않습니다.

(2) 해답 기준을 명시하는 것이 실제 해답을 찾는 것보다 쉬운 문제들이 있습니다. 가장 잘 알려진 예는 아마도 큰 수의 소인수를 찾는 문제일 것입니다. Grover 알고리즘은 그 특정 문제에는 특별히 효과적이지 않으며, 소인수 분해에는 Shor 알고리즘을 사용합니다. 이는 단지 상태의 동작에 대한 기준을 아는 것이 항상 그 상태 자체를 아는 것과 같지 않다는 점을 보여주기 위한 예입니다.

(3) Grover 알고리즘은 고전적인 데이터만을 반환하지 않습니다. 물론 Grover 연산자를 $t$번 반복한 후 최종 상태를 측정하면, 해답 상태를 식별하는 고전 정보를 얻을 가능성이 높습니다. 하지만 고전 정보가 필요하지 않은 경우, 즉 다른 알고리즘에서 추가로 활용하기 위해 양자 컴퓨터에 해답 상태를 준비하고 싶다면 어떨까요? Grover 알고리즘은 실제로 해답이 높은 가중치로 반영된 양자 상태를 생성합니다. 따라서 더 복잡한 양자 알고리즘의 서브루틴으로 Grover 알고리즘이 사용되는 경우를 기대할 수 있습니다.

이러한 점들을 염두에 두고, 몇 가지 예제를 살펴보겠습니다. 먼저 알고리즘의 논리를 따라갈 수 있도록 해답 상태가 명확히 지정된 예제부터 시작하여, Grover 알고리즘의 유용성이 더욱 분명해지는 예제로 나아갈 것입니다.

일반 임포트 및 접근 방식

먼저 필요한 패키지를 임포트합니다.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

이 튜토리얼을 비롯한 다양한 튜토리얼에서는 "Qiskit 패턴"이라고 알려진 양자 컴퓨팅 프레임워크를 사용합니다. 이 프레임워크는 워크플로를 다음 단계로 구분합니다.

• 1단계: 고전적 입력을 양자 문제로 매핑
• 2단계: 양자 실행을 위한 문제 최적화
• 3단계: Qiskit Runtime Primitive를 사용하여 실행
• 4단계: 후처리 및 고전적 분석

일반적으로 이 단계들을 따르되, 항상 명시적으로 레이블을 붙이지는 않을 수 있습니다.

활동 1: 단일 목표 상태 찾기

Step 1: Map classical inputs to a quantum problem

솔루션 상태에는 전체 위상(-1)을 적용하고 비솔루션 상태에는 영향을 주지 않는 위상 질의 Gate가 필요합니다. 다시 말해, Grover's algorithm에는 하나 이상의 표시된 계산 기저 상태를 지정하는 오라클이 필요하며, 여기서 "표시됨"은 위상이 -1인 상태를 의미합니다. 이는 제어-Z Gate 또는 $N$ Qubit에 대한 다중 제어 일반화를 사용하여 구현합니다. 동작 방식을 이해하기 위해 비트 문자열 {110}의 구체적인 예를 살펴봅시다. $|\psi\rangle = |q_2,q_1,q_0\rangle$ 상태에 작용하여 $|\psi\rangle = |011\rangle$일 때 위상을 적용하는 Circuit을 원합니다(이진 문자열의 순서가 반전된 것은 Qiskit 표기법 때문으로, 최하위 (주로 0번) Qubit이 오른쪽에 위치합니다).

따라서 다음을 수행하는 Circuit $Z_f$가 필요합니다.

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{if} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{if} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

다중 제어 다중 타겟 Gate(MCMTGate)를 사용하면 모든 Qubit에 의해 제어되는 Z Gate를 적용할 수 있습니다(모든 Qubit이 $|1\rangle$ 상태일 때 위상을 반전). 물론 원하는 상태의 일부 Qubit은 $|0\rangle$일 수 있습니다. 따라서 그러한 Qubit에는 먼저 X Gate를 적용하고, 다중 제어 Z Gate를 수행한 후, 다시 X Gate를 적용하여 변경을 되돌려야 합니다. MCMTGate는 다음과 같은 형태입니다.

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

제어 과정에 많은 Qubit이 참여할 수 있지만(여기서는 세 개), 어떤 단일 Qubit도 타겟으로 지정되지 않습니다. 전체 상태가 전반적인 "-" 부호(위상 반전)를 얻기 때문에, 이 Gate는 모든 Qubit에 동등하게 영향을 미칩니다. 이는 단일 제어 Qubit과 단일 타겟 Qubit을 갖는 CX Gate와 같은 다른 다중 Qubit Gate와는 다릅니다.

아래 코드에서는 앞서 설명한 동작을 수행하는 위상 질의 Gate(또는 오라클)를 정의합니다. 이 오라클은 비트 문자열 표현을 통해 정의된 하나 이상의 입력 기저 상태를 표시합니다. MCMT Gate는 다중 제어 Z-Gate를 구현하는 데 사용됩니다.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

이제 특정 "표시된" 상태를 목표로 선택하고 방금 정의한 함수를 적용합니다. 어떤 종류의 Circuit이 생성되었는지 확인해 봅시다.

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Qubit 13이 $|1\rangle$ 상태이고 Qubit 0이 처음에 $|0\rangle$ 상태라면, 첫 번째 X Gate가 Qubit 0을 $|1\rangle$로 반전시켜 모든 Qubit이 $|1\rangle$ 상태가 됩니다. 이 경우 MCMT Gate가 원하는 대로 전반적인 부호 변경 또는 위상 반전을 적용합니다. 그 외의 경우에는 Qubit 13이 $|0\rangle$ 상태이거나 Qubit 0이 $|0\rangle$으로 반전되어 위상 반전이 적용되지 않습니다. 이 Circuit이 실제로 원하는 상태 $|0111\rangle$, 즉 비트 문자열 {1110}을 표시함을 확인할 수 있습니다.

완전한 Grover 연산자는 위상 질의 Gate(오라클), Hadamard 레이어, $Z_\text{OR}$ 연산자로 구성됩니다. 위에서 정의한 오라클로부터 내장 grover_operator를 사용하여 이를 구성할 수 있습니다.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

앞서 언급했듯이, Grover 연산자를 여러 번 적용해야 할 수 있습니다. 노이즈가 없는 경우에 목표 상태의 진폭을 최대화하는 최적 반복 횟수 $t$는 다음 식에서 구할 수 있습니다.

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

여기서 $A_1$은 솔루션 또는 목표 상태의 수입니다. 현대의 노이즈가 있는 양자 컴퓨터에서는 실험적으로 최적인 반복 횟수가 다를 수 있지만, 여기서는 $A_1=1$을 사용하여 이 이론적 최적값을 계산하고 적용합니다.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

이제 모든 가능한 상태의 중첩을 생성하는 초기 Hadamard Gate를 포함하고, 최적 횟수만큼 Grover 연산자를 적용하는 Circuit을 구성해 보겠습니다.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Grover Circuit이 완성되었습니다!

Step 2: Optimize problem for quantum hardware execution

추상적인 양자 Circuit을 정의했지만, 실제로 사용할 양자 컴퓨터에 기본으로 탑재된 Gate로 재작성해야 합니다. 또한 양자 컴퓨터에서 어떤 Qubit을 사용할지 지정해야 합니다. 이러한 이유 등으로 Circuit을 트랜스파일해야 합니다. 먼저 사용할 양자 컴퓨터를 지정합니다.

아래에는 최초 사용 시 자격 증명을 저장하는 코드가 있습니다. 자격 증명을 환경에 저장한 후에는 노트북에서 해당 정보를 삭제하여, 노트북을 공유할 때 자격 증명이 실수로 노출되지 않도록 하세요. 자세한 안내는 IBM Cloud 계정 설정 및 신뢰할 수 없는 환경에서 서비스 초기화를 참고하세요.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

이제 사전 설정된 패스 매니저를 사용하여 선택한 Backend에 맞게 양자 Circuit을 최적화합니다.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

이 시점에서 트랜스파일된 양자 Circuit의 깊이가 상당하다는 점을 짚어 둘 필요가 있습니다.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

이 간단한 경우에도 실제로 꽤 큰 수입니다. 모든 양자 Gate(특히 2-Qubit Gate)는 오류와 노이즈의 영향을 받기 때문에, 100개 이상의 2-Qubit Gate로 이루어진 시퀀스는 Qubit 성능이 매우 뛰어나지 않는 한 노이즈만 남게 됩니다. 실제로 어떻게 동작하는지 살펴봅시다.

Qiskit Primitive를 사용하여 실행

많은 측정을 수행하고 가장 가능성이 높은 상태를 확인하려 합니다. 이러한 진폭 증폭은 Sampler Qiskit Runtime Primitive로 실행하기에 적합한 샘플링 문제입니다.

Qiskit Runtime SamplerV2의 run() 메서드는 PUB(Primitive Unified Block)의 이터러블을 인수로 받습니다. Sampler의 경우 각 PUB는 (circuit, parameter_values) 형식의 이터러블입니다. 하지만 최소한으로는 양자 Circuit의 목록만 있으면 됩니다.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

이 경험을 최대한 활용하려면 IBM Quantum에서 제공하는 실제 양자 컴퓨터에서 실험을 실행하는 것을 강력히 권장합니다. 하지만 QPU 시간을 모두 소진한 경우, 아래 줄의 주석을 해제하여 시뮬레이터로 이 활동을 완료할 수 있습니다.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Step 4: Post-process and return result in desired classical format

이제 샘플링 결과를 히스토그램으로 표시할 수 있습니다.

plot_distribution(dist)

Grover's algorithm이 다른 옵션보다 월등히 높은 확률로, 적어도 한 자릿수 이상 높은 확률로 원하는 상태를 반환했음을 확인할 수 있습니다. 다음 활동에서는 알고리즘을 쿼리 알고리즘의 2인 워크플로에 더 부합하는 방식으로 사용합니다.

이해도 확인

아래 질문을 읽고 답을 생각해 본 후, 삼각형을 클릭하여 해답을 확인하세요.

방금 $2^4=16$개의 가능한 상태 중에서 단일 솔루션을 검색했습니다. Grover 연산자의 최적 반복 횟수를 $t=3$으로 결정했습니다. (a) 여러 솔루션 중 하나를 검색하거나, (b) 더 많은 가능한 상태 공간에서 단일 솔루션을 검색한다면, 이 최적 횟수는 증가했을까요, 감소했을까요?

정답:

솔루션의 수가 전체 솔루션 공간에 비해 작다면, 사인 함수를 작은 각도에서 전개하여 다음을 사용할 수 있음을 상기하세요.

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) 위 식에서 솔루션 상태의 수가 증가하면 반복 횟수는 감소합니다. $\frac{|\mathcal{A}_1|}{N}$ 비율이 여전히 작다면, $t$가 어떻게 감소하는지 다음과 같이 설명할 수 있습니다: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}$.

(b) 가능한 솔루션의 공간($N$)이 커질수록 필요한 반복 횟수는 증가하지만, $t~\sqrt{N}$처럼만 증가합니다.

목표 비트 문자열의 크기를 임의로 늘려도 목표 상태의 확률 진폭이 다른 상태보다 적어도 한 자릿수 이상 높다고 가정해 봅시다. 이것이 Grover's algorithm을 사용하여 목표 상태를 신뢰할 수 있게 찾을 수 있다는 의미일까요?

정답:

아닙니다. 20개의 Qubit으로 첫 번째 활동을 반복하고 num_shots = 10,000번 양자 Circuit을 실행한다고 가정합시다. 균일한 확률 분포라면 모든 상태가 $10,000/2^{20}=0.00954$의 확률로 측정될 것입니다. 목표 상태의 측정 확률이 비솔루션의 10배이고(각 비솔루션의 확률이 그에 따라 약간 감소하면), 목표 상태가 단 한 번이라도 측정될 확률은 약 10%밖에 되지 않습니다. 목표 상태가 여러 번 측정될 가능성은 매우 낮아, 무작위로 얻은 수많은 비솔루션 상태와 구별하기 어렵게 됩니다. 다행히도 오류 억제 및 완화를 사용하면 더 높은 신뢰도의 결과를 얻을 수 있습니다.

활동 2: 정확한 쿼리 알고리즘 워크플로

이 활동은 첫 번째 활동과 동일하게 시작하되, 이번에는 다른 Qiskit 동료와 짝을 이루게 됩니다. 여러분은 비밀 비트 문자열을 선택하고, 파트너는 (일반적으로) 다른 비트 문자열을 선택합니다. 각자 오라클로 작동하는 양자 Circuit을 생성하고 서로 교환합니다. 그런 다음 그 오라클로 Grover's algorithm을 사용하여 파트너의 비밀 비트 문자열을 알아냅니다.

Step 1: 고전적 입력을 양자 문제로 변환하기

위에서 정의한 grover_oracle 함수를 사용하여 하나 이상의 표시 상태(marked state)에 대한 오라클 회로를 구성합니다. 파트너에게 표시한 상태의 수를 알려주어야 합니다. 그래야 파트너가 Grover 연산자를 최적 횟수만큼 적용할 수 있습니다. 비트스트링을 너무 길게 만들지 마세요. 3~5비트 정도면 큰 어려움 없이 동작합니다. 비트스트링이 길어지면 깊이가 깊은 회로가 생성되어 오류 완화(error mitigation)와 같은 고급 기법이 필요합니다.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

이제 목표 상태의 위상(phase)을 반전시키는 양자 회로가 만들어졌습니다. 아래 구문을 사용하여 이 회로를 my_circuit.qpy로 저장할 수 있습니다.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

이 파일을 파트너에게 전송합니다(이메일, 메시징 서비스, 공유 저장소 등 원하는 방법을 사용하세요). 파트너도 자신의 회로를 전송해 달라고 요청하세요. 파일을 쉽게 찾을 수 있는 위치에 저장해 두세요. 파트너의 회로를 받은 후 시각화해 볼 수도 있지만, 이는 쿼리 모델을 깨뜨립니다. 즉, 우리는 오라클을 검사하여 대상 상태를 파악하는 것이 아니라, 오라클을 쿼리(사용)하는 상황을 모델링하고 있습니다.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

파트너에게 인코딩한 목표 상태의 수를 물어보고 아래에 입력합니다.

# Update according to your partner's number of target states.
num_marked_states = 1

이 값은 다음 식에서 최적 Grover 반복 횟수를 결정하는 데 사용됩니다.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

Step 2: 양자 하드웨어 실행을 위한 문제 최적화

이 단계는 이전과 동일하게 진행됩니다.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Step 3: Qiskit 프리미티브를 사용하여 실행하기

이 과정도 첫 번째 활동과 동일합니다.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

Step 4: 후처리 및 원하는 고전적 형식으로 결과 반환하기

이제 샘플링 결과의 히스토그램을 표시합니다. 하나 이상의 상태가 다른 상태보다 측정 확률이 훨씬 높게 나타나야 합니다. 이 결과를 파트너에게 알리고 목표 상태를 올바르게 찾았는지 확인합니다. 기본적으로 표시되는 히스토그램은 첫 번째 활동에서 사용한 회로의 결과입니다. 파트너의 회로에서는 다른 결과가 나와야 합니다.

plot_distribution(dist)

이해도 확인

아래 질문이나 지시 사항을 읽고, 답을 생각해 보거나 파트너와 함께 과정을 이야기해 보세요. 삼각형을 클릭하면 힌트나 제안을 확인할 수 있습니다.

파트너의 목표 상태를 올바르게 찾았을 것입니다. 그렇지 않다면 파트너와 함께 무엇이 잘못되었는지 확인해 보세요. 몇 가지 아이디어를 보려면 아래를 클릭하세요.

힌트:

• 파트너의 회로를 시각화/그려보고 올바르게 불러왔는지 확인하세요.
• 사용된 회로를 비교하고 예상 결과와 실제 결과를 비교해 보세요.
• 비트스트링이 너무 길지 않은지, Grover 반복 횟수가 지나치게 많지 않은지 회로 깊이를 확인하세요.

아직 하지 않았다면 파트너가 보낸 오라클 회로를 그려보세요. 각 Gate의 효과를 설명하고 목표 상태가 무엇인지 논리적으로 설명해 볼 수 있는지 확인해 보세요. 표시 상태가 하나인 경우가 여러 개인 경우보다 훨씬 쉬울 것입니다.

힌트:

• 오라클의 역할은 목표 상태의 부호를 반전시키는 것임을 떠올리세요.
• MCMTGate는 제어에 관여하는 모든 Qubit이 $|1\rangle$ 상태일 때만 부호를 반전시킨다는 점을 기억하세요.
• 목표 상태에서 특정 Qubit이 이미 $|1\rangle$이라면 해당 Qubit에 아무것도 할 필요가 없습니다. 목표 상태에서 특정 Qubit이 $|0\rangle$이고 MCMTGate가 부호를 반전시키도록 하려면, 오라클에서 해당 Qubit에 X Gate를 적용한 뒤 MCMTGate 이후 X Gate를 다시 적용하여 되돌려야 합니다.

Grover 연산자의 반복 횟수를 하나 줄여서 실험을 반복해 보세요. 여전히 정확한 답을 얻을 수 있나요? 그 이유는 무엇인가요?

안내:

아마 정확한 답을 얻을 수 있을 것입니다. 단, 인코딩된 해의 수에 따라 달라질 수 있습니다. 이는 미묘한 점을 드러냅니다. "최적" Grover 반복 횟수는 표시 상태를 측정할 확률을 최대로 만드는 횟수입니다. 하지만 그보다 적은 반복 횟수로도 표시 상태가 다른 상태보다 훨씬 높은 확률을 가질 수 있습니다. 따라서 최적 횟수보다 적게 반복해도 충분할 수 있습니다. 이렇게 하면 회로 깊이가 줄어들어 오류율도 낮아집니다.

여기서 식별된 "최적 횟수"보다 Grover 반복 횟수를 줄이고 싶은 이유는 무엇일까요?

답변:

"최적" Grover 반복 횟수는 노이즈가 없는 환경에서 표시 상태를 측정할 확률을 최대로 만드는 횟수입니다. 하지만 그보다 적은 반복 횟수로도 표시 상태가 다른 상태보다 훨씬 높은 확률을 가질 수 있습니다. 따라서 최적 횟수보다 적게 반복해도 충분할 수 있습니다. 이렇게 하면 회로 깊이가 줄어들어 오류율도 낮아집니다.

Activity 3: 특정 비트스트링 이외의 기준

Grover 알고리즘이 서브루틴으로서 어떻게 유용하게 활용될 수 있는지를 보여주는 마지막 예제로, 비트스트링 표현에서 특정 개수의 1이 포함된 양자 상태가 필요한 상황을 가정해 보겠습니다. 이는 보존 법칙이 관련된 상황에서 흔히 등장합니다. 예를 들어 양자 화학의 맥락에서는, Qubit의 1 상태를 전자 오비탈의 점유 상태로 매핑하는 경우가 많습니다. 전하 보존을 위해서는 1의 총 개수도 일정하게 유지되어야 합니다. 이러한 제약 조건은 매우 흔하기 때문에 특별한 이름이 붙어 있습니다. 바로 **해밍 가중치 제약 조건(Hamming weight constraint)**이며, 상태에 포함된 1의 개수를 **해밍 가중치(Hamming weight)**라고 합니다.

Step 1:

먼저 원하는 해밍 가중치를 가진 상태들을 표시하는 함수를 작성해 보겠습니다. 이 함수는 Qubit의 개수 num_qubits와 목표 해밍 가중치 target_weight가 지정되지 않은 일반적인 형태로 작성합니다.

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

여기서부터 전체 과정은 앞선 두 활동과 동일합니다. 간결함을 위해 Qiskit 패턴 단계는 코드 주석으로만 표시합니다.

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:51,686: Default instance not set. Searching all available instances.

ibm_brisbane

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

여기서 Grover 알고리즘은 해밍 가중치가 2인 상태들이 다른 어떤 상태보다도 측정될 확률이 훨씬 높도록(약 한 자릿수 이상 높게) 준비했습니다.

핵심 개념:

이 모듈에서는 Grover 알고리즘의 주요 특징을 학습했습니다.

• 고전 비구조적 탐색 알고리즘은 탐색 공간의 크기 $N$에 선형으로 비례하는 쿼리 수가 필요한 반면, Grover 알고리즘은 $\sqrt{N}$에 비례하는 쿼리 수만으로 탐색이 가능합니다.
• Grover 알고리즘은 일련의 연산(흔히 "Grover 연산자"라 불림)을 $t$번 반복하며, $t$는 목표 상태가 측정될 확률을 최적화하도록 선택됩니다.
• Grover 알고리즘은 $t$번보다 적게 반복해도 목표 상태의 확률을 증폭시킬 수 있습니다.
• Grover 알고리즘은 쿼리 기반 계산 모델에 적합하며, 한 사람이 탐색을 제어하고 다른 사람이 오라클을 제어/구성하는 상황에서 가장 적합합니다. 또한 다른 양자 계산의 서브루틴으로도 유용하게 활용될 수 있습니다.

문제

참/거짓 문제:

1. 참/거짓: Grover 알고리즘은 비구조적 탐색에서 단일 표시 상태를 찾는 데 필요한 쿼리 수에 있어 고전 알고리즘 대비 지수적 향상을 제공한다.

2. 참/거짓: Grover 알고리즘은 해 상태가 측정될 확률을 반복적으로 증가시키는 방식으로 동작한다.

3. 참/거짓: Grover 연산자를 더 많이 반복할수록 해 상태가 측정될 확률이 높아진다.

객관식 문제:

1. 다음 문장을 가장 잘 완성하는 선택지를 고르세요. 현대 양자 컴퓨터에서 Grover 알고리즘을 성공적으로 활용하기 위한 최선의 전략은 Grover 연산자를...

• a. 한 번만 반복한다.
• b. 해 상태의 확률 진폭을 최대화하기 위해 항상 $t$번 반복한다.
• c. 최대 $t$번 반복하되, 해 상태를 두드러지게 만들기에 더 적은 횟수로도 충분할 수 있다.
• d. 10번 이상 반복한다.

2. 특정 상태에 위상 반전을 표시하는 오라클 역할을 하는 위상 쿼리 Circuit이 아래에 있습니다. 다음 중 이 Circuit에 의해 표시되는 상태는 무엇입니까?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. 128개의 후보 중에서 표시된 상태 3개를 탐색하려고 합니다. 표시된 상태들의 진폭을 최대화하기 위한 Grover 연산자의 최적 반복 횟수는 얼마입니까?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

토론 문제:

1. 양자 오라클에서 어떤 다른 조건을 사용할 수 있을까요? 표시된 비트스트링을 직접 나열하는 방식이 아니라, 비트스트링에 명시하거나 부과하기는 쉬운 조건을 생각해 보세요.

2. 현대 양자 컴퓨터에서 Grover 알고리즘을 확장하는 데 어떤 문제가 있을 수 있는지 떠올릴 수 있나요?