Grover’s algorithm examples¶

இந்த குறிப்பேடு Qiskit 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'."

க்ரோவர் உதாரணத்தை உருவாக்க 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 சிக்கலுக்கு திருப்திகரமான தீர்வு பெறப்படுகிறது. இது உண்மையில் மூன்று திருப்திகரமான தீர்வுகளில் ஒன்றாகும்.

நாங்கள் 'மாதிரி'யைப் பயன்படுத்தியதால், முழு அளவீட்டு முடிவும் திருப்பித் தரப்படுகிறது, கீழே உள்ள கதைக்களத்தில் காட்டப்பட்டுள்ளபடி, மூன்று திருப்திகரமான தீர்வுகளுடன் தொடர்புடைய பைனரி சரங்கள் '000', '011', மற்றும் '101' (ஒவ்வொரு சரத்திலும் உள்ள பிட் வரிசையைக் கவனியுங்கள்) அனைத்தும் அவற்றுடன் தொடர்புடைய அதிக நிகழ்தகவுகளைக் கொண்டுள்ளன என்பதைக் காணலாம்.

[5]:

from qiskit.tools.visualization import plot_histogram

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

பூலியன் தருக்க வெளிப்பாடுகள்¶

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.

[ ]: