8000 Implemented Solovay Kitaev's Algorithm by PranavTupe2000 · Pull Request #156 · qBraid/pyqasm · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Implemented Solovay Kitaev's Algorithm #156

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Draft
wants to merge 21 commits into
base: main
Choose a base branch
from

Conversation

PranavTupe2000
Copy link
Contributor

Summary of changes

This PR contains implementation of a Solovay Kitaev's Algorithm to estimate conversion of parameterized gates to non parameterized gate to an arbitrary accuracy.

Copy link
Member
@TheGupta2012 TheGupta2012 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Really great work on the implementation @PranavTupe2000 ! I've given some comments for the next steps as you start integrating this into the code base.

from pyqasm.algorithms.solovay_kitaev.basic_approximation import basic_approximation
from pyqasm.elements import BasisSet

gate_matrix = {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Move this map to the generator.py or basic_approximation.py

target_su2 = SU2Matrix(target, [])

target_basis_gate_list = BASIS_GATE_MAP[target_basis_set]
basic_gates_su2 = [SU2Matrix(gate_matrix[gate], [gate]) for gate in target_basis_gate_list if gate != "cx"]
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should have some identifier in the basis_set which identifies the number of qubits for the gate instead of checking for cx string

Args:
target: Target unitary matrix as numpy array
target_basis_set: The target basis set to rebase the module to.
depth: Recursion depth
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can we try and find some sort of relation between the recursion depth and the depth of the final sequence of gates? It'll be helpful for the user to set a particular depth limit for a gate decomposition


def optimize_gate_sequnce(seq: list[str], target_basis_set):
target_identity_weight_group = IDENTITY_WEIGHT_GROUP[target_basis_set]
while True:
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Let's have a finite limit for this processing, we don't wanna get stuck in the loop. 1e6 iterations should be a good limit to consider

s4 = ['h', 's', 's', 't', 't', 's', 'h'] # []
s5 = ['h', 's', 's', 't', 'h', 'h', 't', 's', 'h', 't'] # ['t']

print(optimize_gate_sequnce(s1, BasisSet.CLIFFORD_T) == ['s', 'h', 's'])
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can we add some randomized tests for this optimizer? I'd like to see how it performs with random inputs by comparing the matrices of the input and output sequences.

}
}

def optimize_gate_sequnce(seq: list[str], target_basis_set):
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
def optimize_gate_sequnce(seq: list[str], target_basis_set):
def optimize_gate_sequence(seq: list[str], target_basis_set):

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Also change the reference at other places


import numpy as np

