자습서: Q#에서 Grover의 검색 알고리즘 구현

아티클
01/13/2024

참고

Microsoft Quantum Development Kit (클래식 QDK)는 2024년 6월 30일 이후에 더 이상 지원되지 않습니다. 기존 QDK 개발자인 경우 새로운 Azure Quantum Development Kit (최신 QDK) 로 전환하여 양자 솔루션을 계속 개발하는 것이 좋습니다. 자세한 내용은 최신 QDK로 코드 마이그레이션을 참조하세요Q#.

이 자습서에서는 에서 Grover 알고리즘 Q# 을 구현하여 검색 기반 문제를 해결합니다. Grover 알고리즘의 이론에 대한 자세한 설명은 Grover 알고리즘 이론을 참조하세요.

이 자습서에서는 다음을 수행합니다.

검색 문제에 대한 Grover 알고리즘을 정의합니다.
에서 Grover 알고리즘을 구현합니다 Q#.

팁

양자 컴퓨팅 과정을 가속화하려면 Azure Quantum 웹 사이트의 고유한 기능인 Azure Quantum을 사용하여 코드를 검사. 여기서는 기본 제공 샘플 또는 사용자 고유 Q# 의 Q# 프로그램을 실행하고, 프롬프트에서 새 Q# 코드를 생성하고, 한 번의 클릭으로 웹용 VS Code에서 코드를 열고 실행하고, Copilot에게 양자 컴퓨팅에 대한 질문을 할 수 있습니다.

사전 요구 사항

Azure Quantum의 Copilot에서 코드 샘플을 실행하려면 다음을 수행합니다.
- MICROSOFT(MSA) 전자 메일 계정.
Visual Studio Code 코드 샘플을 개발하고 실행하려면 다음을 수행합니다.
- 최신 버전의 Visual Studio Code 또는 웹에서 VS Code를 엽니다.
- Azure Quantum Development Kit 확장의 최신 버전입니다. 설치 세부 정보는 VS Code에 최신 QDK 설치를 참조하세요.

문제 정의

Grover의 알고리즘은 양자 컴퓨팅에서 가장 유명한 알고리즘 중 하나입니다. 해결되는 문제 유형은 종종 "데이터베이스 검색"이라고 하지만 검색 문제의 관점에서 생각하는 것이 더 정확합니다.

모든 검색 문제는 검색 항목 $x$를 허용하는 추상 함수 $f(x)$로 수학적으로 수식화될 수 있습니다. $x$ 항목이 검색 문제에 대한 솔루션이면 $f(x)=1$입니다. $x$ 항목이 해가 아니면 $f(x)=0$입니다. 검색 문제는 $f(x_0)=1$과 같은 $x_0$ 항목을 찾는 것으로 구성됩니다.

따라서 검색 문제를 다음과 같이 공식화할 수 있습니다. 클래식 함수 $f(x):\{0,1\}^n \rightarrow\{0,1\}$, 여기서 $n$은 검색 공간의 비트 크기이며 $f(x_0)=1$인 입력 $x_0$을 찾을 수 있습니다.

검색 문제를 해결하기 위해 Grover 알고리즘을 구현하려면 다음을 수행해야 합니다.

문제를 Grover의 작업 형식으로 변환합니다. 예를 들어, Grover 알고리즘을 사용하여 정수 $M$의 인수를 찾고 있다고 가정합니다. $$f_M(x)=1[r]$$ 함수를 만들어 정수 인수 분해 문제를 Grover의 태스크로 변환할 수 있습니다. 여기서 $r=0$일 경우 $1[r]=1$이고, $r\neq0$일 경우 $1[r]=0$이며, $r$은 $M/x$의 나머지입니다. 이런 식으로 $f_M(x_i)=1$을 만드는 정수 $x_i$는 $M$의 요소이며 문제를 Grover의 작업으로 변환했습니다.
Grover의 작업 함수를 양자 오라클로 구현합니다. Grover 알고리즘을 구현하려면 Grover 작업의 $f(x)$ 함수를 양자 오라클로 구현해야 합니다.
작업을 해결하기 위해 오라클과 함께 Grover의 알고리즘을 사용합니다. 양자 오라클이 있으면 이를 Grover의 알고리즘 구현에 연결하여 문제를 해결하고 출력을 해석할 수 있습니다.

Grover 알고리즘

검색 문제에 적합한 항목이 $N=2^n$개 있고 각 항목에 $0$에서 $N-1$까지의 정수를 할당하여 인덱스된다고 가정합니다. 알고리즘의 단계는 다음과 같습니다.

