참고

이 페이지는 tutorials/algorithms/06_grover.ipynb 로부터 생성되었다.

그로버 알고리즘과 진폭 증폭

Grover 알고리즘은 1996년[1]에 Lov Grover가 도입한 가장 유명한 양자 알고리즘들 중 하나이다. 구조화되지 않은 데이터베이스에서 표시된 요소를 찾는, 구조화되지 않은 검색 문제들에 대해 처음 제안되었다. 하지만 Grover 알고리즘은 이제 Grover 적응 탐색 (Grover Adaptive Search)[2]과 같은 여러 다른 알고리즘들의 서브루틴이다. Grover 알고리즘에 대한 자세한 내용은 Qiskit 교재에서 Grover 알고리즘 을 참조하기 바란다.

Qiskit은 Grover 클래스에서 Grover의 알고리즘을 구현한다. 이 클래스에는 일반화된 버전인 진폭 증폭 [3] 이 포함되며, 개별 반복 및 기타 메타 설정을 Grover의 알고리즘으로 설정할 수 있다.

참조:

[1]: L. K. Grover, A fast quantum mechanical algorithm for database search. Proceedings 28th Annual Symposium on the Theory of Computing (STOC) 1996, pp. 212-219. https://arxiv.org/abs/quant-ph/9605043

[2]: A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization. https://arxiv.org/abs/1912.04088

[3]: Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000). Quantum Amplitude Amplification and Estimation. http://arxiv.org/abs/quant-ph/0005055

그로버 알고리즘

그로버 알고리즘은 그로버 연산자 \(\mathcal{Q}\) 를 사용해서 좋은 상태들의 진폭을 증폭시킨다.

\[\mathcal{Q} = \mathcal{A}\mathcal{S_0}\mathcal{A}^\dagger \mathcal{S_f}\]

여기서, * \(\mathcal{A}\) 는 알고리즘의 초기 탐색 상태이며, 이는 하다마드 (Hadamards), 그로버(Grover) 검색 교과서의 경우 \(H^{\otimes n}\) 로도 나타낼 수 있지만 이와 같이 표시할 경우 모든 큐비트가 0인 상태를 나타내는 진폭 증폭 (Amplitude Amplification) * \(\mathcal{S_0}\) 에 대해 더 자세히 설명할 수 있다.

\[\begin{split}|x\rangle \mapsto \begin{cases} -|x\rangle, &x \neq 0 \\ |x\rangle, &x = 0\end{cases}\end{split}\]

* \(\mathcal{S_f}\) 는 적용되는 오라클이며

\[|x\rangle \mapsto (-1)^{f(x)}|x\rangle\]

여기서 \(x\) 가 바람직한 상태일 때, \(f(x)\) 는 1이고, 그렇지 않으면 0이다.

간단히 말해서, 그로버 알고리즘은 \(\mathcal{Q}\) 를 다양한 지수(power)로 적용하여 실행한 후, 각 실행에서 좋은 솔루션이 있는지를 확인한다.

그로버 알고리즘 실행하기

그로버 알고리즘을 Grover 클래스로 실행하려면 먼저 그로버 알고리즘 회로에 오라클을 지정해야 한다. 다음 예에서 우리는 QuantumCircuit 을 그로버 알고리즘의 오라클로 사용한다. 하지만, 그로버 알고리즘의 오라클로 사용할 수 있는 몇 가지 다른 클래스가 있다. 이들에 대해 우리는 이 사용 지침서의 뒷부분에서 이야기한다.

Grover 오라클에는 phase-flip 오라클이 있다는 것을 주목하라. 즉, “좋은 상태” 의 진폭을 \(-1\) 로 곱하는 것이다. 우리는 나중에 다시 한 번 비트-플립 오라클을 위상-플립으로 변환하는 방법을 설명한다.

from qiskit import QuantumCircuit
from qiskit.algorithms import AmplificationProblem

# the state we desire to find is '11'
good_state = ['11']

# specify the oracle that marks the state '11' as a good solution
oracle = QuantumCircuit(2)
oracle.cz(0, 1)

# define Grover's algorithm
problem = AmplificationProblem(oracle, is_good_state=good_state)

# now we can have a look at the Grover operator that is used in running the algorithm
# (Algorithm circuits are wrapped in a gate to appear in composition as a block
# so we have to decompose() the op to see it expanded into its component gates.)
problem.grover_operator.decompose().draw(output='mpl')

다음으로, 백엔드를 지정하고 Grover 의 run 메서드를 백엔드와 함께 호출하여 회로를 실행한다. 반환된 결과 유형은 GroverResult 이다.

만약 검색이 성공하면 도출된 결과의 oracle_evaluation 속성은 참 이 될 것이다. 이 경우에는, 가장 샘플화된 측정인 top_measurement 는 “좋은 상태” 중 하나이며 그렇지 않다면 oracle_evaluation 은 거짓이 될 것이다.

from qiskit.algorithms import Grover
from qiskit.primitives import Sampler


grover = Grover(sampler=Sampler())
result = grover.amplify(problem)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Result type: <class 'qiskit.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

예를 들어, top_measurement 의 결과는 11 이다. 11 은 좋은 상태 중 하나이다. 그래서 우리는 Grover 를 이용해 답을 찾는 데 성공했다.

다양한 유형의 클래스를 Grover 의 오라클로 사용하기

위의 예에서 우리는 QuantumCircuit 을 Grover 의 오라클로 사용했다. 그러나 우리는 또한 qiskit.quantum_info.Statevector 를 오라클로 사용할 수도 있다. 다음의 예제들은 모두 \(|11\rangle\) 가 “좋은 상태”일때 이다.

from qiskit.quantum_info import Statevector
oracle = Statevector.from_label('11')
problem = AmplificationProblem(oracle, is_good_state=['11'])

grover = Grover(sampler=Sampler())
result = grover.amplify(problem)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Result type: <class 'qiskit.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

내부적으로, 상태 벡터는 양자 회로로 대응된다.

problem.grover_operator.oracle.decompose().draw(output='mpl')

Qiskit을 사용하면 보다 복잡한 오라클을 쉽게 구성할 수 있다. * PhaseOracle: '~a | b' 와 같은 논리 식을 구문 분석하는 데 사용된다. 이는 3-SAT 문제를 해결하는 데 특히 유용하며 Grover Examples 사용 지침서에 나와 있다.

여기서는 'a & b' 에 해당하는 상태 \(|11\rangle\) 를 찾는 간단한 예제로 PhaseOracle 을 사용한다.

from qiskit.circuit.library.phase_oracle import PhaseOracle
from qiskit.exceptions import MissingOptionalLibraryError

# `Oracle` (`PhaseOracle`) as the `oracle` argument
expression = '(a & b)'
try:
    oracle = PhaseOracle(expression)
    problem = AmplificationProblem(oracle)
    display(problem.grover_operator.oracle.decompose().draw(output='mpl'))
except MissingOptionalLibraryError as ex:
    print(ex)

이는 상태가 \(|11\rangle\) 일 때 오라클이 위상을 반전시키는 것을 관측한다.

앞서 언급한 대로, Grover 알고리즘은 위상-반전 오라클을 필요로 한다. 비트-반전 오라클은 다른 큐비트들이 조건을 충족하면 보조 큐비트의 상태를 반전시킨다. Grover 알고리즘에서 이러한 유형의 오라클들을 사용하려면 비트-반전 오라클을 \(X\) 와 \(H\) 게이트로 샌드위치처럼 감쌈으로써 비트-반전 오라클을 위상-반전 오라클로 바꿀 필요가 있다.

참고: 비트-플립에서 위상-플립 오라클로의 이러한 변환은 일반적으로 유지되며, 이를 사용하여 오라클을 올바른 표현으로 변환할 수 있다.

