-
Notifications
You must be signed in to change notification settings - Fork 18
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
base: main
Are you sure you want to change the base?
Implemented Solovay Kitaev's Algorithm #156
Conversation
There was a problem hiding this 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 = { |
There was a problem hiding this comment.
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"] |
There was a problem hiding this comment.
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 |
There was a problem hiding this comment.
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: |
There was a problem hiding this comment.
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']) |
There was a problem hiding this comment.
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): |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
def optimize_gate_sequnce(seq: list[str], target_basis_set): | |
def optimize_gate_sequence(seq: list[str], target_basis_set): |
There was a problem hiding this comment.
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 = { |
There was a problem hiding this comment.
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
Some comments following up from the meeting - Testing the algorithmWe 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 Accuracy
Performance
Traversal 8000 Basic ApproximationsInstead 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 -
|
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. |
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. |
There was a problem hiding this comment.
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.
…solovay-kitaev-implementation
There was a problem hiding this comment.
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
src/pyqasm/algorithms/__init__.py
Outdated
|
||
""" | ||
|
||
from pyqasm.algorithms.solovay_kitaev.solovay_kitaev import solovay_kitaev |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
from pyqasm.algorithms.solovay_kitaev.solovay_kitaev import solovay_kitaev | |
from .solovay_kitaev.solovay_kitaev import solovay_kitaev |
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"]) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Remove
# 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 |
There was a problem hiding this comment.
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
# 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) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Remove
There was a problem hiding this comment.
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 |
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
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?
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.