70 lines
2.2 KiB
Python
70 lines
2.2 KiB
Python
# Full circuit + example: https://cstheory.stackexchange.com/questions/38538/oracle-construction-for-grovers-algorithm
|
||
# X-Axis control: https://algassert.com/post/1706
|
||
# http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm
|
||
import itertools
|
||
import random
|
||
from pprint import pprint
|
||
|
||
|
||
def classical_func_search_multi_rv(func, input_range):
|
||
"""Grover’s algorithm takes a function, searches through
|
||
the implicit list of possible inputs to that function, and
|
||
returns inputs that causes the function to return true.
|
||
"""
|
||
rv = []
|
||
for i, params in enumerate(input_range):
|
||
result = func(params)
|
||
if result:
|
||
rv.append(params)
|
||
return rv
|
||
|
||
|
||
def classical_func_search_single_rv(func, input_range):
|
||
"""Grover’s algorithm takes a function, searches through
|
||
the implicit list of possible inputs to that function, and
|
||
returns EXACTLY ONE input that causes the function to return true.
|
||
"""
|
||
rv = None
|
||
for i, params in enumerate(input_range):
|
||
result = func(params)
|
||
if result and rv is None:
|
||
rv = result
|
||
else:
|
||
raise Exception("Exactly one result is needed")
|
||
return rv
|
||
|
||
|
||
def _3sat(params):
|
||
# 3-SAT from here: https://qiskit.org/textbook/ch-applications/satisfiability-grover.html
|
||
x1, x2, x3 = params
|
||
return (not x1 or not x2 or not x3) and \
|
||
(x1 or not x2 or x3) and \
|
||
(x1 or x2 or not x3) and \
|
||
(x1 or not x2 or not x3) and \
|
||
(not x1 or x2 or x3)
|
||
|
||
|
||
def _3sat_2(params):
|
||
# 3-SAT from here: https://cstheory.stackexchange.com/questions/38538/oracle-construction-for-grovers-algorithm
|
||
x1, x2, x3, x4 = params
|
||
return (not x1 or not x3 or not x4) and \
|
||
(x2 or x3 or not x4) and \
|
||
(x1 or not x2 or x4) and \
|
||
(x1 or x3 or x4) and \
|
||
(not x1 or x2 or not x3)
|
||
|
||
|
||
def classical_3sat(func):
|
||
# Generate all possible true/false tuples for the 3-sat problem
|
||
input_range = list(itertools.product([True, False], repeat=3))
|
||
random.shuffle(input_range)
|
||
return classical_func_search_multi_rv(func, input_range)
|
||
|
||
|
||
def main():
|
||
pprint(classical_3sat(_3sat))
|
||
|
||
|
||
if __name__ == "__main__":
|
||
main()
|