진폭 증폭

Grover 알고리즘은 하다마드 (Hadamard) 게이트를 사용하여 Grover 연산자 \(\mathcal{Q}\) 의 시작 부분에 모든 상태의 균일 중첩을 만든다. 좋은 상태에 대한 일부 정보를 사용할 수 있는 경우 균일 중첩 상태에서 시작하지 않고 특정 상태만 초기화하는 것이 유용할 수 있다. 이와 같이 일반화된 버전의 Grover 알고리즘을 Amplitude Amplification 이라고 한다.

Qiskit에서 초기 중첩 상태는 state_preparation 전달인자를 설정하여 쉽게 조정할 수 있다.

상태 준비

state_preparation 인자는 진폭 증폭의 시작점인 양자 상태를 준비하는 양자 회로를 명시하기 위해 사용된다. 기본적으로 \(H^{\otimes n}\) 을 포함한 회로는 (Grover의 검색을 위한) 균일한 중첩 상태를 준비하기 위해 사용된다. 진폭 증폭의 확산 (diffusion) 회로는 자동으로 state_preparation 를 반영한다.

import numpy as np

# Specifying `state_preparation`
# to prepare a superposition of |01>, |10>, and |11>
oracle = QuantumCircuit(3)
oracle.ccz(0, 1, 2)

theta = 2 * np.arccos(1 / np.sqrt(3))
state_preparation = QuantumCircuit(3)
state_preparation.ry(theta, 0)
state_preparation.ch(0,1)
state_preparation.x(1)
state_preparation.h(2)

# we only care about the first two bits being in state 1, thus add both possibilities for the last qubit
problem = AmplificationProblem(oracle, state_preparation=state_preparation, is_good_state=['110', '111'])

# state_preparation
print('state preparation circuit:')
problem.grover_operator.state_preparation.draw(output='mpl')

state preparation circuit:

grover = Grover(sampler=Sampler())
result = grover.amplify(problem)
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Success!
Top measurement: 111

완전한 유연성

고급 사용을 위해서는 grover_operator 인수를 설정하여 전체 그로버 연산자를 지정할 수도 있다. 이는 0을 기준으로 한 반사, 오라클및 상태 준비를 통해 기본 구성보다 \(\mathcal{Q}\) 의 효율적인 구현을 알고 있는 경우에 유용할 수 있다.

qiskit.circuit.library.GroverOperator 는 좋은 출발점이 될 수 있으며 Grover 오퍼레이터의 자동화된 구성을 위한 더 많은 옵션을 제공한다. 예를 들어 reflection_qubits 가 oracle, zero_reflection 및 state_preparation 인수를 사용하여 \(\mathcal{S_f}, \mathcal{S_0}\) 및 \(\mathcal{A}\) 연산을 명시적으로 교환하도록 설정하여 zero reflection에서 큐비트를 무시하도록 mcx_mode 를 설정할 수 있다.

예를 들어, 좋은 상태는 3개의 큐비트 상태 ( \(|111\rangle\)) 이지만, 2개의 추가적인 큐비트를 사용했다고 가정해보자.

oracle = QuantumCircuit(5)
oracle.ccz(0, 1, 2)
oracle.draw(output='mpl')

그 다음, 기본적으로, 그로버 연산자는 5개의 모든 큐비트에 대해 제로 반사를 구현한다.

from qiskit.circuit.library import GroverOperator
grover_op = GroverOperator(oracle, insert_barriers=True)
grover_op.decompose().draw(output='mpl')

하지만 우리는 처음 세 가지만을 고려해도 된다는 것을 알고 있다.

grover_op = GroverOperator(oracle, reflection_qubits=[0, 1, 2], insert_barriers=True)
grover_op.decompose().draw(output='mpl')

Grover 의 여러 인수들에 대하여 알아보기

