{
"cells": [
{
"cell_type": "markdown",
"id": "e98de65a",
"metadata": {},
"source": [
"---\n",
"title: \"그로버 알고리즘\"\n",
"description: \"그로버 알고리즘이 양자 컴퓨팅을 활용하여 비정형 검색 문제를 해결하는 방법을 알아보세요.\"\n",
"---\n",
"\n",
"{/* cspell:ignore bitstr */}\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "9857bace",
"metadata": {},
"source": [
"\n",
"\n",
"# 그로버 알고리즘\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "5c6854a5",
"metadata": {},
"source": [
"이 교실 내 키스킷 모듈을 사용하려면 학생에게 다음 패키지가 설치된 Python 환경이 있어야 합니다:\n",
"\n",
"* `qiskit` v2.1.0 이상\n",
"* `qiskit-ibm-runtime` v0.40.1 이상\n",
"* `qiskit-aer` v0.17.0 이상\n",
"* `qiskit.visualization`\n",
"* `numpy`\n",
"* `pylatexenc`\n",
"\n",
"위의 패키지를 설정하고 설치하려면 [키스킷 설치](/docs/guides/install-qiskit) 가이드를 참조하세요.\n",
"실제 양자 컴퓨터에서 작업을 실행하려면 학생들은 [IBM Cloud 계정 설정](/docs/guides/cloud-setup) 가이드의 단계에 따라 IBM Quantum®에 계정을 설정해야 합니다.\n",
"\n",
"이 모듈은 테스트를 거쳐 12초의 QPU 시간을 사용했습니다. 이는 선의의 추정치이며 실제 사용량은 다를 수 있습니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e16858b0",
"metadata": {},
"outputs": [],
"source": [
"# Uncomment and modify this line as needed to install dependencies\n",
"#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'"
]
},
{
"cell_type": "markdown",
"id": "e57d1e6b",
"metadata": {},
"source": [
"\n",
"\n",
"## 소개\n",
"\n",
"**Grover의 알고리즘은** *비정형 검색 문제를* 해결하는 기본 양자 알고리즘으로, $N$ 항목 집합과 특정 항목이 원하는 항목인지 확인할 수 있는 방법이 주어질 때 원하는 항목을 얼마나 빨리 찾을 수 있는가 하는 문제를 해결합니다 기존 컴퓨팅에서는 데이터가 정렬되지 않고 악용할 구조가 없는 경우, 가장 좋은 방법은 각 항목을 하나씩 확인하는 것이므로 쿼리 복잡도가 $O(N)$ - 평균적으로 대상을 찾기 전에 약 절반의 항목을 확인해야 합니다.\n",
"\n",
"\n",
"\n",
"1996년 러브 그로버가 소개한 그로버 알고리즘은 양자 컴퓨터가 이 문제를 훨씬 더 효율적으로 해결할 수 있는 방법을 보여주며, $O(\\sqrt{N})$ 단계만 거치면 표시된 항목을 높은 확률로 찾을 수 있습니다. 이는 기존 방식에 비해 *4배의 속도 향상을* 의미하며, 대규모 데이터 세트에 큰 도움이 됩니다.\n",
"\n",
"알고리즘은 다음과 같은 맥락에서 작동합니다:\n",
"\n",
"* **문제 설정:** 원하는 항목이 $x$ 인 경우 1을 반환하고 그렇지 않으면 0을 반환하는 $f(x)$ 함수가 있습니다. 이 기능은 $f(x)$ 을 쿼리해야만 데이터에 대해 알 수 있기 때문에 종종 *오라클* 또는 *블랙박스라고* 불립니다.\n",
"* **퀀텀의 유용성:** 이 문제에 대한 기존 알고리즘은 평균적으로 $N/2$ 쿼리가 필요하지만, Grover의 알고리즘은 대략 $\\pi\\sqrt{N}/4$ 쿼리로 해를 찾을 수 있으며, 이는 대규모 $N$ 의 경우 훨씬 빠릅니다.\n",
"* **작동 방식(개략적인 수준):**\n",
" * 양자 컴퓨터는 먼저 가능한 모든 상태의 *중첩을* 생성하여 가능한 모든 항목을 한 번에 표현합니다.\n",
" * 그런 다음 정답의 확률을 증폭시키고 다른 정답을 감소시키는 일련의 양자 연산(Grover 반복)을 반복적으로 적용합니다.\n",
" * 충분한 반복 끝에 양자 상태를 측정하면 높은 확률로 정답을 얻을 수 있습니다.\n",
"\n",
"다음은 많은 뉘앙스를 생략한 Grover 알고리즘의 아주 기본적인 다이어그램입니다. 자세한 다이어그램은 [이 백서를](https://arxiv.org/pdf/2211.04543) 참조하세요.\n",
"\n",
"\n",
"\n",
"Grover의 알고리즘에 대해 몇 가지 주의할 점이 있습니다:\n",
"\n",
"* 비정형 검색에 최적: $O(\\sqrt{N})$ 쿼리보다 적은 수의 쿼리로 문제를 해결할 수 있는 양자 알고리즘은 없습니다.\n",
"* 다른 양자 알고리즘(예: 쇼의 인수분해 알고리즘)과 달리 기하급수적 속도가 아닌 이차적 속도 향상만 제공합니다.\n",
"* 이는 암호화 시스템에 대한 무차별 암호 대입 공격의 속도를 높일 수 있는 등 실질적인 의미가 있지만, 속도 향상만으로는 대부분의 최신 암호화를 깨기에는 충분하지 않습니다.\n",
"\n",
"기본 컴퓨팅 개념과 쿼리 모델에 익숙한 학부생에게 Grover의 알고리즘은 양자 컴퓨팅이 특정 문제에 대해 어떻게 기존 접근법을 능가할 수 있는지, 심지어 개선이 '단지' 이차적일 때에도 명확한 예시를 제공합니다. 또한 더 발전된 양자 알고리즘과 양자 컴퓨팅의 광범위한 잠재력을 이해하는 관문 역할을 합니다.\n",
"\n",
"진폭 증폭은 범용 양자 알고리즘 또는 하위 루틴으로, 몇 가지 기존 알고리즘보다 4배 빠른 속도를 얻는 데 사용할 수 있습니다. [그로버의 알고리즘은](https://arxiv.org/abs/quant-ph/9605043) 비정형 탐색 문제에서 이러한 속도 향상을 보여준 최초의 알고리즘이었습니다. 그로버의 탐색 문제를 공식화하려면 하나 이상의 계산 기준 상태를 찾고자 하는 상태로 표시하는 오라클 함수와 표시된 상태의 진폭을 증가시켜 결과적으로 나머지 상태를 억제하는 증폭 회로가 필요합니다.\n",
"\n",
"여기서는 그로버 오라클을 구성하는 방법을 설명하고, Qiskit 회로 라이브러리의 `GroverOperator` 기능을 활용하여 그로버 검색 인스턴스를 손쉽게 설정하는 방법을 보여드립니다. IBM Quantum 기본 `Sampler` 함수를 사용하면 Grover 회로를 원활하게 실행할 수 있습니다.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "4f900ae6",
"metadata": {},
"source": [
"\n",
"\n",
"## 이론\n",
"\n",
"이진 문자열을 단일 이진 변수에 매핑하는 $f$ 함수가 있다고 가정해 보겠습니다\n",
"\n",
"$$\n",
"f: \\Sigma^n \\rightarrow \\Sigma\n",
"$$\n",
"\n",
"$\\Sigma^6$ 에 정의된 한 가지 예는 다음과 같습니다\n",
"\n",
"$$\n",
"f(x)= \\begin{cases} 1 \\qquad \\text{if }x=\\{010101\\}\\\\\n",
"0 \\qquad \\text{otherwise }\n",
"\\end{cases}\n",
"$$\n",
"\n",
"$\\Sigma^{2n}$ 에 정의된 또 다른 예는 다음과 같습니다\n",
"\n",
"$$\n",
"f(x)= \\begin{cases} 1 \\qquad \\text{if equal numbers of 1's and 0's in string}\\\\\n",
"0 \\qquad \\text{otherwise }\n",
"\\end{cases}\n",
"$$\n",
"\n",
"여러분은 $f(x)$ 의 $x$ 인수가 1에 매핑된 양자 상태에 해당하는 양자 상태를 찾아야 합니다. 즉, $f(x_1)=1$ (또는 해결책이 없는 경우 신고)이 되도록 $\\{x_1\\}\\in \\Sigma^n$ 을 모두 찾습니다. 솔루션이 아닌 것을 $x_0$ 이라고 합니다. 물론 양자 컴퓨터에서 양자 상태를 사용하여 이 작업을 수행할 것이므로 이러한 이진 문자열을 상태로 표현하는 것이 유용합니다:\n",
"\n",
"$$\n",
"\\{|x_1\\rangle\\} \\in |\\Sigma^n\\rangle\n",
"$$\n",
"\n",
"양자 상태(디랙) 표기법을 사용하여, 가능한 상태 집합 $N=2^n$ 내에서 하나 이상의 특수 상태 $\\{|x_1\\rangle\\}$ 를 찾고 있으며, 여기서 $n$ 는 큐비트의 수이고, 해가 아닌 경우를 $\\{|x_0\\rangle\\}$ 로 표기한다.\n",
"\n",
"함수 $f$ 는 오라클이 제공하는 것으로 생각할 수 있습니다. 즉, 상태 $|x\\rangle$ 에 미치는 영향을 확인하기 위해 쿼리를 보낼 수 있는 블랙박스입니다. 실제로는 이 함수를 알고 있는 경우가 많지만, 구현이 매우 복잡할 수 있으므로 $f$ 에 대한 쿼리나 적용 횟수를 줄이는 것이 중요할 수 있습니다. 또는, 한 사람이 다른 사람이 제어하는 오라클에 쿼리를 보내는 패러다임을 상상해 볼 수 있는데, 이때 우리는 오라클의 함수를 알지 못하고, 쿼리를 통해 특정 상태에 대해 오라클이 취하는 행동만 알 수 있다.\n",
"\n",
"이는 검색에 도움이 되는 $f$ 에 특별한 정보가 없다는 점에서 '구조화되지 않은 검색 문제'입니다. 출력은 정렬되지 않으며 솔루션이 클러스터링되는 것으로 알려져 있지 않습니다. 오래된 종이 전화번호부를 비유로 들어보세요. 이러한 비정형 검색은 알파벳순으로 나열된 이름 목록을 살펴보는 것이 아니라 특정 **숫자를** 찾아 스캔하는 것과 같습니다.\n",
"\n",
"단일 해를 찾는 경우, 일반적으로 $N$ 에 선형적으로 비례하는 수의 쿼리가 필요합니다. 물론 첫 번째 시도에서 해를 찾을 수도 있고, 첫 번째 $N-1$ 번의 추측에서 해를 전혀 찾지 못할 수도 있어, $N^{th}$ 입력값을 조회하여 해가 존재하는지 여부를 확인해야 할 수도 있습니다. 이 함수들은 악용할 수 있는 구조가 없기 때문에, 평균적으로 $N/2$ 번의 추측이 필요합니다. 그로버 알고리즘은 $f$ 에 대한 일정한 횟수의 쿼리 또는 연산을 필요로 하며, 이는 $\\sqrt{N}$ 의 비율로 증가한다.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "a1a51eb6",
"metadata": {},
"source": [
"\n",
"\n",
"### 그로버 알고리즘의 회로 개요\n",
"\n",
"예를 들어, 그로버 알고리즘에 대한 전체 수학적 설명은 IBM 양자 학습에서 John Watrous의 강좌인 [양자 알고리즘의 기초에서](/learning/courses/fundamentals-of-quantum-algorithms) 확인할 수 있습니다. 이 모듈의 마지막에 있는 부록에 요약된 치료법이 제공됩니다. 하지만 지금은 그로버의 알고리즘을 구현하는 양자 회로의 전체적인 구조만 살펴보겠습니다.\n",
"\n",
"Grover의 알고리즘은 다음과 같은 단계로 나눌 수 있습니다:\n",
"\n",
"* 초기 중첩 준비(모든 큐비트에 하다마드 게이트 적용)\n",
"* \"위상 반전으로 대상 상태 '표시하기'\n",
"* 하다마드 게이트와 위상 플립이 **모든** 큐비트에 적용되는 '확산' 단계입니다.\n",
"* 목표 상태 측정 확률을 극대화하기 위해 마킹 및 확산 단계를 반복할 수 있습니다\n",
"* 측정\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "15b9e48c",
"metadata": {},
"source": [
"종종 마킹 게이트 $Z_f$ 와 $H$, $Z_{\\text{OR}}$, $H$ 로 구성된 확산층을 통틀어 “그로버 연산자”라고 부릅니다. 이 도식에서는 그로버 연산자가 단 한 번만 반복된 모습만 표시되어 있습니다.\n",
"\n",
"하다마드 게이트 $H$ 는 잘 알려져 있으며 양자 컴퓨팅 전반에 걸쳐 널리 사용되고 있습니다. 하다마드 게이트는 중첩 상태를 생성합니다. 구체적으로 다음과 같이 정의됩니다\n",
"\n",
"$$\n",
"H|0\\rangle = \\frac{1}{\\sqrt{2}}\\left(|0\\rangle+|1\\rangle\\right)\\\\\n",
"H|1\\rangle = \\frac{1}{\\sqrt{2}}\\left(|0\\rangle-|1\\rangle\\right)\n",
"$$\n",
"\n",
"다른 상태에 대한 이 연산의 작용은 선형성을 통해 정의된다.\n",
"특히, 하다마르 게이트(Hadamard gates) 층을 활용하면 모든 큐비트가 $|0\\rangle$ 에 있는 초기 상태( $|0\\rangle^{\\otimes n}$ 로 표기)에서, 각 큐비트가 $|0\\rangle$ 또는 $|1\\rangle$ 중 하나로 측정될 확률을 갖는 상태로 전환할 수 있습니다. 이를 통해 고전적 컴퓨팅과는 다른 방식으로 모든 가능한 상태의 공간을 탐색할 수 있습니다.\n",
"\n",
"하다마드 게이트의 중요한 추론적 특성은 두 번째로 행동하면 이러한 중첩 상태를 되돌릴 수 있다는 것입니다:\n",
"\n",
"$$\n",
"H\\frac{1}{\\sqrt{2}}\\left(|0\\rangle+|1\\rangle\\right)=|0\\rangle\\\\\n",
"H\\frac{1}{\\sqrt{2}}\\left(|0\\rangle-|1\\rangle\\right)=|1\\rangle\n",
"$$\n",
"\n",
"잠시만 기다려주세요.\n",
"\n",
"\n",
"\n",
"#### 이해도 점검\n",
"\n",
"하다마드 게이트의 정의에서 시작하여, 하다마드 게이트를 두 번째로 적용하면 위에서 주장한 것과 같은 중첩이 취소됨을 증명합니다.\n",
"\n",
"\n",
" \n",
" $H$ 를 $|+\\rangle$ 및 $|+\\rangle$ 상태에 적용하면 다음과 같은 결과가 나옵니다:\n",
"\n",
" $$\n",
" H\\frac{1}{\\sqrt{2}}\\left(|0\\rangle+|1\\rangle\\right)=\\frac{1}{2}\\left((|0\\rangle+|1\\rangle)+(|0\\rangle-|1\\rangle)\\right)=|0\\rangle\\\\\n",
" H\\frac{1}{\\sqrt{2}}\\left(|0\\rangle-|1\\rangle\\right)=\\frac{1}{2}\\left((|0\\rangle+|1\\rangle)-(|0\\rangle-|1\\rangle)\\right)=|1\\rangle.\n",
" $$\n",
" \n",
"\n",
"\n",
"$Z_\\text{OR}$ 게이트는 덜 일반적이며 다음에 따라 정의됩니다\n",
"\n",
"$$\n",
"\\text{Z}_\\text{OR}|x\\rangle = \\begin{cases}\n",
"|x\\rangle & \\text{if } x = 0^n \\\\\n",
" -|x\\rangle & \\text{if } x \\neq 0^n\n",
"\\end{cases}\n",
"\\qquad \\forall x \\in \\Sigma^n\n",
"$$\n",
"\n",
"마지막으로 $Z_f$ 게이트는 다음과 같이 정의됩니다\n",
"\n",
"$$\n",
"Z_f:|x\\rangle \\rightarrow (-1)^{f(x)}|x\\rangle \\qquad \\forall x \\in \\Sigma^n\n",
"$$\n",
"\n",
"$Z_f$ 이 경우 $f(x) = 1$ 대상 상태의 부호가 뒤집히고 다른 상태는 영향을 받지 않는다는 점에 유의하세요.\n",
"\n",
"매우 높고 추상적인 수준에서 회로의 단계를 다음과 같은 방식으로 생각할 수 있습니다:\n",
"\n",
"* 첫 번째 하다마드 레이어: 큐비트를 가능한 모든 상태의 중첩에 넣습니다.\n",
"* $Z_f$ 앞에 \"-\" 기호를 추가하여 대상 상태를 표시합니다. 이렇게 하면 측정 확률이 즉시 변경되지는 않지만 후속 단계에서 대상 상태가 작동하는 방식이 변경됩니다.\n",
"* 또 다른 하다마르 층: 이전 단계에서 도입된 “-” 기호는 일부 항들 간의 상대적 부호를 바꾸게 됩니다. 하다마르 게이트는 하나의 계산 상태 혼합 $(|0\\rangle+|1\\rangle)/\\sqrt{2}$ 을 하나의 계산 상태 $|0\\rangle$ 로 변환하고, $(|0\\rangle-|1\\rangle)/\\sqrt{2}$ 을 $|1\\rangle$ 로 변환하기 때문에, 이러한 상대적 부호 차이가 어떤 상태가 측정되는지에 영향을 미치기 시작할 수 있다.\n",
"* 마지막 한 층의 하다마드 게이트를 적용한 다음 측정이 이루어집니다.\n",
" 다음 섹션에서 이 기능이 어떻게 작동하는지 자세히 살펴보겠습니다.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "bf41c02c",
"metadata": {},
"source": [
"\n",
"\n",
"### 예\n",
"\n",
"Grover의 알고리즘이 어떻게 작동하는지 더 잘 이해하기 위해 2쿼트짜리 작은 예제를 살펴보겠습니다. 양자역학 및 디랙 표기법에 관심이 없는 분들에게는 선택 사항으로 간주할 수 있습니다. 하지만 양자 컴퓨터로 실질적인 작업을 하고자 하는 분들께는 이 방법을 적극 권장합니다.\n",
"\n",
"다음은 양자 상태가 전체적으로 다양한 위치에 표시된 회로도입니다. 큐비트가 두 개뿐이므로 어떤 상황에서도 측정할 수 있는 가능한 상태는 네 가지뿐이라는 점에 유의하세요: $|00\\rangle$, $|01\\rangle$, $|10\\rangle$, $|11\\rangle$ 입니다.\n",
"\n",
"\n",
"\n",
"오라클( $Z_f$, 알 수 없음)이 $|01\\rangle$ 상태를 표시한다고 가정해 보겠습니다. 오라클을 포함한 각 양자 게이트 세트의 동작을 살펴보고 측정 시 가능한 상태의 분포가 어떤 식으로 나오는지 살펴볼 것입니다.\n",
"처음에 우리는\n",
"\n",
"$$\n",
"|\\psi_0\\rangle = |00\\rangle\n",
"$$\n",
"\n",
"하다마드 게이트의 정의를 사용하면 다음과 같습니다\n",
"\n",
"$$\n",
"|\\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)\n",
"$$\n",
"\n",
"이제 오라클이 대상 상태를 표시합니다:\n",
"\n",
"$$\n",
"|\\psi_2\\rangle = \\frac{1}{2}\\left(|00\\rangle-|01\\rangle+|10\\rangle+|11\\rangle\\right)\n",
"$$\n",
"\n",
"이 상태에서는 네 가지 가능한 결과 모두 측정될 확률이 동일하다는 점에 유의하십시오. 이들 모두의 가중치는 $1/2$ 의 크기이며, 이는 각각 측정될 확률이 $|1/2|^2=1/4$ 임을 의미합니다. 따라서 상태 $|01\\rangle$ 가 “-” 단계를 거치고 있지만, 아직까지 해당 상태를 관측할 확률이 높아지지는 않았습니다. 이어서 다음 단계의 하다마르 게이트를 적용합니다.\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"|\\psi_3\\rangle = &\\frac{1}{4}\\left(|00\\rangle+|01\\rangle+|10\\rangle+|11\\rangle\\right)\\\\\n",
"-&\\frac{1}{4}\\left(|00\\rangle-|01\\rangle+|10\\rangle-|11\\rangle\\right)\\\\\n",
"+&\\frac{1}{4}\\left(|00\\rangle+|01\\rangle-|10\\rangle-|11\\rangle\\right)\\\\\n",
"+&\\frac{1}{4}\\left(|00\\rangle-|01\\rangle-|10\\rangle+|11\\rangle\\right)\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"유사한 용어를 결합하면 다음과 같은 결과를 얻을 수 있습니다\n",
"\n",
"$$\n",
"|\\psi_3\\rangle = \\frac{1}{2}\\left(|00\\rangle+|01\\rangle-|10\\rangle+|11\\rangle\\right)\n",
"$$\n",
"\n",
"이제 $Z_{\\text{OR}}$ 은 $|00\\rangle$ 을 제외한 모든 주에서 기호를 뒤집습니다:\n",
"\n",
"$$\n",
"|\\psi_4\\rangle = \\frac{1}{2}\\left(|00\\rangle-|01\\rangle+|10\\rangle-|11\\rangle\\right)\n",
"$$\n",
"\n",
"마지막으로 하다마드 게이트의 마지막 레이어를 적용합니다:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"|\\psi_5\\rangle =&\\frac{1}{4}\\left(|00\\rangle+|01\\rangle+|10\\rangle+|11\\rangle\\right)\\\\\n",
"-&\\frac{1}{4}\\left(|00\\rangle-|01\\rangle+|10\\rangle-|11\\rangle\\right)\\\\\n",
"+&\\frac{1}{4}\\left(|00\\rangle+|01\\rangle-|10\\rangle-|11\\rangle\\right)\\\\\n",
"-&\\frac{1}{4}\\left(|00\\rangle-|01\\rangle-|10\\rangle+|11\\rangle\\right)\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"이러한 용어의 조합을 통해 결과를 실제로 확신할 수 있도록 노력할 가치가 있습니다:\n",
"\n",
"$$\n",
"|\\psi_5\\rangle =|01\\rangle\n",
"$$\n",
"\n",
"즉, $|01\\rangle$ 을 측정할 확률은 100%(노이즈와 오류가 없는 경우)이고 다른 상태를 측정할 확률은 0입니다.\n",
"\n",
"이 2쿼트 예시는 특히 깨끗한 사례로, Grover의 알고리즘이 항상 100%의 확률로 목표 상태를 측정하는 것은 아닙니다. 오히려 목표 상태를 측정할 확률을 증폭시킬 수 있습니다. 또한 그로버 연산자를 두 번 이상 반복해야 할 수도 있습니다.\n",
"\n",
"다음 섹션에서는 실제 IBM® 양자 컴퓨터를 사용하여 이 알고리즘을 실습해 보겠습니다.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "geo_picture_01",
"metadata": {},
"source": [
"\n",
"\n",
"### 기하학적 그림\n",
"\n",
"위의 2큐비트 예시는 간단한 경우에 대수 연산이 어떻게 이루어지는지 보여주었지만, 그로버 알고리즘을 이해하는 훨씬 더 직관적인 방법이 있습니다. 바로 2차원 평면에서의 일련의 기하학적 대칭 반사로 보는 것입니다. 아래에서 이 그림에 대해 설명합니다. 자세한 내용은 존 왓루스(John Watrous)의 [‘양자 알고리즘의 기초(Fundamentals of Quantum Algorithms)’](/learning/courses/fundamentals-of-quantum-algorithms/grover-algorithm/analysis) 강좌를 참고하시기 바랍니다.\n",
"\n",
"**비행기 준비하기.** 초기 중첩 상태 $|\\psi\\rangle$ 를 두 개의 성분으로 분해할 수 있다. 우리가 찾고 있는 올바른 상태를 ‘ $|A_1\\rangle$ ’라고 부릅니다. 그 외의 모든 상태를 통틀어 ‘ $|A_0\\rangle$ ’라고 부릅니다. 정의상 ‘ $|A_1\\rangle$ ’와 ‘ $|A_0\\rangle$ ’는 서로 직교하므로, 추상적인 2차원 공간에서 이 두 축을 수직으로 그릴 수 있습니다. $|\\psi\\rangle$ 는 이 두 성분의 선형 조합이므로, $|A_0\\rangle$ 축과 $\\theta$ 라는 작은 각도를 이루며, 이는 $|A_0\\rangle$ 에 가깝습니다. 왜냐하면 초기에는 상태의 극히 일부만이 올바른 성분 $|A_1\\rangle$ 에 속해 있기 때문입니다.\n",
"\n",
"**반추.** 우리가 필요로 하는 핵심적인 수학적 사실은 다음과 같은 형태의 연산자가\n",
"\n",
"$$\n",
"2|v\\rangle\\langle v| - I\n",
"$$\n",
"\n",
"$|v\\rangle$ 로 정의된 축에 대한 모든 상태를 반영합니다. 그 이유를 알아보기 위해 두 가지 경우를 생각해 봅시다. $|v\\rangle$ 를 따라 있는 상태는 변하지 않으며, $|v\\rangle$ 에 수직인 상태는 부호가 반전됩니다. 다른 모든 상태는 이 두 가지 성분으로 분해될 수 있으며, 연산자는 각 성분에 그에 따라 작용합니다. 이는 정확히 $|v\\rangle$ 에 대한 대칭입니다.\n",
"\n",
"알고 보니 그로버 알고리즘의 오라클 단계와 확산 단계 모두 이 기하학적 그림에서 대칭 반사로 표현될 수 있다.\n",
"\n",
"**반영으로서의 오라클.** 오라클은 $|A_1\\rangle$ 상태의 부호를 반전시키고, 그 외의 모든 것은 그대로 둡니다. 이는 $|A_0\\rangle$ 축에 대한 반사와 같습니다.\n",
"\n",
"\n",
"\n",
"**반영으로서의 확산.** 확산 연산자가 어떻게 대칭 연산자이기도 한지 파악하는 것은 조금 더 까다롭습니다. 확산 연산자는\n",
"\n",
"$$\n",
"H^{\\otimes n}\\, Z_{\\text{OR}}\\, H^{\\otimes n}\n",
"$$\n",
"\n",
"$Z_{\\text{OR}}$ 이는 $|0\\rangle^{\\otimes n}$ 가 아닌 모든 상태의 부호를 반전시키기 때문에, 그 자체로 ‘전부 0인 상태’에 대한 대칭 변환입니다. 이를 $2|0\\rangle\\langle 0| - I$ 로 표현할 수 있습니다. 주변의 하다마르 층들은 실질적으로 기저 변환을 수행하여 대칭축을 변환합니다. $H^{\\otimes n}$ 는 $|0\\rangle^{\\otimes n}$ 를 균일 중첩 $|u\\rangle = \\frac{1}{\\sqrt{N}}\\sum_{x}|x\\rangle$ 로 매핑한다는 점을 상기하자. 하다마드 연산자는 자기 역연산자이므로, 전체 식은 다음과 같이 된다\n",
"\n",
"$$\n",
"H^{\\otimes n}\\left(2|0\\rangle\\langle 0| - I\\right)H^{\\otimes n} = 2|u\\rangle\\langle u| - I\n",
"$$\n",
"\n",
"이는 $|u\\rangle$ 에 대한 반사입니다. $|u\\rangle$ 는 $|\\psi\\rangle$ 와 매우 가깝기 때문에(둘 다 $|A_0\\rangle$ 와 거의 일직선상에 있음), 이 두 번째 반사는 상태를 시작점으로부터 $2\\theta$ 의 각도로 이동시킵니다.\n",
"\n",
"\n",
"\n",
"**$2\\theta$ 에 의한 회전.** 이 두 반사의 복합 효과는 $2\\theta$ 방향으로 $|A_1\\rangle$ 쪽으로 회전하는 것입니다. 그로버 연산자를 반복할 때마다 상태는 $2\\theta$ 만큼 추가로 회전합니다.\n",
"\n",
"**최적의 반복 횟수.** 우리의 목표는 상태를 $|A_1\\rangle$ 에 최대한 가깝게 회전시키는 것이며, 이는 총 약 $\\pi/2$ 라디안(4분의 1 바퀴)만큼 회전하는 것을 의미합니다. 각 반복이 $2\\theta$ 를 기여한다면, 최적 반복 횟수 $t$ 는 다음 조건을 만족한다\n",
"\n",
"$$\n",
"(2t + 1)\\theta \\approx \\frac{\\pi}{2}\n",
"$$\n",
"\n",
"$N$ 조건 하에서 단일 해를 구하려면, 초기 각도는 $\\theta \\approx \\sin^{-1}(1/\\sqrt{N}) \\approx 1/\\sqrt{N}$ ( $N$ 가 충분히 클 때)이다. 대입하면,\n",
"\n",
"$$\n",
"t \\approx \\frac{\\pi}{4}\\sqrt{N} - \\frac{1}{2}\n",
"$$\n",
"\n",
"바로 여기서 유명한 ‘ $\\sqrt{N}$ ’의 속도 향상 효과가 비롯됩니다. 즉, 목표 지점에 도달하기 위해 고전적인 탐색 방식에서 필요한 $O(N)$ 번의 확인 대신, $O(\\sqrt{N})$ 번의 반복만으로도 충분합니다.\n",
"\n",
"보다 일반적으로, 총 $N$ 개의 상태 중 $|A_1|$ 개의 해 상태가 존재한다면, 최적의 반복 횟수는\n",
"\n",
"$$\n",
"t \\approx \\frac{\\pi}{4}\\sqrt{\\frac{N}{|A_1|}} - \\frac{1}{2}\n",
"$$\n",
"\n",
"반복 횟수를 너무 많이 설정하면 극한( $|A_1\\rangle$ )을 지나치게 되어, 목표 상태를 찾을 확률이 다시 줄어들기 시작한다는 점에 유의하십시오. 적절한 반복 횟수를 찾는 것이 중요하지만, 잡음이 많은 양자 하드웨어에서는 실험적으로 최적의 횟수가 이 이상적인 공식과 다를 수 있다.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "3fd8fbb3",
"metadata": {},
"source": [
"\n",
"\n",
"### 그로버 알고리즘은 왜 유용한가요?\n",
"\n",
"이쯤 되면 이런 의문이 들 수도 있습니다. 방금 목표 상태를 표시하는 오라클을 만들었지만, 이를 만들기 위해서는 애초에 목표 상태를 알고 있어야 했으니까요. 그럼 우리가 실제로 찾고 있는 것은 무엇일까요?\n",
"\n",
"이건 타당한 질문이며, 몇 가지 훌륭한 답변이 있습니다.\n",
"\n",
"* **쿼리 모델은 이론적 도구입니다.** 계산 쿼리 모델은 애초에 직접적인 실용성을 목적으로 설계된 적이 없다. 이 개념의 목적은 문제를 ‘오라클’과 ‘그 외의 모든 요소’라는 두 부분으로 나누어, 알고리즘의 복잡도를 체계적으로 분석할 수 있는 방법을 제공하는 데 있습니다. 신원 확인이 무료라는 점을 감안할 때, 검색이 얼마나 어려운가요? 쿼리 수는 입력 데이터의 크기에 따라 어떻게 변화하나요? 비록 실제로 이런 식으로 작동하는 시스템은 없더라도, 이 질문들은 유용합니다.\n",
"\n",
"* 이것을 **두 사람이 참여하는** 활동으로 생각할 수도 있습니다. 한 사람은 목표 상태를 알고 오라클을 구축하며, 다른 한 사람은 오라클을 블랙박스처럼 사용하여 내부를 들여다보지 않고 정답을 찾아내는 역할을 맡습니다. 아래의 활동 2에서는 파트너와 함께 바로 이 작업을 수행하게 됩니다.\n",
"\n",
"* **진폭 증폭은 폭넓게 활용되는 서브루틴입니다.** 비록 이 첫 번째 시연이 순환적인 것처럼 보일지라도, *‘진폭 증폭’이라* 불리는 그 근본적인 메커니즘은 양자 컴퓨팅 분야에서 끊임없이 등장합니다. 우리가 여기서 실제로 구축하고 있는 것은, 훨씬 더 복잡한 양자 알고리즘들에서 서브루틴 형태로 등장하는 도구에 대한 직관입니다.\n",
"\n",
"* **정답을 알지 못해도 오라클을 구축할 수 있는 문제들이 있습니다.** 핵심적인 통찰은, 해결책을 *찾* 기는 매우 어렵지만 주어진 해결책이 올바른지 *확인하는* 것은 매우 쉬운 문제들이 한 부류로 존재한다는 점이다. 팩토링이 그 예입니다. 두 개의 큰 소수의 곱이 주어졌을 때, 그 소수들이 무엇인지 알아내는 것은 매우 어렵지만, 일단 그 소수들을 알게 되면 서로 곱해 봄으로써 쉽게 확인할 수 있습니다. (특히 인수분해에 있어서는 그로버의 알고리즘보다 더 나은 알고리즘이 있습니다 — 쇼어의 알고리즘을 참고하세요 — 하지만 이것이 이 기능의 유일한 문제점은 결코 아닙니다.) 스도쿠, 제약 만족 문제, 심지어 고전 게임인 지뢰 찾기까지 모두 풀기는 어렵지만 정답 여부를 확인하기는 쉬운 문제들입니다.\n",
"\n",
"그게 왜 중요한가요? 이는 우리가 해답 자체는 알지 못하더라도, 해답이 충족해야 할 모든 *조건*\\* 과\\* 요건을 파악할 수 있으며, 이러한 요건들을 오라클 역할을 하는 양자 회로에 구현할 수 있음을 의미합니다. 그로버 알고리즘이 그 해답을 찾아줄 것입니다.\n",
"\n",
"이러한 점을 염두에 두고 몇 가지 예시를 살펴보겠습니다. 알고리즘의 논리를 쉽게 이해할 수 있도록, 먼저 해의 상태가 명확하게 지정된 예제로 시작하겠습니다. 이어서 두 사람이 함께 하는 활동으로 넘어가고, 마지막으로 정답에 대한 지식이 아닌 문제의 제약 조건을 바탕으로 오라클을 구축하는 예시를 살펴보겠습니다.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "90cfe463",
"metadata": {},
"source": [
"\n",
"\n",
"### 일반 수입 및 접근 방식\n",
"\n",
"먼저 필요한 몇 가지 패키지를 가져오는 것으로 시작합니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "27a7cc58",
"metadata": {},
"outputs": [],
"source": [
"# Built-in modules\n",
"import math\n",
"\n",
"# Imports from Qiskit\n",
"from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister\n",
"from qiskit.circuit.library import grover_operator, MCMTGate, ZGate\n",
"from qiskit.visualization import plot_distribution\n",
"from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager"
]
},
{
"cell_type": "markdown",
"id": "0d5be4ca",
"metadata": {},
"source": [
"이 튜토리얼과 다른 튜토리얼에서는 워크플로우를 다음 단계로 나누는 \"키스킷 패턴\"이라는 양자 컴퓨팅 프레임워크를 사용합니다:\n",
"\n",
"* 1단계: 기존 입력을 양자 문제에 매핑하기\n",
"* 2단계: 양자 실행을 위한 문제 최적화\n",
"* 3단계: IBM Quantum 기본 함수를 사용하여 실행하기\n",
"* 4단계: 후처리 및 고전적 분석\n",
"\n",
"당사는 일반적으로 이러한 단계를 따르지만, 항상 명시적으로 표시하지는 않습니다.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "5e1d0a46",
"metadata": {},
"source": [
"\n",
"\n",
"## 활동 1: 단일 주어진 목표 상태 찾기\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "23b5217f",
"metadata": {},
"source": [
"\n",
"\n",
"### 1단계: 고전적 입력을 양자 문제에 매핑하기\n",
"\n",
"솔루션 상태에는 전체 페이즈 (-1) 를 설정하고 비솔루션 상태에는 영향을 주지 않는 페이즈 쿼리 게이트가 필요합니다. 이를 다른 말로 표현하면 Grover의 알고리즘에는 하나 이상의 표시된 계산 기준 상태를 지정하는 오라클이 필요하며, 여기서 \"표시된\"은 위상이 -1 인 상태를 의미합니다. 이는 제어된 Z 게이트 또는 $N$ 큐비트를 통한 다중 제어 일반화를 사용하여 수행됩니다. 이것이 어떻게 작동하는지 알아보려면 비트 문자열의 구체적인 예시 `{110}` 를 살펴보세요. 상태 $|\\psi\\rangle = |q_2,q_1,q_0\\rangle$ 에 대해 동작하고 $|\\psi\\rangle = |011\\rangle$ 경우 위상을 적용하는 회로가 필요합니다(여기서 이진 문자열의 순서를 뒤집은 이유는 가장 중요하지 않은(보통 0) 큐비트를 오른쪽에 배치하는 키스킷의 표기법 때문입니다).\n",
"\n",
"따라서 다음을 수행하는 $Z_f$ 회로가 필요합니다\n",
"\n",
"$$\n",
"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}\n",
"$$\n",
"\n",
"다중 제어 다중 타겟 게이트(`MCMTGate`)를 사용하여 모든 큐비트에 의해 제어되는 Z 게이트를 적용할 수 있습니다(모든 큐비트가 $|1\\rangle$ 상태인 경우 위상 반전). 물론 우리가 원하는 상태의 큐비트 중 일부는 $|0\\rangle$ 일 수 있습니다. 따라서 이러한 큐비트에 대해서는 먼저 X 게이트를 적용한 다음 곱셈 제어 Z 게이트를 수행한 다음 다른 X 게이트를 적용하여 변경 사항을 취소해야 합니다. `MCMTGate` 은 다음과 같습니다:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 23,
"id": "66aeceae",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mcmt_ex = QuantumCircuit(3)\n",
"mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)\n",
"mcmt_ex.draw(output=\"mpl\", style=\"iqp\")"
]
},
{
"cell_type": "markdown",
"id": "03b992b2",
"metadata": {},
"source": [
"제어 프로세스에는 많은 큐비트가 관여할 수 있지만(여기서는 3개의 큐비트), 단일 큐비트가 타깃으로 표시되지는 않는다는 점에 유의하세요. 이는 게이트가 모든 큐비트에 동등하게 영향을 미치는 전체 상태의 \"-\" 기호(위상 플립)를 얻기 때문입니다. 이는 단일 제어 큐비트와 단일 타겟 큐비트를 가진 `CX` 게이트와 같은 다른 많은 다중 큐비트 게이트와 다릅니다.\n",
"\n",
"다음 코드에서는 위상 쿼리 게이트(또는 오라클)를 정의하여 방금 설명한 대로 비트스트링 표현을 통해 정의된 하나 이상의 입력 기준 상태를 표시합니다. MCMT 게이트는 다중 제어 Z 게이트를 구현하는 데 사용됩니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "53f8763f",
"metadata": {},
"outputs": [],
"source": [
"def grover_oracle(marked_states):\n",
" \"\"\"Build a Grover oracle for multiple marked states\n",
"\n",
" Here we assume all input marked states have the same number of bits\n",
"\n",
" Parameters:\n",
" marked_states (str or list): Marked states of oracle\n",
"\n",
" Returns:\n",
" QuantumCircuit: Quantum circuit representing Grover oracle\n",
" \"\"\"\n",
" if not isinstance(marked_states, list):\n",
" marked_states = [marked_states]\n",
" # Compute the number of qubits in circuit\n",
" num_qubits = len(marked_states[0])\n",
"\n",
" qc = QuantumCircuit(num_qubits)\n",
" # Mark each target state in the input list\n",
" for target in marked_states:\n",
" # Flip target bitstring to match Qiskit bit-ordering\n",
" rev_target = target[::-1]\n",
" # Find the indices of all the '0' elements in bitstring\n",
" zero_inds = [\n",
" ind for ind in range(num_qubits) if rev_target.startswith(\"0\", ind)\n",
" ]\n",
" # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)\n",
" # where the target bitstring has a '0' entry\n",
" qc.x(zero_inds)\n",
" qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)\n",
" qc.x(zero_inds)\n",
" return qc"
]
},
{
"cell_type": "markdown",
"id": "7349dd38",
"metadata": {},
"source": [
"이제 특정 '표시된' 상태를 타깃으로 선택하고 방금 정의한 함수를 적용합니다. 어떤 종류의 회로가 생성되었는지 살펴보겠습니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "6cb8ce21",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"marked_states = [\"1110\"]\n",
"oracle = grover_oracle(marked_states)\n",
"oracle.draw(output=\"mpl\", style=\"iqp\")"
]
},
{
"cell_type": "markdown",
"id": "5632a1dd",
"metadata": {},
"source": [
"큐비트 1~~3이 $|1\\rangle$ 상태에 있고, 큐비트 0이 처음에 $|0\\rangle$ 상태에 있다면, 첫 번째 X 게이트는 큐비트 0을 $|1\\rangle$ 상태로 반전시키고 모든 큐비트는 $|1\\rangle$ 상태가 됩니다. 이는 MCMT 게이트가 원하는 대로 전체적인 부호 변경 또는 위상 반전을 적용함을 의미합니다. 그 외의 모든 경우에는, 큐비트 1~~3이 $|0\\rangle$ 상태에 있거나, 큐비트 0이 $|0\\rangle$ 상태로 반전된 상태이며, 위상 반전 연산은 적용되지 않습니다. 이 회로가 실제로 우리가 원하는 상태 $|0111\\rangle$ 또는 비트열을 나타낸다는 것을 알 수 있습니다 `{1110}`.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "4cbe89d3",
"metadata": {},
"source": [
"전체 Grover 연산자는 위상 쿼리 게이트(오라클), 하다마드 레이어, $Z_\\text{OR}$ 연산자로 구성됩니다. 기본 제공 `grover_operator` 을 사용하여 위에서 정의한 오라클에서 이를 구성할 수 있습니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "9426f7a5",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grover_op = grover_operator(oracle)\n",
"grover_op.decompose(reps=0).draw(output=\"mpl\", style=\"iqp\")"
]
},
{
"cell_type": "markdown",
"id": "fb293e00",
"metadata": {},
"source": [
"앞서 살펴본 기하학적 그림에서 논의했듯이, 그로버 연산자를 여러 번 적용해야 할 수도 있습니다. 잡음이 없는 상황에서 목표 상태의 진폭을 최대화하기 위한 최적 반복 횟수 $t$ 는 다음과 같습니다\n",
"\n",
"$$\n",
"t\\approx \\frac{\\pi}{4} \\sqrt{\\frac{N}{|A_1|}}-\\frac{1}{2}\n",
"$$\n",
"\n",
"여기서 $|A_1|$ 는 해의 상태 수이며, $N=2^n$ 는 전체 상태 수이다. 현대적인 잡음이 많은 양자 컴퓨터에서는 실험적으로 도출된 최적 반복 횟수가 다를 수 있지만, 여기서는 $|A_1|=1$ 를 사용하여 이 이론적 최적 횟수를 계산하고 적용합니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d07c701a",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3\n"
]
}
],
"source": [
"optimal_num_iterations = math.floor(\n",
" math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n",
")\n",
"print(optimal_num_iterations)"
]
},
{
"cell_type": "markdown",
"id": "4698589c",
"metadata": {},
"source": [
"이제 초기 하다마드 게이트를 포함하는 회로를 구성하여 가능한 모든 상태의 중첩을 생성하고 그로버 연산자를 최적의 횟수만큼 적용해 보겠습니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "63006e25",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"qc = QuantumCircuit(grover_op.num_qubits)\n",
"# Create even superposition of all basis states\n",
"qc.h(range(grover_op.num_qubits))\n",
"# Apply Grover operator the optimal number of times\n",
"qc.compose(grover_op.power(optimal_num_iterations), inplace=True)\n",
"# Measure all qubits\n",
"qc.measure_all()\n",
"qc.draw(output=\"mpl\", style=\"iqp\")"
]
},
{
"cell_type": "markdown",
"id": "f14e6ebd",
"metadata": {},
"source": [
"그로버 서킷을 구축했습니다!\n",
"\n",
"\n",
"\n",
"### 2단계: 양자 하드웨어 실행을 위한 문제 최적화\n",
"\n",
"추상적인 양자 회로를 정의했지만, 실제로 사용하고자 하는 양자 컴퓨터의 고유한 게이트의 관점에서 다시 작성해야 합니다. 또한 양자 컴퓨터에서 어떤 큐비트를 사용해야 하는지 지정해야 합니다. 이러한 이유와 다른 이유들로 인해 이제 우리는 회로를 투명화해야 합니다. 먼저 사용하고자 하는 양자 컴퓨터를 지정해 보겠습니다.\n",
"\n",
"처음 사용할 때 자격 증명을 저장하는 코드는 아래에 있습니다. 노트북을 공유할 때 실수로 자격 증명이 공유되지 않도록 노트북을 환경에 저장한 후 이 정보를 노트북에서 삭제해야 합니다. 자세한 안내는 [IBM Cloud 계정 설정하기](/docs/guides/initialize-account) 및 [신뢰할 수 없는 환경에서 서비스 초기화를](/docs/guides/cloud-setup-untrusted) 참조하세요.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "994ef054",
"metadata": {},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.\n"
]
},
{
"data": {
"text/plain": [
"'ibm_brisbane'"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# To run on hardware, select the backend with the fewest number of jobs in the queue\n",
"from qiskit_ibm_runtime import QiskitRuntimeService\n",
"\n",
"# Syntax for first saving your token. Delete these lines after saving your credentials.\n",
"\n",
"# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',\n",
"# instance = '', token='', overwrite=True, set_as_default=True)\n",
"# service = QiskitRuntimeService(channel='ibm_quantum_platform')\n",
"\n",
"# Load saved credentials\n",
"service = QiskitRuntimeService()\n",
"\n",
"backend = service.least_busy(operational=True, simulator=False)\n",
"backend.name"
]
},
{
"cell_type": "markdown",
"id": "a65cf945",
"metadata": {},
"source": [
"이제 사전 설정된 패스 관리자를 사용하여 선택한 백엔드에 맞게 양자 회로를 최적화합니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 171,
"id": "35fbd6ef",
"metadata": {},
"outputs": [],
"source": [
"target = backend.target\n",
"pm = generate_preset_pass_manager(target=target, optimization_level=3)\n",
"\n",
"circuit_isa = pm.run(qc)\n",
"# The transpiled circuit will be very large. Only draw it if you are really curious.\n",
"# circuit_isa.draw(output=\"mpl\", idle_wires=False, style=\"iqp\")"
]
},
{
"cell_type": "markdown",
"id": "014b7868",
"metadata": {},
"source": [
"이 때 주목할 점은 트랜스파일된 양자 회로의 깊이가 상당하다는 점입니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 172,
"id": "d168576f",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The total depth is 439\n",
"The depth of two-qubit gates is 113\n"
]
}
],
"source": [
"print(\"The total depth is \", circuit_isa.depth())\n",
"print(\n",
" \"The depth of two-qubit gates is \",\n",
" circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),\n",
")"
]
},
{
"cell_type": "markdown",
"id": "aaea2d8d",
"metadata": {},
"source": [
"이 간단한 사례라고 해도 실제로는 상당히 많은 숫자입니다. 모든 양자 게이트(특히 2큐비트 게이트)는 오류가 발생하고 노이즈의 영향을 받기 때문에, 큐비트가 매우 고성능이 아닌 경우 100개 이상의 2큐비트 게이트를 연속으로 사용하면 노이즈만 발생하게 됩니다. 그 성능을 확인해 보겠습니다.\n",
"\n",
"\n",
"\n",
"### 3단계: IBM Quantum 기본 함수를 사용하여 실행하기\n",
"\n",
"우리는 여러 차례 측정을 수행하여 어떤 상태가 가장 가능성이 높은지 확인하고 싶습니다. 이러한 진폭 증폭은 IBM Quantum`Sampler` 프리미티브를 사용하여 실행하기에 적합한 샘플링 문제입니다.\n",
"\n",
"IBM Quantum 의 SamplerV2 메서드는 `run()` 기본 통합 블록(PUB)으로 구성된 반복 가능한 객체를 매개변수로 받는다는 점에 유의하십시오. Sampler의 경우, 각 PUB 는 (회로, 매개변수\\_값) 형식의 반복 가능한 객체입니다. 하지만 최소한 양자 회로 목록은 필요합니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2a272d9e",
"metadata": {},
"outputs": [],
"source": [
"# To run on a real quantum computer (this was tested on a Heron r2 processor and\n",
"# used 4 sec. of QPU time)\n",
"\n",
"from qiskit_ibm_runtime import SamplerV2 as Sampler\n",
"\n",
"sampler = Sampler(mode=backend)\n",
"sampler.options.default_shots = 10_000\n",
"result = sampler.run([circuit_isa]).result()\n",
"dist = result[0].data.meas.get_counts()"
]
},
{
"cell_type": "markdown",
"id": "7a123100",
"metadata": {},
"source": [
"이 경험을 최대한 활용하려면 IBM Quantum에서 제공되는 실제 양자 컴퓨터에서 실험을 실행해 보실 것을 적극 권장합니다. 그러나 QPU 시간을 모두 소진한 경우 아래 줄의 주석을 해제하여 시뮬레이터를 사용하여 이 활동을 완료할 수 있습니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e60bcbec",
"metadata": {},
"outputs": [],
"source": [
"# To run on local simulator:\n",
"# from qiskit.primitives import StatevectorSampler as Sampler\n",
"# sampler = Sampler()\n",
"# result = sampler.run([qc]).result()\n",
"# dist = result[0].data.meas.get_counts()"
]
},
{
"cell_type": "markdown",
"id": "f19b1adb",
"metadata": {},
"source": [
"\n",
"\n",
"### 4단계: 후처리 수행 및 원하는 클래식 형식으로 결과 반환\n",
"\n",
"이제 샘플링 결과를 히스토그램으로 그릴 수 있습니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 97,
"id": "96a9107e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 97,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"plot_distribution(dist)"
]
},
{
"cell_type": "markdown",
"id": "9dabb017",
"metadata": {},
"source": [
"Grover의 알고리즘이 다른 옵션보다 훨씬 더 높은 확률로 원하는 상태를 반환하는 것을 확인할 수 있습니다. 다음 활동에서는 쿼리 알고리즘의 양방향 워크플로우와 보다 일관성 있는 방식으로 알고리즘을 사용하겠습니다.\n",
"\n",
"\n",
"\n",
"#### 이해도 점검\n",
"\n",
"방금 $2^4=16$ 가능한 상태의 집합에서 단일 솔루션을 검색했습니다. Grover 연산자의 최적 반복 횟수를 $t=3$ 로 결정했습니다. (a) 여러 해 중 하나를 찾거나 (b) 더 많은 가능한 상태의 공간에서 단일 해를 찾았다면 이 최적 수는 증가하거나 감소했을까요?\n",
"\n",
"\n",
" \n",
" 솔루션의 전체 공간에 비해 솔루션의 수가 적으면 작은 각도를 중심으로 사인 함수를 확장하고 다음을 사용할 수 있음을 상기하십시오\n",
"\n",
" $$\n",
" (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\\\\\n",
"\n",
" t \\approx \\frac{\\pi}{4}\\sqrt{\\frac{N}{|\\mathcal{A}_1|}}-\\frac{1}{2}\n",
" $$\n",
"\n",
" (a) 위의 식에서 볼 수 있듯이, 해의 상태 수를 늘리면 반복 횟수가 줄어든다. $\\frac{|\\mathcal{A}_1|}{N}$ 의 비율이 여전히 작다고 가정할 때, $t$ 가 어떻게 감소하는지 다음과 같이 설명할 수 있습니다: $t~\\frac{1}{\\sqrt{|\\mathcal{A}_1|}}$.\n",
"\n",
" (b) 가능한 솔루션의 공간( $N$ )이 증가함에 따라 필요한 반복 횟수가 증가하지만 $t~\\sqrt{N}$ 처럼만 증가합니다.\n",
" \n",
"\n",
"\n",
"목표 비트 문자열의 크기를 임의로 길게 늘려도 목표 상태의 확률 진폭이 다른 상태보다 최소 몇 배 이상 크다는 결과를 얻을 수 있다고 가정해 보겠습니다. 그렇다면 Grover의 알고리즘을 사용하여 목표 상태를 안정적으로 찾을 수 있을까요?\n",
"\n",
"\n",
" \n",
" 아니오. 20 큐비트로 첫 번째 활동을 반복하고 양자 회로를 여러 번 실행한다고 가정해 보겠습니다 `num_shots = 10,000`. 균일한 확률 분포는 모든 상태가 한 번이라도 측정될 확률이 $10,000/2^{20}=0.00954$ 라는 것을 의미합니다. 만약 목표 상태를 측정할 확률이 미해결 확률의 10배라면(그리고 각 미해결 확률이 그에 따라 약간씩 감소한다면), 목표 상태를 한 번이라도 측정할 확률은 약 10%에 불과합니다. 목표 상태를 여러 번 측정할 가능성이 매우 낮기 때문에 무작위로 얻은 많은 비해결 상태와 구별할 수 없게 됩니다. 좋은 소식은 오류 억제 및 완화를 사용하면 훨씬 더 높은 충실도의 결과를 얻을 수 있다는 것입니다.\n",
" \n",
"\n",
"\n",
"\n",
"\n",
"## 활동 2: 정확한 쿼리 알고리즘 워크플로\n",
"\n",
"이 활동은 첫 번째 활동과 똑같이 시작하지만, 이번에는 다른 키스킷 애호가와 짝을 이룬다는 점이 다릅니다. 여러분은 비밀 비트스트링을 선택하고, 파트너는 (일반적으로) 다른 비트스트링을 선택합니다. 여러분은 각각 오라클 역할을 하는 양자 회로를 생성하고 이를 교환하게 됩니다. 그런 다음 해당 오라클과 함께 Grover의 알고리즘을 사용하여 파트너의 비밀 비트스트링을 결정합니다.\n",
"\n",
"\n",
"\n",
"### 1단계: 고전적 입력을 양자 문제에 매핑하기\n",
"\n",
"위에 정의된 `grover_oracle` 함수를 사용하여 하나 이상의 표시된 상태에 대한 오라클 회로를 구성합니다. 파트너에게 표시한 상태 수를 알려주면 파트너가 최적의 횟수로 그로버 연산자를 적용할 수 있습니다. **비트줄을 너무 길게 만들지 마세요. 3\\~5 비트는 큰 어려움 없이 작동합니다.** 비트 문자열이 길어지면 오류 완화 같은 고급 기술이 필요한 딥 회로가 생성됩니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 173,
"id": "5be9092e",
"metadata": {},
"outputs": [],
"source": [
"# Modify the marked states to mark those you wish to target.\n",
"marked_states = [\"1000\"]\n",
"oracle = grover_oracle(marked_states)"
]
},
{
"cell_type": "markdown",
"id": "b4874b93",
"metadata": {},
"source": [
"이제 목표 상태의 위상을 뒤집는 양자 회로를 만들었습니다. 아래 구문을 사용하여 이 회로를 `my_circuit.qpy` 으로 저장할 수 있습니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "77093258",
"metadata": {},
"outputs": [],
"source": [
"from qiskit import qpy\n",
"\n",
"# Save to a QPY file at a location where you can easily find it.\n",
"# You might want to specify a global address.\n",
"with open(\"C:\\\\Users\\\\...put your own address here...\\\\my_circuit.qpy\", \"wb\") as f:\n",
" qpy.dump(oracle, f)"
]
},
{
"cell_type": "markdown",
"id": "524f5577",
"metadata": {},
"source": [
"이제 이 파일을 이메일, 메시징 서비스, 공유 리포지토리 등을 통해 파트너에게 보냅니다. 파트너에게 자신의 회로도 보내달라고 요청하세요. 파일을 쉽게 찾을 수 있는 곳에 저장하세요. 파트너의 회로를 확보하면 시각화할 수 있지만 그렇게 하면 쿼리 모델이 깨집니다. 즉, 오라클을 쿼리(오라클 회로 사용)할 수는 있지만 오라클이 어떤 상태를 대상으로 하는지 확인하기 위해 오라클을 검사할 수는 없는 상황을 모델링하고 있습니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "24ba4869",
"metadata": {},
"outputs": [],
"source": [
"from qiskit import qpy\n",
"\n",
"# Load the circuit from your partner's qpy file from the folder where you saved it.\n",
"with open(\"C:\\\\Users\\\\...file location here...\\\\my_circuit.qpy\", \"rb\") as f:\n",
" circuits = qpy.load(f)\n",
"\n",
"# qpy.load always returns a list of circuits\n",
"oracle_partner = circuits[0]\n",
"\n",
"# You could visualize the circuit, but this would break the model of a query algorithm.\n",
"# oracle_partner.draw(\"mpl\")"
]
},
{
"cell_type": "markdown",
"id": "0c7b7012",
"metadata": {},
"source": [
"파트너에게 인코딩한 대상 상태의 수를 물어보고 아래에 입력합니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 174,
"id": "120e339c",
"metadata": {},
"outputs": [],
"source": [
"# Update according to your partner's number of target states.\n",
"num_marked_states = 1"
]
},
{
"cell_type": "markdown",
"id": "f2c4b911",
"metadata": {},
"source": [
"이 값은 다음 표현식에서 최적의 Grover 반복 횟수를 결정하는 데 사용됩니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 175,
"id": "d199a8cc",
"metadata": {},
"outputs": [],
"source": [
"grover_op = grover_operator(oracle_partner)\n",
"optimal_num_iterations = math.floor(\n",
" math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))\n",
")\n",
"qc = QuantumCircuit(grover_op.num_qubits)\n",
"qc.h(range(grover_op.num_qubits))\n",
"qc.compose(grover_op.power(optimal_num_iterations), inplace=True)\n",
"qc.measure_all()"
]
},
{
"cell_type": "markdown",
"id": "37eb709b",
"metadata": {},
"source": [
"\n",
"\n",
"### 2단계: 양자 하드웨어 실행을 위한 문제 최적화\n",
"\n",
"이전과 동일하게 진행됩니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 176,
"id": "e5e89707",
"metadata": {},
"outputs": [],
"source": [
"# To run on hardware, select the backend with the fewest number of jobs in the queue\n",
"service = QiskitRuntimeService()\n",
"backend = service.least_busy(operational=True, simulator=False)\n",
"backend.name\n",
"\n",
"target = backend.target\n",
"pm = generate_preset_pass_manager(target=target, optimization_level=3)\n",
"circuit_partner_isa = pm.run(qc)"
]
},
{
"cell_type": "markdown",
"id": "de2af3e1",
"metadata": {},
"source": [
"\n",
"\n",
"### 3단계: IBM Quantum 기본 함수를 사용하여 실행하기\n",
"\n",
"이 과정도 첫 번째 활동의 과정과 동일합니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "16f97083",
"metadata": {},
"outputs": [],
"source": [
"# To run on a real quantum computer (this was tested on a Heron r2 processor and used\n",
"# 4 seconds of QPU time)\n",
"\n",
"from qiskit_ibm_runtime import SamplerV2 as Sampler\n",
"\n",
"sampler = Sampler(mode=backend)\n",
"sampler.options.default_shots = 10_000\n",
"result = sampler.run([circuit_partner_isa]).result()\n",
"dist = result[0].data.meas.get_counts()"
]
},
{
"cell_type": "markdown",
"id": "14bbde32",
"metadata": {},
"source": [
"\n",
"\n",
"### 4단계: 후처리 수행 및 원하는 클래식 형식으로 결과 반환\n",
"\n",
"이제 샘플링 결과의 히스토그램을 표시합니다. 하나 이상의 상태는 다른 상태보다 측정 확률이 훨씬 높아야 합니다. 이를 파트너에게 보고하고 목표 상태를 올바르게 결정했는지 확인하세요. 기본적으로 표시되는 히스토그램은 첫 번째 활동과 동일한 회로의 히스토그램입니다. 파트너의 서킷과 다른 결과를 얻어야 합니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 114,
"id": "ee7a59ac",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 114,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"plot_distribution(dist)"
]
},
{
"cell_type": "markdown",
"id": "9c03a936",
"metadata": {},
"source": [
"\n",
"\n",
"#### 이해도 점검\n",
"\n",
"파트너의 목표 상태를 올바르게 획득했어야 합니다. 그렇지 않은 경우 파트너와 협력하여 무엇이 잘못되었는지 파악하세요. 몇 가지 아이디어를 보려면 아래를 클릭하세요.\n",
"\n",
"\n",
" \n",
" * 파트너의 회로를 시각화/그리고 올바르게 로드되었는지 확인합니다.\n",
" * 사용된 회로를 비교하고 예상 결과와 얻은 결과를 비교합니다.\n",
" * 비트 문자열이 너무 길거나 그로버 반복 횟수가 지나치게 많지 않은지 사용 된 회로의 깊이를 확인합니다.\n",
" \n",
"\n",
"\n",
"아직 그려보지 않았다면 파트너가 보낸 오라클 회로를 그려보세요. 각 게이트의 효과에 대해 이야기하고 목표 상태가 무엇이었을지 논증할 수 있는지 살펴보세요. 이 작업은 여러 상태보다 단일 표시 상태의 경우에 훨씬 쉽습니다.\n",
"\n",
"\n",
" \n",
" * 오라클의 임무는 대상 상태의 부호를 뒤집는 것임을 기억하세요.\n",
" * 제어에 관련된 모든 큐비트가 $|1\\rangle$ 상태에 있을 때만 MCMTGate가 상태의 부호를 뒤집는다는 점을 기억하세요.\n",
" * 대상 상태에 이미 특정 큐비트에 $|1\\rangle$ 가 있는 경우 해당 큐비트에는 아무 작업도 할 필요가 없습니다. 타겟이 특정 큐비트에 $|0\\rangle$ 를 가지고 있고 MCMT게이트가 부호를 뒤집도록 하려면 오라클에서 해당 큐비트에 `X` 게이트를 적용해야 합니다(그리고 MCMT게이트 뒤의 `X` 게이트를 취소해야 합니다).\n",
" \n",
"\n",
"\n",
"Grover 연산자의 반복 횟수를 한 번 줄여서 실험을 반복합니다. 그래도 정답을 얻었나요? 그 이유는?\n",
"\n",
"\n",
" \n",
" 인코딩된 솔루션의 수에 따라 달라질 수 있지만 아마도 그럴 것입니다. 여기서 한 가지 미묘한 점이 강조됩니다. '최적의' Grover 반복 횟수는 표시된 상태를 측정할 확률을 가능한 한 높게 만드는 횟수입니다. 그러나 이보다 적은 반복 횟수로도 표시된 상태가 다른 상태보다 훨씬 더 가능성이 높을 수 있습니다. 따라서 최적의 반복 횟수보다 더 적은 횟수로 반복할 수 있습니다. 이렇게 하면 회로 깊이가 줄어들어 오류율이 감소합니다.\n",
" \n",
"\n",
"\n",
"여기서 확인된 '최적 횟수'보다 적은 수의 Grover 반복을 사용하려는 이유는 무엇인가요?\n",
"\n",
"\n",
" \n",
" \"최적의\" Grover 반복 횟수는 노이즈가 없을 때 표시된 상태를 측정할 확률을 가능한 한 높게 만드는 횟수입니다. 그러나 이보다 적은 반복 횟수로도 표시된 상태가 다른 상태보다 훨씬 더 가능성이 높을 수 있습니다. 따라서 최적의 반복 횟수보다 더 적은 반복 횟수로도 충분할 수 있습니다. 이렇게 하면 회로 깊이가 줄어들어 오류율이 감소합니다.\n",
" \n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "mine_intro_01",
"metadata": {},
"source": [
"\n",
"\n",
"## 활동 3: 그로버 알고리즘을 사용하여 지뢰 찾기 판을 풀어보세요\n",
"\n",
"이전 절에서 우리는 그로버 알고리즘이 정답에 대한 지식이 아니라 문제의 *제약* 조건들을 바탕으로 오라클을 구축할 수 있을 때 비로소 진정으로 유용해진다는 점을 살펴보았다. 지뢰 찾기가 대표적인 예입니다. 번호가 매겨진 칸들은 인접한 지뢰의 개수를 알려주며, 이러한 제약 조건만으로도 지뢰가 어디에 위치해야 하는지는 완전히 결정되지만, 실제 배치를 찾아내기 위해서는 탐색 과정이 필요합니다.\n",
"\n",
"지뢰 찾기는 NP-완전 문제로 입증되었습니다. 즉, 풀기는 어렵지만 정답 여부를 확인하는 것은 쉽습니다. 따라서 이는 그로버 알고리즘을 적용하기에 안성맞춤인 문제입니다. 물론, 잡음이 많은 양자 컴퓨터로는 아직 9× $\\times$ ×9 격자 전체를 풀 수 없습니다. 회로가 너무 복잡해지기 때문입니다. 대신, 향후 출시될 내결함성 시스템에서 더 큰 보드를 어떻게 처리할지 보여주기 위한 간단한 예시로 아주 작은 그리드를 사용해 보겠습니다.\n",
"\n",
"몇 가지 중요한 주의 사항이 있습니다. 그로버 알고리즘은 *비구조적* 고전적 탐색에 비해 속도가 2배 빨라질 뿐입니다. 지뢰 찾기에는 영리한 고전 알고리즘이 활용할 수 있는 취약점이 거의 확실하게 존재한다. 게다가 기하급수적으로 늘어나는 검색 공간의 경우, $\\sqrt{N}$ 의 개선 효과조차 한계가 있습니다. 하지만 그런 우려는 잠시 접어두고, 이 간단한 예제를 통해 문제 제약 조건이 양자 오라클에 어떻게 반영되는지 살펴보도록 하자.\n",
"\n",
"\n",
"\n",
"### 전력망\n",
"\n",
"다음은 아기 지뢰 찾기 게임의 격자입니다:\n",
"\n",
"\n",
"\n",
"각 빈 칸은 그 안에 지뢰가 있는지 여부를 나타내는 이진 변수로 표현할 수 있습니다. 이 셀들을 각각 $x_0$, $x_1$, $x_2$ 라고 표기하며, 여기서 $x_i = 1$ 는 해당 셀에 지뢰가 있다는 뜻이고, $x_i = 0$ 는 지뢰가 없다는 뜻입니다:\n",
"\n",
"\n",
"\n",
"이 문제는 머릿속으로 약 0.5초 만에 풀 수 있지만, 우리는 이 간단한 예제를 통해 양자 컴퓨터를 이용해 훨씬 더 복잡한 문제를 어떻게 해결할 수 있는지 보여주려고 합니다.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "mine_bool_01",
"metadata": {},
"source": [
"\n",
"\n",
"### 제약 조건 인코딩\n",
"\n",
"번호가 매겨진 각 셀은 인접한 빈 셀에 조건을 부여합니다. 이러한 조건들을 양자 회로로 인코딩할 수 있는 부울 식으로 표현해야 합니다.\n",
"\n",
"$x_0$ 와 $x_1$ 에 인접한 “1” 셀은 이 두 칸 중 정확히 하나에 지뢰가 있다는 것을 의미합니다. 이것이 바로 배타적 논리합(XOR) 연산 $\\oplus$ 이며, 입력값 중 정확히 하나만 참일 때 참을 반환합니다:\n",
"\n",
"$$\n",
"(x_0 \\oplus x_1)\n",
"$$\n",
"\n",
"마찬가지로, 다른 “1”이 적힌 셀( $x_1$ 및 $x_2$ 와 인접한 셀)에서는 다음과 같은 결과가 나옵니다:\n",
"\n",
"$$\n",
"(x_1 \\oplus x_2)\n",
"$$\n",
"\n",
"“2”라고 적힌 칸은 세 개의 빈 칸 중 두 곳에 지뢰가 있어야 함을 의미합니다. XOR은 패리티 연산이기 때문에, 변수 중 참인 개수가 *홀수일* 때 $x_0 \\oplus x_1 \\oplus x_2$ 는 true를 반환합니다. 우리는 *짝수* (구체적으로는 2)가 참이 되기를 원하므로, $\\lnot$ 를 사용하여 부정 연산을 수행합니다:\n",
"\n",
"$$\n",
"\\lnot(x_0 \\oplus x_1 \\oplus x_2)\n",
"$$\n",
"\n",
"이 식 자체는 패리티에 관한 진술이므로, $|1\\rangle$ 상태에 있는 0개 또는 2개의 큐비트 모두에 대해 성립합니다. 그러나 각각 최소 한 개의 지뢰가 있어야 한다는 다른 두 조건과 결합하면, 이 조건을 모두 만족시키는 유일한 해는 지뢰가 정확히 두 개인 경우뿐이다.\n",
"\n",
"세 가지 조건이 모두 동시에 충족되어야 하므로, ‘and’ 연산자로 이를 결합합니다 $\\land$ :\n",
"\n",
"$$\n",
"(x_0 \\oplus x_1) \\;\\land\\; (x_1 \\oplus x_2) \\;\\land\\; \\lnot(x_0 \\oplus x_1 \\oplus x_2)\n",
"$$\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "mine_oracle_01",
"metadata": {},
"source": [
"\n",
"\n",
"### 1단계: 고전적 입력을 양자 문제에 매핑하기\n",
"\n",
"이제 이 부울 식을 오라클 역할을 하는 양자 회로로 변환해야 합니다. 양자 XOR 연산은 CX(CNOT) 게이트를 사용하여 수행할 수 있습니다. 데이터 큐비트에 두 개의 CX 게이트를 적용하여 작업 공간(ancilla) 큐비트로 전송하면, 이는 사실상 두 큐비트의 XOR 연산을 수행하는 것이며 그 결과를 작업 공간 큐비트에 저장하게 됩니다.\n",
"\n",
"각 절마다 하나씩, 총 세 개의 작업 공간 큐비트를 도입합니다. 각 부울 식의 결과를 해당 작업 공간 큐비트에 저장한 다음, 다중 제어 Z 게이트를 사용하여 세 개의 작업 공간 큐비트가 모두 ‘ $|1\\rangle$ ’ 상태가 되도록(즉, 모든 절이 동시에 충족되도록) 3큐비트 상태의 위상을 반전시킵니다.\n",
"\n",
"아래 첫 번째 코드 셀에서는 오라클의 “계산” 부분을 구현합니다. 이 부분은 각 절을 평가하고 그 결과를 작업 공간 큐비트에 기록하는 역할을 합니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "mine_code_oracle1",
"metadata": {},
"outputs": [],
"source": [
"x = QuantumRegister(3, \"x\")\n",
"a = QuantumRegister(3, \"a\")\n",
"qc = QuantumCircuit(x, a)\n",
"\n",
"# Clause 1: x0 XOR x1 -> stored in a[0]\n",
"qc.cx(x[0], a[0])\n",
"qc.cx(x[1], a[0])\n",
"\n",
"# Clause 2: x1 XOR x2 -> stored in a[1]\n",
"qc.cx(x[1], a[1])\n",
"qc.cx(x[2], a[1])\n",
"\n",
"# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]\n",
"qc.cx(x[0], a[2])\n",
"qc.cx(x[1], a[2])\n",
"qc.cx(x[2], a[2])\n",
"qc.x(a[2]) # The NOT\n",
"\n",
"qc.draw(\"mpl\", style=\"iqp\")"
]
},
{
"cell_type": "markdown",
"id": "mine_mcz_01",
"metadata": {},
"source": [
"이 시점에서 각 절의 결과는 해당 작업 공간 큐비트에 저장됩니다. 이제 작업 공간의 세 큐비트 모두 $|1\\rangle$ 가 음의 부호를 띠게 만드는 3큐비트 데이터 상태가 필요합니다. 우리는 다중 제어 Z 게이트(표적 게이트 양쪽에 하다마르 게이트가 배치된 MCX 게이트 형태로 구현됨)를 사용하여 이를 수행합니다.\n",
"\n",
"위상 반전을 적용한 후에는, 작업 공간 큐비트를 ‘ $|0\\rangle$ ’ 상태로 다시 초기화하기 위해 **‘uncompute’** — 즉, 모든 절 평가 단계를 역순으로 되돌리는 작업 — 을 수행해야 합니다. 이는 Grover 연산자의 후속 반복을 위해 작업 공간 큐비트를 깨끗한 상태로 유지하기 위해 필수적입니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "mine_code_oracle2",
"metadata": {},
"outputs": [],
"source": [
"# Multi-controlled Z: flip phase if all workspace qubits are |1>\n",
"qc.h(a[2])\n",
"qc.mcx([a[0], a[1]], a[2])\n",
"qc.h(a[2])\n",
"\n",
"# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)\n",
"qc.x(a[2])\n",
"qc.cx(x[2], a[2])\n",
"qc.cx(x[1], a[2])\n",
"qc.cx(x[0], a[2])\n",
"\n",
"# Uncompute clause 2: x1 XOR x2\n",
"qc.cx(x[2], a[1])\n",
"qc.cx(x[1], a[1])\n",
"\n",
"# Uncompute clause 1: x0 XOR x1\n",
"qc.cx(x[1], a[0])\n",
"qc.cx(x[0], a[0])\n",
"\n",
"qc.draw(\"mpl\", style=\"iqp\")"
]
},