Ancilla-Free Quantum Adder with Sublinear Depth #13975
Conversation
Pull Request Test Coverage Report for Build 14886717457Warning: 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 |
|
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:
|
|
The core adder is now functional. Where should I add tests? They are currently located in |
|
@patelvyom - Thanks for your contribution to Qiskit! |
There was a problem hiding this comment.
@patelvyom - thank you very much for another high-quality and important contribution to qiskit!
I have a few comments and questions:
-
I am not sure if we would like to add more arithmetic gates to the circuit library, or use them only via the HLS plugin (see #13354).
Anyway, could you please add the "see also" comment that appear in the other adders?
@Cryoris - what is your opinion? -
I noticed that you changed the default definition of the adder gate to use this synthesis method. Could you please add in the PR some benchmarks (on cx-count and depth) to support this decision?
I agree that asymptotically it looks better, but I wonder if this remains correct when dealing with small number of qubits. -
Is it possible to add some tests on the synthesis including CX cost and circuit depth?
-
Could you also add release notes?
|
Re CX count: Yes, I've been working on that. I actually found something interesting: it appears that it's not better compared to HalfAdder with ancilla. I am still in the process of creating some plots to see what the ideal conditions are for using this adder. I'll resolve your comments soon as well. |
|
I'll actually wait until #14143 is merged. That way we don't have to call MCX directly from synthesis and also there are many cases where we have more than 2 dirty ancillae available so we can let the transpiler figure out optimal CX decomp. |
There was a problem hiding this comment.
@patelvyom - thank you very much for your contribution to qiskit! The code is well-written.
-
We currently don't want to add to the circuit library specific adders, like
RVRippleCarryAdder, and plan to deprecate all the other specific adders, in favor of theHalfAdderGateetc. Could you please remove it from your code? -
According to your results, it seems that except of n=4,
'adder_ripple_rv25'is better than'adder_qft_d00'. For n>=5 other methods are better, but they require using ancilla qubits.
We should probably add some benchmarks, but this could be done in another PR.
I have some other minor comments.
qiskit/circuit/library/arithmetic/adders/rv_ripple_carry_adder.py
Outdated
Show resolved
Hide resolved
There was a problem hiding this comment.
@patelvyom - thanks for another high-quality contribution to qiskit!
It looks good to me.
@alexanderivrii @Cryoris - do you have any further comments?
Co-authored-by: Julien Gacon <gaconju@gmail.com>
|
I believe I fixed all suggestions. Let me know in case I missed something. |
|
Thanks for addressing all of my points! |
Summary
This PR introduces an implementation of Ancilla-Free Quantum Adder with Sublinear Depth. The implementation follows the paper’s methodology, leveraging optimized CNOT and Toffoli ladder constructions to achieve an efficient ripple-carry addition without ancillary qubits. It achieves an overall depth of O(log² n) and gate count of O(n log(n)) without using any ancillae.
Details and comments
The implementation relies on the Log-depth MCX using conditionally clean ancillae introduced in #13922. The current version is not functional because log-depth MCX is not yet merged into main. I welcome any suggestions in the meantime. Since #13922 is part of the Qiskit 2.0 feature, I thought this might make a good addition. Tagging @ShellyGarion as you are already familiar with some of the changes.