gate_sets = {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can we instead expand the IDENTITY_WEIGHT_GROUP to also contain the matrix and use that here as I see duplication between the two data structures

@TheGupta2012
Copy link
Member
TheGupta2012 commented Mar 6, 2025

Some comments following up from the meeting -

Testing the algorithm

We need to test the algorithm on performance and accuracy across a varying range of input matrices. A good way to randomize these tests would be to use Qiskit's random_circuit method. This will enable you to test for 1-qubit circuits of depths. The plan would be something like -

Accuracy

  1. Set depth range - (1 - 20)
  2. Generate 100 random circuits with depth <= depth range
  3. Extract the unitary matrix for the circuit
  4. Run the solovay kitaev decomposer for the circuit
  5. We should be able to converge to a clifford sequence for the given gate

Performance

  • Steps 1-5 should be timed for 100 experiments with run time of each experiment averaged over 10 runs.
  • We want our decomposer to scale upto $10^6$ (possibly $10^9$) gate decompositions. A reasonable running time for $10^6$ decompositions should be < 10s, which puts a limit to $10^{-5} s$ per gate.
  • It is okay if we do not reach these run times in this PR but this is somewhere we should be headed towards as the decomposer should scale well for it to work with very large qasm files

Traversal 8000 Basic Approximations

Instead of generating a cache file for the initial guesses, we should be able to traverse the tree of possibilities in that cache. The major advantages of this approach are -

  • Lesser memory requirements as it is not required to generate a cache of basic approximations
  • More flexibility for the algorithm as we do not have to pre-compute the approximation cache before running the solovay kitaev algorithm for different initial depths

@PranavTupe2000
Copy link
Contributor Author

For now, I have just pushed the code of Traversal basic approximation, if anyone wants to check it out. Now I will integrate it with main code, and then I will perform the testing.

@TheGupta2012
Copy link
Member

The changes look great @PranavTupe2000! I think the PR is quite close in terms of implementation. I'll add some more comments related to the general code structure. I think the major remaining chunk of implementation is with respect to the tests for performance and accuracy for decomposing non-clifford 1 qubit gates.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Let us export the algorithm in the __init__.py so that we can import it something like -

from pyqasm.algorithms import solovay_kitaev

Although we are majorly gonna be using it internally, it helps to import the core functionality of a module for easier imports . See the pyqasm/modules for reference.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Let's add an import here -

from .solovay_kitaev import solovay_kitaev

and then in the algorithms init, use -

from pyqasm.algorithms.solovay_kitaev import solovay_kitaev
__all__ = ["solovay_kitaev"]

Looks a little cleaner that way


"""

from pyqasm.algorithms.solovay_kitaev.solovay_kitaev import solovay_kitaev
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
from pyqasm.algorithms.solovay_kitaev.solovay_kitaev import solovay_kitaev
from .solovay_kitaev.solovay_kitaev import solovay_kitaev

Comment on lines +59 to +94
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"])
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Remove

Comment on lines +86 to +100
# error = target * prev_sequence.dagger()

# # Find Va and Vb such that their group commutator approximates the error
# best_v = None
# best_w = None
# best_error = float("inf")

# for v in basic_gates:
# for w in basic_gates:
# comm = group_commutator(v, w)
# curr_error = error.distance(comm)
# if curr_error < best_error:
# best_error = curr_error
# best_v = v
# best_w = w
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Remove if not relevant, or convert to code

Comment on lines +154 to +182
# if __name__ == "__main__":
# target_matrix_U = np.array([[0.70711, 0.70711j], [0.70711j, 0.70711]])

# r0 = solovay_kitaev(target_matrix_U, BasisSet.CLIFFORD_T, depth=0)
# print(r0.name) # Output: ['s', 'h', 's']

# r1 = solovay_kitaev(target_matrix_U, BasisSet.CLIFFORD_T, depth=1)
# print(
# r1.name
# ) # Output: ['s', 's', 's', 't', 't', 'tdg', 'sdg', 'sdg', 'sdg', 'tdg', 's', 'h', 's']

# r2 = solovay_kitaev(target_matrix_U, BasisSet.CLIFFORD_T, depth=2)
# print(r2.name) # Output: ['t', 's', 's', 's', 't',
# # 'tdg', 'tdg', 'sdg', 'sdg', 'sdg',
# # 't', 's', 's', 's', 't',
# # 'tdg', 'tdg', 'sdg', 'sdg', 'sdg',
# # 's', 'h', 's']

# print(np.allclose(r0.matrix, r1.matrix)) # Output: True
# print(np.allclose(r1.matrix, r2.matrix)) # Output: True
# print(np.allclose(r2.matrix, r0.matrix)) # Output: True

if __name__ == '__main__':
U = np.array([[-0.8987577 +0.j, -0.31607208+0.30386352j],[-0.14188982-0.41485163j, 0.79903828+0.41146473j]])
r0 = solovay_kitaev(U, BasisSet.CLIFFORD_T, depth=2)
print("----------------")
print(r0.distance(SU2Matrix(U, [])))
print(r0.matrix)
# print(r0.name)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Remove

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Remove


_, ud = np.linalg.eig(u)

vwvdwd = v @ w @ v.conj().T @ w.conj().T
Copy link
Member
@TheGupta2012 TheGupta2012 May 1, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@PranavTupe2000 I believe this also requires diagonalization of the matrix as done in a reference implementation.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hi @PranavTupe2000 checking in to see if were you able to solve this issue?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants
0