13109762827

Committed 03 Feb 2025 08:55AM UTC coverage: 88.96% (+0.1%) from 88.827%

Build # 13109762827

Build Type

Pull #13769

github

Committed by

web-flow

Commit Message

Merge 0f0683c75 into d03a61e09

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

Coverage Stats

180 of 184 new or added lines in 5 files covered. (97.83%)

24 existing lines in 4 files now uncovered.

80011 of 89940 relevant lines covered (88.96%)

347333.38 hits per line

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

96.1

/qiskit/circuit/classicalfunction/boolean_expression_synth.py

# This code is part of Qiskit.
#
# (C) Copyright IBM 2025.
#
# 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.
"""Circuit synthesizers and related classes for boolean expressions"""

import itertools
from qiskit.circuit import QuantumCircuit
from qiskit.circuit.library import ZGate, XGate
from qiskit.exceptions import QiskitError


class EsopGenerator:
    """Generates an ESOP (Exlusive-sum-of-products) representation
    for a boolean function given by its truth table"""

    def __init__(self, truth_table):
        self.truth_table = truth_table
        self.n = len(next(iter(truth_table)))
        self.cofactor_table = {}
        self.esop = self.generate_esop(assignment=())

    def clause_diff(self, clause1, clause2):
        """The indices of variables where the clauses differ"""
        return [i for i in range(len(clause1)) if clause1[i] != clause2[i]]

    def combine_and_optimize(self, clauses_1, clauses_2):
        """Combining clauses of distance 1 until no more combinations can be performed"""
        something_changed = True
        combined_clauses = clauses_1 + clauses_2
        while something_changed:
            something_changed = False
            for clause_1, clause_2 in itertools.combinations(combined_clauses, 2):
                diff = self.clause_diff(clause_1, clause_2)
                if len(diff) == 1:
                    new_clause = clause_1[: diff[0]] + "-" + clause_1[diff[0] + 1 :]
                    if new_clause not in combined_clauses:
                        combined_clauses.remove(clause_1)
                        combined_clauses.remove(clause_2)
                        combined_clauses.append(new_clause)
                        something_changed = True
                        break
        return combined_clauses

    def generate_esop(self, assignment):
        """Recursively generates an ESOP for a partially determined boolean expression
        'assignment' is a partial assignment to the expression's variables
        """
        # this base case is non-optimized;
        # we may be able to terminate even before having a full assignment
        if len(assignment) == self.n:
            if self.truth_table[assignment]:
                return ["-" * self.n]  # True; a don't care clause
            else:
                return []  # False
        if assignment in self.cofactor_table:
            return self.cofactor_table[assignment]
        i = len(assignment)  # current variable
        negative_esop = self.generate_esop(assignment + (False,))
        positive_esop = self.generate_esop(assignment + (True,))
        # Boole's expansion
        negative_esop_bool_expanded = [
            clause[:i] + "0" + clause[i + 1 :] for clause in negative_esop
        ]
        positive_esop_bool_expanded = [
            clause[:i] + "1" + clause[i + 1 :] for clause in positive_esop
        ]
        self.cofactor_table[assignment] = self.combine_and_optimize(
            negative_esop_bool_expanded, positive_esop_bool_expanded
        )
        return self.cofactor_table[assignment]


def synth_phase_oracle_from_esop(esop):
    """
    Generates a phase oracle for the boolean function f given in ESOP (Exlusive sum of products) form
    esop is of the form ('01-1', '11-0', ...) etc
    where 1 is the variable, 0 is negated variable and - is don't care
    """
    sizes = {len(clause) for clause in esop}
    if len(sizes) > 1:
        raise QiskitError("In the given ESOP, all clauses must be of equal size")
    num_qubits = next(iter(sizes))
    qc = QuantumCircuit(num_qubits)
    clause_data = [
        (zip(*[qubit_data for qubit_data in enumerate(clause) if qubit_data[1] != "-"]))
        for clause in esop
    ]
    for qubit_indices, control_data in clause_data:
        control_state = "".join(control_data)
        if len(control_state) == 1:  # single qubit; either Z or XZX
            if control_state == "0":
                qc.x(qubit_indices[0])
            qc.z(qubit_indices[0])
            if control_state == "0":
                qc.x(qubit_indices[0])
        else:  # use custom controlled-Z gate
            # we use the last qubit as the target, flipping it if the control is 0 for that qubit
            gate = ZGate().control(len(qubit_indices) - 1, ctrl_state=control_state[:-1][::-1])
            if control_state[-1] == "0":
                qc.x(qubit_indices[-1])
            qc.append(gate, qubit_indices)
            if control_state[-1] == "0":
                qc.x(qubit_indices[-1])
    return qc


