7567300363

Committed 18 Jan 2024 08:32AM UTC coverage: 99.83%. Remained the same

Build # 7567300363

Build Type

push

github

Committed by

web-flow

Commit Message

Prepare for release 1.1.0 (#120)

Run Details

2353 of 2357 relevant lines covered (99.83%)

3.97 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0

/examples/grover-3-sat.py

# This code is part of Qiskit.
#
# (C) Copyright Alpine Quantum Technologies GmbH 2023
#
# 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.

"""3-SAT solving example using the Grover algorithm.

This is a modified version of the corresponding
[Qiskit tutorial](https://qiskit.org/documentation/tutorials/algorithms/07_grover_examples.html).
"""
import tempfile
import textwrap
from typing import Final, Set, Tuple

from qiskit.circuit.library.phase_oracle import PhaseOracle
from qiskit_algorithms import AmplificationProblem, Grover

from qiskit_aqt_provider import AQTProvider
from qiskit_aqt_provider.primitives import AQTSampler


class ThreeSatProblem:
    """A 3-SAT problem, defined as DIMACS-CNF."""

    def __init__(self, dimacs_cnf: str, *, num_solutions: int):
        with tempfile.NamedTemporaryFile(mode="w+t", encoding="ascii") as fp:
            fp.write(dimacs_cnf)
            fp.flush()

            self.func = tweedledum.BoolFunction.from_dimacs_file(fp.name)
            self.oracle = PhaseOracle.from_dimacs_file(fp.name)
            self.num_solutions = num_solutions

    def is_solution(self, bits: str) -> bool:
        """Whether the given bitstring is a solution to the problem."""
        args = [tweedledum.BitVec(bit) for bit in reversed(bits)]
        return bool(self.func.simulate(*args))


def format_bitstring(bits: str) -> Tuple[bool, ...]:
    """Format a bitstring as tuple of boolean values.

    Warning: this reverses the bit order.
    In `bits`, the order is MSB-first. In the return value,
    the order is LSB-first.

    >>> format_bitstring("110")
    (False, True, True)

    >>> format_bitstring("001")
    (True, False, False)
    """
    return tuple(bool(int(bit)) for bit in reversed(bits))


if __name__ == "__main__":
    import sys

    try:
        import tweedledum
    except ImportError:  # pragma: no cover
        print("Tweedledum not available: example not supported.", file=sys.stderr)
        sys.exit(0)  # not a critical error

    # Problem definition
    sat_problem = ThreeSatProblem(
        textwrap.dedent(
            """
            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
            """
        ),
        num_solutions=3,
    )

    # Select the sampling engine
    backend = AQTProvider("token").get_backend("offline_simulator_no_noise")
    sampler = AQTSampler(backend)

    # Map the problem to a Grover search
    problem = AmplificationProblem(sat_problem.oracle, is_good_state=sat_problem.is_solution)
    grover = Grover(
        iterations=Grover.optimal_num_iterations(sat_problem.num_solutions, 3), sampler=sampler
    )

    # Run the Grover search until all solutions are found
    MAX_ITERATIONS: Final = 100
    solutions: Set[str] = set()
    for _ in range(MAX_ITERATIONS):
        solutions.add(grover.amplify(problem).assignment)
        if len(solutions) == sat_problem.num_solutions:
            break
    else:  # pragma: no cover
        raise RuntimeError(f"Didn't find all solutions in {MAX_ITERATIONS} iterations.")

    for solution in solutions:
        print(format_bitstring(solution))

1	# This code is part of Qiskit.
2	#
3	# (C) Copyright Alpine Quantum Technologies GmbH 2023
4	#
5	# This code is licensed under the Apache License, Version 2.0. You may
6	# obtain a copy of this license in the LICENSE.txt file in the root directory
7	# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
8	#
9	# Any modifications or derivative works of this code must retain this
10	# copyright notice, and modified files need to carry a notice indicating
11	# that they have been altered from the originals.
12
13	"""3-SAT solving example using the Grover algorithm.	4✔
14
15	This is a modified version of the corresponding
16	[Qiskit tutorial](https://qiskit.org/documentation/tutorials/algorithms/07_grover_examples.html).
17	"""
18	import tempfile	4✔
19	import textwrap	4✔
20	from typing import Final, Set, Tuple	4✔
21
22	from qiskit.circuit.library.phase_oracle import PhaseOracle	4✔
23	from qiskit_algorithms import AmplificationProblem, Grover	4✔
24
25	from qiskit_aqt_provider import AQTProvider	4✔
26	from qiskit_aqt_provider.primitives import AQTSampler	4✔
27
28
29	class ThreeSatProblem:	4✔
30	"""A 3-SAT problem, defined as DIMACS-CNF."""	4✔
31
32	def __init__(self, dimacs_cnf: str, *, num_solutions: int):	4✔
33	with tempfile.NamedTemporaryFile(mode="w+t", encoding="ascii") as fp:	3✔
34	fp.write(dimacs_cnf)	3✔
35	fp.flush()	3✔
36
37	self.func = tweedledum.BoolFunction.from_dimacs_file(fp.name)	3✔
38	self.oracle = PhaseOracle.from_dimacs_file(fp.name)	3✔
39	self.num_solutions = num_solutions	3✔
40
41	def is_solution(self, bits: str) -> bool:	4✔
42	"""Whether the given bitstring is a solution to the problem."""
43	args = [tweedledum.BitVec(bit) for bit in reversed(bits)]	3✔
44	return bool(self.func.simulate(*args))	3✔
45
46
47	def format_bitstring(bits: str) -> Tuple[bool, ...]:	4✔
48	"""Format a bitstring as tuple of boolean values.
49
50	Warning: this reverses the bit order.
51	In `bits`, the order is MSB-first. In the return value,
52	the order is LSB-first.
53
54	>>> format_bitstring("110")
55	(False, True, True)
56
57	>>> format_bitstring("001")
58	(True, False, False)
59	"""
60	return tuple(bool(int(bit)) for bit in reversed(bits))	4✔
61
62
63	if __name__ == "__main__":	4✔
64	import sys	4✔
65
66	try:	4✔
67	import tweedledum	4✔
68	except ImportError: # pragma: no cover
69	print("Tweedledum not available: example not supported.", file=sys.stderr)
70	sys.exit(0) # not a critical error
71
72	# Problem definition
73	sat_problem = ThreeSatProblem(	3✔
74	textwrap.dedent(
75	"""
76	c example DIMACS-CNF 3-SAT
77	p cnf 3 5
78	-1 -2 -3 0
79	1 -2 3 0
80	1 2 -3 0
81	1 -2 -3 0
82	-1 2 3 0
83	"""
84	),
85	num_solutions=3,
86	)
87
88	# Select the sampling engine
89	backend = AQTProvider("token").get_backend("offline_simulator_no_noise")	3✔
90	sampler = AQTSampler(backend)	3✔
91
92	# Map the problem to a Grover search
93	problem = AmplificationProblem(sat_problem.oracle, is_good_state=sat_problem.is_solution)	3✔
94	grover = Grover(	3✔
95	iterations=Grover.optimal_num_iterations(sat_problem.num_solutions, 3), sampler=sampler
96	)
97
98	# Run the Grover search until all solutions are found
99	MAX_ITERATIONS: Final = 100	3✔
100	solutions: Set[str] = set()	3✔
101	for _ in range(MAX_ITERATIONS):	3✔
102	solutions.add(grover.amplify(problem).assignment)	3✔
103	if len(solutions) == sat_problem.num_solutions:	3✔
104	break	3✔
105	else: # pragma: no cover
106	raise RuntimeError(f"Didn't find all solutions in {MAX_ITERATIONS} iterations.")
107
108	for solution in solutions:	3✔
109	print(format_bitstring(solution))	3✔

qiskit-community / qiskit-aqt-provider / 7567300363

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous