-
Notifications
You must be signed in to change notification settings - Fork 2.6k
Porting some of the MCX synthesis methods to Rust #13929
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
Conversation
This struct is going to be used to represent circuits produced by synthesis algorithms. Ideally it should be replaced by CircuitData, however at the moment CircuitData has too high of an overhead.
This is the beginning of porting of (some) of the MCX synthesis methods to Rust. Here it also serves as a very simple example of using SynthesisData.
One or more of the following people are relevant to this code:
|
Pull Request Test Coverage Report for Build 15415079830Warning: 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 |
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.
This is much closer now, thank you for the quick changes. Here are some more comments.
/// | ||
/// This trait is **not** intended to be user-facing. It defines utility functions | ||
/// that make the code easier to read and that are used only for synthesis. | ||
trait CircuitDataAdder { |
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.
Now that the trait adds more functionality than just adding gates to the circuit, you might want to rename it to something that reflects that it's an extension aimed mainly at synthesis. Some suggestions may be CircuitDataForSynthesis
or CircuitDataExt
, I'll let you be the judge here.
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.
Changing this to CircuitDataForSynthesis
. Done in Done in 501c568..
let mcphase_gate = mcphase_cls | ||
.call1((PI, num_controls)) | ||
.expect("Could not create MCPhaseGate Python-side"); |
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.
Is there a reason why we're not leveraging the Result
nature of the function here and unwrapping the value? Remember that panicking is an error that you can't recover from. Since this here is only creating the gate instance, I don't see why we couldn't just return whatever error happens here in the Python side. So here I would just keep the result and handle it with the ?
operator.
let mcphase_gate = mcphase_cls
.call1((PI, num_controls))?;
or if you wanted a custom error message (something with CircuitError
rather), you could do something like:
let mcphase_gate = mcphase_cls
.call1((PI, num_controls))
.map_err(|_| CircuitError::new_err("Could not create MCPhaseGate Python-side"))?;
I'll leave that up to you :)
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.
Done in 501c568.
/// Efficient synthesis for 3-controlled X-gate. | ||
#[pyfunction] | ||
#[pyo3(name = "c3x")] | ||
pub fn py_c3x() -> PyResult<CircuitData> { | ||
c3x() | ||
} | ||
|
||
/// Efficient synthesis for 4-controlled X-gate. | ||
#[pyfunction] | ||
#[pyo3(name = "c4x")] | ||
pub fn py_c4x() -> PyResult<CircuitData> { | ||
c4x() | ||
} |
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.
This is mostly a nitpick but for these two methods, as well as the ones following it, I think you could just expose the original methods as pyfunction
. The only reason I'd see you separate them would be that they'd possibly return a rust-only error type instead of a PyError
, or that they use references, but neither seems to be the case.
I do like the fact that it keeps things cleaner and streamlined, so I have no problem keeping it this way either. Let me know if there is any other reasoning that I might be missing here.
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.
This is a good suggestion. I think I have originally made the split because the functions needed the 'py
token.
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.
Done in 501c568.
/// | ||
/// This trait is **not** intended to be user-facing. It defines utility functions | ||
/// that make the code easier to read and that are used only for synthesis. | ||
trait CircuitDataAdder { |
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.
You might want to move the trait to its own file within the synthesis
crate in the future, if needed. (Not for this PR).
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.
This is a good idea.
# same circuit but with barriers, otherwise the order of nodes before and | ||
# after expanding the MCX gate might not be preserved |
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.
Would adding barriers to self.complex_circuit
affect any of the other tests?
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.
Unfortunately it does. But I agree that it makes sense to minimize code duplication, for example by creating self.complex_circuit_with_barriers
and using it in multiple tests.
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.
Done in 501c568.
@@ -412,7 +412,7 @@ def test_circuit_qasm_with_mcx_gate_variants(self): | |||
expected_qasm = """OPENQASM 2.0; | |||
include "qelib1.inc"; | |||
gate mcx_gray q0,q1,q2,q3,q4,q5 { h q5; cu1(pi/16) q4,q5; cx q4,q3; cu1(-pi/16) q3,q5; cx q4,q3; cu1(pi/16) q3,q5; cx q3,q2; cu1(-pi/16) q2,q5; cx q4,q2; cu1(pi/16) q2,q5; cx q3,q2; cu1(-pi/16) q2,q5; cx q4,q2; cu1(pi/16) q2,q5; cx q2,q1; cu1(-pi/16) q1,q5; cx q4,q1; cu1(pi/16) q1,q5; cx q3,q1; cu1(-pi/16) q1,q5; cx q4,q1; cu1(pi/16) q1,q5; cx q2,q1; cu1(-pi/16) q1,q5; cx q4,q1; cu1(pi/16) q1,q5; cx q3,q1; cu1(-pi/16) q1,q5; cx q4,q1; cu1(pi/16) q1,q5; cx q1,q0; cu1(-pi/16) q0,q5; cx q4,q0; cu1(pi/16) q0,q5; cx q3,q0; cu1(-pi/16) q0,q5; cx q4,q0; cu1(pi/16) q0,q5; cx q2,q0; cu1(-pi/16) q0,q5; cx q4,q0; cu1(pi/16) q0,q5; cx q3,q0; cu1(-pi/16) q0,q5; cx q4,q0; cu1(pi/16) q0,q5; cx q1,q0; cu1(-pi/16) q0,q5; cx q4,q0; cu1(pi/16) q0,q5; cx q3,q0; cu1(-pi/16) q0,q5; cx q4,q0; cu1(pi/16) q0,q5; cx q2,q0; cu1(-pi/16) q0,q5; cx q4,q0; cu1(pi/16) q0,q5; cx q3,q0; cu1(-pi/16) q0,q5; cx q4,q0; cu1(pi/16) q0,q5; h q5; } | |||
gate mcx_recursive q0,q1,q2,q3,q4,q5,q6 { h q6; t q6; cx q2,q6; tdg q6; cx q3,q6; h q3; t q3; cx q0,q3; tdg q3; cx q1,q3; t q3; cx q0,q3; tdg q3; h q3; cx q3,q6; t q6; cx q2,q6; tdg q6; h q6; h q3; t q3; cx q0,q3; tdg q3; cx q1,q3; t q3; cx q0,q3; tdg q3; h q3; h q5; p(pi/8) q3; p(pi/8) q4; p(pi/8) q6; p(pi/8) q5; cx q3,q4; p(-pi/8) q4; cx q3,q4; cx q4,q6; p(-pi/8) q6; cx q3,q6; p(pi/8) q6; cx q4,q6; p(-pi/8) q6; cx q3,q6; cx q6,q5; p(-pi/8) q5; cx q4,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q3,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q4,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q3,q5; h q5; h q3; t q3; cx q0,q3; tdg q3; cx q1,q3; t q3; cx q0,q3; tdg q3; h q3; h q6; t q6; cx q2,q6; tdg q6; cx q3,q6; h q3; t q3; cx q0,q3; tdg q3; cx q1,q3; t q3; cx q0,q3; tdg q3; h q3; cx q3,q6; t q6; cx q2,q6; tdg q6; h q6; h q5; p(pi/8) q3; p(pi/8) q4; p(pi/8) q6; p(pi/8) q5; cx q3,q4; p(-pi/8) q4; cx q3,q4; cx q4,q6; p(-pi/8) q6; cx q3,q6; p(pi/8) q6; cx q4,q6; p(-pi/8) q6; cx q3,q6; cx q6,q5; p(-pi/8) q5; cx q4,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q3,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q4,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q3,q5; h q5; } | |||
gate mcx_recursive q0,q1,q2,q3,q4,q5,q6 { h q6; t q6; cx q2,q6; tdg q6; cx q3,q6; h q3; t q3; cx q1,q3; tdg q3; cx q0,q3; t q3; cx q1,q3; tdg q3; h q3; cx q3,q6; t q6; cx q2,q6; tdg q6; h q6; h q3; t q3; cx q1,q3; tdg q3; cx q0,q3; t q3; cx q1,q3; tdg q3; h q3; h q5; p(pi/8) q3; p(pi/8) q4; p(pi/8) q6; p(pi/8) q5; cx q3,q4; p(-pi/8) q4; cx q3,q4; cx q4,q6; p(-pi/8) q6; cx q3,q6; p(pi/8) q6; cx q4,q6; p(-pi/8) q6; cx q3,q6; cx q6,q5; p(-pi/8) q5; cx q4,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q3,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q4,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q3,q5; h q5; h q3; t q3; cx q1,q3; tdg q3; cx q0,q3; t q3; cx q1,q3; tdg q3; h q3; h q6; t q6; cx q2,q6; tdg q6; cx q3,q6; h q3; t q3; cx q1,q3; tdg q3; cx q0,q3; t q3; cx q1,q3; tdg q3; h q3; cx q3,q6; t q6; cx q2,q6; tdg q6; h q6; h q5; p(pi/8) q3; p(pi/8) q4; p(pi/8) q6; p(pi/8) q5; cx q3,q4; p(-pi/8) q4; cx q3,q4; cx q4,q6; p(-pi/8) q6; cx q3,q6; p(pi/8) q6; cx q4,q6; p(-pi/8) q6; cx q3,q6; cx q6,q5; p(-pi/8) q5; cx q4,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q3,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q4,q5; p(pi/8) q5; cx q6,q5; p(-pi/8) q5; cx q3,q5; h q5; } |
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.
What triggered the changes here? From checking locally it seems to just be the order some gates appear for different qubits, but still what is causing this to happen?
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.
Ah yes, there is indeed a subtle difference between the circuits produced by the old Python code and the new Rust code for synth_mcx_n_dirty_i15
.
The Python code had the following lines
# implements an optimized toffoli operation
# up to a diagonal gate, akin to lemma 6 of arXiv:1501.06911
qc.h(targets[i])
qc.t(targets[i])
qc.cx(q_controls[num_ctrl_qubits - i - 2], targets[i])
qc.tdg(targets[i])
qc.cx(q_controls[num_ctrl_qubits - i - 1], targets[i])
qc.t(targets[i])
qc.cx(q_controls[num_ctrl_qubits - i - 2], targets[i])
qc.tdg(targets[i])
qc.h(targets[i])
which implement a relative Toffoli gate, and which got replaced by the single Rust line
circuit.compose(
&rccx()?,
&[Qubit(controls[0]), Qubit(controls[1]), Qubit(ancillas[0])],
&[]
)?;
where rccx
is a shortcut for extracting the definition circuit for RCCX
(from operations.rs
).
This is correct in the sense that both the Python code above and the definition for RCCX
in operations.rs
lead to correct decompositions for the original MCX gate (and we have lots of tests that check the correctness of circuits produced by different synthesis methods). However, the two definitions for RCCX
are slightly different (I think you can get one from the other by swapping qubits 0 and 1).
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.
The code looks great, I only found a few misprints.
)) | ||
} | ||
|
||
/// Definition circuit for RC3X. |
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.
in the comment it should be RCCX
circuit.cx(q1, q2); | ||
} | ||
|
||
/// Adds gates of the "rest gadget" to the circuit |
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.
"rest gadget" -> "reset gadget"
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.
LGTM but Iet's wait to see if @ShellyGarion or @raynelfss have other comments 👍🏻
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.
LGTM! Thank you for the additions
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.
* Adding SynthesizedData struct. This struct is going to be used to represent circuits produced by synthesis algorithms. Ideally it should be replaced by CircuitData, however at the moment CircuitData has too high of an overhead. * Adding num_qubits field * inlining and temporarily removing dead code warnings * Adding to_circuit_data method and some other improvements * Porting synth_c3x to Rust This is the beginning of porting of (some) of the MCX synthesis methods to Rust. Here it also serves as a very simple example of using SynthesisData. * Porting synth_mcx_n_dirty_i15 to rust * failing attempt to add MCX decomposition based on MCPhase gate * Improving MCX tests to compare against expected matrices * failing attempt to get definition * rewriting in terms of circuit data * fixes and adding testing * removing old python code * renaming * using def * adding CircuitData.inverse; implementing c4x * sync with the Python code * clean up and fixing some tests * finalizing tests * removing unused code * removing duplicated tests * cleanup * removing push_py_gate and push_py_instruction from circuit_data, using push_packed_operation instead * updating the implementation of CircuitData.compose * removing from_standard_gate_definition from CircuitData * not adding h, t, etc. methods to the CircuitData directly. Instead implementing a trait in the synthesis code * removing pub keyword and making more clear that the CircuitAdder trait is not user-facing * fixing qasm tests (as expected) * moving compose and inverse methods from CircuitData to the private trait * addressing Ray's review comments * addressing Julien's review comments * adding add_action_gadget and add_reset_gadget functions * further simplifying the code * typos
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 ports some of the MCX synthesis algorithms from Python to Rust:
c3x
- synthesis of MCX(3)c4x
- synthesis of MCX(4)synth_mcx_n_dirty_i15
- synthesis of MCX(k) using k-2 ancilla qubitssynth_mcx_noaux_v24
- synthesis of MCX(k) using no ancilla qubitsOne important change is that the Rust circuits are "flat" (contain no nested subcircuits), so for instance the 4-controlled X-gate now gets expanded into 69 "basic" operations instead of a hierarchical circuit with nested subcircuits.
To support hierarchical synthesis algorithms, all the new internal synthesis functions return
CircuitData
(or ratherPyResult<CircuitData>
, instead of vectors or iterators over custom structs as used until now. In particular, this would immediately allow to use MCX-gates as building blocks within larger circuits.In the process, I have extended
CircuitData
with multiple convenience functions:push_standard_instruction
andpush_py_gate
are analogues of the existingpush_standard_gate
from_standard_gate_definition
- returns the definition circuit of a particular gatecompose
- composes one quantum circuit onto another while optionally remapping qubits, this is a simpler variant of the PythonQuantumCircuit.compose
methodinverse
- constructs the inverse circuit, similar to the PythonQuantumCircuit.inverse
methodh
,cx
,cp
, etc. - similar to the PythonQuantumCircuit
functions.The 4 ported MCX synthesis methods above each have a slightly different flavour:
c3x
- this is the definition circuit for the standardC3X
gatec4x
- hierarchical circuitsynth_mcx_n_dirty_i15
- another hierarchical circuitsynth_mcx_noaux_v24
- uses Python-sideMCPhase
-gate.