23457822425

Committed 23 Mar 2026 08:10PM UTC coverage: 87.24% (-0.03%) from 87.268%

Build # 23457822425

Build Type

Pull #15352

github

Committed by

web-flow

Commit Message

Merge 978cfb8de into 572045f51

Pull Request Pull Request #15352: Add transpiler pass for complementary control pattern simplification using Boolean algebra

Coverage Stats

306 of 376 new or added lines in 3 files covered. (81.38%)

16 existing lines in 3 files now uncovered.

103784 of 118964 relevant lines covered (87.24%)

997041.3 hits per line

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

81.28

/qiskit/transpiler/passes/optimization/control_pattern_simplification.py

# This code is part of Qiskit.
#
# (C) Copyright IBM 2017, 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 https://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.

"""Simplify multi-controlled gates by Boolean algebraic reduction of control patterns."""

import numpy as np

from qiskit.circuit import ControlledGate
from qiskit.circuit.annotated_operation import AnnotatedOperation
from qiskit.circuit.library import CXGate, XGate
from qiskit.transpiler.basepasses import TransformationPass


class BitwisePatternAnalyzer:
    """Analyze control-state bit patterns for Boolean simplification opportunities."""

    def __init__(self, num_qubits):
        self.num_qubits = num_qubits

    def _find_common_bits(self, patterns):
        """Find bit positions that have the same value across all patterns."""
        if not patterns:
            return [], 0
        # AND all patterns together to find bits that are 1 in all
        all_ones = patterns[0]
        # AND all inverted patterns to find bits that are 0 in all
        all_zeros = ~patterns[0]
        for p in patterns[1:]:
            all_ones &= p
            all_zeros &= ~p
        mask = (1 << self.num_qubits) - 1
        all_zeros &= mask

        common_pos = []
        common_val = 0
        for pos in range(self.num_qubits):
            bit_mask = 1 << pos
            if all_ones & bit_mask:
                common_pos.append(pos)
                common_val |= bit_mask
            elif all_zeros & bit_mask:
                common_pos.append(pos)
                # bit is 0 in common_val already
        return common_pos, common_val

    def _check_single_variable(self, patterns):
        """Check if the pattern set simplifies to controlling on a single qubit."""
        n = self.num_qubits
        pattern_set = set(patterns)
        if len(pattern_set) != 2 ** (n - 1):
            return None
        for ctrl_pos in range(n):
            for val in (0, 1):
                expected = set()
                bit_mask = 1 << ctrl_pos
                for combo in range(2 ** (n - 1)):
                    p = 0
                    bit_idx = 0
                    for pos in range(n):
                        if pos == ctrl_pos:
                            if val:
                                p |= bit_mask
                        else:
                            if (combo >> bit_idx) & 1:
                                p |= 1 << pos
                            bit_idx += 1
                    expected.add(p)
                if pattern_set == expected:
                    return (ctrl_pos, val)
        return None

    def simplify_patterns_pairwise(self, patterns):
        """Find one pairwise simplification (complementary, XOR, or XOR-chain)."""
        if len(patterns) < 2:
            return None
        patterns_list = sorted(set(patterns))
        n = self.num_qubits

        # Hash-based search for Hamming distance 1 (complementary pairs)
        pattern_set = set(patterns_list)
        for p in patterns_list:
            for bit_pos in range(n):
                neighbor = p ^ (1 << bit_pos)
                if neighbor > p and neighbor in pattern_set:
                    # Found complementary pair differing at bit_pos
                    common_pos = [k for k in range(n) if k != bit_pos]
                    # Reindex ctrl_state to only include common positions
                    ctrl_state = 0
                    for idx, k in enumerate(common_pos):
                        if p & (1 << k):
                            ctrl_state |= 1 << idx
                    return [
                        {
                            "type": "complementary",
                            "patterns": [p, neighbor],
                            "control_positions": common_pos,
                            "ctrl_state": ctrl_state,
                        }
                    ]

        # O(n^2) search for Hamming distance 2 (XOR) and n (full chain)
        for i, p1 in enumerate(patterns_list):
            for p2 in patterns_list[i + 1 :]:
                xor_val = p1 ^ p2
                hamming = bin(xor_val).count("1")
                if hamming == 2:
                    diff = []
                    for k in range(n):
                        if xor_val & (1 << k):
                            diff.append(k)
                    pi, pj = diff
                    b1_i = (p1 >> pi) & 1
                    b1_j = (p1 >> pj) & 1
                    b2_i = (p2 >> pi) & 1
                    b2_j = (p2 >> pj) & 1
                    bits = ((b1_i, b1_j), (b2_i, b2_j))
                    if bits in [((1, 0), (0, 1)), ((0, 1), (1, 0))]:
                        xtype = "xor_standard"
                    elif bits in [((1, 1), (0, 0)), ((0, 0), (1, 1))]:
                        xtype = "xor_with_x"
                    else:
                        continue
                    common = [k for k in range(n) if k not in diff]
                    ctrl_pos = sorted(common + [pj])
                    ctrl_state = 0
                    for idx, k in enumerate(ctrl_pos):
                        if k == pj:
                            ctrl_state |= 1 << idx
                        elif p1 & (1 << k):
                            ctrl_state |= 1 << idx
                    return [
                        {
                            "type": xtype,
                            "patterns": [p1, p2],
                            "control_positions": ctrl_pos,
                            "ctrl_state": ctrl_state,
                            "xor_qubits": [pi, pj],
                        }
                    ]
                if hamming == n >= 2:
                    diff = []
                    for k in range(n):
                        if xor_val & (1 << k):
                            diff.append(k)
                    anchor = diff[0]
                    targets = diff[1:]
                    anchor_val = (p1 >> anchor) & 1
                    ctrl_state = 0
                    for idx in range(len(targets)):
                        if anchor_val:
                            ctrl_state |= 1 << idx
                    return [
                        {
                            "type": "xor_chain",
                            "patterns": [p1, p2],
                            "control_positions": targets,
                            "ctrl_state": ctrl_state,
                            "xor_anchor": anchor,
                            "xor_targets": targets,
                        }
                    ]
        return None

    def simplify_patterns_iterative(self, patterns):
        """Apply pairwise simplifications repeatedly until no more are found."""
        remaining = sorted(set(patterns))
        all_opts = []
        while len(remaining) >= 2:
            result = self.simplify_patterns_pairwise(remaining)
            if not result:
                break
            all_opts.append(result[0])
            matched = set(result[0]["patterns"])
            remaining = [p for p in remaining if p not in matched]
        if not all_opts:
            return (None, None, None)
        return (
            "pairwise_iterative",
            {"optimizations": all_opts, "remaining_patterns": remaining},
            None,
        )

    def simplify_patterns(self, patterns):
        """Determine the best simplification for a set of control patterns."""
        if not patterns:
            return ("no_optimization", None, None)
        unique = sorted(set(patterns))
        n = self.num_qubits
        # Complete partition
        if len(unique) == 2**n:
            return ("unconditional", [], 0)
        # Complement: all but one pattern
        if len(unique) == 2**n - 1:
            all_p = set(range(2**n))
            missing = list(all_p - set(unique))
            if len(missing) == 1:
                return ("complement", list(range(n)), missing[0])
        # Iterative pairwise
        if len(unique) > 2:
            result = self.simplify_patterns_iterative(unique)
            if result[0] == "pairwise_iterative":
                return result
        # Single pairwise
        pairwise = self.simplify_patterns_pairwise(unique)
        if pairwise:
            return ("pairwise", pairwise, None)
        # Single variable
        single = self._check_single_variable(unique)
        if single:
            return ("single", [single[0]], single[1])
        # Common bits (AND)
        common_pos, common_val = self._find_common_bits(unique)
        if common_pos and len(common_pos) < n:
            varying = [i for i in range(n) if i not in common_pos]
            if len(unique) == 2 ** len(varying):
                # Reindex ctrl_state for just the common positions
                ctrl_state = 0
                for idx, pos in enumerate(common_pos):
                    if common_val & (1 << pos):
                        ctrl_state |= 1 << idx
                cls = "single" if len(common_pos) == 1 else "and"
                return (cls, common_pos, ctrl_state)
        return ("no_optimization", None, None)


