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

이 자습서에서는 검색 기반 문제를 해결하기 위해 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 알고리즘을 구현하려면 다음을 수행해야 합니다.

1. 문제를 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의 작업으로 변환했습니다.
2. Grover의 작업 함수를 양자 오라클로 구현합니다. Grover 알고리즘을 구현하려면 Grover 작업의 $f(x)$ 함수를 양자 오라클로 구현해야 합니다.
3. 작업을 해결하기 위해 오라클과 함께 Grover의 알고리즘을 사용합니다. 양자 오라클이 있으면 이를 Grover의 알고리즘 구현에 연결하여 문제를 해결하고 출력을 해석할 수 있습니다.

Grover 알고리즘

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

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

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

최적의 반복 횟수 정의

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

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

반복의 최적 수를 계속 반복하면 반복 $2 N_{\text{optimal}}$에서 거의 0에 가까운 성공 확률에 도달할 때까지 해당 확률이 감소하기 시작합니다. 이후 확률은 $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# 할 수 있는 표시된 상태 및 시작 상태에 대해 반복적으로 반영하는 것으로 구성됩니다. 마지막으로 레지스터를 측정하고 결과를 반환합니다.

이 코드는 세 가지 PrepareUniformReflectAboutUniformReflectAboutAllOnes도우미 작업을 사용합니다.

모든 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으로 변환합니다. 그런 다음, 모두 0 상태를 모두로 변환합니다. 마지막으로, 모든 상태를 반영합니다. 이 연산은 균일한 중첩 상태에 대한 벡터 공간의 리플렉션으로 기하학적으로 해석될 수 있기 때문에 호출 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의 부조종사

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

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

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

   import Microsoft.Quantum.Convert.*;
   import Microsoft.Quantum.Math.*;
   import Microsoft.Quantum.Arrays.*;
   import Microsoft.Quantum.Measurement.*;
   import Microsoft.Quantum.Diagnostics.*;
   
   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에서 프로그램을 열 수 있습니다.

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

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

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

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

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

Visual Studio Code

1. Visual Studio Code를 열고 파일>새 텍스트 파일을 선택하여 새 파일을 만듭니다.

2. 파일을 GroversAlgorithm.qs로 저장합니다. 이 파일에는 프로그램에 대한 코드가 Q# 포함됩니다.

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

   
   import Microsoft.Quantum.Convert.*;
   import Microsoft.Quantum.Math.*;
   import Microsoft.Quantum.Arrays.*;
   import Microsoft.Quantum.Measurement.*;
   import Microsoft.Quantum.Diagnostics.*;
   
   
   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);
       }
   }
   

4. 프로그램을 실행하기 전에 프로필이 target 제한 없음으로 설정되어 있는지 확인합니다. 보기 - 명령 팔레트를 선택하고, QIR을 검색하고, 다음을 선택합니다Q#. Azure Quantum QIR target 프로필 설정, 다음을 선택합니다Q#.>

5. 프로그램을 실행하려면 작업 위의 Main 명령 목록에서 실행을 선택하거나 Ctrl+F5를 누릅니다. 기본적으로 컴파일러는 기본 시뮬레이터에서 Main 작업 또는 함수를 실행합니다.

6. 출력이 터미널의 디버그 콘솔에 표시됩니다.

참고 항목

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

관련 콘텐츠

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

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