def synth_bit_oracle_from_esop(esop):
    """
    Generates a bit-flip oracle for the boolean function f given in ESOP (Exlusive sum of products) form
    esop is of the form ('01-1', '11-0', ...) etc
    where 1 is the variable, 0 is negated variable and - is don't care
    """
    sizes = {len(clause) for clause in esop}
    if len(sizes) > 1:
        raise QiskitError("In the given ESOP, all clauses must be of equal size")
    num_qubits = next(iter(sizes)) + 1  # one additional qubit for the output
    output_index = num_qubits - 1
    qc = QuantumCircuit(num_qubits)
    clause_data = [
        (zip(*[qubit_data for qubit_data in enumerate(clause) if qubit_data[1] != "-"]))
        for clause in esop
    ]
    for qubit_indices, control_data in clause_data:
        control_state = "".join(control_data)
        # use custom controlled-X gate
        gate = XGate().control(len(qubit_indices), ctrl_state=control_state)
        qc.append(gate, qubit_indices + (output_index,))
    return qc

1	# This code is part of Qiskit.
2	#
3	# (C) Copyright IBM 2025.
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	"""Circuit synthesizers and related classes for boolean expressions"""
13
14	import itertools	1✔
15	from qiskit.circuit import QuantumCircuit	1✔
16	from qiskit.circuit.library import ZGate, XGate	1✔
17	from qiskit.exceptions import QiskitError	1✔
18
19
20	class EsopGenerator:	1✔
21	"""Generates an ESOP (Exlusive-sum-of-products) representation
22	for a boolean function given by its truth table"""
23
24	def __init__(self, truth_table):	1✔
25	self.truth_table = truth_table	1✔
26	self.n = len(next(iter(truth_table)))	1✔
27	self.cofactor_table = {}	1✔
28	self.esop = self.generate_esop(assignment=())	1✔
29
30	def clause_diff(self, clause1, clause2):	1✔
31	"""The indices of variables where the clauses differ"""
32	return [i for i in range(len(clause1)) if clause1[i] != clause2[i]]	1✔
33
34	def combine_and_optimize(self, clauses_1, clauses_2):	1✔
35	"""Combining clauses of distance 1 until no more combinations can be performed"""
36	something_changed = True	1✔
37	combined_clauses = clauses_1 + clauses_2	1✔
38	while something_changed:	1✔
39	something_changed = False	1✔
40	for clause_1, clause_2 in itertools.combinations(combined_clauses, 2):	1✔
41	diff = self.clause_diff(clause_1, clause_2)	1✔
42	if len(diff) == 1:	1✔
43	new_clause = clause_1[: diff[0]] + "-" + clause_1[diff[0] + 1 :]	1✔
44	if new_clause not in combined_clauses:	1✔
45	combined_clauses.remove(clause_1)	1✔
46	combined_clauses.remove(clause_2)	1✔
47	combined_clauses.append(new_clause)	1✔
48	something_changed = True	1✔
49	break	1✔
50	return combined_clauses	1✔
51
52	def generate_esop(self, assignment):	1✔
53	"""Recursively generates an ESOP for a partially determined boolean expression
54	'assignment' is a partial assignment to the expression's variables
55	"""
56	# this base case is non-optimized;
57	# we may be able to terminate even before having a full assignment
58	if len(assignment) == self.n:	1✔
59	if self.truth_table[assignment]:	1✔
60	return ["-" * self.n] # True; a don't care clause	1✔
61	else:
62	return [] # False	1✔
63	if assignment in self.cofactor_table:	1✔
NEW 64	return self.cofactor_table[assignment]	×
65	i = len(assignment) # current variable	1✔
66	negative_esop = self.generate_esop(assignment + (False,))	1✔
67	positive_esop = self.generate_esop(assignment + (True,))	1✔
68	# Boole's expansion
69	negative_esop_bool_expanded = [	1✔
70	clause[:i] + "0" + clause[i + 1 :] for clause in negative_esop
71	]
72	positive_esop_bool_expanded = [	1✔
73	clause[:i] + "1" + clause[i + 1 :] for clause in positive_esop
74	]
75	self.cofactor_table[assignment] = self.combine_and_optimize(	1✔
76	negative_esop_bool_expanded, positive_esop_bool_expanded
77	)
78	return self.cofactor_table[assignment]	1✔
79
80
81	def synth_phase_oracle_from_esop(esop):	1✔
82	"""
83	Generates a phase oracle for the boolean function f given in ESOP (Exlusive sum of products) form
84	esop is of the form ('01-1', '11-0', ...) etc
85	where 1 is the variable, 0 is negated variable and - is don't care
86	"""
87	sizes = {len(clause) for clause in esop}	1✔
88	if len(sizes) > 1:	1✔
NEW 89	raise QiskitError("In the given ESOP, all clauses must be of equal size")	×
90	num_qubits = next(iter(sizes))	1✔
91	qc = QuantumCircuit(num_qubits)	1✔
92	clause_data = [	1✔
93	(zip(*[qubit_data for qubit_data in enumerate(clause) if qubit_data[1] != "-"]))
94	for clause in esop
95	]
96	for qubit_indices, control_data in clause_data:	1✔
97	control_state = "".join(control_data)	1✔
98	if len(control_state) == 1: # single qubit; either Z or XZX	1✔
99	if control_state == "0":	1✔
100	qc.x(qubit_indices[0])	1✔
101	qc.z(qubit_indices[0])	1✔
102	if control_state == "0":	1✔
103	qc.x(qubit_indices[0])	1✔
104	else: # use custom controlled-Z gate
105	# we use the last qubit as the target, flipping it if the control is 0 for that qubit
106	gate = ZGate().control(len(qubit_indices) - 1, ctrl_state=control_state[:-1][::-1])	1✔
107	if control_state[-1] == "0":	1✔
108	qc.x(qubit_indices[-1])	1✔
109	qc.append(gate, qubit_indices)	1✔
110	if control_state[-1] == "0":	1✔
111	qc.x(qubit_indices[-1])	1✔
112	return qc	1✔
113
114
115	def synth_bit_oracle_from_esop(esop):	1✔
116	"""
117	Generates a bit-flip oracle for the boolean function f given in ESOP (Exlusive sum of products) form
118	esop is of the form ('01-1', '11-0', ...) etc
119	where 1 is the variable, 0 is negated variable and - is don't care
120	"""
121	sizes = {len(clause) for clause in esop}	1✔
122	if len(sizes) > 1:	1✔
NEW 123	raise QiskitError("In the given ESOP, all clauses must be of equal size")	×
124	num_qubits = next(iter(sizes)) + 1 # one additional qubit for the output	1✔
125	output_index = num_qubits - 1	1✔
126	qc = QuantumCircuit(num_qubits)	1✔
127	clause_data = [	1✔
128	(zip(*[qubit_data for qubit_data in enumerate(clause) if qubit_data[1] != "-"]))
129	for clause in esop
130	]
131	for qubit_indices, control_data in clause_data:	1✔
132	control_state = "".join(control_data)	1✔
133	# use custom controlled-X gate
134	gate = XGate().control(len(qubit_indices), ctrl_state=control_state)	1✔
135	qc.append(gate, qubit_indices + (output_index,))	1✔
136	return qc	1✔

Qiskit / qiskit / 13109762827

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