Grover 는 oracle 과 state_preparation 이외에도 여러 인수들을 가지고 있다. 이 섹션에서는 이에 대하여 설명할 것이다.

good_state 를 지정하기

good_state 는 측정 결과가 내부적으로 올바른지 여부를 확인하는 데 사용된다. 이는 바이너리 문자열 리스트, 정수 리스트, Statevector 및 Callable일 수 있다. 입력이 비트 문자열 리스트인 경우 리스트의 각 비트 문자열은 좋은 상태(good state)를 나타낸다. 입력이 정수 리스트인 경우 각 정수는 좋은 상태의 인덱스가 \(|1\rangle\) 임을 나타낸다. 입력이 Statevector 이면 모든 좋은 상태의 중첩을 나타낸다.

# a list of binary strings good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = ['11', '00']
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

# a list of integer good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = [0, 1]
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

from qiskit.quantum_info import Statevector

# `Statevector` good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = Statevector.from_label('11')
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

# Callable good state
def callable_good_state(bitstr):
    if bitstr == "11":
        return True
    return False

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

iterations 의 횟수

Grover 알고리즘을 사용하여 올바른 결과를 얻으려면 Grover 연산자를 적용하는 반복 횟수가 중요하다. 반복 횟수는 Grover 의 iteration 인수로 설정할 수 있다. 다음과 같은 입력이 지원된다: * 적용되는 Grover 연산자의 단일 거듭 제곱(a single power) 을 지정하는 정수 * 또는 Grover 연산자의 이러한 모든 서로 다른 거듭 제곱이 연속적으로 실행되며 올바른 솔루션을 찾았다면 매번 다음과 같은지 확인한다.

이와 더불어 sample_from_iterations 인수가 있다. True 이면 iterations 의 특정 거듭 제곱 대신 0과 iterations 의 값 사이의 임의의 정수가 그로버 연산자의 제곱으로 사용된다. 이러한 접근 방식은 솔루션의 개수를 모를 때 조차도 유용하다.

sample_from_iterations 를 사용하는 알고리즘에 대한 자세한 내용은 [4] 를 참조하라.

참조:

[4]: Boyer et al., Tight bounds on quantum searching arxiv:quant-ph/9605034

# integer iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=1)

# list iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=[1, 2, 3])

# using sample_from_iterations
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=[1, 2, 3], sample_from_iterations=True)

솔루션의 개수를 알고있는 경우 정적 메서드 optimal_num_iterations 를 사용하여 최적의 반복 횟수를 찾을 수도 있다. 출력된 반복 횟수는 대략적인(approximate) 값임에 주의하여야 한다. 큐비트 수가 적으면 출력된 값은 최적이 아닐 수도 있다.

iterations = Grover.optimal_num_iterations(num_solutions=1, num_qubits=8)
iterations

12

post_processing 적용하기

가독성을 높이기 위해 상단 측정에 선택적 후처리를 적용할 수 있다. 이는 예를 들어 측정된 [1, 0, 1] 의 비트 표현 형식으로부터 DIMACS CNF 형식의 [1, -2, 3] 으로 변환하는 데 사용될 수 있다.

def to_DIAMACS_CNF_format(bit_rep):
    return [index+1 if val==1 else -1 * (index + 1) for index, val in enumerate(bit_rep)]

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'], post_processing=to_DIAMACS_CNF_format)
problem.post_processing([1, 0, 1])

[1, -2, 3]

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
qiskit-terra	0.23.0.dev0+0f6c75e
qiskit-aer	0.11.1
qiskit-optimization	0.5.0
System information
Python version	3.9.10
Python compiler	Clang 13.1.6 (clang-1316.0.21.2.5)
Python build	main, Aug 9 2022 18:26:17
OS	Darwin
CPUs	10
Memory (Gb)	64.0
Fri Nov 25 21:25:09 2022 JST

This code is a part of Qiskit

© Copyright IBM 2017, 2022.

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.