$\ket{0}$ 상태에서 초기화된 $n$개 큐비트의 레지스터로 시작합니다.
레지스터의 각 큐비트에 $H$를 적용하여 레지스터를 균일 중첩으로 준비합니다. $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
다음 연산을 레지스터 $N_{\text{optimal}}$ 시간에 적용합니다.
1. 해 항목에 대해 $-1$의 조건부 위상 편이를 적용하는 위상 오라클 $O_f$.
2. 레지스터의 각 큐비트에 $H$ 적용.
3. $\ket{0}$를 제외한 모든 계산 기반 상태로 $-1$의 조건부 위상 편이 $-O_0$ 적용.
4. 레지스터의 각 큐비트에 $H$ 적용.
확률이 매우 높은 해인 항목의 인덱스를 가져오려면 레지스터를 측정합니다.
항목을 확인하여 유효한 솔루션인지 확인합니다. 그렇지 않은 경우 다시 시작합니다.

다음에서 Grover 알고리즘에 대한 코드를 작성합니다. Q#

이 섹션에서는 Q#에서 알고리즘을 구현하는 방법에 대해 설명합니다. Grover 알고리즘을 구현할 때 고려해야 할 사항은 거의 없습니다. 표시된 상태, 해당 상태를 반영하는 방법 및 알고리즘을 실행할 반복 횟수를 정의해야 합니다. Grover 작업의 함수를 구현하는 오라클도 정의해야 합니다.

표시된 상태 정의

먼저 검색에서 찾으려는 입력을 정의합니다. 이렇게 하려면 Grover 알고리즘에서 b, c 및 d 단계를 적용하는 작업을 작성합니다.

이러한 단계를 Grover의 확산 연산자 $-H^{\otimes n}O_0 H^{\otimes n}$이라고도 합니다.

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use outputQubit = Qubit();
    within {
        // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
        // toggling it results in a (-1) phase.
        X(outputQubit);
        H(outputQubit);
        // Flip the outputQubit for marked states.
        // Here, we get the state with alternating 0s and 1s by using the X
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

연산은 ReflectAboutMarked 0과 0을 번갈아 표시하여 표시된 기본 상태를 반영합니다. 이렇게 하려면 Grover의 확산 연산자를 입력 큐비트에 적용합니다. 이 작업은 $X$ 및 $H$ 게이트를 적용하여 $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket)$ 상태에서 초기화된 보조 큐비outputQubit트{1} 를 사용합니다. 그런 다음, 작업은 레지스터의 다른 모든 큐비트에 $X$ 게이트를 적용하여 큐비트의 상태를 대칭 이동합니다. 마지막으로 제어된 $X$ 게이트를 보조 큐비트 및 입력 큐비트에 적용합니다. 이 작업은 모든 입력 큐비트가 표시된 상태인 $\ket$상태에 있는 경우에만 보조 큐비트를{1} 대칭 이동합니다.

최적의 반복 횟수 정의

Grover의 검색에는 유효한 출력을 측정할 가능성이 가장 높은 최적의 반복 횟수가 있습니다. 문제에서 가능한 적격 항목이 $N=2^n$개이고 그 중 $M$개가 문제의 해인 경우 최적의 반복 횟수는 다음과 같습니다.

$$N_{\text{optimal}}\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}$$

반복의 최적 횟수를 계속 반복하면 반복에 대해 거의 0에 가까운 성공 확률에 도달할 때까지 해당 확률이 감소하기 시작합니다N_ {\text{optimal}}$. 이후 확률은 $3 N_{\text{optimal}}$까지 다시 증가하는 식입니다.

실제 애플리케이션에서는 일반적으로 문제를 해결하기 전에는 해가 몇 개인지 알 수 없습니다. 이 문제를 처리하는 효율적인 전략은 2의 제곱(즉, $1, 2, 4, 8, 16, ..., 2^n$) 단위로 추측을 점차적으로 향상시켜 $M$ 해의 개수를 "추측"하는 것입니다. 이러한 추측 중 하나는 알고리즘이 평균 약 $\sqrt{\frac{N}{M}}$ 반복 횟수로 솔루션을 여전히 찾을 수 있을 만큼 충분히 가깝습니다.

다음 Q# 함수는 레지스터에서 지정된 수의 큐비트에 대한 최적의 반복 수를 계산합니다.

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

함수는 CalculateOptimalIterations 위의 수식을 사용하여 반복 횟수를 계산한 다음 가장 가까운 정수로 반올림합니다.

Grover의 작업 정의

Grover의 검색 알고리즘 작업에는 Q# 다음 세 가지 입력이 있습니다.

큐비트 nQubits : Int레지스터의 큐비트 수입니다. 이 레지스터는 임시 해를 검색 문제로 인코딩합니다. 작업 후 측정됩니다.
최적의 반복 횟수입니다 iterations : Int.
Grover 작업의 단계 오라클을 나타내는 연 phaseOracle : Qubit[] => Unit) : Result[]산입니다. 이 연산은 일반 큐비트 레지스터에 대해 단일 변환을 적용합니다.

operation GroverSearch( nQubits : Int, iterations : Int, phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];
    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

이 GroverSearch 작업은 $\ket$상태에서 $n$ 큐비트의{0} 레지스터를 초기화하고 레지스터를 균일한 중첩으로 준비한 다음 지정된 반복 수에 Grover 알고리즘을 적용합니다. 검색 자체는 표시된 상태와 시작 상태를 반복적으로 반영하여 for 루프로 작성 Q# 할 수 있습니다. 마지막으로 레지스터를 측정하고 결과를 반환합니다.

이 코드는 , ReflectAboutUniform및 ReflectAboutAllOnes의 세 가지 PrepareUniform도우미 작업을 사용합니다.

모든 0 상태에서 레지스터를 지정하면 연산은 PrepareUniform 모든 기본 상태에 대해 균일한 중첩을 준비합니다.

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

''ReflectAboutAllOnes' 작업은 모든 상태를 반영합니다.

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

연산 ReflectAboutUniform 은 균일한 중첩 상태를 반영합니다. 먼저 균일한 중첩을 모두 0으로 변환합니다. 그런 다음, all-zero 상태를 all-ones으로 변환합니다. 마지막으로, 모든 상태를 반영합니다. 이 연산은 기하학적으로 균일 중첩 상태에 대한 벡터 공간의 리플렉션으로 해석할 수 있기 때문에 ReflectAboutUniform이라고 합니다.

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } apply {
        ReflectAboutAllOnes(inputQubits);
    }
}

최종 코드 실행

이제 Grover 검색 알고리즘의 특정 인스턴스를 구현하고 인수 분해 문제를 해결하는 데 필요한 모든 재료가 준비되었습니다. 작업을 완료 Main 하려면 큐비트 수와 반복 횟수를 지정하여 문제를 설정합니다.

operation Main() : Result[] {
let nQubits = 5;
let iterations = CalculateOptimalIterations(nQubits);
Message($"Number of iterations: {iterations}");

// Use Grover's algorithm to find a particular marked state.
let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
return results;
}

Azure Quantum의 Copilot를 사용하여 무료로 코드를 테스트 Q# 할 수 있습니다. 필요한 것은 Microsoft(MSA) 전자 메일 계정만 있으면 됩니다. Azure Quantum의 Copilot에 대한 자세한 내용은 Azure Quantum 탐색을 참조하세요.

브라우저에서 Azure Quantum에서 Copilot 를 엽니다.

다음 코드를 복사하여 코드 편집기에 붙여넣습니다.

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");

    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
    }

    operation GroverSearch(
        nQubits : Int,
        iterations : Int,
        phaseOracle : Qubit[] => Unit) : Result[] {

        use qubits = Qubit[nQubits];

        PrepareUniform(qubits);

        for _ in 1..iterations {
            phaseOracle(qubits);
            ReflectAboutUniform(qubits);
        }

        // Measure and return the answer.
        return MResetEachZ(qubits);
    }

    function CalculateOptimalIterations(nQubits : Int) : Int {
        if nQubits > 63 {
            fail "This sample supports at most 63 qubits.";
        }
        let nItems = 1 <<< nQubits; // 2^nQubits
        let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
        let iterations = Round(0.25 * PI() / angle - 0.5);
        return iterations;
    }

    operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
        Message("Reflecting about marked state...");
        use outputQubit = Qubit();
        within {
            // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
            // toggling it results in a (-1) phase.
            X(outputQubit);
            H(outputQubit);
            // Flip the outputQubit for marked states.
            // Here, we get the state with alternating 0s and 1s by using the X
            // operation on every other qubit.
            for q in inputQubits[...2...] {
                X(q);
            }
        } apply {
            Controlled X(inputQubits, outputQubit);
        }
    }

    operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
        for q in inputQubits {
            H(q);
        }
    }

    operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
        Controlled Z(Most(inputQubits), Tail(inputQubits));
    }

    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            // Transform the uniform superposition to all-zero.
            Adjoint PrepareUniform(inputQubits);
            // Transform the all-zero state to all-ones
            for q in inputQubits {
                X(q);
            }
        } apply {
            // Now that we've transformed the uniform superposition to the
            // all-ones state, reflect about the all-ones state, then let the
            // within/apply block transform us back.
            ReflectAboutAllOnes(inputQubits);
        }
    }
}

팁

