跳转至

utility

QuICT.qcda.optimization.cnot_without_ancilla.utility

Merged 

Merged(deg: int, nodes: List[int])

Merged points in heap

Attributes:

  • deg (int) –

    degree of x

  • nodes (List[int]) –

    node indices in a bipartite

Get a merged point

Parameters:

  • deg (int) –

    degree of x

  • nodes (List[int]) –

    node indices in a bipartite

Source code in QuICT/qcda/optimization/cnot_without_ancilla/utility.py 
17
18
19
20
21
22
23
24
25
26
def __init__(self, deg: int, nodes: List[int]):
    """
    Get a merged point

    Args:
        deg (int): degree of x
        nodes (List[int]): node indices in a bipartite
    """
    self.deg = deg
    self.nodes = nodes
__add__ 
__add__(other: Merged) -> Merged

combine two merged points to a larger merged

Parameters:

  • other (Merged) –

    Another Merged node.

Source code in QuICT/qcda/optimization/cnot_without_ancilla/utility.py 
28
29
30
31
32
33
34
35
36
37
def __add__(self, other: "Merged") -> "Merged":
    """
    combine two merged points to a larger merged

    Args:
        other (Merged): Another Merged node.
    """
    d = self.deg + other.deg
    x = self.nodes + other.nodes
    return Merged(d, x)

f2_half_gaussian_elimination 

f2_half_gaussian_elimination(mat_: ndarray) -> np.ndarray

Gaussian elimination to convert a matrix into triangular form over F_2. Args: mat_ (np.ndarray): Input boolean matrix.

Returns:

  • ndarray –

    np.ndarray: Eliminated triangular matrix.

Source code in QuICT/qcda/optimization/cnot_without_ancilla/utility.py 
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
def f2_half_gaussian_elimination(mat_: np.ndarray) -> np.ndarray:
    """
    Gaussian elimination to convert a matrix into triangular form over F_2.
    Args:
        mat_ (np.ndarray): Input boolean matrix.

    Returns:
        np.ndarray: Eliminated triangular matrix.
    """
    mat: np.ndarray = mat_.copy()
    row_pivot = 0
    col_pivot = 0
    m = mat.shape[0]
    n = mat.shape[1]
    while row_pivot < m and col_pivot < n:
        if not mat[row_pivot, col_pivot]:
            for k in range(row_pivot + 1, m):
                if mat[k, col_pivot]:
                    mat[[k, row_pivot], :] = mat[[row_pivot, k], :]
                    break
        if mat[row_pivot, col_pivot]:
            for k in range(row_pivot + 1, m):
                if mat[k, col_pivot]:
                    mat[k, :] ^= mat[row_pivot, :]
            row_pivot += 1
            col_pivot += 1
        else:
            col_pivot += 1
    return mat

f2_inverse 

f2_inverse(mat_: ndarray) -> np.ndarray

Matrix inverse over F_2. Args: mat_ (np.ndarray): Input boolean matrix.

Returns:

  • ndarray –

    np.ndarray: The inverse boolean matrix of mat_ over F_2.

Source code in QuICT/qcda/optimization/cnot_without_ancilla/utility.py 
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
def f2_inverse(mat_: np.ndarray) -> np.ndarray:
    """
    Matrix inverse over F_2.
    Args:
        mat_ (np.ndarray): Input boolean matrix.

    Returns:
        np.ndarray: The inverse boolean matrix of mat_ over F_2.
    """
    n = mat_.shape[0]
    aug = np.empty(shape=(n, 2 * n), dtype=bool)
    aug[:, :n] = mat_
    aug[:, n:] = np.eye(n, dtype=bool)

    # gaussian elimination
    for i in range(n):
        if not aug[i, i]:
            for k in range(i + 1, n):
                if aug[k, i]:
                    aug[[k, i], :] = aug[[i, k], :]
                    break
        if not aug[i, i]:
            raise Exception("Matrix is not invertible!")
        for k in range(n):
            if i != k and aug[k, i]:
                aug[k, :] ^= aug[i, :]
    ret = aug[:, n:].copy()
    return ret

f2_matmul 

f2_matmul(a: ndarray, b: ndarray) -> np.ndarray

Multiply 2 matrices in F_2.

Parameters:

  • a (ndarray) –

    Input boolean matrix a.

  • b (ndarray) –

    Input boolean matrix b.

Returns:

  • ndarray –

    np.ndarray: Production of ab over F_2.

Source code in QuICT/qcda/optimization/cnot_without_ancilla/utility.py 
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def f2_matmul(a: np.ndarray, b: np.ndarray) -> np.ndarray:
    """
    Multiply 2 matrices in F_2.

    Args:
        a (np.ndarray): Input boolean matrix a.
        b (np.ndarray): Input boolean matrix b.

    Returns:
        np.ndarray: Production of ab over F_2.
    """
    a_ = np.array(a, dtype=int)
    b_ = np.array(b, dtype=int)
    c_ = a_ @ b_
    c_ %= 2
    c = np.array(c_, dtype=bool)
    return c

f2_rank 

f2_rank(mat_: ndarray) -> int

Rank of a matrix over F_2. Args: mat_ (np.ndarray): Input boolean matrix.

Returns:

  • int ( int ) –

    Rank of mat_ over F_2.

Source code in QuICT/qcda/optimization/cnot_without_ancilla/utility.py 
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
def f2_rank(mat_: np.ndarray) -> int:
    """
    Rank of a matrix over F_2.
    Args:
        mat_ (np.ndarray): Input boolean matrix.

    Returns:
        int: Rank of mat_ over F_2.
    """
    mat = f2_half_gaussian_elimination(mat_)
    rk = 0
    for i in range(mat.shape[0]):
        if np.any(mat[i, :]):
            rk += 1
    return rk