Skip to content
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

mcry circuit requires an exponential number of cx gates #9741

Closed
adjs opened this issue Mar 6, 2023 · 0 comments
Closed

mcry circuit requires an exponential number of cx gates #9741

adjs opened this issue Mar 6, 2023 · 0 comments
Labels
bug Something isn't working

Comments

@adjs
Copy link
Contributor

adjs commented Mar 6, 2023

Environment

  • Qiskit Terra version: 0.23.2
  • Python version: 3.8.10
  • Operating system: Ubuntu 20.04.5 LTS

What is happening?

QuantumCircuit.mcry creates a circuit with a exponential number of cx gates.

How can we reproduce the issue?

The number of cx gates doubles after adding a control. For example, with 6 and 7 controls, the number of cx is 92 and 188.

from qiskit import QuantumCircuit, transpile
qc6 = QuantumCircuit(6)
qc6.mcry(0.3, [0, 1, 2, 3, 4], 5)
tqc6 = transpile(qc6, basis_gates=['u', 'cx'])
tqc6.count_ops()['cx']
from qiskit import QuantumCircuit, transpile
qc7 = QuantumCircuit(7)
qc7.mcry(0.3, [0, 1, 2, 3, 4, 5], 6)
tqc7 = transpile(qc7, basis_gates=['u', 'cx'])
tqc7.count_ops()['cx']

What should happen?

The number of cx gates should be 16k-40 [Section 3.1, https://arxiv.org/pdf/2302.06377.pdf].

Disclaimer: I am an author of this paper.

Any suggestions?

No response
@adjs adjs added the bug Something isn't working label Mar 6, 2023
This was referenced Mar 6, 2023
Merged
Closed
1ucian0 pushed a commit that referenced this issue Apr 2, 2023
@rafaella-vale @thiagom123
@IsmaelCesar @israelferrazaraujo @adjs
Fixes issue #9741 from exponential to linear number of cx gates in mc…
9ec073e 
…ry (#9688)

* efficient multicontrolled su2 gate decomposition

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>

* removed optimization flag

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>

* tox -eblack

* updated docstrings

* Adds `MCSU2Gate` to `__init__`

* fixed circular import

* defined control and inverse methods

* changed MCSU2Gate from Gate to ControlledGate

* adjusted some tests for controlled gates

* reformatting

* Fix regarding the integer `ctrl_state` parameter

* Tests to check the CX count upper bound

* Gate's `label` in the `control` function

* Upd. Qiskit tests to include cases for MCSU2Gate

* Upd. Qiskit tests to include cases for MCSU2Gate

* Revert "Upd. Qiskit tests to include cases for MCSU2Gate"

This reverts commit c1ceaf6.

* Revert "Upd. Qiskit tests to include cases for MCSU2Gate"

This reverts commit 7c75611.

* Revert "Tests to check the CX count upper bound"

This reverts commit 100a690.

* Update test_controlled_gate.py

* Update test_circuit_operations.py

* remove mcsu2gate class

* remove mcsu2gate class

* fix mcry

* lint

* fix mcrx

* add reference

* Create `s_gate` directly

* Revert "Create `s_gate` directly"

This reverts commit b762b39.

* review

* release notes

* review 2

* backwards compat

* function signature and number of controls

* review 3

* Update multi_control_rotation_gates.py

* Update multi_control_rotation_gates.py

* Revert "Update multi_control_rotation_gates.py"

This reverts commit e371ef8.

* Revert "Update multi_control_rotation_gates.py"

This reverts commit b4c3fe4.

---------

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>
Co-authored-by: Adenilton Silva <ajsilva@cin.ufpe.br>
ElePT pushed a commit to ElePT/qiskit that referenced this issue Apr 5, 2023
@rafaella-vale @thiagom123
@IsmaelCesar @israelferrazaraujo @adjs @ElePT
Fixes issue Qiskit#9741 from exponential to linear number of cx gates…
d67e38d 
… in mcry (Qiskit#9688)

* efficient multicontrolled su2 gate decomposition

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>

* removed optimization flag

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>

* tox -eblack

* updated docstrings

* Adds `MCSU2Gate` to `__init__`

* fixed circular import

* defined control and inverse methods

* changed MCSU2Gate from Gate to ControlledGate

* adjusted some tests for controlled gates

* reformatting

* Fix regarding the integer `ctrl_state` parameter

* Tests to check the CX count upper bound

* Gate's `label` in the `control` function

* Upd. Qiskit tests to include cases for MCSU2Gate

* Upd. Qiskit tests to include cases for MCSU2Gate

* Revert "Upd. Qiskit tests to include cases for MCSU2Gate"

This reverts commit c1ceaf6.

* Revert "Upd. Qiskit tests to include cases for MCSU2Gate"

This reverts commit 7c75611.

* Revert "Tests to check the CX count upper bound"

This reverts commit 100a690.

* Update test_controlled_gate.py

* Update test_circuit_operations.py

* remove mcsu2gate class

* remove mcsu2gate class

* fix mcry

* lint

* fix mcrx

* add reference

* Create `s_gate` directly

* Revert "Create `s_gate` directly"

This reverts commit b762b39.

* review

* release notes

* review 2

* backwards compat

* function signature and number of controls

* review 3

* Update multi_control_rotation_gates.py

* Update multi_control_rotation_gates.py

* Revert "Update multi_control_rotation_gates.py"

This reverts commit e371ef8.

* Revert "Update multi_control_rotation_gates.py"

This reverts commit b4c3fe4.

---------

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>
Co-authored-by: Adenilton Silva <ajsilva@cin.ufpe.br>
@adjs adjs closed this as completed Apr 5, 2023
giacomoRanieri pushed a commit to giacomoRanieri/qiskit-terra that referenced this issue Apr 16, 2023
@rafaella-vale @thiagom123
@IsmaelCesar @israelferrazaraujo @adjs @giacomoRanieri
Fixes issue Qiskit#9741 from exponential to linear number of cx gates…
a334f09 
… in mcry (Qiskit#9688)

* efficient multicontrolled su2 gate decomposition

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>

* removed optimization flag

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>

* tox -eblack

* updated docstrings

* Adds `MCSU2Gate` to `__init__`

* fixed circular import

* defined control and inverse methods

* changed MCSU2Gate from Gate to ControlledGate

* adjusted some tests for controlled gates

* reformatting

* Fix regarding the integer `ctrl_state` parameter

* Tests to check the CX count upper bound

* Gate's `label` in the `control` function

* Upd. Qiskit tests to include cases for MCSU2Gate

* Upd. Qiskit tests to include cases for MCSU2Gate

* Revert "Upd. Qiskit tests to include cases for MCSU2Gate"

This reverts commit c1ceaf6.

* Revert "Upd. Qiskit tests to include cases for MCSU2Gate"

This reverts commit 7c75611.

* Revert "Tests to check the CX count upper bound"

This reverts commit 100a690.

* Update test_controlled_gate.py

* Update test_circuit_operations.py

* remove mcsu2gate class

* remove mcsu2gate class

* fix mcry

* lint

* fix mcrx

* add reference

* Create `s_gate` directly

* Revert "Create `s_gate` directly"

This reverts commit b762b39.

* review

* release notes

* review 2

* backwards compat

* function signature and number of controls

* review 3

* Update multi_control_rotation_gates.py

* Update multi_control_rotation_gates.py

* Revert "Update multi_control_rotation_gates.py"

This reverts commit e371ef8.

* Revert "Update multi_control_rotation_gates.py"

This reverts commit b4c3fe4.

---------

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>
Co-authored-by: Adenilton Silva <ajsilva@cin.ufpe.br>
king-p3nguin pushed a commit to king-p3nguin/qiskit-terra that referenced this issue May 22, 2023
@rafaella-vale @thiagom123
@IsmaelCesar @israelferrazaraujo @adjs @king-p3nguin
Fixes issue Qiskit#9741 from exponential to linear number of cx gates…
12da224 
… in mcry (Qiskit#9688)

* efficient multicontrolled su2 gate decomposition

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>

* removed optimization flag

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>

* tox -eblack

* updated docstrings

* Adds `MCSU2Gate` to `__init__`

* fixed circular import

* defined control and inverse methods

* changed MCSU2Gate from Gate to ControlledGate

* adjusted some tests for controlled gates

* reformatting

* Fix regarding the integer `ctrl_state` parameter

* Tests to check the CX count upper bound

* Gate's `label` in the `control` function

* Upd. Qiskit tests to include cases for MCSU2Gate

* Upd. Qiskit tests to include cases for MCSU2Gate

* Revert "Upd. Qiskit tests to include cases for MCSU2Gate"

This reverts commit c1ceaf6.

* Revert "Upd. Qiskit tests to include cases for MCSU2Gate"

This reverts commit 7c75611.

* Revert "Tests to check the CX count upper bound"

This reverts commit 100a690.

* Update test_controlled_gate.py

* Update test_circuit_operations.py

* remove mcsu2gate class

* remove mcsu2gate class

* fix mcry

* lint

* fix mcrx

* add reference

* Create `s_gate` directly

* Revert "Create `s_gate` directly"

This reverts commit b762b39.

* review

* release notes

* review 2

* backwards compat

* function signature and number of controls

* review 3

* Update multi_control_rotation_gates.py

* Update multi_control_rotation_gates.py

* Revert "Update multi_control_rotation_gates.py"

This reverts commit e371ef8.

* Revert "Update multi_control_rotation_gates.py"

This reverts commit b4c3fe4.

---------

Co-authored-by: thiagom123 <thiagomdazevedo@hotmail.com>
Co-authored-by: IsmaelCesar <leamscesar@gmail.com>
Co-authored-by: Israel F. Araujo <israelferrazaraujo@hotmail.com>
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>
Co-authored-by: Adenilton Silva <ajsilva@cin.ufpe.br>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@adjs