qBraid · PranavTupe2000 · Mar 3, 2025 · Mar 4, 2025 · Mar 4, 2025 · Mar 6, 2025
@@ -0,0 +1,14 @@
+"""
+Sub module for quantum algorithms.
+
+Functions:
+----------
+    solovay_kitaev: Solovay-Kitaev algorithm for approximating unitary gates.
+
+"""
+
+from .solovay_kitaev import solovay_kitaev
+
+__all__ = [
+    "solovay_kitaev",
+]
@@ -0,0 +1,14 @@
+"""
+Sub module for quantum algorithms.
+
+Functions:
+----------
+    solovay_kitaev: Solovay-Kitaev algorithm for approximating unitary gates.
+
+"""
+
+from .solovay_kitaev import solovay_kitaev
+
+__all__ = [
+    "solovay_kitaev",
+]
@@ -0,0 +1,98 @@
+"""
+Definition of the basic approximation algorithm for the Solovay-Kitaev theorem.
+"""
+
+import numpy as np
+
+from pyqasm.algorithms.solovay_kitaev.utils import TU2Matrix, get_tu2matrix_for_basic_approximation
+from pyqasm.elements import BasisSet
+
+
+def rescursive_traversal(
+    target_matrix, approximated_matrix, target_gate_set_list, current_depth, params
+):
+    """Recursively traverse the tree to find the best approximation of the target matrix.
+    Args:
+        target_matrix (np.ndarray): The target matrix to approximate.
+        approximated_matrix (TU2Matrix): The approximated matrix.
+        target_gate_set_list (list): The list of target gates to approximate.
+        current_depth (int): The current depth of the tree.
+        params (tuple): The parameters for the approximation.
+
+    Returns:
+        float: The closest difference between the target and approximated matrix.
+        TU2Matrix: The closest approximated matrix.
+        TU2Matrix: The best approx
+
+    """
+    accuracy, max_tree_depth, best_gate = params
+
+    if current_depth >= max_tree_depth:
+        return best_gate
+
+    for gate in target_gate_set_list:
+        if not approximated_matrix.can_multiple(gate):
+            continue
+        approximated_matrix_copy = approximated_matrix.copy()
+        approximated_matrix = approximated_matrix * gate
+
+        diff = approximated_matrix.distance(target_matrix)
+        if diff < accuracy:
+            best_gate = approximated_matrix.copy()
+            return best_gate
+
+        # Update the closest gate if the current one is closer
+        if diff < best_gate.distance(target_matrix):
+            best_gate = approximated_matrix.copy()
+
+        best_gate = rescursive_traversal(
+            target_matrix,
+            approximated_matrix.copy(),
+            target_gate_set_list,
+            current_depth + 1,
+            (accuracy, max_tree_depth, best_gate),
+        )
+        approximated_matrix = approximated_matrix_copy.copy()
+
+    return best_gate
+
+
+def basic_approximation(target_matrix, target_gate_set, accuracy=0.001, max_tree_depth=3):
+    """Approximate the target matrix using the basic approximation algorithm.
+
+    Args:
+        target_matrix (np.ndarray): The target matrix to approximate.
+        target_gate_set (BasisSet): The target gate set to approximate.
+        accuracy (float): The accuracy of the approximation.
+        max_tree_depth (int): The maximum depth of the tree.
+
+    Returns:
+        TU2Matrix: The approximated matrix.
+    """
+    approximated_matrix = TU2Matrix(np.identity(2), [], None, None)
+    target_gate_set_list = get_tu2matrix_for_basic_approximation(target_gate_set)
+    current_depth = 0
+    best_gate = TU2Matrix(np.identity(2), [], None, None)
+
+    params = (accuracy, max_tree_depth, best_gate)
+
+    best_gate = rescursive_traversal(
+        target_matrix, approximated_matrix.copy(), target_gate_set_list, current_depth, params
+    )
+
+    return best_gate
+
+    # result = None
+
+    # if best_gate:
+    #     result = best_gate.copy()
+    # else:
+    #     result = closest_gate.copy()
+
+    # return result
+
+
+if __name__ == "__main__":
+    target_matrix_U = np.array([[0.70711, 0.70711j], [0.70711j, 0.70711]])
+
+    print(basic_approximation(target_matrix_U, BasisSet.CLIFFORD_T, 0.0001, 3))
@@ -0,0 +1,59 @@
+import math
+from typing import List
+import numpy as np
+from pyqasm.algorithms.solovay_kitaev.utils import SU2Matrix
+
+def u_to_bloch(u):
+  """Compute angle and axis for a unitary."""
+
+  angle = np.real(np.arccos((u[0, 0] + u[1, 1]) / 2))
+  sin = np.sin(angle)
+  if sin < 1e-10:
+    axis = [0, 0, 1]
+  else:
+    nx = (u[0, 1] + u[1, 0]) / (2j * sin)
+    ny = (u[0, 1] - u[1, 0]) / (2 * sin)
+    nz = (u[0, 0] - u[1, 1]) / (2j * sin)
+    axis = [nx, ny, nz]
+  return axis, 2 * angle
+
+def Rotation(vparm: List[float], theta: float, name: str):
+  """Produce the single-qubit rotation operator."""
+
+  v = np.asarray(vparm)
+  if v.shape != (3,) or not math.isclose(v @ v, 1) or not np.all(np.isreal(v)):
+    raise ValueError('Rotation vector v must be a 3D real unit vector.')
+
+  return np.cos(theta / 2) * np.identity(2) - 1j * np.sin(theta / 2) * (v[0] * np.array([[0.0, 1.0], [1.0, 0.0]]) + v[1] * np.array([[0.0, -1.0j], [1.0j, 0.0]]) + v[2] * np.array([[1.0, 0.0], [0.0, -1.0]]))
+
+
+def RotationX(theta: float):
+  return Rotation([1.0, 0.0, 0.0], theta, 'Rx')
+
+
+def RotationY(theta: float):
+  return Rotation([0.0, 1.0, 0.0], theta, 'Ry')
+
+
+def RotationZ(theta: float):
+  return Rotation([0.0, 0.0, 1.0], theta, 'Rz')
+
+def gc_decomp(u):
+    axis, theta = u_to_bloch(u)
+
+    phi = 2.0 * np.arcsin(np.sqrt(np.sqrt((0.5 - 0.5 * np.cos(theta / 2)))))
+    v = RotationX(phi)
+    if axis[2] > 0:
+        w = RotationY(2 * np.pi - phi)
+    else:
+        w = RotationY(phi)
+
+    _, ud = np.linalg.eig(u)
+
+    vwvdwd = v @ w @ v.conj().T @ w.conj().T
+
+    s = ud @ vwvdwd.conj().T
+
+    v_hat = s @ v @ s.conj().T
+    w_hat = s @ w @ s.conj().T
+    return SU2Matrix(v_hat, []), SU2Matrix(w_hat, [])
@@ -0,0 +1,94 @@
+"""
+Definition of the optimizer for the Solovay-Kitaev theorem.
+"""
+
+from pyqasm.algorithms.solovay_kitaev.utils import get_identity_weight_group_for_optimizer
+from pyqasm.elements import BasisSet
+
+
+def optimize_gate_sequence(seq: list[str], target_basis_set):
+    """Optimize a gate sequence based on the identity weight group.
+    Args:
+        seq (list[str]): The gate sequence to optimize.
+        target_basis_set (BasisSet): The target basis set.
+
+    Returns:
+        list[str]: The optimized gate sequence.
+    """
+    target_identity_weight_group = get_identity_weight_group_for_optimizer(target_basis_set)
+    for _ in range(int(1e6)):
+        current_group = None
+        current_weight = 0
+        start_index = 0
+        changed = False
+
+        for i, gate_name in enumerate(seq):
+            if gate_name not in target_identity_weight_group:
+                continue
+
+            gate = target_identity_weight_group[gate_name]
+            new_group = gate["group"]
+            new_weight = gate["weight"]
+
+            if current_group is None or new_group != current_group:
+                current_group = new_group
+                current_weight = new_weight
+                start_index = i
+            else:
+                current_weight += new_weight
+
+            if current_weight == 1:
+                seq = seq[:start_index] + seq[i + 1 :]
+                changed = True
+                break
+            if current_weight > 1:
+                remaining_weight = current_weight - 1
+                for key, value in target_identity_weight_group.items():
+                    if value["group"] == current_group and value["weight"] == remaining_weight:
+                        seq = seq[:start_index] + [key] + seq[i + 1 :]
+                        changed = True
+                        break
+                break
+
+        if not changed:
+            return seq
+
+    return seq
+
+
+if __name__ == "__main__":
+    s1 = ["s", "s", "s", "t", "t", "tdg", "sdg", "sdg", "sdg", "tdg", "s", "h", "s"]
+    s2 = [
+        "t",
+        "s",
+        "s",
+        "s",
+        "t",
+        "tdg",
+        "tdg",
+        "sdg",
+        "sdg",
+        "sdg",
+        "t",
+        "s",
+        "s",
+        "s",
+        "t",
+        "tdg",
+        "tdg",
+        "sdg",
+        "sdg",
+        "sdg",
+        "s",
+        "h",
+        "s",
+    ]
+    s3 = ["h", "s", "s", "t", "t", "s", "t"]  # ['h', 't']
+    s4 = ["h", "s", "s", "t", "t", "s", "h"]  # []
+    s5 = ["h", "s", "s", "t", "h", "h", "t", "s", "h", "t"]  # ['t']
+
+    print(optimize_gate_sequence(s1, BasisSet.CLIFFORD_T) == ["s", "h", "s"])
+    print(optimize_gate_sequence(s2, BasisSet.CLIFFORD_T) == ["s", "h", "s"])
+    print(optimize_gate_sequence(s3, BasisSet.CLIFFORD_T) == ["h", "t"])
+    print(optimize_gate_sequence(s4, BasisSet.CLIFFORD_T) == [])
+    print(optimize_gate_sequence(s5, BasisSet.CLIFFORD_T) == ["t"])