Grover’s algorithm examples¶

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

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

Let’s look at an example 3-Satisfiability (3-SAT) problem and walk-through how we can use Quantum Search to find its satisfying solutions. 3-SAT problems are usually expressed in Conjunctive Normal Forms (CNF) and written in the DIMACS-CNF format. For example:

[1]:

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 을 작성한다. 특히, 여기에는 PhaseOracle 성분을 사용하는데, 이는 DIMACS-CNF 형태 문자열의 파싱 및 대응하는 오라클 회로를 구성하는 것을 지원한다.

[2]:

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


fp = tempfile.NamedTemporaryFile(mode='w+t', delete=False)
fp.write(input_3sat_instance)
file_name = fp.name
fp.close()
oracle = None
try:
    oracle = PhaseOracle.from_dimacs_file(file_name)
except ImportError as ex:
    print(ex)
finally:
    os.remove(file_name)

"The 'tweedledum' library is required to use 'classical function oracles'. You can install it with 'pip install tweedledum'."

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

[3]:

from qiskit.algorithms import AmplificationProblem

problem = None
if oracle is not None:
    problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)

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

[4]:

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

grover = Grover(sampler=Sampler())
result = None
if problem is not None:
    result = grover.amplify(problem)
    print(result.assignment)

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

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

[5]:

from qiskit.tools.visualization import plot_histogram

if result is not None:
    display(plot_histogram(result.circuit_results[0]))

불리언(Boolean) 논리 표현식¶

Qiskit’s Grover can also be used to perform Quantum Search on an Oracle constructed from other means, in addition to DIMACS. For example, the PhaseOracle can actually be configured using arbitrary Boolean logical expressions, as demonstrated below.

[6]:

expression = '(w ^ x) & ~(y ^ z) & (x & y & z)'
try:
    oracle = PhaseOracle(expression)
    problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)
    grover = Grover(sampler=Sampler())
    result = grover.amplify(problem)
    display(plot_histogram(result.circuit_results[0]))
except MissingOptionalLibraryError as ex:
    print(ex)

"The 'tweedledum' library is required to use 'PhaseOracle'. You can install it with 'pip install tweedledum'."

In the example above, the input Boolean logical expression '(w ^ x) & ~(y ^ z) & (x & y & z)' should be quite self-explanatory, where ^, ~, and & represent the Boolean logical XOR, NOT, and AND operators, respectively. It should be quite easy to figure out the satisfying solution by examining its parts: w ^ x calls for w and x taking different values; ~(y ^ z) requires y and z be the same; x & y & z dictates all three to be True. Putting these together, we get the satisfying solution (w, x, y, z) = (False, True, True, True), which our Grover’s result agrees with.

[7]:

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
`qiskit-terra`	0.23.3
`qiskit-aer`	0.12.0
`qiskit-ibmq-provider`	0.20.2
`qiskit`	0.42.1
System information
Python version	3.10.10
Python compiler	GCC 12.2.1 20230201
Python build	main, Mar 5 2023 22:26:53
OS	Linux
CPUs	32
Memory (Gb)	125.66083908081055
Thu May 04 15:38:15 2023 EDT

This code is a part of Qiskit

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.

[ ]: