13097520676

Committed 02 Feb 2025 09:25AM UTC coverage: 88.939% (+0.1%) from 88.826%

Build # 13097520676

Build Type

Pull #13769

github

Committed by

web-flow

Commit Message

Merge 4ee65b348 into d03a61e09

Pull Request Pull Request #13769: Remove dependance of `BooleanExpression` on `tweedledum`

Coverage Stats

168 of 182 new or added lines in 5 files covered. (92.31%)

31 existing lines in 4 files now uncovered.

79990 of 89938 relevant lines covered (88.94%)

347805.83 hits per line

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

88.41

/qiskit/circuit/classicalfunction/boolean_expression.py

# This code is part of Qiskit.
#
# (C) Copyright IBM 2021.
#
# 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.

"""A quantum oracle constructed from a logical expression or a string in the DIMACS format."""

import ast
import itertools
import re
from os.path import basename, isfile

from qiskit.circuit import Gate
from .boolean_expression_visitor import (
    BooleanExpressionEvalVisitor,
    BooleanExpressionArgsCollectorVisitor,
)


class BooleanExpression(Gate):
    """The Boolean Expression gate."""

    def __init__(self, expression: str, name: str = None, var_order: list = None) -> None:
        """
        Args:
            expression (str): The logical expression string.
            name (str): Optional. Instruction gate name. Otherwise part of the expression is
               going to be used.
            var_order(list): A list with the order in which variables will be created.
               (default: by appearance)
        """
        self.expression = expression
        self.expression_ast = ast.parse(expression)
        short_expr_for_name = (expression[:10] + "...") if len(expression) > 13 else expression
        args_collector = BooleanExpressionArgsCollectorVisitor()
        args_collector.visit(self.expression_ast)
        self.args = args_collector.get_sorted_args()
        if var_order is not None:
            missing_args = set(self.args) - set(var_order)
            if len(missing_args) > 0:
                raise ValueError(f"var_order missing the variable(s) {', '.join(missing_args)}")
            self.args.sort(key=var_order.index)

        num_qubits = len(self.args) + 1  # one for output qubit
        self.definition = None
        super().__init__(name or short_expr_for_name, num_qubits=num_qubits, params=[])

    def simulate(self, bitstring: str) -> bool:
        """Evaluate the expression on a bitstring.

        This evaluation is done classically.

        Args:
            bitstring: The bitstring for which to evaluate.

        Returns:
            bool: result of the evaluation.
        """
        eval_visitor = BooleanExpressionEvalVisitor()
        if len(self.args) != len(bitstring):
            raise ValueError(
                f"bitstring length differs from the number of variables "
                f"({len(bitstring)} != {len(self.args)})"
            )
        for arg, bit in zip(self.args, bitstring):
            if not bit in ["0", "1"]:
                raise ValueError("bitstring must be composed of 0 and 1 only")
            eval_visitor.arg_values[arg] = bit == "1"
        return eval_visitor.visit(self.expression_ast)

    def truth_table(self) -> dict:
        """Generates the full truth table for the expression
        Returns:
            dict: A dictionary mapping boolean assignments to the boolean result
        """
        return {
            assignment: self.simulate("".join("1" if val else "0" for val in assignment))
            for assignment in itertools.product([False, True], repeat=len(self.args))
        }

    def synth(self, circuit_type: str = "bit"):
        """Synthesis the logic network into a :class:`~qiskit.circuit.QuantumCircuit`.
        There are two common types of circuits for a boolean function f(x):
            1) bit-flip oracles which compute |x>|y> |-> |x>|f(x)+y>
            2) phase-flip oracles which compute |x> |-> (-1)^f(x)|x>
            By default the bit-flip oracle is generated
        Args:
            circuit_type: which type of oracle to create, 'bit' or 'phase' flip oracle.
        Returns:
            QuantumCircuit: A circuit implementing the logic network.
        """
        # pylint: disable=cyclic-import
        from .boolean_expression_synth import (
            synth_bit_oracle_from_esop,
            synth_phase_oracle_from_esop,
            EsopGenerator,
        )  # import here to avoid cyclic import

        # generating the esop currntly requires generating the full truth table
        # there are many optimizations that can be done to improve this step
        esop = EsopGenerator(self.truth_table()).esop
        if circuit_type == "bit":
            return synth_bit_oracle_from_esop(esop)
        if circuit_type == "phase":
            return synth_phase_oracle_from_esop(esop)
        raise ValueError("'circuit_type' must be either 'bit' or 'phase'")

    def _define(self):
        """The definition of the boolean expression is its synthesis"""
        self.definition = self.synth()

    @staticmethod
    def from_dimacs(dimacs: str, name: str = None):
        """Create a BooleanExpression from a string in the DIMACS format.
        Args:
            dimacs : A string in DIMACS format.
            name: an optional name for the BooleanExpression

        Returns:
            BooleanExpression: A gate for the input string

        Raises:
            ValueError: If the string is not formatted according to DIMACS rules
        """
        header_regex = re.compile(r"p\s+cnf\s+(\d+)\s+(\d+)")
        clause_regex = re.compile(r"(-?\d+)")
        lines = [
            line for line in dimacs.split("\n") if not line.startswith("c") and line != ""
        ]  # DIMACS comment line start with c
        header_match = header_regex.match(lines[0])
        if not header_match:
            raise ValueError("First line must start with 'p cnf'")
        num_vars, _ = map(int, header_match.groups())
        variables = [f"x{i+1}" for i in range(num_vars)]
        clauses = []
        for line in lines[1:]:
            literals = clause_regex.findall(line)
            if len(literals) == 0 or literals[-1] != "0":
                continue
            clauses.append([int(c) for c in literals[:-1]])
        clause_strings = [
            " | ".join([f'{"~" if lit < 0 else ""}{variables[abs(lit)-1]}' for lit in clause])
            for clause in clauses
        ]
        expr = " & ".join([f"({c})" for c in clause_strings])
        return BooleanExpression(expr, name=name, var_order=variables)

    @staticmethod
    def from_dimacs_file(filename: str):
        """Create a BooleanExpression from a file in the DIMACS format.
        Args:
            filename: A file in DIMACS format.

        Returns:
            BooleanExpression: A gate for the input string

        Raises:
            FileNotFoundError: If filename is not found.
        """
        if not isfile(filename):
            raise FileNotFoundError(f"The file {filename} does not exists.")
        with open(filename, "r") as dimacs_file:
            dimacs = dimacs_file.read()
        return BooleanExpression.from_dimacs(dimacs, name=basename(filename))

1	# This code is part of Qiskit.
2	#
3	# (C) Copyright IBM 2021.
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	"""A quantum oracle constructed from a logical expression or a string in the DIMACS format."""
14
15	import ast	1✔
16	import itertools	1✔
17	import re	1✔
18	from os.path import basename, isfile	1✔
19
20	from qiskit.circuit import Gate	1✔
21	from .boolean_expression_visitor import (	1✔
22	BooleanExpressionEvalVisitor,
23	BooleanExpressionArgsCollectorVisitor,
24	)
25
26
27	class BooleanExpression(Gate):	1✔
28	"""The Boolean Expression gate."""
29
30	def __init__(self, expression: str, name: str = None, var_order: list = None) -> None:	1✔
31	"""
32	Args:
33	expression (str): The logical expression string.
34	name (str): Optional. Instruction gate name. Otherwise part of the expression is
35	going to be used.
36	var_order(list): A list with the order in which variables will be created.
37	(default: by appearance)
38	"""
39	self.expression = expression	1✔
40	self.expression_ast = ast.parse(expression)	1✔
41	short_expr_for_name = (expression[:10] + "...") if len(expression) > 13 else expression	1✔
42	args_collector = BooleanExpressionArgsCollectorVisitor()	1✔
43	args_collector.visit(self.expression_ast)	1✔
44	self.args = args_collector.get_sorted_args()	1✔
45	if var_order is not None:	1✔
46	missing_args = set(self.args) - set(var_order)	1✔
47	if len(missing_args) > 0:	1✔
NEW 48	raise ValueError(f"var_order missing the variable(s) {', '.join(missing_args)}")	×
49	self.args.sort(key=var_order.index)	1✔
50
51	num_qubits = len(self.args) + 1 # one for output qubit	1✔
52	self.definition = None	1✔
53	super().__init__(name or short_expr_for_name, num_qubits=num_qubits, params=[])	1✔
54
55	def simulate(self, bitstring: str) -> bool:	1✔
56	"""Evaluate the expression on a bitstring.
57
58	This evaluation is done classically.
59
60	Args:
61	bitstring: The bitstring for which to evaluate.
62
63	Returns:
64	bool: result of the evaluation.
65	"""
66	eval_visitor = BooleanExpressionEvalVisitor()	1✔
67	if len(self.args) != len(bitstring):	1✔
NEW 68	raise ValueError(	×
69	f"bitstring length differs from the number of variables "
70	f"({len(bitstring)} != {len(self.args)})"
71	)
72	for arg, bit in zip(self.args, bitstring):	1✔
73	if not bit in ["0", "1"]:	1✔
NEW 74	raise ValueError("bitstring must be composed of 0 and 1 only")	×
75	eval_visitor.arg_values[arg] = bit == "1"	1✔
76	return eval_visitor.visit(self.expression_ast)	1✔
77
78	def truth_table(self) -> dict:	1✔
79	"""Generates the full truth table for the expression
80	Returns:
81	dict: A dictionary mapping boolean assignments to the boolean result
82	"""
83	return {	1✔
84	assignment: self.simulate("".join("1" if val else "0" for val in assignment))
85	for assignment in itertools.product([False, True], repeat=len(self.args))
86	}
87
88	def synth(self, circuit_type: str = "bit"):	1✔
89	"""Synthesis the logic network into a :class:`~qiskit.circuit.QuantumCircuit`.
90	There are two common types of circuits for a boolean function f(x):
91	1) bit-flip oracles which compute \|x>\|y> \|-> \|x>\|f(x)+y>
92	2) phase-flip oracles which compute \|x> \|-> (-1)^f(x)\|x>
93	By default the bit-flip oracle is generated
94	Args:
95	circuit_type: which type of oracle to create, 'bit' or 'phase' flip oracle.
96	Returns:
97	QuantumCircuit: A circuit implementing the logic network.
98	"""
99	# pylint: disable=cyclic-import
100	from .boolean_expression_synth import (	1✔
101	synth_bit_oracle_from_esop,
102	synth_phase_oracle_from_esop,
103	EsopGenerator,
104	) # import here to avoid cyclic import
105
106	# generating the esop currntly requires generating the full truth table
107	# there are many optimizations that can be done to improve this step
108	esop = EsopGenerator(self.truth_table()).esop	1✔
109	if circuit_type == "bit":	1✔
110	return synth_bit_oracle_from_esop(esop)	1✔
111	if circuit_type == "phase":	1✔
112	return synth_phase_oracle_from_esop(esop)	1✔
NEW 113	raise ValueError("'circuit_type' must be either 'bit' or 'phase'")	×
114
115	def _define(self):	1✔
116	"""The definition of the boolean expression is its synthesis"""
117	self.definition = self.synth()	×
118
119	@staticmethod	1✔
120	def from_dimacs(dimacs: str, name: str = None):	1✔
121	"""Create a BooleanExpression from a string in the DIMACS format.
122	Args:
123	dimacs : A string in DIMACS format.
124	name: an optional name for the BooleanExpression
125
126	Returns:
127	BooleanExpression: A gate for the input string
128
129	Raises:
130	ValueError: If the string is not formatted according to DIMACS rules
131	"""
132	header_regex = re.compile(r"p\s+cnf\s+(\d+)\s+(\d+)")	1✔
133	clause_regex = re.compile(r"(-?\d+)")	1✔
134	lines = [	1✔
135	line for line in dimacs.split("\n") if not line.startswith("c") and line != ""
136	] # DIMACS comment line start with c
137	header_match = header_regex.match(lines[0])	1✔
138	if not header_match:	1✔
NEW 139	raise ValueError("First line must start with 'p cnf'")	×
140	num_vars, _ = map(int, header_match.groups())	1✔
141	variables = [f"x{i+1}" for i in range(num_vars)]	1✔
142	clauses = []	1✔
143	for line in lines[1:]:	1✔
144	literals = clause_regex.findall(line)	1✔
145	if len(literals) == 0 or literals[-1] != "0":	1✔
NEW 146	continue	×
147	clauses.append([int(c) for c in literals[:-1]])	1✔
148	clause_strings = [	1✔
149	" \| ".join([f'{"~" if lit < 0 else ""}{variables[abs(lit)-1]}' for lit in clause])
150	for clause in clauses
151	]
152	expr = " & ".join([f"({c})" for c in clause_strings])	1✔
153	return BooleanExpression(expr, name=name, var_order=variables)	1✔
154
155	@staticmethod	1✔
156	def from_dimacs_file(filename: str):	1✔
157	"""Create a BooleanExpression from a file in the DIMACS format.
158	Args:
159	filename: A file in DIMACS format.
160
161	Returns:
162	BooleanExpression: A gate for the input string
163
164	Raises:
165	FileNotFoundError: If filename is not found.
166	"""
167	if not isfile(filename):	1✔
168	raise FileNotFoundError(f"The file {filename} does not exists.")	×
169	with open(filename, "r") as dimacs_file:	1✔
170	dimacs = dimacs_file.read()	1✔
171	return BooleanExpression.from_dimacs(dimacs, name=basename(filename))	1✔

Qiskit / qiskit / 13097520676

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