CliffordRzOptimization

QuICT.qcda.optimization.clifford_rz_optimization.CliffordRzOptimization

CliffordRzOptimization(level='light', optimize_toffoli=True, keep_phase=False, verbose=False)

Bases: object

Heuristic optimization of circuits in Clifford + Rz.

References

[1] Automated optimization of large quantum circuits with continuous parameters https://arxiv.org/abs/1710.07345

Examples:

>>> from QuICT.qcda.optimization import CliffordRzOptimization
>>> CRO = CliffordRzOptimization()
>>> circ_opt = CRO.execute(circuit)

Parameters:

• level (str, default: 'light' ) –

  Support 'light' and 'heavy' level. See details in [1]

• optimize_toffoli (bool, default: True ) –

  whether to decompose and optimize ccx/ccz gates into Clifford+rz

• keep_phase (bool, default: False ) –

  whether to keep the global phase as a GPhase gate in the output

• verbose (bool, default: False ) –

  whether to output details of each step

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def __init__(self, level='light', optimize_toffoli=True, keep_phase=False, verbose=False):
    """
    Args:
        level (str): Support 'light' and 'heavy' level. See details in [1]
        optimize_toffoli (bool): whether to decompose and optimize ccx/ccz gates into Clifford+rz
        keep_phase (bool): whether to keep the global phase as a GPhase gate in the output
        verbose (bool): whether to output details of each step
    """
    assert level in self._optimize_routine, Exception(f'unrecognized level {level}')
    self.level = level
    self.verbose = verbose
    self.optimize_toffoli = optimize_toffoli
    self.keep_phase = keep_phase

ReachableSet

ReachableSet(succ_node=None, max_size=1000000)

Data structure that manages the reachable relations in a DAG.

For a DAG of over 10000 nodes, storing reachable relations between all nodes consumes excessive memories. ReachableSet will automatically manage and store recently used relations.

Parameters:

• succ_node (List[Tuple[Node, int]], default: None ) –

  right boundary

• max_size (int, default: 1000000 ) –

  max number of entries stored in this set.

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def __init__(self, succ_node=None, max_size=1000000):
    """
    Args:
          succ_node (List[Tuple[DAG.Node, int]]): right boundary
          max_size (int): max number of entries stored in this set.
    """
    self.succ_node = succ_node
    self.size = 0
    self.reachable = {}
    self.max_size = max_size

query

query(node, qubit_, other) -> bool

Ask whether (node, qubit_) can reach the node other.

Parameters:

• node (Node) –

  the starting node

• qubit_ (int) –

  the starting wire

• other (Node) –

  the target node

Returns:

• bool ( bool ) –

  whether reachable

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def query(self, node, qubit_, other) -> bool:
    """
    Ask whether `(node, qubit_)` can reach the node `other`.

    Args:
        node (DAG.Node): the starting node
        qubit_ (int): the starting wire
        other (DAG.Node): the target node

    Returns:
        bool: whether reachable
    """
    key = (id(node), qubit_)
    if key not in self.reachable:
        new_set = DAG.get_reachable_set(node, qubit_, self.succ_node)
        if len(new_set) + self.size > self.max_size:
            self.reachable.clear()
        self.reachable[key] = new_set
        self.size += len(new_set)

    return id(other) in self.reachable[key]

assign_symbolic_phases

assign_symbolic_phases(gates: DAG) -> int

Assign polarity to undetermined T gates in the circuit. Do it greedily to reduce gate count.

Parameters:

• gates (DAG) –

  DAG of the circuit

Returns:

• int ( int ) –

  Number of gates reduced.

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def assign_symbolic_phases(self, gates: DAG) -> int:
    """
    Assign polarity to undetermined T gates in the circuit. Do it greedily to reduce gate count.

    Args:
        gates (DAG): DAG of the circuit

    Returns:
        int: Number of gates reduced.
    """
    if not gates.has_symbolic_rz:
        return 0

    # collect all variables in the circuit
    # label -> (variable, expr list)
    var_dict = {}
    for node_ in gates.topological_sort():
        if node_.gate_type == GateType.rz and isinstance(node_.params[0], SymbolicPhase):
            cur_var_dict = node_.params[0].var_dict
            for label in cur_var_dict:
                var, _ = cur_var_dict[label]
                if label not in var_dict:
                    var_dict[label] = [var, []]

                var_dict[label][1].append(node_.params[0])

    ret = 0
    # greedily assign polarity to each variable
    for var, expr_list in var_dict.values():
        var.phase = np.pi / 4
        t_cnt = sum([np.isclose(expr.evaluate(), 0) for expr in expr_list])
        var.phase = -np.pi / 4
        tdg_cnt = sum([np.isclose(expr.evaluate(), 0) for expr in expr_list])
        if t_cnt >= tdg_cnt:
            var.phase = np.pi / 4

        ret += max(t_cnt, tdg_cnt)

    # replace all symbolic param with actual value
    for node_ in gates.topological_sort():
        if node_.gate_type == GateType.rz and isinstance(node_.params[0], SymbolicPhase):
            node_.params[0] = node_.params[0].evaluate()

    # evaluate global phase
    gates.global_phase = gates.global_phase.evaluate()
    gates.has_symbolic_rz = False
    return ret

cancel_single_qubit_gates

cancel_single_qubit_gates(gates: DAG) -> int

Merge Rz gates in Clifford+Rz circuit.

Parameters:

• gates(DAG) –

  DAG of the circuit

Returns:

• int ( int ) –

  Number of gates reduced.

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def cancel_single_qubit_gates(self, gates: DAG) -> int:
    """
    Merge Rz gates in Clifford+Rz circuit.

    Args:
        gates(DAG): DAG of the circuit

    Returns:
        int: Number of gates reduced.
    """
    cnt = 0
    for node in list(gates.topological_sort()):
        # enumerate every single qubit gate
        if node.gate_type == GateType.id:
            node.erase()
            cnt += 1
            continue

        if node.gate_type != GateType.rz or node.flag == node.FLAG_ERASED:
            continue
        # erase the gate if degree = 0
        if np.isclose(float(node.params[0]), 0):
            node.erase()
            cnt += 1
            continue

        # try cancelling while commuting the gate with templates
        # (c_node, c_qubit): the position right before template matching
        c_node, c_qubit = node, 0
        while True:
            # (n_node, n_qubit): the start of template matching
            n_node, n_qubit = c_node.successors[c_qubit]
            # stop if reaching the end of circuit
            if not n_node.gate_type:
                break

            # if n_node is another rz, merge and erase the original node
            if n_node.gate_type == node.gate_type:
                n_node.params[0] = n_node.params[0] + node.params[0]
                node.erase()
                cnt += 1
                break

            # template matching
            mapping = None
            for template in self.single_qubit_gate_templates:
                mapping = mapping or template.compare(c_node.successors[c_qubit])
                if mapping:
                    # found a sub-circuit that commutes
                    # set (c_node, c_qubit) to be the last position of this sub-circuit
                    c_node, c_qubit = template.template.end_nodes[template.anchor].predecessors[0]
                    c_node = mapping[id(c_node)]
                    break
            # found no templates. commuting fails
            if not mapping:
                break
    return cnt

cancel_two_qubit_gates

cancel_two_qubit_gates(gates: DAG) -> int

Merge CX gate in Clifford+Rz circuit.

Parameters:

• gates (DAG) –

  DAG of the circuit

Returns:

• int ( int ) –

  Number of gates reduced.

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def cancel_two_qubit_gates(self, gates: DAG) -> int:
    """
    Merge CX gate in Clifford+Rz circuit.

    Args:
        gates (DAG): DAG of the circuit

    Returns:
        int: Number of gates reduced.
    """
    cnt = 0
    reachable = self.ReachableSet()
    for node in list(gates.topological_sort()):
        # enumerate every cnot gate
        if node.flag == DAG.Node.FLAG_ERASED or node.gate_type != GateType.cx:
            continue

        c_ctrl_node, c_ctrl_qubit = node, 0
        c_targ_node, c_targ_qubit = node, 1
        while True:
            n_ctrl_node, n_ctrl_qubit = c_ctrl_node.successors[c_ctrl_qubit]
            n_targ_node, n_targ_qubit = c_targ_node.successors[c_targ_qubit]
            # remove two adjacent cnot gates
            if id(n_ctrl_node) == id(n_targ_node) and n_ctrl_node.gate_type == GateType.cx and \
                    n_ctrl_qubit == 0 and n_targ_qubit == 1:
                n_ctrl_node.erase()
                node.erase()
                cnt += 2
                break

            # try commuting node with templates anchored in control qubit
            mapping = None
            for template in self.cnot_ctrl_template:
                mapping = template.compare(c_ctrl_node.successors[c_ctrl_qubit])
                # After we find a template U after current cnot, there are two cases:
                # Case 1:        .___.         .___.
                #         --O----| U |--     --| U |---O--
                #           |    |___|     =   |___|   |
                #         --X-----------     ----------X--
                # Case 2:        .___.         .___.
                #         --O----|   |--     --|   |---O--
                #           |    | U |    !=   | U |   |
                #         --X----|___|--     --|___|---X--
                # The template only guarantees control node 'O' can be moved across U, so case 2 is invalid.
                # By further checking whether 'X' can reach any nodes in U, we can exclude case 2.

                if mapping and all([not reachable.query(c_targ_node, c_targ_qubit, o) for o in mapping.values()]):
                    c_ctrl_node, c_ctrl_qubit = template.template.end_nodes[template.anchor].predecessors[0]
                    c_ctrl_node = mapping[id(c_ctrl_node)]
                    break
                else:
                    mapping = None
            if mapping:
                continue

            # try commuting node with templates anchored in target qubit
            for template in self.cnot_targ_template:
                mapping = template.compare(c_targ_node.successors[c_targ_qubit])
                # if control node can reach any node in the template, it will block commuting.
                if mapping and all([not reachable.query(c_ctrl_node, c_ctrl_qubit, o) for o in mapping.values()]):
                    c_targ_node, c_targ_qubit = template.template.end_nodes[template.anchor].predecessors[0]
                    c_targ_node = mapping[id(c_targ_node)]
                    break
                else:
                    mapping = None
            if not mapping:
                break
    return cnt

deparameterize_all

deparameterize_all(gates: DAG)

Convert all applicable T/Tdg/S/Sdg/Z into Rz in the circuit.

Parameters:

• gates (DAG) –

  DAG of the circuit

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def deparameterize_all(self, gates: DAG):
    """
    Convert all applicable T/Tdg/S/Sdg/Z into Rz in the circuit.

    Args:
        gates (DAG): DAG of the circuit
    """
    for node in gates.topological_sort():
        if node.gate_type == GateType.rz and not isinstance(node.params[0], SymbolicPhase):
            compo_gate_, phase_ = CommutativeOptimization.deparameterize(node.get_gate())
            if len(compo_gate_.gates) > 1:
                continue
            node.gate_type = compo_gate_[0].type
            node.params = compo_gate_[0].pargs.copy()
            gates.global_phase += phase_

    if not isinstance(gates.global_phase, SymbolicPhase):
        gates.global_phase %= 2 * np.pi
    else:
        gates.global_phase = np.mod(gates.global_phase, 2 * np.pi)

execute

execute(gates) -> Circuit

Parameters:

• gates (Circuit) –

  Circuit to be optimized

Returns:

• Circuit ( Circuit ) –

  The circuit after optimization

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

@OutputAligner()
def execute(self, gates) -> Circuit:
    """
    Args:
        gates (Circuit): Circuit to be optimized

    Returns:
        Circuit: The circuit after optimization
    """
    routine = self._optimize_routine[self.level]
    _gates = DAG(gates, self.optimize_toffoli)
    self.parameterize_all(_gates)

    gate_cnt = 0
    round_cnt = 0
    total_time = 0

    while True:
        round_cnt += 1
        if self.verbose:
            print(f'ROUND #{round_cnt}:')

        cnt = 0
        # apply each method in routine
        for step in routine:
            start_time = time.time()
            cur_cnt = getattr(self, self._optimize_sub_method[step])(_gates)
            end_time = time.time()

            if self.verbose:
                print(f'\t{self._optimize_sub_method[step]}: {cur_cnt} '
                      f'gates reduced, cost {np.round(end_time - start_time, 3)} s')

            cnt += cur_cnt
            total_time += end_time - start_time

        if cnt == 0:
            # assign symbolic t gates for nearly optimized circuit
            start_time = time.time()
            cnt += self.assign_symbolic_phases(_gates)
            end_time = time.time()
            if self.verbose:
                print(f'\tassign_symbolic_phases: {cnt} '
                      f'gates reduced, cost {np.round(end_time - start_time, 3)} s')

            # stop if nothing can be optimized
            if cnt == 0:
                break

        gate_cnt += cnt

    self.deparameterize_all(_gates)
    ret = _gates.get_circuit(self.keep_phase)

    if self.verbose:
        print(f'initially {_gates.init_size} gates, '
              f'remain {ret.size()} gates, cost {np.round(total_time, 3)} s')
    return ret

float_cancel_two_qubit_gates

float_cancel_two_qubit_gates(gates)

Merge CX gates in the circuit while considering float positions of Rz gates.

Parameters:

• gates (DAG) –

  DAG of the circuit

Returns:

• int –

  Number of gates reduced.

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def float_cancel_two_qubit_gates(self, gates):
    """
    Merge CX gates in the circuit while considering float positions of Rz gates.

    Args:
        gates (DAG): DAG of the circuit

    Returns:
        int: Number of gates reduced.
    """
    gates.reset_flag()
    gates.set_qubit_loc()
    cnt = 0
    for prev_node, succ_node, node_cnt in list(self._enumerate_cnot_rz_circuit(gates)):
        # the boundary given by enumerate_cnot_rz_circuit is described by internal node of
        # the sub circuit, but PhasePolynomial and replace method need eternal boundary.
        # This conversion is necessary because nodes in eternal boundary may change due to previous iteration.
        for qubit_ in range(gates.width()):
            if prev_node[qubit_] is not None:
                c_node, c_qubit = prev_node[qubit_]
                prev_node[qubit_] = c_node.predecessors[c_qubit]
                c_node, c_qubit = succ_node[qubit_]
                succ_node[qubit_] = c_node.successors[c_qubit]
        cnt += self._float_cancel_sub_circuit(prev_node, succ_node)
    return cnt

float_rotations

float_rotations(gates: DAG)

Reduce gate count by considering float positions of Rz gates.

Parameters:

• gates (DAG) –

  DAG of the circuit

Returns:

• int –

  Number of gates reduced.

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def float_rotations(self, gates: DAG):
    """
    Reduce gate count by considering float positions of Rz gates.

    Args:
        gates (DAG): DAG of the circuit

    Returns:
        int: Number of gates reduced.
    """
    cnt = 0
    cnt += self.float_cancel_two_qubit_gates(gates)
    cnt += self.gate_preserving_rewrite(gates)
    cnt += self.gate_reducing_rewrite(gates)
    return cnt

gate_preserving_rewrite

gate_preserving_rewrite(gates)

Reduce gate count by gate preserving rewrite rules.

Parameters:

• gates (DAG) –

  DAG of the circuit

Returns: int: Number of gates reduced.

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def gate_preserving_rewrite(self, gates):
    """
    Reduce gate count by gate preserving rewrite rules.

    Args:
        gates (DAG): DAG of the circuit
    Returns:
        int: Number of gates reduced.
    """

    cnt = 0
    success = True
    while success:
        success = False
        for template in self.gate_preserving_rewrite_template:
            for node in gates.topological_sort():
                mapping = template.compare((node, -1), dummy_rz=True)
                if not mapping:
                    continue
                original, undo_mapping = template.regrettable_replace(mapping)

                if self.try_float_cancel_two_qubit_gates(gates):
                    # if rewriting enables cancellation else where, do it and restart template matching
                    cnt += self.float_cancel_two_qubit_gates(gates)
                    success = True
                    break

                # undo replacing if otherwise
                template.undo_replace(original, undo_mapping)
            if success:
                break
    return cnt

gate_reducing_rewrite

gate_reducing_rewrite(gates)

Reduce gate count by gate reducing rewrite rules.

Parameters:

• gates (DAG) –

  DAG of the circuit

Returns:

• int –

  Number of gates reduced.

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def gate_reducing_rewrite(self, gates):
    """
    Reduce gate count by gate reducing rewrite rules.

    Args:
        gates (DAG): DAG of the circuit

    Returns:
        int: Number of gates reduced.
    """
    cnt = 0
    for template in self.gate_reducing_rewrite_template:
        cnt += template.replace_all(gates) * template.weight
    if cnt:
        cnt += self.float_cancel_two_qubit_gates(gates)
        cnt += self.cancel_two_qubit_gates(gates)
    return cnt

merge_rotations

merge_rotations(gates: DAG)

Merge Rz gates using phase polynomials.

Parameters:

• gates (DAG) –

  DAG of the circuit

Returns:

• int –

  Number of gates reduced.

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def merge_rotations(self, gates: DAG):
    """
    Merge Rz gates using phase polynomials.

    Args:
        gates (DAG): DAG of the circuit

    Returns:
        int: Number of gates reduced.
    """
    gates.reset_flag()
    gates.set_qubit_loc()
    cnt = 0
    for idx, anchor_ in enumerate(list(gates.topological_sort())):
        if anchor_.gate_type != GateType.cx or anchor_.flag == anchor_.FLAG_VISITED:
            continue

        node_list = self._traverse_cnot_rz_circuit(anchor_, idx * 2)
        cnt += self._parse_cnot_rz_circuit(node_list)

    return cnt

parameterize_all

parameterize_all(gates: DAG)

Convert all applicable Rz gates into T/Tdg/S/Sdg/Z in the circuit.

Parameters:

• gates (DAG) –

  DAG of the circuit

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def parameterize_all(self, gates: DAG):
    """
    Convert all applicable Rz gates into T/Tdg/S/Sdg/Z in the circuit.

    Args:
        gates (DAG): DAG of the circuit
    """
    for node in gates.topological_sort():
        if node.gate_type in [GateType.s, GateType.t, GateType.sdg, GateType.tdg, GateType.z]:
            gate_, phase_ = CommutativeOptimization.parameterize(node.get_gate())
            node.gate_type = gate_.type
            node.params = gate_.pargs.copy()
            gates.global_phase += phase_

    if not isinstance(gates.global_phase, SymbolicPhase):
        gates.global_phase %= 2 * np.pi
    else:
        gates.global_phase = np.mod(gates.global_phase, 2 * np.pi)

reduce_hadamard_gates

reduce_hadamard_gates(gates: DAG) -> int

Reduce hadamard gates in Clifford+Rz circuits by template matching. Adjacent X gates will also be cancelled out.

Parameters:

• gates (DAG) –

  DAG of the circuit

Returns:

• int ( int ) –

  Number of H gates reduced.

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def reduce_hadamard_gates(self, gates: DAG) -> int:
    """
    Reduce hadamard gates in Clifford+Rz circuits by template matching.
    Adjacent X gates will also be cancelled out.

    Args:
        gates (DAG): DAG of the circuit

    Returns:
        int: Number of H gates reduced.
    """
    cnt = 0
    self.deparameterize_all(gates)
    # enumerate templates and replace every occurrence
    for template in self.hadamard_templates:
        cnt += template.replace_all(gates) * template.weight
    self.parameterize_all(gates)
    return cnt

try_float_cancel_two_qubit_gates

try_float_cancel_two_qubit_gates(gates)

Test whether float_cancel_two_qubit_gates can reduce gate count in the current circuit.

Parameters:

• gates (DAG) –

  DAG of the circuit

Returns:

• bool –

  whether float_cancel_two_qubit_gates can reduce gate count

Source code in QuICT/qcda/optimization/clifford_rz_optimization/clifford_rz_optimization.py

def try_float_cancel_two_qubit_gates(self, gates):
    """
    Test whether float_cancel_two_qubit_gates can reduce gate count in the current circuit.

    Args:
        gates (DAG): DAG of the circuit

    Returns:
        bool: whether float_cancel_two_qubit_gates can reduce gate count
    """

    gates.reset_flag()
    gates.set_qubit_loc()
    for prev_node, succ_node, node_cnt in list(self._enumerate_cnot_rz_circuit(gates)):
        # the boundary given by enumerate_cnot_rz_circuit is described by internal node of
        # the sub circuit, but PhasePolynomial and replace method need eternal boundary.
        # This conversion is necessary because nodes in eternal boundary may change due to previous iteration.
        for qubit_ in range(gates.width()):
            if prev_node[qubit_] is not None:
                c_node, c_qubit = prev_node[qubit_]
                prev_node[qubit_] = c_node.predecessors[c_qubit]
                c_node, c_qubit = succ_node[qubit_]
                succ_node[qubit_] = c_node.successors[c_qubit]
        if self._try_float_cancel_sub_circuit(prev_node, succ_node):
            return True

    return False