
{
"cell_type": "markdown",
"id": "mine_groverop_01",
"metadata": {},
"source": [
"이 회로는 우리의 ‘오라클’ 역할을 합니다. 이 회로는 ‘지뢰 찾기’의 세 가지 제약 조건을 모두 충족하는 데이터 큐비트 상태의 위상을 반전시키며, 작업 공간 큐비트들은 ‘ $|0\\rangle$ ’ 상태로 되돌려 놓습니다.\n",
"\n",
"이제 이 오라클을 바탕으로 완전한 그로버 연산자를 구성해 보겠습니다. `x`다음 `reflection_qubits` 점에 유의하십시오: 작업 공간 큐비트는 탐색 공간의 일부가 아니므로, 데이터 큐비트만 전달합니다. 오라클이 적용되면 그들의 임무는 끝난다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "mine_code_groverop",
"metadata": {},
"outputs": [],
"source": [
"grover_op = grover_operator(qc, reflection_qubits=x)\n",
"grover_op.decompose(reps=0).draw(output=\"mpl\", style=\"iqp\")"
]
},
{
"cell_type": "markdown",
"id": "mine_circuit_01",
"metadata": {},
"source": [
"데이터 큐비트 3개와 솔루션 상태 1개를 사용할 때, 그로버 반복의 최적 횟수는 $t \\approx \\frac{\\pi}{4}\\sqrt{8} - \\frac{1}{2} \\approx 1.7$ 이므로, 우리는 두 번의 반복을 수행합니다. 데이터 큐비트에 하다마르 게이트를 적용하여 초기 중첩 상태를 생성하고, 그로버 연산자를 두 번 연산한 뒤, 데이터 큐비트만 측정합니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "mine_code_circuit",
"metadata": {},
"outputs": [],
"source": [
"x = QuantumRegister(3, \"x\")\n",
"a = QuantumRegister(4, \"a\")\n",
"meas = ClassicalRegister(3, \"meas\")\n",
"\n",
"qc = QuantumCircuit(x, a, meas)\n",
"# Create superposition over the data qubits only\n",
"qc.h(x)\n",
"# Apply 2 iterations of the Grover operator\n",
"qc.compose(grover_op.power(2), inplace=True)\n",
"# Measure only the data qubits\n",
"qc.measure(x, meas)\n",
"qc.decompose().draw(output=\"mpl\", style=\"iqp\")"
]
},
{
"cell_type": "markdown",
"id": "mine_step2_01",
"metadata": {},
"source": [
"\n",
"\n",
"### 2단계: 양자 하드웨어 실행을 위한 문제 최적화\n",
"\n",
"이전과 마찬가지로, 대상 백엔드에 맞게 회로를 트랜스파일합니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "mine_code_transpile",
"metadata": {},
"outputs": [],
"source": [
"service = QiskitRuntimeService()\n",
"backend = service.least_busy(operational=True, simulator=False)\n",
"print(backend.name)\n",
"\n",
"target = backend.target\n",
"pm = generate_preset_pass_manager(target=target, optimization_level=3)\n",
"circuit_isa = pm.run(qc)"
]
},
{
"cell_type": "markdown",
"id": "mine_depth_01",
"metadata": {},
"source": [
"이제 트랜스파일된 회로의 깊이를 확인할 수 있습니다. 마인스위퍼 오라클은 작업 공간 큐비트와 여러 개의 CX 게이트를 사용하기 때문에, 변환된 회로는 이전 활동들에서 본 회로들보다 더 깊어질 것입니다.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "mine_code_depth",
"metadata": {},
"outputs": [],
"source": [
"print(\"The total depth is \", circuit_isa.depth())\n",
"print(\n",
" \"The depth of two-qubit gates is \",\n",
" circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),\n",
")"
]
},
{
"cell_type": "markdown",
"id": "mine_step3_01",
"metadata": {},
"source": [
"\n",
"\n",
"### 3단계: IBM Quantum 기본 함수를 사용하여 실행하기\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "mine_code_run",
"metadata": {},
"outputs": [],
"source": [
"# To run on a real quantum computer (this was tested on a Heron r2 processor and\n",
"# used 4 sec. of QPU time)\n",
"\n",
"from qiskit_ibm_runtime import SamplerV2 as Sampler\n",
"\n",
"sampler = Sampler(mode=backend)\n",
"sampler.options.default_shots = 10_000\n",
"result = sampler.run([circuit_isa]).result()\n",
"dist = result[0].data.meas.get_counts()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "mine_code_sim",
"metadata": {},
"outputs": [],
"source": [
"# To run on local simulator:\n",
"# from qiskit.primitives import StatevectorSampler as Sampler\n",
"# sampler = Sampler()\n",
"# result = sampler.run([qc]).result()\n",
"# dist = result[0].data.meas.get_counts()"
]
},
{
"cell_type": "markdown",
"id": "mine_step4_01",
"metadata": {},
"source": [
"\n",
"\n",
"### 4단계: 후처리 수행 및 원하는 클래식 형식으로 결과 반환\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "mine_code_plot",
"metadata": {},
"outputs": [],
"source": [
"plot_distribution(dist)"
]
},
{
"cell_type": "markdown",
"id": "mine_conclusion_01",
"metadata": {},
"source": [
"이 `101` 상태가 다른 어떤 상태보다 훨씬 더 높은 확률로 나타날 것이며, 이는 지뢰가 $x_0$ 및 $x_2$ 에 위치해 있음을 의미합니다. 우리는 양자 컴퓨터를 사용하여 간단한 지뢰 찾기 게임을 해결했습니다!\n",
"\n",
"물론, 지뢰 찾기 게임에 적용되는 최적의 고전 알고리즘은 모든 가능한 지뢰 배치를 일일이 탐색하는 무차별 대입 방식보다 우수합니다. 이 알고리즘들은 격자판의 구조를 활용하기 때문입니다. 그로버 알고리즘은 최대한 모호하게 설계된 극도로 난해한 보드에서만 이점을 제공할 뿐이며, 설령 그런 경우에도 2차적인 속도 향상만으로는 지수적인 증가세를 무한정 따라잡을 수 없다. 하지만 진정한 핵심은 바로 이 기법입니다. 문제의 제약 조건을 양자 오라클에 인코딩하는 것은 제약 조건 충족, 조합 최적화 및 기타 여러 분야로 확장될 수 있는 강력한 패턴입니다.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "494c1799",
"metadata": {},
"source": [
"\n",
"\n",
"## 질문 및 핵심 개념:\n",
"\n",
"\n",
"\n",
"### 핵심 개념:\n",
"\n",
"이 모듈에서는 Grover 알고리즘의 몇 가지 주요 기능에 대해 알아보았습니다:\n",
"\n",
"* 기존의 비정형 검색 알고리즘은 검색 공간의 크기에 따라 선형적으로 증가하는 쿼리 횟수( $N$ )가 필요한 반면, 그로버 알고리즘은 검색 공간의 크기에 비례하여 증가하는 쿼리 횟수( $\\sqrt{N}$ )가 필요합니다.\n",
"* 그로버 알고리즘은 목표 상태가 측정될 확률을 최적으로 높일 수 있도록 선택된 일련의 연산(일반적으로 “그로버 연산자”라고 함)을 여러 번 반복하는 것을 포함한다 $t$.\n",
"* Grover의 알고리즘은 $t$ 반복 횟수보다 적은 횟수로 실행할 수 있으며 여전히 목표 상태를 증폭할 수 있습니다.\n",
"* Grover의 알고리즘은 쿼리 계산 모델에 적합하며 한 사람이 검색을 제어하고 다른 사람이 오라클을 제어/구축할 때 가장 적합합니다. 다른 양자 계산의 서브루틴으로도 유용할 수 있습니다.\n",
"* 지뢰 찾기 예시에서 보았듯이, 오라클은 해법에 대한 지식보다는 *문제의 제약* 조건을 바탕으로 구축될 수 있다.\n",
"\n",
"\n",
"\n",
"### T/F 문제:\n",
"\n",
"1. T/F Grover의 알고리즘은 비정형 검색에서 하나의 표시된 상태를 찾는 데 필요한 쿼리 횟수를 기존 알고리즘보다 기하급수적으로 개선했습니다.\n",
"\n",
"2. T/F Grover의 알고리즘은 솔루션 상태가 측정될 확률을 반복적으로 높이는 방식으로 작동합니다.\n",
"\n",
"3. T/F 그로버 연산자를 반복하는 횟수가 많을수록 솔루션 상태를 측정할 확률이 높아집니다.\n",
"\n",
"\n",
"\n",
"### MC 질문:\n",
"\n",
"1. 문장을 완성하는 데 가장 적합한 옵션을 선택합니다. 최신 양자 컴퓨터에서 그로버 알고리즘을 성공적으로 사용하기 위한 최선의 전략은 그로버 연산자를 반복하는 것입니다...\n",
"\n",
"* a. 일 수에 관계 없이\n",
"* b. 솔루션 상태의 확률 진폭을 최대화하려면 항상 $t$ 번을 사용합니다.\n",
"* c. 최대 $t$ 횟수까지 가능하지만, 이보다 적은 횟수라도 솔루션 상태를 돋보이게 하기에 충분할 수 있습니다.\n",
"* d. 10회 이상.\n",
"\n",
"2. 위상 쿼리 회로는 특정 상태를 위상 반전으로 표시하는 오라클로 작동합니다. 다음 중 이 회로에 표시되는 상태는 어느 것입니까?\n",
"\n",
"\n",
"\n",
"* a. $|0000\\rangle$\n",
"* b. $|0101\\rangle$\n",
"* c. $|0110\\rangle$\n",
"* d. $|1001\\rangle$\n",
"* e. $|1010\\rangle$\n",
"* f. $|1111\\rangle$\n",
"\n",
"3. 128개의 집합에서 3개의 표시된 상태를 검색한다고 가정해 보겠습니다. 표시된 상태의 진폭을 최대화하기 위한 그로버 연산자의 최적 반복 횟수는 얼마입니까?\n",
"\n",
"* a. 1\n",
"* b. 3\n",
"* c. 5\n",
"* d. 6\n",
"* e. 20\n",
"* f. 33\n",
"\n",
"\n",
"\n",
"### 토론 질문:\n",
"\n",
"1. 그로버 검색으로 어떤 다른 문제들을 정의할 수 있을까요? 해결책을 찾기는 어렵지만, 그 해결책이 맞는지 확인하기는 쉬운 문제들을 생각해 보세요.\n",
"\n",
"2. 최신 양자 컴퓨터에서 Grover의 알고리즘을 확장하는 데 어떤 문제가 있나요?\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"id": "a1b8767d",
"source": "© IBM Corp., 2017-2026"
}
],
"metadata": {
"in_page_toc_max_heading_level": 2,
"in_page_toc_min_heading_level": 2,
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3"
}
},
"nbformat": 4,
"nbformat_minor": 5
}