跳转至

CNFSolver

QuICT.algorithm.quantum_algorithm.CNFSolver 

CNFSolver(cnf_file: str)

A solver for CNF satisfiability problem by using grover's search algorithm.

Parameters:

  • cnf_file (str) –

    Path to the cnf dimacs file.

Source code in QuICT/algorithm/quantum_algorithm/cnf_solver/cnf_solver.py 
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def __init__(self, cnf_file: str):
    """
    Args:
        cnf_file (str): Path to the cnf dimacs file.
    """
    self._file_path = cnf_file
    self._circuit = None

    self._var_num, self._cl_num, self._cnf_data = CNFSATOracle.read_CNF(cnf_file)

    self._grover = Grover(
        targ_bit_len=self._var_num,
        oracle=self._cnf_phase_oracle(self._var_num, self._cl_num, self._cnf_data)
    )

check_solution 

check_solution(assignment: str) -> bool

Check if the given assignment is a satisfying assignment for the cnf.

Parameters:

  • assignment (str) –

    the variable assignments to be tested.

Returns: bool, whether or not the cnf is satisfied.

Source code in QuICT/algorithm/quantum_algorithm/cnf_solver/cnf_solver.py 
80
81
82
83
84
85
86
87
88
89
def check_solution(self, assignment: str) -> bool:
    """ Check if the given assignment is a satisfying assignment for the cnf.

    Args:
        assignment: the variable assignments to be tested.

    Returns: bool, whether or not the cnf is satisfied.
    """

    return CNFSATOracle.check_solution([int(i) for i in assignment], self._var_num, self._cl_num, self._cnf_data)

circuit 

circuit(iteration: int) -> Circuit

Construct grover search circuit for cnf-sat problem.

Parameters:

  • iteration (int) –

    number of cnf oracle query in the circuit.

Returns: Circuit, the quantum circuit for cnf-sat problem with given iteration.

Source code in QuICT/algorithm/quantum_algorithm/cnf_solver/cnf_solver.py 
40
41
42
43
44
45
46
47
48
def circuit(self, iteration: int) -> Circuit:
    """ Construct grover search circuit for cnf-sat problem.

    Args:
        iteration (int): number of cnf oracle query in the circuit.

    Returns: Circuit, the quantum circuit for cnf-sat problem with given iteration.
    """
    return self._grover.circuit(iteration)

run 

run(n_solution: int, backend=StateVectorSimulator(), shots: int = 1) -> Dict[str, int]

Given number of solution, run cnf solver with the optimal grover iteration.

Parameters:

  • n_solution (int) –

    number of solutions for the cnf-sat problem.

  • backend (Any, default: StateVectorSimulator() ) –

    Device to run the quantum algorithm.

  • shots (int, default: 1 ) –

    Number of experiments to run.

Dict[str, int], a dictionary in which the key-value pairs are sample strings, denoting cnf

  • Dict[str, int] –

    variable assignments, with their number of times been sampled.

Source code in QuICT/algorithm/quantum_algorithm/cnf_solver/cnf_solver.py 
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def run(
    self,
    n_solution: int,
    backend=StateVectorSimulator(),
    shots: int = 1
) -> Dict[str, int]:
    """ Given number of solution, run cnf solver with the optimal grover iteration.

    Args:
        n_solution: number of solutions for the cnf-sat problem.
        backend (Any): Device to run the quantum algorithm.
        shots (int): Number of experiments to run.

    Returns: Dict[str, int], a dictionary in which the key-value pairs are sample strings, denoting cnf
        variable assignments, with their number of times been sampled.
    """
    return self._grover.run(n_solution, backend, shots)

run_iterative 

run_iterative(backend=StateVectorSimulator()) -> Union[Tuple[str, int], None]

Search by iterative grover without knowning the number of satisfiable solutions.

Parameters:

Tuple[str, int] | None, when success, the satisfying assignment and the number of

  • Union[Tuple[str, int], None] –

    oracle calls been used are returned.

Source code in QuICT/algorithm/quantum_algorithm/cnf_solver/cnf_solver.py 
68
69
70
71
72
73
74
75
76
77
78
def run_iterative(self, backend=StateVectorSimulator()) -> Union[Tuple[str, int], None]:
    """ Search by iterative grover without knowning the number of satisfiable solutions.

    Args:
        backend (Any): Device to run the quantum algorithm.

    Returns: Tuple[str, int] | None, when success, the satisfying assignment and the number of
        oracle calls been used are returned.
    """

    return self._grover.run_iterative(self.check_solution, backend)