Skip to content

Update MCX recursive synthesis method to reduce number of CX gates #12772

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.

Sign up for GitHub

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

Jump to bottom
Merged
merged 19 commits into from
Jul 17, 2024
Merged

Update MCX recursive synthesis method to reduce number of CX gates #12772

merged 19 commits into from
Jul 17, 2024

Conversation

ShellyGarion
Copy link
Member

Summary

Close #9743.
This PR replaces #8710 in order to get it merged on time for qiskit 1.2 release.

Details and comments

thiagom123 and others added 9 commits September 7, 2022 17:30
@thiagom123 @rafaella-vale @JeffersonDeyvis
Optimization for the MCX Recursive Gate
507d5b3 
Change the recursive method for the Lemma 9 of arXiv:1501.06911, first shown in Lemma 7.3 of https://link.aps.org/doi/10.1103/PhysRevA.52.3457

Co-Authored-By: Rafaella Vale <26910380+rafaella-vale@users.noreply.github.com>
Co-Authored-By: Jefferson Deyvis <67497412+jeffersondeyvis@users.noreply.github.com>
@thiagom123 @rafaella-vale @JeffersonDeyvis
Revert "Optimization for the MCX Recursive Gate"
4671b7e 
This reverts commit 507d5b3.

Co-Authored-By: Rafaella Vale <26910380+rafaella-vale@users.noreply.github.com>
Co-Authored-By: Jefferson Deyvis <67497412+jeffersondeyvis@users.noreply.github.com>
@thiagom123
Revert "Revert "Optimization for the MCX Recursive Gate""
af4c3f6 
This reverts commit 4671b7e.
@thiagom123 @rafaella-vale
@JeffersonDeyvis @adjs
Optimization for MCX Recursive
8ca0031 
Fixing co-authors

Co-Authored-By: Rafaella Vale <26910380+rafaella-vale@users.noreply.github.com>
Co-Authored-By: Jefferson Deyvis <67497412+jeffersondeyvis@users.noreply.github.com>
Co-Authored-By: Adenilton Silva <7927558+adjs@users.noreply.github.com>
@thiagom123 @rafaella-vale
@JeffersonDeyvis @adjs
Optimization of MCX Recursive
e3729c9 
Now with fixed co-authors

Co-Authored-By: Rafaella Vale <26910380+rafaella-vale@users.noreply.github.com>
Co-Authored-By: Jefferson Deyvis <67497412+jeffersondeyvis@users.noreply.github.com>
Co-Authored-By: Adenilton Silva <7927558+adjs@users.noreply.github.com>
@rafaella-vale
refactored MCXRecursive and unused method deleted
4f10325
@rafaella-vale
fixed qasm string for mcx test with variants
a891dc4
@rafaella-vale
remove draw
09f0884
@ShellyGarion
merge main
cdccc8b
@ShellyGarion ShellyGarion added Changelog: New Feature Include in the "Added" section of the changelog synthesis mod: circuit Related to the core of the `QuantumCircuit` class or the circuit library labels Jul 15, 2024
@ShellyGarion ShellyGarion added this to the 1.2.0 milestone Jul 15, 2024
@ShellyGarion ShellyGarion requested a review from a team as a code owner July 15, 2024 06:49
@qiskit-bot
Copy link
Collaborator

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

  • @Cryoris
  • @Qiskit/terra-core
  • @ajavadia

@ShellyGarion ShellyGarion mentioned this pull request Jul 15, 2024
Closed
@ShellyGarion
Copy link
Member Author

Comparison of the old vs. new code:

        from qiskit import transpile
        from qiskit.circuit.library import MCXRecursive
        for n in range(5, 20):
            qc_rec = MCXRecursive(n).definition
            tqc_rec = transpile(qc_rec, basis_gates=['u', 'cx'])
            print("num_qubits=", n, "cx count=", tqc_rec.count_ops()["cx"])

Current code:

num_qubits= 5 cx count= 56
num_qubits= 6 cx count= 100
num_qubits= 7 cx count= 144
num_qubits= 8 cx count= 184
num_qubits= 9 cx count= 224
num_qubits= 10 cx count= 312
num_qubits= 11 cx count= 400
num_qubits= 12 cx count= 488
num_qubits= 13 cx count= 576
num_qubits= 14 cx count= 656
num_qubits= 15 cx count= 736
num_qubits= 16 cx count= 816
num_qubits= 17 cx count= 896
num_qubits= 18 cx count= 1072
num_qubits= 19 cx count= 1248

New code:

num_qubits= 5 cx count= 56
num_qubits= 6 cx count= 80
num_qubits= 7 cx count= 104
num_qubits= 8 cx count= 120
num_qubits= 9 cx count= 136
num_qubits= 10 cx count= 152
num_qubits= 11 cx count= 168
num_qubits= 12 cx count= 184
num_qubits= 13 cx count= 200
num_qubits= 14 cx count= 216
num_qubits= 15 cx count= 232
num_qubits= 16 cx count= 248
num_qubits= 17 cx count= 264
num_qubits= 18 cx count= 280
num_qubits= 19 cx count= 296

@ShellyGarion
Copy link
Member Author

For n>=7 the number of CX gates is 16*n-8

@coveralls
Copy link

coveralls commented Jul 16, 2024 •
edited
Loading

Pull Request Test Coverage Report for Build 9973712807

Details

  • 11 of 11 (100.0%) changed or added relevant lines in 1 file are covered.
  • 12 unchanged lines in 3 files lost coverage.
  • Overall coverage decreased (-0.004%) to 89.897%
Files with Coverage Reduction New Missed Lines %
crates/qasm2/src/expr.rs 1 94.02%
crates/qasm2/src/lex.rs 5 92.37%
crates/qasm2/src/parse.rs 6 96.69%
Totals Coverage Status
Change from base Build 9958403825: -0.004%
Covered Lines: 65790
Relevant Lines: 73184
💛 - Coveralls

@Cryoris Cryoris changed the title Update MCX recursive syntehesis method to reduce number of CX gates Update MCX recursive synthesis method to reduce number of CX gates Jul 17, 2024
Cryoris
Cryoris reviewed Jul 17, 2024
View reviewed changes
Cryoris
Cryoris reviewed Jul 17, 2024
View reviewed changes
@ShellyGarion
Copy link
Member Author

Some further experiments with more qubits:

num_qubits= 50 cx count current code= 9536 cx count new code= 792
num_qubits= 100 cx count current code= 38784 cx count new code=1592

@Cryoris Cryoris added this pull request to the merge queue Jul 17, 2024
Merged via the queue into Qiskit:main with commit 5a6312d Jul 17, 2024
Procatv pushed a commit to Procatv/qiskit-terra-catherines that referenced this pull request Aug 1, 2024
@ShellyGarion @thiagom123
@rafaella-vale @JeffersonDeyvis @adjs @Procatv
Update MCX recursive synthesis method to reduce number of CX gates (Q…
4e90bcf 
…iskit#12772)

* Optimization for the MCX Recursive Gate

Change the recursive method for the Lemma 9 of arXiv:1501.06911, first shown in Lemma 7.3 of https://link.aps.org/doi/10.1103/PhysRevA.52.3457

Co-Authored-By: Rafaella Vale <26910380+rafaella-vale@users.noreply.github.com>
Co-Authored-By: Jefferson Deyvis <67497412+jeffersondeyvis@users.noreply.github.com>

* Revert "Optimization for the MCX Recursive Gate"

This reverts commit 507d5b3.

Co-Authored-By: Rafaella Vale <26910380+rafaella-vale@users.noreply.github.com>
Co-Authored-By: Jefferson Deyvis <67497412+jeffersondeyvis@users.noreply.github.com>

* Revert "Revert "Optimization for the MCX Recursive Gate""

This reverts commit 4671b7e.

* Optimization for MCX Recursive

Fixing co-authors

Co-Authored-By: Rafaella Vale <26910380+rafaella-vale@users.noreply.github.com>
Co-Authored-By: Jefferson Deyvis <67497412+jeffersondeyvis@users.noreply.github.com>
Co-Authored-By: Adenilton Silva <7927558+adjs@users.noreply.github.com>

* Optimization of MCX Recursive

Now with fixed co-authors

Co-Authored-By: Rafaella Vale <26910380+rafaella-vale@users.noreply.github.com>
Co-Authored-By: Jefferson Deyvis <67497412+jeffersondeyvis@users.noreply.github.com>
Co-Authored-By: Adenilton Silva <7927558+adjs@users.noreply.github.com>

* refactored MCXRecursive and unused method deleted

* fixed qasm string for mcx test with variants

* remove draw

* fix qasm file in test_circuit_qasm_with_mcx_gate_variants

* update the MCXRecursive class docstring

* add a test of the upper bound limit of the number of CX gates

* fix failing qasm test

* fix qasm file in test_export in qasm2 tests

* fix format lint errors in qasm strings

* add release notes

* update references format

* update release notes after review

---------

Co-authored-by: Thiago Melo <thiagomdazevedo@hotmail.com>
Co-authored-by: Rafaella Vale <26910380+rafaella-vale@users.noreply.github.com>
Co-authored-by: Jefferson Deyvis <67497412+jeffersondeyvis@users.noreply.github.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@alexanderivrii alexanderivrii alexanderivrii left review comments

@Cryoris Cryoris Cryoris approved these changes

Assignees

@Cryoris Cryoris

Labels
Changelog: New Feature Include in the "Added" section of the changelog mod: circuit Related to the core of the `QuantumCircuit` class or the circuit library synthesis
Projects
None yet
Milestone
1.2.0
Development

Successfully merging this pull request may close these issues.

MCXRecursive should use MCXVChain with dirty ancillas
7 participants
@ShellyGarion @qiskit-bot @coveralls @Cryoris @alexanderivrii @thiagom123 @rafaella-vale