Oxidize the Solovay Kitaev algorithm #14203
Conversation
|
One or more of the following people are relevant to this code:
|
crates/accelerate/src/synthesis/discrete_basis/solovay_kitaev.rs
Outdated
Show resolved
Hide resolved
There was a problem hiding this comment.
Just bringing in a comment I made offline to Julien: I feel like this PR would be better if we only do the move to Rust space using f64 at first, and then look at methods to improve precision in follow-ups.
Personally, I'm concerned about the big-decimal implementation here. If nothing else, that project is abandoned. That more, my larger issue is that the error rates here suggest to me that we have catastrophic cancellation in floating-point addition/subtraction along the way in the algorithm, and that throwing a software-emulated higher-precision type at it is not a scalable way to go.
The BigFloat type used here is a software-emulated base-10 floating-point number, with just under 133 bits of precision, so about 2.5x greater precision than double-precision IEEE-754 floats. That 2.5 number is then seen again in the precision improvement. I haven't done the maths exactly to verify my expectations, but that feels to me to be indicative of catastrophic cancellations; if it were simply round-off error in matrix construction, we wouldn't expect to see much of an improvement, because the initial matrix constructions are done using f64 maths, so the round-off would have occurred before switching to the new type.
I would need to look into the algorithm and our implementation in a lot more detail, but overall:
- I wonder if swapping it from an SO3-based decomposition to a direct SU2-based one would help phase issues
- If using an SU2-based one, perhaps just a quick swap to quaternion-based representations could yield some performance and precision improvements
- More properly, I feel like we ought to do more research into the floating-point characteristics of this, and understand more where the error terms are coming from. I doubt it's as easier as just wrapping one part of the algorithm in a Kahan sum, but that's the type of thing I'm thinking about.
There was a problem hiding this comment.
This is a really impressive work - porting the Solovay-Kitaev algorithm to Rust and fixing a multitude of Python-code bugs we have recently discovered. I still have not actually experimented with the code or looked closely at the two key files math.rs and basic_approximations.rs (I will do this a bit later), but I have left some random comments as I was looking through the other files.
crates/accelerate/src/synthesis/discrete_basis/solovay_kitaev.rs
Outdated
Show resolved
Hide resolved
crates/accelerate/src/synthesis/discrete_basis/solovay_kitaev.rs
Outdated
Show resolved
Hide resolved
|
One additional quick request: could you please provide a script to reproduce the experiments listed in the summary? And do I understand correctly that Python code is actually faster for |
Pull Request Test Coverage Report for Build 15414389477Warning: 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 |
This is not the proper import path for from qiskit.synthesis import generate_basic_approximationsUsually we only guarantee that this, API-documented path works. |
There was a problem hiding this comment.
I have looked at the rest of the Rust code (still not the Python code, but that part should be much more straightforward).
I think that using R* to store information is really clever, I like this a lot.
I had two sets of general questions/comments that ended up in many in-code comments.
First, I think that the function recurse should explicitly take an SO(3)-matrix and not a GateSequence. This allows to have GateSequence representing only a sequence of gates, and not also optionally a matrix. And this simplifies the code quite a bit (the changes are mostly automatic).
Second, I was not sure what was true when supporting BigFloats in the first iteration of the code vs. right now. Do we still get better precision when working with gates rather than their U(2)-matrices?
|
One additional question, can you please describe the backwards compatibility issues and solutions to support the Python |
- gates are not optional - don't store u2 matrix
- adapting tolerances - outer prod - update docs/minors
- better docs - SO(3) for any pauli
There was a problem hiding this comment.
Thanks for doing all these changes! This is almost completely ready. I have left a few really minor nitpicks and questions. Other than that, there is a small CI docs issue and you need release notes.
I don't know if you have answered my question on backwards compatibility (I may have missed your reply with so many comments on the issue). Please tell me if I understand the following correctly. The flow of first generating basic approximations and then instantiating SolovayKitaevDecomposition with these approximations is still supported
approx = generate_basic_approximations(basis_gates=gates, depth=depth)
sk = SolovayKitaevDecomposition(approx)
and this uses the new SK code in Rust only.
Saving and loading approximations in the new bin fomat works.
Loading and working with approximations saved in legacy ".npy" format still works, however gives a warning message. Saving in ".npy" format is no longer supported.
Given the above, I don't think there is a breaking API change (you have done an amazing job of keeping all the different ways of using the code intact) unless someone exploits the fact that the newly saved approximations are stored in npy format. Actually I don't consider this an API change as the exact format in which the approximations are saved are not a part of the publicly exposed API, yet we might reflect this in the upgrade section of the release notes. You should also mention that the default values were changed. Also, you probably want to add something to the deprecations section of the release notes.
| /// Get the gate labels. | ||
| pub fn label(&self) -> String { | ||
| self.gates.iter().map(|gate| gate.name()).collect() | ||
| } |
There was a problem hiding this comment.
Not important, but do we use this function anywhere?
There was a problem hiding this comment.
I've used it a fair amount in debugging, I can also remove it, if you prefer 🙂
There was a problem hiding this comment.
It's fine to keep it. I am not asking for additional changes, but for debugging purposes I found it useful to print from the Python side the set of basic approximations (that is, gate sequences and corresponding matrices), and now it seems the most I can get is the list of objects of the form <builtins.GateSequence object at 0x1048a4530>. Thus, it might be nice to have a pymethod __str__() for GateSequence, or expose this function label (along with a function that returns the SO(3)-matrix) as pyfunction. But again this is not something I am asking for this PR.
|
I've actually missed the explanations on backwards compatibility, but what you describe above is exactly correct and there shouldn't be a breaking API change (which is also not allowed 😛). I'll reflect the change in format in the release notes, but note that there are not deprecations yet, only pending deprecations. |
- add reno - fix gate path + more tests - use gate path per default - more docs
- tolerances - rm unused errors
In the recently merged Qiskit#14203 the bincode dependency was added to the qiskit-synthesis crate to provide a binary serialization of the computed basic approximations. However, under the covers this library is using serde and it depends on having anything passed to it be serde serializable. When building the qiskit-synthesis crate by itself the hashbrown crate does not enable the serde feature meaning it doesn't derive the necessary serialization traits for serde. This didn't show up in a full build because other libraries pulled in as part of the build cause serde to be enabled for hashbrown. This commit fixes this by adding the serde feature to the Cargo.toml for hashbrown to ensure we're building with the feature required in the crate using it. This also takes the opportunity to fix some small clippy lint issues identified by the latest stable version of clippy in the synthesis crate which were introduced in Qiskit#14203 and Qiskit#13929.
In the recently merged Qiskit#14203 the bincode dependency was added to the qiskit-synthesis crate to provide a binary serialization of the computed basic approximations. However, under the covers this library is using serde and it depends on having anything passed to it be serde serializable. When building the qiskit-synthesis crate by itself the hashbrown crate does not enable the serde feature meaning it doesn't derive the necessary serialization traits for serde. This didn't show up in a full build because other libraries pulled in as part of the build cause serde to be enabled for hashbrown. This commit fixes this by adding the serde feature to the Cargo.toml for hashbrown to ensure we're building with the feature required in the crate using it. This also takes the opportunity to fix some small clippy lint issues identified by the latest stable version of clippy in the synthesis crate which were introduced in Qiskit#14203 and Qiskit#13929.
In the recently merged #14203 the bincode dependency was added to the qiskit-synthesis crate to provide a binary serialization of the computed basic approximations. However, under the covers this library is using serde and it depends on having anything passed to it be serde serializable. When building the qiskit-synthesis crate by itself the hashbrown crate does not enable the serde feature meaning it doesn't derive the necessary serialization traits for serde. This didn't show up in a full build because other libraries pulled in as part of the build cause serde to be enabled for hashbrown. This commit fixes this by adding the serde feature to the Cargo.toml for hashbrown to ensure we're building with the feature required in the crate using it. This also takes the opportunity to fix some small clippy lint issues identified by the latest stable version of clippy in the synthesis crate which were introduced in #14203 and #13929.
* SolovayKitaev in Rust * fix decorator order * use `f64` * fix tests and SO(3) formula * merge artifacts * mostly backward compat * fix tests * docs * some initial comments * simplify GateSequence - gates are not optional - don't store u2 matrix * directly solve Eq. (10) * more review comments - adapting tolerances - outer prod - update docs/minors * more review comments - better docs - SO(3) for any pauli * further review comments - add reno - fix gate path + more tests - use gate path per default - more docs * more review comments - tolerances - rm unused errors
In the recently merged Qiskit#14203 the bincode dependency was added to the qiskit-synthesis crate to provide a binary serialization of the computed basic approximations. However, under the covers this library is using serde and it depends on having anything passed to it be serde serializable. When building the qiskit-synthesis crate by itself the hashbrown crate does not enable the serde feature meaning it doesn't derive the necessary serialization traits for serde. This didn't show up in a full build because other libraries pulled in as part of the build cause serde to be enabled for hashbrown. This commit fixes this by adding the serde feature to the Cargo.toml for hashbrown to ensure we're building with the feature required in the crate using it. This also takes the opportunity to fix some small clippy lint issues identified by the latest stable version of clippy in the synthesis crate which were introduced in Qiskit#14203 and Qiskit#13929.
Summary
This PR implements
SolovayKitaevDecompositionin Rust, along with some algorithmic changes and fixes.Details and comments
Main contributions:
Benchmark of the new code:
In comparison the old code (current
main) is significantly slower (very roughly a factor 100):(I didn't make a nice plot comparing the runtime data in the same figure, feel free to request, or just squint and look at both numbers separately)