Azure Quantum의 Copilot에서 코드 편집기의 오른쪽 모서리에 있는 VS Code 로고 단추를 클릭하여 웹용 VS Code에서 프로그램을 열 수 있습니다.

메모리 내 시뮬레이터를 사용하여 프로그램 실행

메모리 내 시뮬레이터를 선택합니다.
실행할 샷 수를 선택하고 실행을 클릭합니다.
결과는 히스토그램 및 결과 필드에 표시됩니다.
코드 설명을 클릭하여 Copilot에게 코드를 설명하라는 메시지를 표시합니다.

Quantinuum H 시리즈 에뮬레이터를 사용하여 프로그램 실행

무료 Quantinuum H 시리즈 에뮬레이터에 프로그램을 제출할 수도 있습니다. 에뮬레이터는 20개의 큐비트가 있는 양자 컴퓨터를 시뮬레이션합니다.

메모리 내 시뮬레이터 드롭다운을 선택하고 Quantinuum H 시리즈 에뮬레이터를 선택합니다.
샷 수(현재 20개로 제한됨)를 선택하고 실행을 선택합니다.

Visual Studio Code 열고 파일 > 새 텍스트 파일을 선택하여 새 파일을 만듭니다.
파일을 GroversAlgorithm.qs로 저장합니다. 이 파일에는 프로그램의 코드가 Q# 포함됩니다.

파일에서 다음 코드를 복사합니다 GroversAlgorithm.qs .

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");

    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
    }

    operation GroverSearch(
        nQubits : Int,
        iterations : Int,
        phaseOracle : Qubit[] => Unit) : Result[] {

        use qubits = Qubit[nQubits];

        PrepareUniform(qubits);

        for _ in 1..iterations {
            phaseOracle(qubits);
            ReflectAboutUniform(qubits);
        }

        // Measure and return the answer.
        return MResetEachZ(qubits);
    }

    function CalculateOptimalIterations(nQubits : Int) : Int {
        if nQubits > 63 {
            fail "This sample supports at most 63 qubits.";
        }
        let nItems = 1 <<< nQubits; // 2^nQubits
        let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
        let iterations = Round(0.25 * PI() / angle - 0.5);
        return iterations;
    }

    operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
        Message("Reflecting about marked state...");
        use outputQubit = Qubit();
        within {
            // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
            // toggling it results in a (-1) phase.
            X(outputQubit);
            H(outputQubit);
            // Flip the outputQubit for marked states.
            // Here, we get the state with alternating 0s and 1s by using the X
            // operation on every other qubit.
            for q in inputQubits[...2...] {
                X(q);
            }
        } apply {
            Controlled X(inputQubits, outputQubit);
        }
    }

    operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
        for q in inputQubits {
            H(q);
        }
    }

    operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
        Controlled Z(Most(inputQubits), Tail(inputQubits));
    }

    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            // Transform the uniform superposition to all-zero.
            Adjoint PrepareUniform(inputQubits);
            // Transform the all-zero state to all-ones
            for q in inputQubits {
                X(q);
            }
        } apply {
            // Now that we've transformed the uniform superposition to the
            // all-ones state, reflect about the all-ones state, then let the
            // within/apply block transform us back.
            ReflectAboutAllOnes(inputQubits);
        }
    }
}

프로그램을 실행하기 전에 프로필을 무제한으로 설정 target 해야 합니다. 보기 -> 명령 팔레트를 선택하고, QIR을 검색하고, : Azure Quantum QIR 프로필 설정을 선택한 다음, : 무제한을 선택합니다Q#.targetQ#
프로그램을 실행하려면 아래 @EntryPoint()명령 목록에서 실행을 클릭하거나 Ctrl+F5를 누릅니다. 프로그램은 기본 시뮬레이터에서 특성으로 @EntryPoint() 표시된 작업 또는 함수를 실행합니다.
출력이 디버그 콘솔에 표시됩니다.

참고

프로필이 target무제한으로 설정되지 않은 경우 프로그램을 실행할 때 오류가 발생합니다.

다음 단계

다른 Q# 자습서 살펴보기:

양자 얽힘 은 큐비트를 조작하고 측정하고 중첩 및 얽힘의 효과를 보여 주는 프로그램을 작성하는 Q# 방법을 보여 줍니다.
양자 난수 생성기는 중첩의 큐비트에서 난수를 생성하는 프로그램을 작성하는 Q# 방법을 보여 줍니다.
Quantum Fourier Transform 은 특정 큐비트를 직접 해결하는 프로그램을 작성하는 Q# 방법을 살펴봅니다.
Quantum Katas는 양자 컴퓨팅 및 프로그래밍 요소를 동시에 교육하기 위한 자기 주도적인 자습서 및 Q# 프로그래밍 연습입니다.