Better MCX Decomposition with logarithmic Toffoli Depth #13922
Conversation
|
Thank you for opening a new pull request. Before your PR can be merged it will first need to pass continuous integration tests and be reviewed. Sometimes the review process can be slow, so please be patient. While you're waiting, please feel free to review other open PRs. While only a subset of people are authorized to approve pull requests for merging, everyone is encouraged to review open pull requests. Doing reviews helps reduce the burden on the core team and helps make the project's code better for everyone. One or more of the following people are relevant to this code:
|
|
|
|
@patelvyom - thank you very much for your contribution to qiskit. You've made a great start! |
Pull Request Test Coverage Report for Build 14063143389Warning: This coverage report may be inaccurate.This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.
Details
💛 - Coveralls |
|
@ShellyGarion Existing MCX decompositions have test cases defined in Also, I believe all style and linter-related errors have been fixed. |
Could you please add a new test file of the synthesis methods called Unfortunately, it seems that our mcx synthesis tests are somewhat hidden inside the circuit library tests (which we should refactor in the future). See for example these tests: |
|
I've added the required tests. I couldn't add tests for checking depth for the 2 ancilla cases because the constant factors in O(log(n)) fluctuate a lot across |
There was a problem hiding this comment.
Thanks for this work, @patelvyom! The code is very clean and I very much like that it uses the new testing framework. I have left a question about the difference between "1_clean" and "2_clean" methods (most probably because I have not actually read the paper) and a few suggestions on improving the release notes. I have also briefly experimented with the code and saw that the new 1-clean method adds less 2-qubit gates than the old 1-clean method (which makes it a very useful contribution). As a follow-up we should extend the synthesis plugin interface, including the default plugin.
| cx_count = transpiled_circuit.count_ops()["cx"] | ||
| # Based on the bound from the Sec 5.2 of arXiv:2407.17966, assuming Toffoli decomposition | ||
| # requires 6 CX gates. | ||
| self.assertLessEqual(cx_count, 12 * num_ctrl_qubits - 18) |
There was a problem hiding this comment.
I have not read the paper but it seems (both from the assertions here and from manually running the code) that the numbers of CX gates produced by synth_mcx_1_clean_kg24 and by synth_mcx_2_clean_kg24 methods are exactly the same (with the similar statement true for dirty). What is the advantage of using 2_clean method over 1_clean and the other way around?
There was a problem hiding this comment.
if you look at the paper then you can see that the difference is at the circuit depth O(n) or O(log n).
but it's difficult to test it since there is no formulas for this bound.
There was a problem hiding this comment.
A long time ago I created this rough plot (using optimization_level = 2)
Co-authored-by: Alexander Ivrii <alexi@il.ibm.com>
… mcx_gidney_khattar
There was a problem hiding this comment.
@patelvyom - the PR looks great! thanks for your contribution!
|
BTW, @patelvyom - would you like to open another PR to add these methods to the transpiler synthesis plugins? |
Yes, I will do that this week. |
Summary
Implement four new multi-controlled-x synthesis functions:
synth_mcx_1_clean_kg24,synth_mcx_1_dirty_kg24,synth_mcx_2_clean_kg24,synth_mcx_2_dirty_kg24as discussed in #13913.Details and comments
Once implementations are confirmed, these should be added to the HLS transpiler synthesis plugin.