class ControlPatternSimplification(TransformationPass):
    """Simplify groups of multi-controlled gates that share the same base gate and target
    by applying Boolean algebra to their control-state patterns."""

    def __init__(self, tolerance=1e-10):
        """ControlPatternSimplification initializer.

        Args:
            tolerance (float): numerical tolerance for comparing gate parameters.
        """
        super().__init__()
        self.tolerance = tolerance

    def _get_controlled_info(self, op):
        """Return ``(base_gate, num_ctrl_qubits, ctrl_state)`` or ``None``."""
        if isinstance(op, ControlledGate):
            return (op.base_gate, op.num_ctrl_qubits, op.ctrl_state)
        if isinstance(op, AnnotatedOperation):
            from qiskit.circuit import ControlModifier

            ctrl_mods = [m for m in op.modifiers if isinstance(m, ControlModifier)]
            if ctrl_mods:
                nc = sum(m.num_ctrl_qubits for m in ctrl_mods)
                return (op.base_op, nc, ctrl_mods[0].ctrl_state)
        return None

    def _params_match(self, p1, p2):
        """Check if two parameter tuples match within tolerance."""
        if len(p1) != len(p2):
            return False
        return all(
            (
                np.isclose(a, b, atol=self.tolerance)
                if isinstance(a, (int, float)) and isinstance(b, (int, float))
                else a == b
            )
            for a, b in zip(p1, p2)
        )

    def _collect_gates(self, dag):
        """Collect runs of consecutive controlled gates from the DAG."""
        runs, current = [], []
        for node in dag.topological_op_nodes():
            info = self._get_controlled_info(node.op)
            if info is not None:
                base_gate, nc, ctrl_state = info
                qargs = [dag.find_bit(q).index for q in node.qargs]
                ctrl_qubits = qargs[:nc]
                tgt_qubits = qargs[nc:]
                params = tuple(node.op.params) if node.op.params else ()
                # Normalize control qubit ordering and remap ctrl_state
                if ctrl_qubits != sorted(ctrl_qubits):
                    sort_order = sorted(range(nc), key=lambda k: ctrl_qubits[k])
                    new_cs = 0
                    for new_idx, old_idx in enumerate(sort_order):
                        if ctrl_state & (1 << old_idx):
                            new_cs |= 1 << new_idx
                    ctrl_qubits = [ctrl_qubits[k] for k in sort_order]
                    ctrl_state = new_cs
                current.append((node, base_gate, ctrl_qubits, tgt_qubits, ctrl_state, params))
            elif current:
                runs.append(current)
                current = []
        if current:
            runs.append(current)
        return runs

    def _group_same_controls(self, gates):
        """Group gates sharing the same base gate, control qubits, and target."""
        if len(gates) < 2:
            return []
        groups = []
        used = set()
        for i in range(len(gates)):
            if i in used:
                continue
            _, bg_i, ctrl_i, tgt_i, _, params_i = gates[i]
            group = [gates[i]]
            group_indices = [i]
            for j in range(i + 1, len(gates)):
                if j in used:
                    continue
                _, bg_j, ctrl_j, tgt_j, _, params_j = gates[j]
                if (
                    bg_j.name == bg_i.name
                    and tgt_j == tgt_i
                    and ctrl_j == ctrl_i
                    and self._params_match(params_j, params_i)
                ):
                    group.append(gates[j])
                    group_indices.append(j)
                else:
                    # Two controlled gates commute if their target qubits
                    # are disjoint (shared controls don't break commutativity).
                    # For safety, also require no target-control overlap.
                    group_tgts = set(tgt_i)
                    gate_tgts = set(tgt_j)
                    if (
                        group_tgts.isdisjoint(gate_tgts)
                        and group_tgts.isdisjoint(set(ctrl_j))
                        and gate_tgts.isdisjoint(set(ctrl_i))
                    ):
                        continue  # skip over commuting gate
                    else:
                        break
            if len(group) >= 2:
                groups.append(group)
                used.update(group_indices)
        return groups

    def _group_mixed_controls(self, gates):
        """Group gates with subset/superset control qubit relationships."""
        if len(gates) < 2:
            return []
        groups, used = [], set()
        for i in range(len(gates)):
            if i in used:
                continue
            _, bg_i, ctrl_i, tgt_i, _, params_i = gates[i]
            group = [gates[i]]
            base_c = set(ctrl_i)
            for j in range(i + 1, len(gates)):
                if j in used:
                    continue
                _, bg_j, ctrl_j, tgt_j, _, params_j = gates[j]
                cand_c = set(ctrl_j)
                if (
                    bg_j.name == bg_i.name
                    and tgt_j == tgt_i
                    and self._params_match(params_j, params_i)
                    and (base_c <= cand_c or cand_c <= base_c)
                ):
                    group.append(gates[j])
                    used.add(j)
            if len(group) >= 2 and len({len(g[2]) for g in group}) > 1:
                groups.append(group)
                used.add(i)
        return groups

    def _expand_pattern(self, ctrl_state, gate_ctrls, superset):
        """Expand a control pattern to a superset of control qubits."""
        missing = [q for q in superset if q not in gate_ctrls]
        if not missing:
            return [ctrl_state]
        expanded = []
        gate_ctrl_set = set(gate_ctrls)
        for combo in range(2 ** len(missing)):
            p = 0
            gate_bit_idx = 0
            miss_bit_idx = 0
            for sup_idx, q in enumerate(superset):
                if q in gate_ctrl_set:
                    if ctrl_state & (1 << gate_bit_idx):
                        p |= 1 << sup_idx
                    gate_bit_idx += 1
                else:
                    if (combo >> miss_bit_idx) & 1:
                        p |= 1 << sup_idx
                    miss_bit_idx += 1
            expanded.append(p)
        return expanded

    def _build_gate(self, base_gate, params, ctrl_qubits, target_qubits, ctrl_state):
        """Build a ``(gate, qargs)`` tuple from the given parameters."""
        gate = base_gate(*params) if params else base_gate()
        if not ctrl_qubits:
            return (gate, target_qubits)
        return (
            gate.control(len(ctrl_qubits), ctrl_state=ctrl_state, annotated=False),
            ctrl_qubits + target_qubits,
        )

    def _build_optimized(self, group, optimizations, remaining):
        """Translate pairwise optimization descriptions into gate operations."""
        bg = type(group[0][1])  # base_gate type
        params = group[0][5]  # params
        tgt = group[0][3]  # target_qubits
        all_c = group[0][2]  # control_qubits
        gates = []
        for opt in optimizations:
            t = opt["type"]
            cp = opt["control_positions"]
            cs = opt["ctrl_state"]
            cq = [all_c[p] for p in cp]
            if t == "complementary":
                gates.append(self._build_gate(bg, params, cq, tgt, cs))
            elif t == "xor_standard":
                qi, qj = opt["xor_qubits"]
                gates.extend(
                    [
                        (CXGate(), [all_c[qi], all_c[qj]]),
                        self._build_gate(bg, params, cq, tgt, cs),
                        (CXGate(), [all_c[qi], all_c[qj]]),
                    ]
                )
            elif t == "xor_with_x":
                qi, qj = opt["xor_qubits"]
                qic, qjc = all_c[qi], all_c[qj]
                gates.extend(
                    [
                        (XGate(), [qjc]),
                        (CXGate(), [qic, qjc]),
                        self._build_gate(bg, params, cq, tgt, cs),
                        (CXGate(), [qic, qjc]),
                        (XGate(), [qjc]),
                    ]
                )
            elif t == "xor_chain":
                anc = all_c[opt["xor_anchor"]]
                tgts = [all_c[x] for x in opt["xor_targets"]]
                for tc in tgts:
                    gates.append((CXGate(), [anc, tc]))
                gates.append(self._build_gate(bg, params, cq, tgt, cs))
                for tc in reversed(tgts):
                    gates.append((CXGate(), [anc, tc]))
        # Remaining unmatched patterns
        rem_set = set(remaining)
        for g in group:
            if g[4] in rem_set:  # ctrl_state
                gates.append((g[0].op, [g[2][i] for i in range(len(g[2]))] + g[3]))
        return gates or None

    def run(self, dag):
        """Run the ControlPatternSimplification pass on ``dag``.

        Args:
            dag (DAGCircuit): the DAG to be optimized.

        Returns:
            DAGCircuit: the optimized DAG.
        """
        # Identify groups of gates to optimize and their replacements.
        # Use _node_id (stable DAG node identifier) as keys.
        nodes_to_replace = {}
        for run in self._collect_gates(dag):
            used = set()
            # Mixed control counts
            for group in self._group_mixed_controls(run):
                all_ctrls = sorted(set().union(*(set(g[2]) for g in group)))
                expanded = []
                for g in group:
                    expanded.extend(self._expand_pattern(g[4], g[2], all_ctrls))
                if len(set(expanded)) == 2 ** len(all_ctrls):
                    bg = type(group[0][1])
                    repl = [self._build_gate(bg, group[0][5], [], group[0][3], 0)]
                    nodes_to_replace[group[0][0]._node_id] = repl
                    for g in group[1:]:
                        nodes_to_replace[g[0]._node_id] = None
                    used.update(g[0]._node_id for g in group)

            # Same control qubits
            remaining_gates = [g for g in run if g[0]._node_id not in used]
            for group in self._group_same_controls(remaining_gates):
                patterns = [g[4] for g in group]
                nq = len(group[0][2])
                unique = set(patterns)
                g0 = group[0]
                bg = type(g0[1])
                params = g0[5]
                ctrls = g0[2]
                tgt = g0[3]

                repl = None
                if len(unique) == 1:
                    # All gates have the same ctrl_state: merge angles
                    merged_params = (sum(g[5][0] for g in group),) if params else ()
                    repl = [self._build_gate(bg, merged_params, ctrls, tgt, g0[4])]
                else:
                    # Check for duplicate patterns: merge them first
                    from collections import Counter

                    counts = Counter(patterns)
                    has_duplicates = any(c > 1 for c in counts.values())
                    if has_duplicates:
                        # Merge duplicate patterns by summing angles, keep
                        # unique patterns as-is. Only proceed with pattern
                        # simplification on the unique-count subset.
                        repl = []
                        for cs_val, cnt in counts.items():
                            if cnt > 1 and params:
                                mp = (params[0] * cnt,) + params[1:]
                            else:
                                mp = params
                            repl.append(self._build_gate(bg, mp, ctrls, tgt, cs_val))
                    else:
                        # Each pattern appears exactly once: safe to simplify
                        cls, info, cs = BitwisePatternAnalyzer(nq).simplify_patterns(patterns)
                        if cls == "single" and info:
                            repl = [self._build_gate(bg, params, [ctrls[info[0]]], tgt, cs)]
                        elif cls == "and" and info:
                            repl = [self._build_gate(bg, params, [ctrls[i] for i in info], tgt, cs)]
                        elif cls == "unconditional":
                            repl = [self._build_gate(bg, params, [], tgt, 0)]
                        elif cls == "complement" and info:
                            neg = tuple(-p for p in params) if params else ()
                            repl = [
                                self._build_gate(bg, params, [], tgt, 0),
                                self._build_gate(bg, neg, [ctrls[i] for i in info], tgt, cs),
                            ]
                        elif cls == "pairwise_iterative" and info:
                            repl = self._build_optimized(
                                group, info["optimizations"], info["remaining_patterns"]
                            )
                        elif cls == "pairwise" and info:
                            repl = self._build_optimized(group, info, [])

                if repl:
                    nodes_to_replace[group[0][0]._node_id] = repl
                    for g in group[1:]:
                        nodes_to_replace[g[0]._node_id] = None

        # Build a new DAG preserving topological order
        new_dag = dag.copy_empty_like()
        for node in dag.topological_op_nodes():
            nid = node._node_id
            if nid in nodes_to_replace:
                replacement = nodes_to_replace[nid]
                if replacement is not None:
                    for gate, qargs in replacement:
                        new_dag.apply_operation_back(gate, [new_dag.qubits[i] for i in qargs])
            else:
                new_dag.apply_operation_back(node.op, node.qargs, node.cargs)

        return new_dag

1	# This code is part of Qiskit.
2	#
3	# (C) Copyright IBM 2017, 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 https://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	"""Simplify multi-controlled gates by Boolean algebraic reduction of control patterns."""
14
15	import numpy as np	1✔
16
17	from qiskit.circuit import ControlledGate	1✔
18	from qiskit.circuit.annotated_operation import AnnotatedOperation	1✔
19	from qiskit.circuit.library import CXGate, XGate	1✔
20	from qiskit.transpiler.basepasses import TransformationPass	1✔
21
22
23	class BitwisePatternAnalyzer:	1✔
24	"""Analyze control-state bit patterns for Boolean simplification opportunities."""
25
26	def __init__(self, num_qubits):	1✔
27	self.num_qubits = num_qubits	1✔
28
29	def _find_common_bits(self, patterns):	1✔
30	"""Find bit positions that have the same value across all patterns."""
NEW 31	if not patterns:	×
NEW 32	return [], 0	×
33	# AND all patterns together to find bits that are 1 in all
NEW 34	all_ones = patterns[0]	×
35	# AND all inverted patterns to find bits that are 0 in all
NEW 36	all_zeros = ~patterns[0]	×
NEW 37	for p in patterns[1:]:	×
NEW 38	all_ones &= p	×
NEW 39	all_zeros &= ~p	×
NEW 40	mask = (1 << self.num_qubits) - 1	×
NEW 41	all_zeros &= mask	×
42
NEW 43	common_pos = []	×
NEW 44	common_val = 0	×
NEW 45	for pos in range(self.num_qubits):	×
NEW 46	bit_mask = 1 << pos	×
NEW 47	if all_ones & bit_mask:	×
NEW 48	common_pos.append(pos)	×
NEW 49	common_val \|= bit_mask	×
NEW 50	elif all_zeros & bit_mask:	×
NEW 51	common_pos.append(pos)	×
52	# bit is 0 in common_val already
NEW 53	return common_pos, common_val	×
54
55	def _check_single_variable(self, patterns):	1✔
56	"""Check if the pattern set simplifies to controlling on a single qubit."""
NEW 57	n = self.num_qubits	×
NEW 58	pattern_set = set(patterns)	×
NEW 59	if len(pattern_set) != 2 ** (n - 1):	×
NEW 60	return None	×
NEW 61	for ctrl_pos in range(n):	×
NEW 62	for val in (0, 1):	×
NEW 63	expected = set()	×
NEW 64	bit_mask = 1 << ctrl_pos	×
NEW 65	for combo in range(2 ** (n - 1)):	×
NEW 66	p = 0	×
NEW 67	bit_idx = 0	×
NEW 68	for pos in range(n):	×
NEW 69	if pos == ctrl_pos:	×
NEW 70	if val:	×
NEW 71	p \|= bit_mask	×
72	else:
NEW 73	if (combo >> bit_idx) & 1:	×
NEW 74	p \|= 1 << pos	×
NEW 75	bit_idx += 1	×
NEW 76	expected.add(p)	×
NEW 77	if pattern_set == expected:	×
NEW 78	return (ctrl_pos, val)	×
NEW 79	return None	×
80
81	def simplify_patterns_pairwise(self, patterns):	1✔
82	"""Find one pairwise simplification (complementary, XOR, or XOR-chain)."""
83	if len(patterns) < 2:	1✔
NEW 84	return None	×
85	patterns_list = sorted(set(patterns))	1✔
86	n = self.num_qubits	1✔
87
88	# Hash-based search for Hamming distance 1 (complementary pairs)
89	pattern_set = set(patterns_list)	1✔
90	for p in patterns_list:	1✔
91	for bit_pos in range(n):	1✔
92	neighbor = p ^ (1 << bit_pos)	1✔
93	if neighbor > p and neighbor in pattern_set:	1✔
94	# Found complementary pair differing at bit_pos
95	common_pos = [k for k in range(n) if k != bit_pos]	1✔
96	# Reindex ctrl_state to only include common positions
97	ctrl_state = 0	1✔
98	for idx, k in enumerate(common_pos):	1✔
99	if p & (1 << k):	1✔
100	ctrl_state \|= 1 << idx	1✔
101	return [	1✔
102	{
103	"type": "complementary",
104	"patterns": [p, neighbor],
105	"control_positions": common_pos,
106	"ctrl_state": ctrl_state,
107	}
108	]
109
110	# O(n^2) search for Hamming distance 2 (XOR) and n (full chain)
111	for i, p1 in enumerate(patterns_list):	1✔
112	for p2 in patterns_list[i + 1 :]:	1✔
113	xor_val = p1 ^ p2	1✔
114	hamming = bin(xor_val).count("1")	1✔
115	if hamming == 2:	1✔
116	diff = []	1✔
117	for k in range(n):	1✔
118	if xor_val & (1 << k):	1✔
119	diff.append(k)	1✔
120	pi, pj = diff	1✔
121	b1_i = (p1 >> pi) & 1	1✔
122	b1_j = (p1 >> pj) & 1	1✔
123	b2_i = (p2 >> pi) & 1	1✔
124	b2_j = (p2 >> pj) & 1	1✔
125	bits = ((b1_i, b1_j), (b2_i, b2_j))	1✔
126	if bits in [((1, 0), (0, 1)), ((0, 1), (1, 0))]:	1✔
127	xtype = "xor_standard"	1✔
128	elif bits in [((1, 1), (0, 0)), ((0, 0), (1, 1))]:	1✔
129	xtype = "xor_with_x"	1✔
130	else:
NEW 131	continue	×
132	common = [k for k in range(n) if k not in diff]	1✔
133	ctrl_pos = sorted(common + [pj])	1✔
134	ctrl_state = 0	1✔
135	for idx, k in enumerate(ctrl_pos):	1✔
136	if k == pj:	1✔
137	ctrl_state \|= 1 << idx	1✔
138	elif p1 & (1 << k):	1✔
139	ctrl_state \|= 1 << idx	1✔
140	return [	1✔
141	{
142	"type": xtype,
143	"patterns": [p1, p2],
144	"control_positions": ctrl_pos,
145	"ctrl_state": ctrl_state,
146	"xor_qubits": [pi, pj],
147	}
148	]
149	if hamming == n >= 2:	1✔
150	diff = []	1✔
151	for k in range(n):	1✔
152	if xor_val & (1 << k):	1✔
153	diff.append(k)	1✔
154	anchor = diff[0]	1✔
155	targets = diff[1:]	1✔
156	anchor_val = (p1 >> anchor) & 1	1✔
157	ctrl_state = 0	1✔
158	for idx in range(len(targets)):	1✔
159	if anchor_val:	1✔
NEW 160	ctrl_state \|= 1 << idx	×
161	return [	1✔
162	{
163	"type": "xor_chain",
164	"patterns": [p1, p2],
165	"control_positions": targets,
166	"ctrl_state": ctrl_state,
167	"xor_anchor": anchor,
168	"xor_targets": targets,
169	}
170	]
NEW 171	return None	×
172
173	def simplify_patterns_iterative(self, patterns):	1✔
174	"""Apply pairwise simplifications repeatedly until no more are found."""
175	remaining = sorted(set(patterns))	1✔
176	all_opts = []	1✔
177	while len(remaining) >= 2:	1✔
178	result = self.simplify_patterns_pairwise(remaining)	1✔
179	if not result:	1✔
NEW 180	break	×
181	all_opts.append(result[0])	1✔
182	matched = set(result[0]["patterns"])	1✔
183	remaining = [p for p in remaining if p not in matched]	1✔
184	if not all_opts:	1✔
NEW 185	return (None, None, None)	×
186	return (	1✔
187	"pairwise_iterative",
188	{"optimizations": all_opts, "remaining_patterns": remaining},
189	None,
190	)
191
192	def simplify_patterns(self, patterns):	1✔
193	"""Determine the best simplification for a set of control patterns."""
194	if not patterns:	1✔
NEW 195	return ("no_optimization", None, None)	×
196	unique = sorted(set(patterns))	1✔
197	n = self.num_qubits	1✔
198	# Complete partition
199	if len(unique) == 2**n:	1✔
200	return ("unconditional", [], 0)	1✔
201	# Complement: all but one pattern
202	if len(unique) == 2**n - 1:	1✔
203	all_p = set(range(2**n))	1✔
204	missing = list(all_p - set(unique))	1✔
205	if len(missing) == 1:	1✔
206	return ("complement", list(range(n)), missing[0])	1✔
207	# Iterative pairwise
208	if len(unique) > 2:	1✔
209	result = self.simplify_patterns_iterative(unique)	1✔
210	if result[0] == "pairwise_iterative":	1✔
211	return result	1✔
212	# Single pairwise
213	pairwise = self.simplify_patterns_pairwise(unique)	1✔
214	if pairwise:	1✔
215	return ("pairwise", pairwise, None)	1✔
216	# Single variable
NEW 217	single = self._check_single_variable(unique)	×
NEW 218	if single:	×
NEW 219	return ("single", [single[0]], single[1])	×
220	# Common bits (AND)
NEW 221	common_pos, common_val = self._find_common_bits(unique)	×
NEW 222	if common_pos and len(common_pos) < n:	×
NEW 223	varying = [i for i in range(n) if i not in common_pos]	×
NEW 224	if len(unique) == 2 ** len(varying):	×
225	# Reindex ctrl_state for just the common positions
NEW 226	ctrl_state = 0	×
NEW 227	for idx, pos in enumerate(common_pos):	×
NEW 228	if common_val & (1 << pos):	×
NEW 229	ctrl_state \|= 1 << idx	×
NEW 230	cls = "single" if len(common_pos) == 1 else "and"	×
NEW 231	return (cls, common_pos, ctrl_state)	×
NEW 232	return ("no_optimization", None, None)	×
233
234
235	class ControlPatternSimplification(TransformationPass):	1✔
236	"""Simplify groups of multi-controlled gates that share the same base gate and target
237	by applying Boolean algebra to their control-state patterns."""
238
239	def __init__(self, tolerance=1e-10):	1✔
240	"""ControlPatternSimplification initializer.
241
242	Args:
243	tolerance (float): numerical tolerance for comparing gate parameters.
244	"""
245	super().__init__()	1✔
246	self.tolerance = tolerance	1✔
247
248	def _get_controlled_info(self, op):	1✔
249	"""Return ``(base_gate, num_ctrl_qubits, ctrl_state)`` or ``None``."""
250	if isinstance(op, ControlledGate):	1✔
251	return (op.base_gate, op.num_ctrl_qubits, op.ctrl_state)	1✔
252	if isinstance(op, AnnotatedOperation):	1✔
NEW 253	from qiskit.circuit import ControlModifier	×
254
NEW 255	ctrl_mods = [m for m in op.modifiers if isinstance(m, ControlModifier)]	×
NEW 256	if ctrl_mods:	×
NEW 257	nc = sum(m.num_ctrl_qubits for m in ctrl_mods)	×
NEW 258	return (op.base_op, nc, ctrl_mods[0].ctrl_state)	×
259	return None	1✔
260
261	def _params_match(self, p1, p2):	1✔
262	"""Check if two parameter tuples match within tolerance."""
263	if len(p1) != len(p2):	1✔
NEW 264	return False	×
265	return all(	1✔
266	(
267	np.isclose(a, b, atol=self.tolerance)
268	if isinstance(a, (int, float)) and isinstance(b, (int, float))
269	else a == b
270	)
271	for a, b in zip(p1, p2)
272	)
273
274	def _collect_gates(self, dag):	1✔
275	"""Collect runs of consecutive controlled gates from the DAG."""
276	runs, current = [], []	1✔
277	for node in dag.topological_op_nodes():	1✔
278	info = self._get_controlled_info(node.op)	1✔
279	if info is not None:	1✔
280	base_gate, nc, ctrl_state = info	1✔
281	qargs = [dag.find_bit(q).index for q in node.qargs]	1✔
282	ctrl_qubits = qargs[:nc]	1✔
283	tgt_qubits = qargs[nc:]	1✔
284	params = tuple(node.op.params) if node.op.params else ()	1✔
285	# Normalize control qubit ordering and remap ctrl_state
286	if ctrl_qubits != sorted(ctrl_qubits):	1✔
287	sort_order = sorted(range(nc), key=lambda k: ctrl_qubits[k])	1✔
288	new_cs = 0	1✔
289	for new_idx, old_idx in enumerate(sort_order):	1✔
290	if ctrl_state & (1 << old_idx):	1✔
291	new_cs \|= 1 << new_idx	1✔
292	ctrl_qubits = [ctrl_qubits[k] for k in sort_order]	1✔
293	ctrl_state = new_cs	1✔
294	current.append((node, base_gate, ctrl_qubits, tgt_qubits, ctrl_state, params))	1✔
295	elif current:	1✔
296	runs.append(current)	1✔
297	current = []	1✔
298	if current:	1✔
299	runs.append(current)	1✔
300	return runs	1✔
301
302	def _group_same_controls(self, gates):	1✔
303	"""Group gates sharing the same base gate, control qubits, and target."""
304	if len(gates) < 2:	1✔
305	return []	1✔
306	groups = []	1✔
307	used = set()	1✔
308	for i in range(len(gates)):	1✔
309	if i in used:	1✔
310	continue	1✔
311	_, bg_i, ctrl_i, tgt_i, _, params_i = gates[i]	1✔
312	group = [gates[i]]	1✔
313	group_indices = [i]	1✔
314	for j in range(i + 1, len(gates)):	1✔
315	if j in used:	1✔
316	continue	1✔
317	_, bg_j, ctrl_j, tgt_j, _, params_j = gates[j]	1✔
318	if (	1✔
319	bg_j.name == bg_i.name
320	and tgt_j == tgt_i
321	and ctrl_j == ctrl_i
322	and self._params_match(params_j, params_i)
323	):
324	group.append(gates[j])	1✔
325	group_indices.append(j)	1✔
326	else:
327	# Two controlled gates commute if their target qubits
328	# are disjoint (shared controls don't break commutativity).
329	# For safety, also require no target-control overlap.
330	group_tgts = set(tgt_i)	1✔
331	gate_tgts = set(tgt_j)	1✔
332	if (	1✔
333	group_tgts.isdisjoint(gate_tgts)
334	and group_tgts.isdisjoint(set(ctrl_j))
335	and gate_tgts.isdisjoint(set(ctrl_i))
336	):
337	continue # skip over commuting gate	1✔
338	else:
339	break	1✔
340	if len(group) >= 2:	1✔
341	groups.append(group)	1✔
342	used.update(group_indices)	1✔
343	return groups	1✔
344
345	def _group_mixed_controls(self, gates):	1✔
346	"""Group gates with subset/superset control qubit relationships."""
347	if len(gates) < 2:	1✔
348	return []	1✔
349	groups, used = [], set()	1✔
350	for i in range(len(gates)):	1✔
351	if i in used:	1✔
352	continue	1✔
353	_, bg_i, ctrl_i, tgt_i, _, params_i = gates[i]	1✔
354	group = [gates[i]]	1✔
355	base_c = set(ctrl_i)	1✔
356	for j in range(i + 1, len(gates)):	1✔
357	if j in used:	1✔
358	continue	1✔
359	_, bg_j, ctrl_j, tgt_j, _, params_j = gates[j]	1✔
360	cand_c = set(ctrl_j)	1✔
361	if (	1✔
362	bg_j.name == bg_i.name
363	and tgt_j == tgt_i
364	and self._params_match(params_j, params_i)
365	and (base_c <= cand_c or cand_c <= base_c)
366	):
367	group.append(gates[j])	1✔
368	used.add(j)	1✔
369	if len(group) >= 2 and len({len(g[2]) for g in group}) > 1:	1✔
370	groups.append(group)	1✔
371	used.add(i)	1✔
372	return groups	1✔
373
374	def _expand_pattern(self, ctrl_state, gate_ctrls, superset):	1✔
375	"""Expand a control pattern to a superset of control qubits."""
376	missing = [q for q in superset if q not in gate_ctrls]	1✔
377	if not missing:	1✔
378	return [ctrl_state]	1✔
379	expanded = []	1✔
380	gate_ctrl_set = set(gate_ctrls)	1✔
381	for combo in range(2 ** len(missing)):	1✔
382	p = 0	1✔
383	gate_bit_idx = 0	1✔
384	miss_bit_idx = 0	1✔
385	for sup_idx, q in enumerate(superset):	1✔
386	if q in gate_ctrl_set:	1✔
387	if ctrl_state & (1 << gate_bit_idx):	1✔
388	p \|= 1 << sup_idx	1✔
389	gate_bit_idx += 1	1✔
390	else:
391	if (combo >> miss_bit_idx) & 1:	1✔
392	p \|= 1 << sup_idx	1✔
393	miss_bit_idx += 1	1✔
394	expanded.append(p)	1✔
395	return expanded	1✔
396
397	def _build_gate(self, base_gate, params, ctrl_qubits, target_qubits, ctrl_state):	1✔
398	"""Build a ``(gate, qargs)`` tuple from the given parameters."""
399	gate = base_gate(*params) if params else base_gate()	1✔
400	if not ctrl_qubits:	1✔
401	return (gate, target_qubits)	1✔
402	return (	1✔
403	gate.control(len(ctrl_qubits), ctrl_state=ctrl_state, annotated=False),
404	ctrl_qubits + target_qubits,
405	)
406
407	def _build_optimized(self, group, optimizations, remaining):	1✔
408	"""Translate pairwise optimization descriptions into gate operations."""
409	bg = type(group[0][1]) # base_gate type	1✔
410	params = group[0][5] # params	1✔
411	tgt = group[0][3] # target_qubits	1✔
412	all_c = group[0][2] # control_qubits	1✔
413	gates = []	1✔
414	for opt in optimizations:	1✔
415	t = opt["type"]	1✔
416	cp = opt["control_positions"]	1✔
417	cs = opt["ctrl_state"]	1✔
418	cq = [all_c[p] for p in cp]	1✔
419	if t == "complementary":	1✔
420	gates.append(self._build_gate(bg, params, cq, tgt, cs))	1✔
421	elif t == "xor_standard":	1✔
422	qi, qj = opt["xor_qubits"]	1✔
423	gates.extend(	1✔
424	[
425	(CXGate(), [all_c[qi], all_c[qj]]),
426	self._build_gate(bg, params, cq, tgt, cs),
427	(CXGate(), [all_c[qi], all_c[qj]]),
428	]
429	)
430	elif t == "xor_with_x":	1✔
431	qi, qj = opt["xor_qubits"]	1✔
432	qic, qjc = all_c[qi], all_c[qj]	1✔
433	gates.extend(	1✔
434	[
435	(XGate(), [qjc]),
436	(CXGate(), [qic, qjc]),
437	self._build_gate(bg, params, cq, tgt, cs),
438	(CXGate(), [qic, qjc]),
439	(XGate(), [qjc]),
440	]
441	)
442	elif t == "xor_chain":	1✔
443	anc = all_c[opt["xor_anchor"]]	1✔
444	tgts = [all_c[x] for x in opt["xor_targets"]]	1✔
445	for tc in tgts:	1✔
446	gates.append((CXGate(), [anc, tc]))	1✔
447	gates.append(self._build_gate(bg, params, cq, tgt, cs))	1✔
448	for tc in reversed(tgts):	1✔
449	gates.append((CXGate(), [anc, tc]))	1✔
450	# Remaining unmatched patterns
451	rem_set = set(remaining)	1✔
452	for g in group:	1✔
453	if g[4] in rem_set: # ctrl_state	1✔
454	gates.append((g[0].op, [g[2][i] for i in range(len(g[2]))] + g[3]))	1✔
455	return gates or None	1✔
456
457	def run(self, dag):	1✔
458	"""Run the ControlPatternSimplification pass on ``dag``.
459
460	Args:
461	dag (DAGCircuit): the DAG to be optimized.
462
463	Returns:
464	DAGCircuit: the optimized DAG.
465	"""
466	# Identify groups of gates to optimize and their replacements.
467	# Use _node_id (stable DAG node identifier) as keys.
468	nodes_to_replace = {}	1✔
469	for run in self._collect_gates(dag):	1✔
470	used = set()	1✔
471	# Mixed control counts
472	for group in self._group_mixed_controls(run):	1✔
473	all_ctrls = sorted(set().union(*(set(g[2]) for g in group)))	1✔
474	expanded = []	1✔
475	for g in group:	1✔
476	expanded.extend(self._expand_pattern(g[4], g[2], all_ctrls))	1✔
477	if len(set(expanded)) == 2 ** len(all_ctrls):	1✔
478	bg = type(group[0][1])	1✔
479	repl = [self._build_gate(bg, group[0][5], [], group[0][3], 0)]	1✔
480	nodes_to_replace[group[0][0]._node_id] = repl	1✔
481	for g in group[1:]:	1✔
482	nodes_to_replace[g[0]._node_id] = None	1✔
483	used.update(g[0]._node_id for g in group)	1✔
484
485	# Same control qubits
486	remaining_gates = [g for g in run if g[0]._node_id not in used]	1✔
487	for group in self._group_same_controls(remaining_gates):	1✔
488	patterns = [g[4] for g in group]	1✔
489	nq = len(group[0][2])	1✔
490	unique = set(patterns)	1✔
491	g0 = group[0]	1✔
492	bg = type(g0[1])	1✔
493	params = g0[5]	1✔
494	ctrls = g0[2]	1✔
495	tgt = g0[3]	1✔
496
497	repl = None	1✔
498	if len(unique) == 1:	1✔
499	# All gates have the same ctrl_state: merge angles
500	merged_params = (sum(g[5][0] for g in group),) if params else ()	1✔
501	repl = [self._build_gate(bg, merged_params, ctrls, tgt, g0[4])]	1✔
502	else:
503	# Check for duplicate patterns: merge them first
504	from collections import Counter	1✔
505
506	counts = Counter(patterns)	1✔
507	has_duplicates = any(c > 1 for c in counts.values())	1✔
508	if has_duplicates:	1✔
509	# Merge duplicate patterns by summing angles, keep
510	# unique patterns as-is. Only proceed with pattern
511	# simplification on the unique-count subset.
512	repl = []	1✔
513	for cs_val, cnt in counts.items():	1✔
514	if cnt > 1 and params:	1✔
515	mp = (params[0] * cnt,) + params[1:]	1✔
516	else:
517	mp = params	1✔
518	repl.append(self._build_gate(bg, mp, ctrls, tgt, cs_val))	1✔
519	else:
520	# Each pattern appears exactly once: safe to simplify
521	cls, info, cs = BitwisePatternAnalyzer(nq).simplify_patterns(patterns)	1✔
522	if cls == "single" and info:	1✔
NEW 523	repl = [self._build_gate(bg, params, [ctrls[info[0]]], tgt, cs)]	×
524	elif cls == "and" and info:	1✔
NEW 525	repl = [self._build_gate(bg, params, [ctrls[i] for i in info], tgt, cs)]	×
526	elif cls == "unconditional":	1✔
527	repl = [self._build_gate(bg, params, [], tgt, 0)]	1✔
528	elif cls == "complement" and info:	1✔
529	neg = tuple(-p for p in params) if params else ()	1✔
530	repl = [	1✔
531	self._build_gate(bg, params, [], tgt, 0),
532	self._build_gate(bg, neg, [ctrls[i] for i in info], tgt, cs),
533	]
534	elif cls == "pairwise_iterative" and info:	1✔
535	repl = self._build_optimized(	1✔
536	group, info["optimizations"], info["remaining_patterns"]
537	)
538	elif cls == "pairwise" and info:	1✔
539	repl = self._build_optimized(group, info, [])	1✔
540
541	if repl:	1✔
542	nodes_to_replace[group[0][0]._node_id] = repl	1✔
543	for g in group[1:]:	1✔
544	nodes_to_replace[g[0]._node_id] = None	1✔
545
546	# Build a new DAG preserving topological order
547	new_dag = dag.copy_empty_like()	1✔
548	for node in dag.topological_op_nodes():	1✔
549	nid = node._node_id	1✔
550	if nid in nodes_to_replace:	1✔
551	replacement = nodes_to_replace[nid]	1✔
552	if replacement is not None:	1✔
553	for gate, qargs in replacement:	1✔
554	new_dag.apply_operation_back(gate, [new_dag.qubits[i] for i in qargs])	1✔
555	else:
556	new_dag.apply_operation_back(node.op, node.qargs, node.cargs)	1✔
557
558	return new_dag	1✔

Qiskit / qiskit / 23457822425

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