참고

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

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

그로버 알고리즘 예제들

본 노트북에는 Grover 검색 알고리즘을 다양한 오라클과 함께 사용하는 방법을 설명하는 예제가 있다.

import pylab
import numpy as np
from qiskit import BasicAer
from qiskit.tools.visualization import plot_histogram
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Grover
from qiskit.aqua.components.oracles import LogicalExpressionOracle, TruthTableOracle

3-SAT 문제에 대한 해결책 찾기

3-SAT (3-Satisfiability) 문제의 예를 살펴보고 Quantum Search를 사용하여 만족스러운 솔루션을 찾는 방법을 살펴보겠다. 3-SAT 문제는 일반적으로 Conjunctive Normal Forms (CNF) 로 표현되고 DIMACS-CNF 형식으로 작성된다. 예를 들면:

input_3sat_instance = '''
c example DIMACS-CNF 3-SAT
p cnf 3 5
-1 -2 -3 0
1 -2 3 0
1 2 -3 0
1 -2 -3 0
-1 2 3 0
'''

이 3-SAT 인스턴스의 CNF는 3개의 변수와 5개의 절을 포함한다:

\((\neg v_1 \vee \neg v_2 \vee \neg v_3) \wedge (v_1 \vee \neg v_2 \vee v_3) \wedge (v_1 \vee v_2 \vee \neg v_3) \wedge (v_1 \vee \neg v_2 \vee \neg v_3) \wedge (\neg v_1 \vee v_2 \vee v_3)\)

이 3-SAT 문제 인스턴스는 다음과 같은 세 가지 해결책을 갖고 있다는 것을 확인할 수 있다.

\((v_1, v_2, v_3) = (T, F, T)\) or \((F, F, F)\) or \((T, T, F)\)

또는 DIMACS 표기법을 사용하여 표현하시오.

1 -2 3 혹은 -1 -2 -3 혹은 1 2 -3.

이 예제 문제 입력을 통해 우리는 Grover 검색을 위해 해당 oracle 을 작성한다. 특히, 여기에는 LogicalExpressionOracle 성분을 사용하는데, 이는 DIMACS-CNF 포맷 문자열의 파싱 및 대응하는 oracle 회로를 구성하는 것을 지원한다.

oracle = LogicalExpressionOracle(input_3sat_instance)

이제 Grover 인스턴스를 생성하는 데 oracle 을 사용할 수 있다.

grover = Grover(oracle)

그런 다음 백엔드를 구성하고 Grover 인스턴스를 실행하여 결과를 얻을 수 있다.

backend = BasicAer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
result = grover.run(quantum_instance)
print(result.assignment)

[1, 2, -3]

위에서 볼 수 있듯이 지정된 3-SAT 문제에 대한 만족스러운 솔루션을 얻는다. 그리고 획득한 솔루션은 실제로 세 가지 만족스러운 솔루션 중 하나이다.

'qasm_simulator' 를 사용했기 때문에, 아래의 플롯과 같이 전체 측정 결과도 반환된다. 여기서 바이너리 문자열 000``과 ``011``과 ``101 (각 문자열의 비트 순서에 주의) 들은 모두 이에 대응되는 높은 확률을 갖는 3 개의 만족하는 솔루션에 대응한다.

plot_histogram(result.measurement)

불리언(Boolean) 논리 표현식

키스킷의 Grover 는 또한 DIMM외에 다른 방법으로 구성된 Oracle 에서 퀀텀 서치(Quantum Search) 를 수행하는 데 사용될 수 있다. 예를 들어, LogicalExpressionOracle 은 실제로 임의의 불리언 논리식을 사용하여 구성할 수 있다.

expression = '(w ^ x) & ~(y ^ z) & (x & y & z)'
oracle = LogicalExpressionOracle(expression)
grover = Grover(oracle)
result = grover.run(QuantumInstance(BasicAer.get_backend('qasm_simulator'), shots=1024))
plot_histogram(result.measurement)

위의 예에서, 입련된 불리언 논리 표현식 '(w ^ x) & ~(y ^ z) & (x & y & z)' 은 상당히 스스로 설명가능(self-explanatory) 해야 하는데, ^, ~, & 는 각각 불리언 논리 XOR, NOT, AND 오퍼레이터를 나타낸다. 각 요소들을 살펴보면 만족스러운 솔루션을 쉽게 찾을 수 있다: w ^ x 는 w 와 x 가 서로 다른 값을 갖도록; ~(y ^ z) 는 y 와 z 가 같은 값을 갖도록; x & y & z 는 모든 세 값이 반드시 True 가 되도록 호출한다. 이를 종합해보면, Grover 들의 결과와 일치하는 만족스러운 솔루션 (w, x, y, z) = (False, True, True, True) 를 얻는다.

오라클의 진리표

키스킷을 사용하면 Oracle 들 또한 진리표에서 구성될 수 있으며, 이는 또한 진리표에서 Quantum Search를 수행할 수 있다는 것을 의미한다. 진리표에서 \(1\) 값을 탐색하는 것이 논점(moot point)처럼 보여질 수 있지만, 이는 여전히 설명을 위한 좋은 예이다.

truthtable = '1000000000000001'

표시된 바와 같이, truthtable 은 테이블에 있는 모든 항목의 값을 포함하는 비트 문자열로 지정된다. 길이는 \(16\) 입력 비트이다. 첫 번째 값과 마지막 값은 \(1\) 이므로 해당하는 진리표 목표 항목은 0000 와 1111 이다.

다음으로 Oracle 와 Grover 객체를 설정하여 평소와 같이 Quantum Search를 수행할 수 있다.

oracle = TruthTableOracle(truthtable)
grover = Grover(oracle)
result = grover.run(QuantumInstance(BasicAer.get_backend('qasm_simulator'), shots=1024))
plot_histogram(result.measurement)

위에서 볼 수 있는 바와 같이, 검색 결과는 우리의 기대와 일치한다.

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:26:36 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.