Skip to content

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

Merged
merged 39 commits into from
Jun 3, 2025

Conversation

alexanderivrii
Copy link
Member

@alexanderivrii alexanderivrii commented Feb 27, 2025

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 qubits
  • synth_mcx_noaux_v24 - synthesis of MCX(k) using no ancilla qubits

One 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 rather PyResult<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 and push_py_gate are analogues of the existing push_standard_gate
  • from_standard_gate_definition - returns the definition circuit of a particular gate
  • compose - composes one quantum circuit onto another while optionally remapping qubits, this is a simpler variant of the Python QuantumCircuit.compose method
  • inverse - constructs the inverse circuit, similar to the Python QuantumCircuit.inverse method
  • h, cx, cp, etc. - similar to the Python QuantumCircuit functions.

The 4 ported MCX synthesis methods above each have a slightly different flavour:

  • c3x - this is the definition circuit for the standard C3X gate
  • c4x - hierarchical circuit
  • synth_mcx_n_dirty_i15 - another hierarchical circuit
  • synth_mcx_noaux_v24 - uses Python-side MCPhase-gate.

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.
@alexanderivrii alexanderivrii requested a review from a team as a code owner February 27, 2025 11:34
@qiskit-bot
Copy link
Collaborator

One or more of the following people are relevant to this code:

  • @Qiskit/terra-core

@alexanderivrii alexanderivrii added the Rust This PR or issue is related to Rust code in the repository label Feb 27, 2025
@alexanderivrii alexanderivrii added this to the 2.1.0 milestone Feb 27, 2025
@coveralls
Copy link

coveralls commented Feb 27, 2025

Pull Request Test Coverage Report for Build 15415079830

Warning: 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

  • 247 of 259 (95.37%) changed or added relevant lines in 3 files are covered.
  • 1209 unchanged lines in 27 files lost coverage.
  • Overall coverage increased (+0.07%) to 87.881%

Changes Missing Coverage Covered Lines Changed/Added Lines %
crates/synthesis/src/multi_controlled/mcx.rs 227 239 94.98%
Files with Coverage Reduction New Missed Lines %
crates/synthesis/src/two_qubit_decompose.rs 1 91.63%
qiskit/circuit/library/pauli_evolution.py 2 96.49%
qiskit/result/sampled_expval.py 2 93.55%
crates/qasm2/src/lex.rs 3 93.23%
qiskit/transpiler/passes/routing/sabre_swap.py 3 96.97%
crates/cext/src/exit_codes.rs 4 0.0%
qiskit/synthesis/evolution/suzuki_trotter.py 4 90.38%
qiskit/synthesis/multi_controlled/mcx_synthesis.py 4 97.7%
crates/transpiler/src/passes/split_2q_unitaries.rs 5 96.62%
qiskit/synthesis/evolution/qdrift.py 5 86.49%
Totals Coverage Status
Change from base Build 15300012488: 0.07%
Covered Lines: 80958
Relevant Lines: 92122

💛 - Coveralls

Copy link
Contributor

@raynelfss raynelfss left a 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 {
Copy link
Contributor

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.

Copy link
Member Author

@alexanderivrii alexanderivrii Jun 1, 2025

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..

Comment on lines 414 to 416
let mcphase_gate = mcphase_cls
.call1((PI, num_controls))
.expect("Could not create MCPhaseGate Python-side");
Copy link
Contributor

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 :)

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done in 501c568.

Comment on lines 20 to 32
/// 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()
}
Copy link
Contributor

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.

Copy link
Member Author

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.

Copy link
Member Author

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 {
Copy link
Contributor

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).

Copy link
Member Author

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.

Comment on lines 202 to 203
# same circuit but with barriers, otherwise the order of nodes before and
# after expanding the MCX gate might not be preserved
Copy link
Contributor

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?

Copy link
Member Author

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.

Copy link
Member Author

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; }
Copy link
Contributor

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?

Copy link
Member Author

@alexanderivrii alexanderivrii Jun 1, 2025

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).

@alexanderivrii alexanderivrii requested a review from raynelfss June 1, 2025 16:13
@alexanderivrii alexanderivrii requested a review from Cryoris June 3, 2025 07:45
Copy link
Member

@ShellyGarion ShellyGarion left a 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.
Copy link
Member

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
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

"rest gadget" -> "reset gadget"

Copy link
Contributor

@Cryoris Cryoris left a 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 👍🏻

Copy link
Contributor

@raynelfss raynelfss left a 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

@ShellyGarion ShellyGarion added this pull request to the merge queue Jun 3, 2025
Merged via the queue into Qiskit:main with commit 56885f0 Jun 3, 2025
26 checks passed
mtreinish added a commit to mtreinish/qiskit-core that referenced this pull request Jun 3, 2025
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.
mtreinish added a commit to mtreinish/qiskit-core that referenced this pull request Jun 3, 2025
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.
github-merge-queue bot pushed a commit that referenced this pull request Jun 3, 2025
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.
rahaman-quantum pushed a commit to rahaman-quantum/qiskit that referenced this pull request Jun 20, 2025
* 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
rahaman-quantum pushed a commit to rahaman-quantum/qiskit that referenced this pull request Jun 20, 2025
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Rust This PR or issue is related to Rust code in the repository synthesis
Projects
None yet
Development

Successfully merging this pull request may close these issues.

6 participants