Port linear_depth_lnn to rust #13654
Conversation
|
One or more of the following people are relevant to this code:
|
Pull Request Test Coverage Report for Build 12986663347Details
💛 - Coveralls |
There was a problem hiding this comment.
Thanks @gadial for your contribution! I only have some minor comments and questions.
|
I also think we can add some release notes saying that there was a performance improvement in synth_cnot_depth_line_kms since it's implementation was ported to rust |
| #[pyfunction] | ||
| #[pyo3(signature = (mat))] | ||
| pub fn optimize_cx_circ_depth_5n_line( | ||
| _py: Python, | ||
| mat: PyReadonlyArray2<bool>, | ||
| ) -> PyResult<(InstructionList, InstructionList)> { |
There was a problem hiding this comment.
For the rust function to be entirely self-contained and for consistency with other synthesis functions, it would be nice to return PyResult<CircuitData>.
There was a problem hiding this comment.
This looks great! I have left a few minor in-place suggestions, but I don't feel strongly about any of these, so feel free to ignore, I am completely happy to approve this PR just as it is right now. @ShellyGarion, please take a look to see if you have any more comments. I am not sure if we need release notes: on the one hand, we can skip release notes if there is no API change, but on the other hand it might be nice to highlight that a certain algorithm was ported to Rust, giving 20x performance speedup.
| // Find the last "1" in row i, use COL operations to the left in order to | ||
| // zero out all other "1"s in that row. | ||
| let cols_to_update: Vec<usize> = (0..n).rev().filter(|&j| mat[[i, j]]).collect(); | ||
| let (first_j, cols_to_update) = cols_to_update.split_first().unwrap(); |
There was a problem hiding this comment.
oh nice! I didn't know about split_first before :)
| let cols_to_update: Vec<usize> = (0..n).rev().filter(|&j| mat[[i, j]]).collect(); | ||
| let (first_j, cols_to_update) = cols_to_update.split_first().unwrap(); | ||
| cols_to_update.iter().for_each(|j| { | ||
| _col_op_inv(mat.view_mut(), *j, *first_j); |
There was a problem hiding this comment.
Would it make sense to replace _col_op_inv by _col_op and swap the order of the arguments? (I know this is how it was done in the Python code, and badly named at that).
| #[pyfunction] | ||
| #[pyo3(signature = (mat))] | ||
| pub fn optimize_cx_circ_depth_5n_line( | ||
| _py: Python, |
There was a problem hiding this comment.
We can probably skip passing _py to the function.
There was a problem hiding this comment.
The function name is not particularly representative of what the function is doing (in particular, it does not optimize anything). Maybe something like synth_cnot_depth_line_pair (but please find a better name than that). Also it seems that our new agreed on convention is to prefix python interface functions with py, i.e. let's change the names to py_synth_cnot_depth_line_pair and to py_synth_cnot_depth_line_kms. We don't follow this convention anywhere else in the synthesis code yet, but I believe someone is working on that already.
| /// `arXiv:quant-ph/0701194 <https://arxiv.org/abs/quant-ph/0701194>`_. | ||
| #[pyfunction] | ||
| #[pyo3(signature = (mat))] | ||
| pub fn py_synth_cnot_depth_line_kms( |
There was a problem hiding this comment.
this is a minor comment: both these pyfunctions have exactly the same docstring. could you add an explanation? it seems that the difference is in the args+returns. Could you please add them too (at least to the pyfunctions)?
* Port linear_depth_lnn to rust * Remove unnecessary release note * Changes according to code review * More corrections based on the review * Changes according to code review * Small fix * Docstring change according to PR review * Cargo fmt for version 1.79
Summary
Ports the
optimize_cx_circ_depth_5n_linemethod to Rust.Closes #12228
Details and comments
This is synthesis pass for constructing general linear reversible circuits given by an invertible boolean matrix. The code generating the instruction list was ported to Rust in a straightforward manner; construction of the circuit itself is done in Python.
A quick benchmarking was performed by using
random_invertible_binary_matrix(n, seed=seed)and timing the application ofsynth_cnot_depth_line_kmson the result, showing consistent improvement for the rust version.