{ "cells": [ { "cell_type": "markdown", "id": "76d7b924", "metadata": {}, "source": [ "---\n", "title: \"그로버 알고리즘\"\n", "description: \"그로버 알고리즘을 사용하여 비정형 데이터베이스를 2차 속도로 검색한다.\"\n", "---\n", "\n", "{/* cspell:ignore fontsize */}\n", "\n", "\n", "\n", "# 그로버 알고리즘\n", "\n", "*예상 소요 시간: Eagle r3 프로세서 기준 1분 미만 (참고: 이는 예상치에 불과합니다.) (실행 시간은 다를 수 있습니다.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "88aa4204", "metadata": {}, "source": [ "\n", "\n", "## 학습 성과\n", "\n", "* 하나 이상의 계산 기저 상태를 표시하는 그로버 오라클을 구성하는 방법\n", "* Qiskit 회로 라이브러리의 함수 `grover_operator()` 사용 방법\n", "* 주어진 문제에 대해 Grover 반복 횟수의 최적값을 결정하는 방법\n", "* IBM Quantum 샘플러 프리미티브를 사용하여 그로버 알고리즘을 실행하는 방법\n", "\n", "\n", "\n", "## 전제조건\n", "\n", "* [양자 알고리즘의 기초: 그로버 알고리즘](/learning/courses/fundamentals-of-quantum-algorithms/grover-algorithm/introduction)\n", "* [양자 정보의 기초](/learning/courses/basics-of-quantum-information)\n", "\n", "\n", "\n", "## 배경\n", "\n", "진폭 증폭(Amplitude amplification)은 몇 가지 고전 알고리즘에 비해 2차적인 속도 향상을 얻을 수 있는 범용 양자 알고리즘, 즉 서브루틴입니다. [그로버 알고리즘은](https://arxiv.org/abs/quant-ph/9605043) 비정형 검색 문제에서 이러한 속도 향상을 최초로 입증한 알고리즘이다. 그로버 검색 문제를 구성하려면, 하나 이상의 계산 기저 상태를 우리가 찾고자 하는 상태로 표시하는 오라클 함수와, 표시된 상태의 진폭을 증가시켜 나머지 상태의 신호를 억제하는 증폭 회로가 필요합니다.\n", "\n", "여기서는 Grover 오라클을 구성하고 키스킷 회로 라이브러리의 [`grover_operator()`](/docs/api/qiskit/qiskit.circuit.library.grover_operator) 를 사용하여 Grover의 검색 인스턴스를 쉽게 설정하는 방법을 보여드리겠습니다. 런타임 `Sampler` 프리미티브는 그로버 회로를 원활하게 실행할 수 있게 해줍니다.\n", "\n" ] }, { "cell_type": "markdown", "id": "5bbba268", "metadata": {}, "source": [ "\n", "\n", "## 요구사항\n", "\n", "이 튜토리얼을 시작하기 전에 다음 항목이 설치되어 있는지 확인하십시오:\n", "\n", "* Qiskit SDK v2.0 또는 그 이후 버전, [시각화](/docs/api/qiskit/visualization) 기능 지원\n", "* Qiskit Runtime v0.22 또는 그 이후 (`pip install qiskit-ibm-runtime`)\n", "\n" ] }, { "cell_type": "markdown", "id": "bfccad15", "metadata": {}, "source": [ "\n", "\n", "## 설정\n", "\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "e2cb0472", "metadata": {}, "outputs": [], "source": [ "# Built-in modules\n", "import math\n", "\n", "# Imports from Qiskit\n", "from qiskit import QuantumCircuit\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\n", "\n", "# Imports from qiskit-ibm-runtime\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "from qiskit_ibm_runtime import SamplerV2 as Sampler\n", "\n", "\n", "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 bit-string to match Qiskit bit-ordering\n", " rev_target = target[::-1]\n", " # Find the indices of all the '0' elements in bit-string\n", " zero_inds = [\n", " ind\n", " for ind in range(num_qubits)\n", " 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 bit-string has a '0' entry\n", " if zero_inds:\n", " qc.x(zero_inds)\n", " qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)\n", " if zero_inds:\n", " qc.x(zero_inds)\n", " return qc" ] }, { "cell_type": "markdown", "id": "77e41aba", "metadata": {}, "source": [ "\n", "\n", "## 소규모 시뮬레이터 예시\n", "\n", "이 섹션에서는 실제 양자 하드웨어에서 동일한 문제를 실행하기 전에, 로컬 시뮬레이터를 사용하여 소규모로 그로버 알고리즘의 각 단계를 단계별로 살펴보겠습니다.\n", "\n" ] }, { "cell_type": "markdown", "id": "0c0fb667", "metadata": {}, "source": [ "\n", "\n", "### 1단계: 고전적 입력을 양자 문제에 매핑하기\n", "\n", "그로버 알고리즘을 사용하려면 하나 이상의 ‘표시된’ 계산 기저 상태를 지정하는 [오라클](/learning/modules/computer-science/grovers#introduction) 이 필요하며, 여기서 ‘표시된’이란 위상이 -1 인 상태를 의미한다. 제어된 Z 게이트, 또는 $N$ 큐비트에 대한 다중 제어 일반화는 $2^{N}-1$ 상태(`'1'`\\* $N$ 비트열)를 나타냅니다. 이진 표현에서 기저 상태를 하나 이상의 `'0'` 로 표시하려면, 제어 Z 게이트 전후에 해당 큐비트에 X-게이트를 적용해야 하며, 이는 해당 큐비트에 오픈-컨트롤을 적용하는 것과 동일하다. 다음 코드에서는 비트열 표현을 통해 정의된 하나 이상의 입력 기저 상태를 식별하는 오라클을 정의합니다. 이 `MCMT` 게이트는 다중 제어 Z-게이트를 구현하는 데 사용됩니다.\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "bca14740", "metadata": {}, "source": [ "\n", "\n", "### 특정 그로버 인스턴스\n", "\n", "이제 오라클 함수가 생겼으므로 Grover 검색의 특정 인스턴스를 정의할 수 있습니다. 이 예제에서는 3큐비트 계산 공간에서 사용 가능한 8개의 계산 상태 중 2개의 계산 상태를 표시합니다:\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "c150298f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "marked_states = [\"011\", \"100\"]\n", "\n", "oracle = grover_oracle(marked_states)\n", "oracle.draw(output=\"mpl\", style=\"iqp\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "25487b93", "metadata": {}, "source": [ "\n", "\n", "### 그로버 연산자\n", "\n", "내장된 키스킷( `grover_operator()` )은 오라클 회로를 가져와서 오라클 회로 자체와 오라클이 표시한 상태를 증폭하는 회로로 구성된 회로를 반환합니다. 여기서는 `decompose()` 메서드를 사용하여 회로를 통해 오퍼레이터 내의 게이트를 확인합니다:\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "283d5265", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grover_op = grover_operator(oracle)\n", "grover_op.decompose().draw(output=\"mpl\", style=\"iqp\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "83c34dc9", "metadata": {}, "source": [ "이 `grover_op` 회로를 반복적으로 적용하면 표시된 상태가 증폭되어 회로의 출력 분포에서 가장 가능성이 높은 비트 문자열이 됩니다. 이러한 애플리케이션의 최적 수는 가능한 총 계산 상태 수에 대한 표시된 상태의 비율에 따라 결정됩니다:\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "f4c3d4b5", "metadata": {}, "outputs": [], "source": [ "optimal_num_iterations = math.floor(\n", " math.pi\n", " / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n", ")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "e06c8238", "metadata": {}, "source": [ "\n", "\n", "### 풀 그로버 회로\n", "\n", "완전한 Grover 실험은 각 큐비트에 Hadamard 게이트로 시작하여 모든 계산 기준 상태를 균등하게 중첩한 다음 Grover 연산자(`grover_op`)가 최적의 횟수만큼 반복하는 것으로 시작됩니다. 여기서는 `QuantumCircuit.power(INT)` 메서드를 사용하여 Grover 연산자를 반복적으로 적용합니다.\n", "\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "4933ae44", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 5, "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": "0649c854", "metadata": {}, "source": [ "\n", "\n", "### 2단계: 양자 하드웨어 실행을 위한 문제 최적화\n", "\n", "소규모 시뮬레이션을 위해, 특정 하드웨어를 대상으로 하지 않고 회로를 트랜스파일합니다.\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "c4f67f35", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pm = generate_preset_pass_manager(optimization_level=3)\n", "circuit_isa = pm.run(qc)\n", "circuit_isa.draw(output=\"mpl\", idle_wires=False, style=\"iqp\")" ] }, { "cell_type": "markdown", "id": "4e0d4d90", "metadata": {}, "source": [ "\n", "\n", "### 3단계: `Qiskit primitives` 명령어로 실행합니다\n", "\n", "진폭 증폭은 프라이머리(primitive)를 [`SamplerV2`](/docs/api/qiskit-ibm-runtime/sampler-v2) 사용하여 실행하기에 적합한 샘플링 문제입니다. 여기서는 지역 시뮬레이션을 위해 에서 `qiskit.primitives` 를 `StatevectorSampler` 사용합니다.\n", "\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "7666ad7c", "metadata": {}, "outputs": [], "source": [ "from qiskit.primitives import StatevectorSampler\n", "\n", "sampler = StatevectorSampler()\n", "result = sampler.run([circuit_isa], shots=10_000).result()\n", "dist = result[0].data.meas.get_counts()" ] }, { "cell_type": "markdown", "id": "5c8263c7", "metadata": {}, "source": [ "\n", "\n", "### 4단계: 후처리 수행 및 원하는 클래식 형식으로 결과 반환\n", "\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "a5ef9913", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plot_distribution(dist)" ] }, { "cell_type": "markdown", "id": "2b45b2ee", "metadata": {}, "source": [ "\n", "\n", "## 하드웨어 예시\n", "\n" ] }, { "cell_type": "markdown", "id": "5fb22680", "metadata": {}, "source": [ "\n", "\n", "### 1\\~4단계\n", "\n", "그로버 알고리즘은 근본적으로 내결함성 알고리즘입니다. 오라클과 확산 연산자의 핵심을 이루는 다중 제어 Z 게이트는 2큐비트 게이트의 깊이가 큐비트 수에 따라 매우 빠르게 증가하게 만듭니다(다음 절에서 보여드리겠지만). 즉, 이 알고리즘은 오늘날의 불안정한 하드웨어 환경에서는 확장성이 좋지 않다는 뜻입니다. 이러한 이유로, 우리는 더 큰 규모의 문제를 다루기보다는 앞서 소개한 시뮬레이터 예제와 동일한 소규모 수준에서 하드웨어 실행을 시연합니다.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "be3c3d9e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# -------------------------Step 1-------------------------\n", "marked_states = [\"011\", \"100\"]\n", "\n", "oracle = grover_oracle(marked_states)\n", "grover_op = grover_operator(oracle)\n", "\n", "optimal_num_iterations = math.floor(\n", " math.pi\n", " / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n", ")\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()\n", "\n", "# -------------------------Step 2-------------------------\n", "service = QiskitRuntimeService()\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "circuit_isa = pm.run(qc)\n", "\n", "# -------------------------Step 3-------------------------\n", "sampler = Sampler(mode=backend)\n", "sampler.options.default_shots = 10_000\n", "sampler.options.environment.job_tags = [\"TUT-GA\"]\n", "result = sampler.run([circuit_isa]).result()\n", "dist = result[0].data.meas.get_counts()\n", "\n", "# -------------------------Step 4-------------------------\n", "plot_distribution(dist)" ] }, { "cell_type": "markdown", "id": "12e72eab", "metadata": {}, "source": [ "\n", "\n", "## 토론: 2-큐비트 게이트의 깊이 확장\n", "\n", "그로버 알고리즘이 내결함성 알고리즘으로 간주되는 주요 이유는 큐비트 수가 증가함에 따라 회로의 2-큐비트 게이트 깊이가 급격히 증가하기 때문이다. 오라클과 확산 연산자의 핵심을 이루는 다중 제어 Z 게이트는 제어 큐비트의 수에 따라 기하급수적으로 증가하는 여러 개의 2-큐비트 게이트로 분해된다. 그로버 반복 횟수의 최적값 자체가 $O(\\sqrt{2^n})$ 의 비율로 증가한다는 점을 고려할 때, 전체 2-큐비트 연산 깊이는 잡음이 있는 하드웨어 환경에서는 금세 실용성을 잃게 된다.\n", "\n", "아래에서는 큐비트 수가 증가함에 따라 그로버 회로를 구성하고, 이를 트랜스파일링한 뒤, 그 결과로 얻어진 2-큐비트 게이트 깊이를 그래프로 표시하여 이러한 확장성을 보여줍니다.\n", "\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "abc6b43c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=3: optimal_iters=2, 2Q depth=39\n", "n=4: optimal_iters=3, 2Q depth=111\n", "n=5: optimal_iters=4, 2Q depth=466\n", "n=6: optimal_iters=6, 2Q depth=1646\n", "n=7: optimal_iters=8, 2Q depth=3550\n", "n=8: optimal_iters=12, 2Q depth=7989\n", "n=9: optimal_iters=17, 2Q depth=14824\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import matplotlib.pyplot as plt\n", "\n", "num_qubits_list = list(range(3, 10))\n", "two_q_depths = []\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "for n in num_qubits_list:\n", " # Mark a single state for simplicity\n", " marked = [\"1\" * n]\n", " oracle_n = grover_oracle(marked)\n", " grover_op_n = grover_operator(oracle_n)\n", "\n", " # Optimal number of iterations\n", " num_iters = math.floor(\n", " math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))\n", " )\n", "\n", " # Build the full Grover circuit\n", " qc_n = QuantumCircuit(n)\n", " qc_n.h(range(n))\n", " qc_n.compose(grover_op_n.power(num_iters), inplace=True)\n", " qc_n.measure_all()\n", "\n", " # Transpile to a basis gate set and count 2Q depth\n", " pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)\n", " qc_transpiled = pm_n.run(qc_n)\n", "\n", " # Compute depth restricted to 2-qubit operations\n", " depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)\n", "\n", " two_q_depths.append(depth_2q)\n", " print(f\"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}\")\n", "\n", "# Plot\n", "fig, ax = plt.subplots(figsize=(8, 5))\n", "ax.plot(\n", " num_qubits_list,\n", " two_q_depths,\n", " \"o-\",\n", " linewidth=2,\n", " markersize=8,\n", " color=\"#6929C4\",\n", ")\n", "ax.set_xlabel(\"Number of qubits\", fontsize=13)\n", "ax.set_ylabel(\"Two-qubit gate depth\", fontsize=13)\n", "ax.set_title(\"Grover's algorithm: 2Q depth scaling\", fontsize=14)\n", "ax.set_yscale(\"log\")\n", "ax.grid(True, alpha=0.3)\n", "ax.set_xticks(num_qubits_list)\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "f3ddda55", "metadata": {}, "source": [ "그래프에서 볼 수 있듯이, 2큐비트 게이트의 깊이는 큐비트 수에 따라 극도로 빠르게 증가하며, 대략 지수적으로 증가합니다. 이로 인해 그로버 알고리즘은 문제 규모가 매우 작지 않은 한, 현재의 잡음이 많은 양자 하드웨어에서는 실용적이지 못합니다. 이 알고리즘은 오류 정정을 통해 심층 회로를 안정적으로 실행할 수 있게 될 미래의 내결함성 양자 컴퓨터를 위한 중요한 연구 과제로 남아 있다.\n", "\n" ] }, { "cell_type": "markdown", "id": "cf6e8fe6", "metadata": {}, "source": [ "\n", "\n", "## 다음 단계\n", "\n", "\n", " 이 글이 흥미로웠다면, 다음 자료도 참고해 보시기 바랍니다:\n", "\n", " * [Qiskit 회로 라이브러리: `grover_operator()` API 참조](/docs/api/qiskit/qiskit.circuit.library.grover_operator)\n", " * [QAOA 튜](/docs/tutorials/quantum-approximate-optimization-algorithm) 토리얼과 [대규모 QAOA 강의에서는](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa) 양자 컴퓨터를 활용한 최적화의 최근 사례를 다룹니다\n", " * 단기 알고리즘에 대해 더 자세히 알아보려면 [‘실전 양자 컴퓨팅](/learning/courses/quantum-computing-in-practice) ’ 강좌를 참고하세요\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "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" }, "hours": 1, "qpuSeconds": 60 }, "nbformat": 4, "nbformat_minor": 5 }