Add the MCX synthesis algorithm by Huang and Palsberg #14666

alexanderivrii · 2025-06-25T13:04:31Z

Summary

This PR implements the MCX synthesis algorithm from https://dl.acm.org/doi/10.1145/3656436. The algorithm (called Qulin) significantly improves on the number of 2-qubit gates when no auxiliary qubits are available (details below).

This is a collaboration with the authors of the paper, Keli Huang and Jens Palsberg, who have very kindly provided me with the Python version of their code, which I have then ported to Rust (with some modifications).

Details and comments

Let us say that Increment1(n) and Decrement1(n) are high-level gates operating on n qubits that respectively add and subtract 1 modulo $2^n$. The new algorithm implements MCX(n) gates using Increment1/Decrement1 and smaller MCX gates, while cleverly leveraging available ancillas. We do not have Increment1/Decrement1 gates natively in Qiskit, and I expect these to be useful for other applications as well; see Question 1 below.

Internally, the code also provides the following synthesis methods:

Implementing Increment1(n)/Decrement1(n) using n dirty auxiliary qubits. There are in fact two methods for this, one being more efficient when n is large, and one being more efficient when n is small.
Synthesizing a relative-MCX(n) gate without any auxiliary qubits. This leads to Questions 2 and 3.
Implementing Increment1(n), Decrement1(n) using 1 auxiliary qubits when n is odd, and using 2 auxiliary qubits for both even and odd values of n.

Interesting questions:

Question 1: Do we want to add high-level gates Increment1 and Decrement1 to Qiskit?
Question 2: Do we need a native "relative MCX gate" in Qiskit? Note that such a gate is not precisely defined: the requirement is that it should be the same as MCX up to some diagonal matrix. There might be multiple useful relative MCX gates, both in terms of the operator and the synthesized circuit. In particular, a recent Update synth_mcx_kg24 to use relative phase Toffolis #14394 introduced a very different implementation for the MCX gate (I have not checked if the corresponding operators match, but I doubt that this is the case).
Question 3: In fact, for this PR we need an implementation of a relative MCX(n) gate when n auxiliary qubits available. Currently, when n is small we use a recursive algorithm for building a relative MCX gate that does not use any auxiliary qubits, and when n is large we switch to an algorithm that constructs a true MCX gate that uses n auxiliary qubits. Do we have an algorithm that constructs a relative MCX gate using auxiliary qubits? Can Update synth_mcx_kg24 to use relative phase Toffolis #14394 help?
Question 4: the experimental data shows that the new algorithm is much better than Qiskit's when no auxiliary qubits are available, however is significantly worse when at leas 1 auxiliary qubit is available (see Update synth_mcx_kg24 to use relative phase Toffolis #14394 for the latter data). One of the reasons for this is that the new algorithm assumes that initially no auxilary qubits are available, and while it cleverly manages its own qubits as auxiliary qubits for different parts of the problem, it does not leverage other available qubits in the larger circuit. What is the best way to achieve that?

Comparison without and with this PR

The following data compares the number of CX-gates introduced by the Qiskit's default synthesis function qiskit (aka synth_mcx_noaux_v24) against the new method qulin (aka synth_mcx_noaux_hp24) for synthesizing the MCX(n) gate (where n is the number of controls), when no auxiliary qubits are available. We can clearly see that the number of CX-gates is improved by about 3x for large n.

n = 1: #cx (qiskit) = 1, #cx (qulin) = 1
n = 2: #cx (qiskit) = 6, #cx (qulin) = 6
n = 3: #cx (qiskit) = 14, #cx (qulin) = 32
n = 4: #cx (qiskit) = 36, #cx (qulin) = 52
n = 5: #cx (qiskit) = 84, #cx (qulin) = 96
n = 6: #cx (qiskit) = 140, #cx (qulin) = 136
n = 7: #cx (qiskit) = 220, #cx (qulin) = 192
n = 8: #cx (qiskit) = 324, #cx (qulin) = 264
n = 9: #cx (qiskit) = 444, #cx (qulin) = 344
n = 10: #cx (qiskit) = 580, #cx (qulin) = 464
n = 11: #cx (qiskit) = 732, #cx (qulin) = 576
n = 12: #cx (qiskit) = 900, #cx (qulin) = 728
n = 13: #cx (qiskit) = 1084, #cx (qulin) = 864
n = 14: #cx (qiskit) = 1284, #cx (qulin) = 1048
n = 15: #cx (qiskit) = 1500, #cx (qulin) = 1200
n = 16: #cx (qiskit) = 1732, #cx (qulin) = 1416
n = 17: #cx (qiskit) = 1980, #cx (qulin) = 1624
n = 18: #cx (qiskit) = 2244, #cx (qulin) = 1872
n = 19: #cx (qiskit) = 2524, #cx (qulin) = 2048
n = 20: #cx (qiskit) = 2820, #cx (qulin) = 2328
n = 21: #cx (qiskit) = 3132, #cx (qulin) = 2474
n = 22: #cx (qiskit) = 3460, #cx (qulin) = 2678
n = 23: #cx (qiskit) = 3804, #cx (qulin) = 2762
n = 24: #cx (qiskit) = 4164, #cx (qulin) = 2942
n = 25: #cx (qiskit) = 4540, #cx (qulin) = 3010
n = 26: #cx (qiskit) = 4932, #cx (qulin) = 3206
n = 27: #cx (qiskit) = 5340, #cx (qulin) = 3258
n = 28: #cx (qiskit) = 5764, #cx (qulin) = 3470
n = 29: #cx (qiskit) = 6204, #cx (qulin) = 3506
n = 30: #cx (qiskit) = 6660, #cx (qulin) = 3734
n = 31: #cx (qiskit) = 7132, #cx (qulin) = 3754
n = 32: #cx (qiskit) = 7620, #cx (qulin) = 3998
n = 33: #cx (qiskit) = 8124, #cx (qulin) = 4002
n = 34: #cx (qiskit) = 8644, #cx (qulin) = 4262
n = 35: #cx (qiskit) = 9180, #cx (qulin) = 4250
n = 36: #cx (qiskit) = 9732, #cx (qulin) = 4526
n = 37: #cx (qiskit) = 10300, #cx (qulin) = 4498
n = 38: #cx (qiskit) = 10884, #cx (qulin) = 4790
n = 39: #cx (qiskit) = 11484, #cx (qulin) = 4746
n = 40: #cx (qiskit) = 12100, #cx (qulin) = 5054
n = 41: #cx (qiskit) = 12732, #cx (qulin) = 4994
n = 42: #cx (qiskit) = 13380, #cx (qulin) = 5318
n = 43: #cx (qiskit) = 14044, #cx (qulin) = 5242
n = 44: #cx (qiskit) = 14724, #cx (qulin) = 5582
n = 45: #cx (qiskit) = 15420, #cx (qulin) = 5490
n = 46: #cx (qiskit) = 16132, #cx (qulin) = 5846
n = 47: #cx (qiskit) = 16860, #cx (qulin) = 5738
n = 48: #cx (qiskit) = 17604, #cx (qulin) = 6110
n = 49: #cx (qiskit) = 18364, #cx (qulin) = 5986
n = 50: #cx (qiskit) = 19140, #cx (qulin) = 6374

However, when at least 1 ancillary qubit is available, Qiskit produces much better gate counts than either of these two methods above.

ToDo:

release notes
plugin for the new MCX synthesis method (including documentation)
modifying the default MCX synthesis plugin to make use of the new method when appropriate

Co-authored-by: Jens Palsberg <palsberg@ucla.edu> Co-authored-by: Keli Huang <kelihuang@cs.ucla.edu>

qiskit-bot · 2025-06-25T13:04:37Z

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

@Qiskit/terra-core

coveralls · 2025-06-25T13:40:09Z

Pull Request Test Coverage Report for Build 16807106158

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.

For more information on this, see Tracking coverage changes with pull request builds.
To avoid this issue with future PRs, see these Recommended CI Configurations.
For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

294 of 308 (95.45%) changed or added relevant lines in 4 files are covered.
364 unchanged lines in 9 files lost coverage.
Overall coverage increased (+0.02%) to 87.668%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/transpiler/passes/synthesis/hls_plugins.py	8	9	88.89%
crates/synthesis/src/multi_controlled/mcx.rs	279	292	95.55%

Files with Coverage Reduction	New Missed Lines	%
crates/circuit/src/parameter/parameter_expression.rs	1	83.39%
crates/circuit/src/parameter/symbol_expr.rs	1	74.7%
crates/qasm2/src/expr.rs	1	93.63%
crates/transpiler/src/passes/inverse_cancellation.rs	4	95.52%
crates/qasm2/src/lex.rs	5	92.01%
crates/qasm2/src/parse.rs	6	97.56%
crates/transpiler/src/passes/unitary_synthesis.rs	74	92.34%
crates/synthesis/src/two_qubit_decompose.rs	100	90.77%
crates/circuit/src/operations.rs	172	85.63%

Totals
Change from base Build 16796589902:	0.02%
Covered Lines:	82209
Relevant Lines:	93773

💛 - Coveralls

ShellyGarion

Thanks @alexanderivrii for your important contribution and to Keli Huang and Jans Palsberg for providing their python code and their help.

I mainly have a few comments on the documentation and tests.
In addition, in the benchmarks of your PR, could you please add which of the qulin algorithms was actually used?

Some answers to your questions:

I don't think that Increment1 and Decrement1 should have gates. These are helper functions and not standalone building blocks.
I don't think that we need a native "relative MCX gate" in Qiskit. It's a helper function and not a standalone building block, and it's also not well defined.

ShellyGarion · 2025-07-13T05:43:44Z

crates/synthesis/src/multi_controlled/mcx.rs

+///
+/// A quantum circuit with :math:`2 * n` qubits.
+fn increment_n_dirty(n: u32) -> PyResult<CircuitData> {
+    if n <= 10 {


is there a reference to a theorem stating why n=10 is the bound here?

I wouldn't call this a theorem. There are two constructions given in the paper (+ supplementary material): the construction in Fig. 18 and the construction in Fig. 10. The first has better asymptotic behavior but the second is better for small values of n. Numerically, the switch happens when n = 10.

ShellyGarion · 2025-07-13T05:46:42Z

crates/synthesis/src/multi_controlled/mcx.rs

+    // mot efficient to construct the true MCX gate that uses num_controls ancillas.
+    // An interesting question is whether there are relative-MCX implmentations that
+    // use ancilla qubits.
+    if num_controls < 11 {


is there a reference to a theorem stating why n=11 is the bound here?

It's pretty much the same answer than before: there is one construction that is better asymptotically (i.e. for large values of n) and another construction that is better for small values of n. I believe that in the future we will see more constructions of relative MCX gates with ancillas, in which case we would be able to further fine-tune this function.

crates/synthesis/src/multi_controlled/mcx.rs

ShellyGarion · 2025-07-13T05:54:44Z

qiskit/synthesis/multi_controlled/mcx_synthesis.py

+    Synthesize a multi-controlled X gate with :math:`k` controls based on
+    the work by Huang and Palsberg.
+
+    Produces a quantum circuit with :math:`k + 1` qubits.


should it also mention that "The number of CX-gates is linear in k" ?

ShellyGarion · 2025-07-13T05:56:05Z

qiskit/transpiler/passes/synthesis/hls_plugins.py

+
+    For a multi-controlled X gate with :math:`k` control qubits this synthesis
+    method requires no additional clean auxiliary qubits. The synthesized
+    circuit consists of :math:`k + 1` qubits.


should it also mention that "The number of CX-gates is linear in k" ?

releasenotes/notes/add-new-mcx-noaux-method-6f38c3cd3708df3c.yaml

ShellyGarion · 2025-07-13T06:08:28Z

test/python/synthesis/test_multi_controlled_synthesis.py

@@ -192,6 +193,14 @@ def test_mcx_noaux_v24(self, num_ctrl_qubits: int):
            XGate(), num_ctrl_qubits, synthesized_circuit, clean_ancillas=False
        )

+    @data(1, 2, 3, 4, 5, 6, 7, 8)
+    def test_mcx_noaux_hp24(self, num_ctrl_qubits: int):


I think that some more tests are needed.

Since there are two different synthesis methods, for small and large number of qubits, should we also check the large here? maybe using the Statevector simulator?

Can we add a test_mcx_noaux_hp24_cx_count test? based on some formulas from the paper (Theorem 4.5)?
usually we check it for n=5,10,15, should we also check n>22 here?

The bound in the tests in line 469 should be updates:

if isinstance(base_gate, (XGate, YGate, ZGate, HGate)): # MCX gate and other locally equivalent multi-controlled gates expected = {1: 1, 2: 6, 3: 14, 4: 36, 5: 84, 6: 140, 7: 220, 8: 324}

I have addressed the second and the third comments (both are great suggestions).

Regarding the first point. I completely agree that it would be very nice to add some correctness checking for large values of n, especially that the algorithm follows different compilation schemes for large values of n. However, at this point constructing either Operator or Statevector is impossible, do you agree? What can we do instead?

Consructs a unitary matrix from a CircuitData with only unitary operations, exactly as what Operator(quantum_circuit).data does. The code is a simple wrapper on top of unitary_compose.

alexanderivrii · 2025-07-16T10:02:16Z

Update: this PR is now based on top of #14746 as to add at least some tests for our Rust synthesis code. We have discussed this offline, and the general consensus was that we should have Rust-space tests for different helper functions that are normally not explored for small numbers of qubits.

So far, I have added a test that increment_n_dirty_large produces the same matrix as increment_n_dirty_small for n=1,2,3,4,5. Explaining this a bit more precisely, for small values of n the overall algorithm calls increment_n_dirty_small. By constructing and comparing unitary matrices in our Python tests, we gain some confidence that both increment_n_dirty_small and its integration into the overall algorithm are correct. For large values of n the overall algorithm calls increment_n_dirty_large, however at this point the unitary matrices are prohibitively large. So here we are checking that increment_n_dirty_large does work correctly for small values of n, increasing our confidence that it also works correctly for large values of n.

@ShellyGarion, are there any more tests you think we should add?

For the record, this is the command I am using to run Rust synthesis tests: cargo test -p qiskit-synthesis --lib --release.

ShellyGarion

a few more comments on the docs and tests. other than that, it looks great!

releasenotes/notes/add-new-mcx-noaux-method-6f38c3cd3708df3c.yaml

ShellyGarion · 2025-07-17T08:39:28Z

crates/synthesis/src/multi_controlled/mcx.rs

+    use super::{increment_n_dirty_large, increment_n_dirty_small};
+
+    #[test]
+    fn test_increment_n_dirty() {


it's great to see these tests!

perhaps the range of nq could be larger? we usually take 1,2,...,8 (in most tests)

are there tests needed also for increment_1_dirty and increment_2_dirty ?

are there tests needed for synth_relative_mcx ?

For larger values of nq the simulation starts taking > 30 seconds on my laptop and I am not sure if we should add slow in-Rust tests. Hopefully the existing tests for smaller values of nq rule out most of the "obvious" bugs.

I am less worried about increment_1_dirty and increment_2_dirty since these functions are tested for smaller values of nq (though with different implementations of some internal components).

We could add tests for synth_relative_mcx as we have discussed offline, however for small values of nq this is covered in our Python testing, and for larger values of nq this is just our synth_mcx_n_dirty_i15 algorithm, which is also covered by our Python testing. So, thinking about this, we can skip such tests for now.

I do agree that we should think how to generally improve the testing strategy for synthesis methods, but let's do this in a follow-up. On this topic, I believe it could even be possible to formally prove correctness of certain synthesis methods (software verification/theorem proving) but this would be a huge project in itself.

qiskit/transpiler/passes/synthesis/hls_plugins.py

ShellyGarion

It's a great contribution to qiskit!
I only have a minor comment on the release notes. we can handle it now or as part of the 2.2 release PR.

releasenotes/notes/add-new-mcx-noaux-method-6f38c3cd3708df3c.yaml

In the recently merged Qiskit#14666 two small clippy issues with latest stable slipped into the PR. We run clippy with our MSRV in CI for a stable CI as newer versions of Rust/clippy introduce new rules and/or change/improve existing rules so a new rust release would break CI which is disruptive. However, you can still use newer clippy for local development and when you do the issues it finds highlight real things that need to be fixed in the code. This commit fixes the two things that clippy flags in the mcx plugin code, one is just a code style change but the other is a small docs formatting issue which would have resulted in weird formatting for the rendered rustdoc.

In the recently merged #14666 two small clippy issues with latest stable slipped into the PR. We run clippy with our MSRV in CI for a stable CI as newer versions of Rust/clippy introduce new rules and/or change/improve existing rules so a new rust release would break CI which is disruptive. However, you can still use newer clippy for local development and when you do the issues it finds highlight real things that need to be fixed in the code. This commit fixes the two things that clippy flags in the mcx plugin code, one is just a code style change but the other is a small docs formatting issue which would have resulted in weird formatting for the rendered rustdoc.

alexanderivrii and others added 3 commits June 25, 2025 14:45

Adding the MCX synthesis code based on PLDI24 paper

8c8851a

Co-authored-by: Jens Palsberg <palsberg@ucla.edu> Co-authored-by: Keli Huang <kelihuang@cs.ucla.edu>

Adding new funcion to init and docs

b00cdc7

adding test (for small values for the number of controls)

ea5744d

alexanderivrii requested a review from a team as a code owner June 25, 2025 13:04

alexanderivrii added 3 commits June 26, 2025 09:42

adding plugin + test for the new method

7371a9c

modifying the default MCX plugin to use the new method when appropriate

31f5920

adding release notes

8a35533

alexanderivrii changed the title ~~[WIP] Add the MCX synthesis algorithm by Huang and Palsberg~~ Add the MCX synthesis algorithm by Huang and Palsberg Jun 26, 2025

ShellyGarion self-assigned this Jun 29, 2025

ShellyGarion added the synthesis label Jul 9, 2025

ShellyGarion mentioned this pull request Jul 13, 2025

Port MCX synthesis to rust #13930

Closed

ShellyGarion reviewed Jul 13, 2025

View reviewed changes

alexanderivrii added 7 commits July 14, 2025 10:02

doctrings

353b2a4

fixing comment about v24; adding more tests; improving bounds

cdda005

adding unitary simulator in Rust

4068f2a

Consructs a unitary matrix from a CircuitData with only unitary operations, exactly as what Operator(quantum_circuit).data does. The code is a simple wrapper on top of unitary_compose.

adding simple test

bae2774

ignoring barriers during simulation

58b5bd3

change error to QiskitError

4b88676

splitting code into Rust and Python facing

9ac5e73

alexanderivrii mentioned this pull request Jul 16, 2025

Unitary simulator in Rust #14746

Merged

alexanderivrii added 3 commits July 16, 2025 11:15

Merge branch 'main' into mcx_pldi

29bf607

Merge branch 'unitary_simulator' into mcx_pldi

882031c

adding correctness test for increment_n_dirty

38eafbf

ShellyGarion reviewed Jul 17, 2025

View reviewed changes

alexanderivrii added 3 commits July 18, 2025 08:27

Merge branch 'main' into mcx_pldi

a75b964

improving release note

0e0620e

improving documentation

97553c8

alexanderivrii added 3 commits July 18, 2025 09:19

more docs

f6e2c6e

Merge branch 'main' into mcx_pldi

925c500

updating the code following the changes in Qiskit#14799

fc4ad77

alexanderivrii mentioned this pull request Aug 7, 2025

Python-free path for circuit parameters #14799

Merged

3 tasks

disabling miri on the rust tests: it's way too slow

f9d54ea

ShellyGarion added the Changelog: New Feature Include in the "Added" section of the changelog label Aug 7, 2025

ShellyGarion added this to the 2.2.0 milestone Aug 7, 2025

ShellyGarion previously approved these changes Aug 7, 2025

View reviewed changes

releasenotes/notes/add-new-mcx-noaux-method-6f38c3cd3708df3c.yaml Outdated Show resolved Hide resolved

releasenotes/notes/add-new-mcx-noaux-method-6f38c3cd3708df3c.yaml Outdated Show resolved Hide resolved

updating release notes following review

bee7bec

alexanderivrii dismissed ShellyGarion’s stale review via bee7bec August 7, 2025 14:17

ShellyGarion approved these changes Aug 7, 2025

View reviewed changes

ShellyGarion added this pull request to the merge queue Aug 7, 2025

Merged via the queue into Qiskit:main with commit 5fc45b6 Aug 7, 2025
26 checks passed

mtreinish mentioned this pull request Aug 8, 2025

Fix clippy issues in new MCX synthesis plugin #14843

Merged

Add the MCX synthesis algorithm by Huang and Palsberg #14666

Add the MCX synthesis algorithm by Huang and Palsberg #14666

Uh oh!

Conversation

alexanderivrii commented Jun 25, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Details and comments

Interesting questions:

Comparison without and with this PR

ToDo:

Uh oh!

qiskit-bot commented Jun 25, 2025

Uh oh!

coveralls commented Jun 25, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 16807106158

Warning: This coverage report may be inaccurate.

Details

💛 - Coveralls

Uh oh!

ShellyGarion left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alexanderivrii commented Jul 16, 2025

Uh oh!

ShellyGarion left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

ShellyGarion left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

alexanderivrii commented Jun 25, 2025 •

edited

Loading

coveralls commented Jun 25, 2025 •

edited

Loading