참고

이 페이지는 tutorials/algorithms/07_grover.ipynb 에서 생성되었다.

IBM 퀀텀 랩 에서 대화식으로 실행하시오.

Grover 알고리즘 및 확률진폭 증폭

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

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

그로버 알고리즘

Grover의 알고리즘은 Grover 연산자 \(\mathcal{Q}\) 를 사용하여 우수한 상태의 진폭을 확대한다.

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

여기서, * \(\mathcal{A}\) 는 알고리즘의 초기 탐색 상태이며, 이는 Hadamards, Grover search 사용 지침서의 경우 \(H^{\otimes n}\) 로도 나타낼 수 있지만 이와 같이 표시할 경우 진폭 증폭 (Amplitude Amplification)에 대해 더 자세히 설명할 수 있다. * :math:’mathcal{S_0}’ 는 모든 큐비트가 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의 알고리즘을 Grover 클래스로 실행하려면 먼저 Grover의 알고리즘 회로에 oracle을 지정해야 한다. 다음 예에서 우리는 QuantumCircuit 를 Grover의 알고리즘의 장으로 사용한다. 하지만, 우리가 Grover의 알고리즘의 oracle로 사용할 수 있는 몇 가지 다른 클래스가 있다. 이 튜토리얼에서 나중에 설명한다.

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

from qiskit import QuantumCircuit
from qiskit.aqua.algorithms import Grover

# 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
grover = Grover(oracle=oracle, good_state=good_state)

# now we can have a look at the Grover operator that is used in running the algorithm
grover.grover_operator.draw(output='mpl')

<matplotlib.figure.Figure at 0x7f359572eba8>

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

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

from qiskit import Aer
from qiskit.aqua import QuantumInstance

qasm_simulator = Aer.get_backend('qasm_simulator')
result = grover.run(quantum_instance=qasm_simulator)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

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

Success!
Top measurement: 11

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

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

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

from qiskit.quantum_info import Statevector
oracle = Statevector.from_label('11')
grover = Grover(oracle=oracle, good_state=['11'])

result = grover.run(quantum_instance=qasm_simulator)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

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

Success!
Top measurement: 11

내부적으로 상태 벡터는 다음과 같이 퀀텀 회로에 나타낸다.

grover.grover_operator.oracle.draw(output='mpl')

키스킷 아쿠아의 Oracle 구성요소를 사용하면 더 복잡한 오라클을 쉽게 구성할 수 있다. Oracle 유형은 흥미로운 하위 클래스를 갖는다: * LogicalExpressionOracle: '~a | b' 와 같은 논리 표현식을 구문 분석하는 데 사용된다. 이는 특히 3-SAT 문제를 해결하는 데 유용하며 함께 제공되는 Grover Examples 사용 지침서에서 확인할 수 있다. * TrutheTableOracle: 바이너리 진리표를 회로로 변환하는 데 사용된다.

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

from qiskit.aqua.components.oracles import LogicalExpressionOracle

# `Oracle` (`LogicalExpressionOracle`) as the `oracle` argument
expression = '(a & b)'
oracle = LogicalExpressionOracle(expression)
grover = Grover(oracle=oracle)
grover.grover_operator.oracle.draw(output='mpl')

여러분은 이것이 실제로 2개가 아니라 3개의 큐비트로 구현된다는 것을 관찰할 수 있습니다!

LogicalExpressionOracle 은 (좋은 상태의 위상을 뒤집는) 위상 반전 오라클이 아니라 비트 플립 오라클이기 때문이다. 즉, 다른 큐비트가 조건을 충족하면 보조(auxiliary) 큐비트의 상태를 뒤집는다. 그러나 Grover 알고리즘의 경우 위상 반전 오라클이 필요하다. 비트 플립 오라클을 위상 플립 오라클로 변환하기 위하여 위의 회로에서 볼 수 있듯 controlled–NOT 게이트의 좌우에 \(X\) 와 \(H\) 게이트를 배치하여 샌드위치 형태로 감싼다.

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

진폭 증폭

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

키스킷에서 초기 중첩 상태는 state_preparation 인수를 설정하여 쉽게 조정할 수 있다.

상태 준비

A state_preparation argument is used to specify a quantum circuit that prepares a quantum state for the start point of the amplitude amplification. By default, a circuit with \(H^{\otimes n}\) is used to prepare uniform superposition (so it will be Grover’s search). The diffusion circuit of the amplitude amplification reflects state_preparation automatically.

import numpy as np

# Specifying `state_preparation`
# to prepare a superposition of |01>, |10>, and |11>
oracle = QuantumCircuit(3)
oracle.h(2)
oracle.ccx(0,1,2)
oracle.h(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
grover = Grover(oracle=oracle, state_preparation=state_preparation, good_state=['110', '111'])

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

state preparation circuit:

result = grover.run(quantum_instance=qasm_simulator)
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Success!
Top measurement: 111

유연성

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

The qiskit.circuit.library.GroverOperator can be a good starting point and offers more options for an automated construction of the Grover operator. You can for instance

• set the mcx_mode

• ignore qubits in the zero reflection by setting reflection_qubits

• explicitly exchange the \(\mathcal{S_f}, \mathcal{S_0}\) and \(\mathcal{A}\) operations using the oracle, zero_reflection and state_preparation arguments

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

from qiskit.circuit.library import GroverOperator, ZGate

oracle = QuantumCircuit(5)
oracle.append(ZGate().control(2), [0, 1, 2])
oracle.draw(output='mpl')

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

grover_op = GroverOperator(oracle, insert_barriers=True)
grover_op.draw(output='mpl')

하지만 우리는 처음 세 가지를 고려해야 한다는 것을 알고 있다.

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

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

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

good_state 를 지정하기

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

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

True

# a list of integer good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = [0, 1]
grover = Grover(oracle=oracle, good_state=good_state)
print(grover.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')
grover = Grover(oracle=oracle, good_state=good_state)
print(grover.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)
grover = Grover(oracle=oracle, good_state=callable_good_state)
print(grover.is_good_state('11'))

True

iterations 의 횟수

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

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

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)
grover = Grover(oracle=oracle, good_state=['11'], iterations=1)

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

# using sample_from_iterations
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
grover = Grover(oracle=oracle, good_state=['11'], 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)
grover = Grover(oracle=oracle, good_state=['11'],post_processing=to_DIAMACS_CNF_format)
grover.post_processing([1, 0, 1])

[1, -2, 3]

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	0.23.0
Terra	0.16.0
Aer	0.7.0
Ignis	0.5.0
Aqua	0.8.0
IBM Q Provider	0.11.0
System information
Python	3.6.1 |Continuum Analytics, Inc.| (default, May 11 2017, 13:09:58) [GCC 4.4.7 20120313 (Red Hat 4.4.7-1)]
OS	Linux
CPUs	1
Memory (Gb)	5.827335357666016
Sun Nov 08 17:30:57 2020 EST

This code is a part of Qiskit

© Copyright IBM 2017, 2020.

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.