block diagonal optimized quantum shannon decomposition #13688

ewinston · 2025-01-18T04:42:47Z

Summary

This PR attempts to detect when the unitary matrix has a block diagonal representation with respect to one of it's qubits at each step of the recursion in the QSD. If this occurs, one may skip the cosine-sine decomposition and therefore reduce the CX gate count. In addition this may help avoid numerical errors the underlying scipy.linalg.cossin function seems to have for block-diagonal input matrices.

Details and comments

qiskit-bot · 2025-01-18T04:42:51Z

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

@Qiskit/terra-core

coveralls · 2025-01-18T06:27:49Z

Pull Request Test Coverage Report for Build 15163180521

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

40 of 42 (95.24%) changed or added relevant lines in 3 files are covered.
953 unchanged lines in 22 files lost coverage.
Overall coverage decreased (-0.4%) to 88.325%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/circuit/library/generalized_gates/unitary.py	6	8	75.0%

Files with Coverage Reduction	New Missed Lines	%
qiskit/transpiler/passes/optimization/template_matching/template_substitution.py	1	93.54%
crates/qasm2/src/lex.rs	2	92.23%
qiskit/circuit/parameter.py	2	96.77%
crates/circuit/src/packed_instruction.rs	4	93.18%
qiskit/primitives/containers/observables_array.py	4	96.53%
qiskit/transpiler/passes/optimization/optimize_1q_decomposition.py	4	94.9%
qiskit/transpiler/passes/routing/star_prerouting.py	4	97.77%
crates/circuit/src/lib.rs	6	94.44%
qiskit/transpiler/passes/layout/dense_layout.py	6	93.26%
qiskit/transpiler/passes/layout/sabre_layout.py	8	93.94%

Totals
Change from base Build 14929222382:	-0.4%
Covered Lines:	78396
Relevant Lines:	88759

💛 - Coveralls

ShellyGarion · 2025-01-28T12:27:00Z

should hopefully close #10313 and replace #12779 (#10320)

jakelishman · 2025-04-28T12:54:25Z

Glancing quickly, I think this PR is implementing a special case of a question something like "is there a subset of target qubits for which the partial trace commutes with $Z^{(i)}$?". That feels like something we could tackle by Hilbert-space re-ordering at the top level of the decomposition, so we can get them out of the way earlier and reduce the difficulty at all levels.

I want to stress how little I've thought this through, so I might just be chatting nonsense.

ShellyGarion · 2025-05-05T11:56:28Z

Glancing quickly, I think this PR is implementing a special case of a question something like "is there a subset of target qubits for which the partial trace commutes with Z ( i ) ?". That feels like something we could tackle by Hilbert-space re-ordering at the top level of the decomposition, so we can get them out of the way earlier and reduce the difficulty at all levels.

I want to stress how little I've thought this through, so I might just be chatting nonsense.

@jakelishman - We have tried to extend this suggestion to the case of multi-controlled gates, but it seems that the algorithm of Shende et. al. decomposes the unitary gate using uniformly-controlled Rz or Ry gates, and this structure is not preserved in the induction step. Any concrete suggestions would be helpful.

ShellyGarion · 2025-05-05T11:59:41Z

Comparing QSD to multi-controlled synthesis for 1-qubit gates (see: test_mc_1qubit_opt):
Usually it's better to use the multi-controlled synthesis directly, except of a few cases (with 3,4,5 qubits and p or u basis gate).

num_qubits= 3 base_gate= x cx count using mc: OrderedDict({'u': 8, 'cx': 6}) cx count using qsd: OrderedDict({'u': 15, 'cx': 8})
num_qubits= 3 base_gate= p cx count using mc: OrderedDict({'u': 7, 'cx': 6}) cx count using qsd: OrderedDict({'u': 10, 'cx': 6})
num_qubits= 3 base_gate= u cx count using mc: OrderedDict({'u': 25, 'cx': 22}) cx count using qsd: OrderedDict({'u': 20, 'cx': 10})
num_qubits= 4 base_gate= x cx count using mc: OrderedDict({'u': 16, 'cx': 14}) cx count using qsd: OrderedDict({'u': 77, 'cx': 47})
num_qubits= 4 base_gate= p cx count using mc: OrderedDict({'u': 24, 'cx': 20}) cx count using qsd: OrderedDict({'u': 18, 'cx': 14})
num_qubits= 4 base_gate= u cx count using mc: OrderedDict({'u': 56, 'cx': 51}) cx count using qsd: OrderedDict({'u': 87, 'cx': 51})
num_qubits= 5 base_gate= x cx count using mc: OrderedDict({'u': 41, 'cx': 36}) cx count using qsd: OrderedDict({'u': 396, 'cx': 238})
num_qubits= 5 base_gate= p cx count using mc: OrderedDict({'u': 53, 'cx': 44}) cx count using qsd: OrderedDict({'u': 34, 'cx': 30})
num_qubits= 5 base_gate= u cx count using mc: OrderedDict({'u': 109, 'cx': 92}) cx count using qsd: OrderedDict({'u': 388, 'cx': 236})
num_qubits= 6 base_gate= x cx count using mc: OrderedDict({'u': 97, 'cx': 84}) cx count using qsd: OrderedDict({'u': 1642, 'cx': 1012})
num_qubits= 6 base_gate= p cx count using mc: OrderedDict({'u': 97, 'cx': 84}) cx count using qsd: OrderedDict({'u': 1686, 'cx': 1046})
num_qubits= 6 base_gate= u cx count using mc: OrderedDict({'u': 181, 'cx': 164}) cx count using qsd: OrderedDict({'u': 1668, 'cx': 1030})
num_qubits= 7 base_gate= x cx count using mc: OrderedDict({'u': 155, 'cx': 140}) cx count using qsd: OrderedDict({'u': 6794, 'cx': 4244})
num_qubits= 7 base_gate= p cx count using mc: OrderedDict({'u': 155, 'cx': 140}) cx count using qsd: OrderedDict({'u': 2364, 'cx': 1488})
num_qubits= 7 base_gate= u cx count using mc: OrderedDict({'u': 267, 'cx': 252}) cx count using qsd: OrderedDict({'u': 3436, 'cx': 2156})
num_qubits= 8 base_gate= x cx count using mc: OrderedDict({'u': 242, 'cx': 220}) cx count using qsd: OrderedDict({'u': 27734, 'cx': 17494})

ShellyGarion · 2025-05-05T12:02:35Z

Comparing QSD to multi-controlled synthesis for 2-qubit gates (see: test_mc_2qubit_opt):
Usually it's better to use the multi-controlled synthesis directly, except when the number of qubits is 4.

num_qubits= 3 cx count using mc: OrderedDict({'u': 20, 'cx': 10}) cx count using qsd: OrderedDict({'u': 20, 'cx': 10})
num_qubits= 4 cx count using mc: OrderedDict({'u': 82, 'cx': 48}) cx count using qsd: OrderedDict({'u': 78, 'cx': 46})
num_qubits= 5 cx count using mc: OrderedDict({'u': 396, 'cx': 238}) cx count using qsd: OrderedDict({'u': 406, 'cx': 246})
num_qubits= 6 cx count using mc: OrderedDict({'u': 1668, 'cx': 1030}) cx count using qsd: OrderedDict({'u': 1686, 'cx': 1046})
num_qubits= 7 cx count using mc: OrderedDict({'u': 6836, 'cx': 4278}) cx count using qsd: OrderedDict({'u': 6870, 'cx': 4310})

Co-authoed by: Alexander Ivrii <alexi@il.ibm.com>

alexanderivrii · 2025-05-13T08:44:49Z

Thanks for providing the table (the second last column should read "opt_a2 = True", correct?

ShellyGarion · 2025-05-13T08:49:26Z

Thanks for providing the table (the second last column should read "opt_a2 = True", correct?

yes, fixed. thanks!

…ery instead of QSD

ShellyGarion · 2025-05-18T14:00:17Z

qiskit/circuit/library/generalized_gates/unitary.py

+            if not (
+                matrix_equal(Operator(self.definition).to_matrix(), self.to_matrix(), atol=1e-7)
+            ):
+                self.definition = Isometry(self.matrix, 0, 0).definition


code updated to use Isometry the calculated Operator is different than the original matrix.

This is not ideal as this adds additional overhead and does not guarantee that we always get the better definition based on QSD. However, this is the best we can do for now and this does significantly improve the gate counts when this does work. Thus I am in favor of merging this in the current form, but we should open an issue to investigate and improve numerical decomposition errors in cossin.

ShellyGarion · 2025-05-18T14:00:51Z

qiskit/circuit/library/generalized_gates/unitary.py

+
+            cmat_def = qs_decomposition(cmat, opt_a1=True, opt_a2=False)
+            if not matrix_equal(Operator(cmat_def).to_matrix(), cmat, atol=1e-7):
+                self.definition = Isometry(cmat, 0, 0).definition


code updated to use Isometry the calculated Operator is different than the original matrix.

Do you know what are the typical numerical errors when running the Isometry code?

I don't think there are special numerical errors. QSD is done recursively and this is the reason that we get numeric errors. However, Isometry is not iterative. I can add similar tests to Isometry.

alexanderivrii

Thanks for doing this, this looks good. I have left just one nitpick about the argument _ctrl_index. Can you also open an issue to investigate/fix numerical errors in the cossin decomposition?

alexanderivrii · 2025-05-20T11:43:07Z

qiskit/circuit/library/generalized_gates/unitary.py

+            if not (
+                matrix_equal(Operator(self.definition).to_matrix(), self.to_matrix(), atol=1e-7)
+            ):
+                self.definition = Isometry(self.matrix, 0, 0).definition


This is not ideal as this adds additional overhead and does not guarantee that we always get the better definition based on QSD. However, this is the best we can do for now and this does significantly improve the gate counts when this does work. Thus I am in favor of merging this in the current form, but we should open an issue to investigate and improve numerical decomposition errors in cossin.

alexanderivrii · 2025-05-20T11:43:53Z

qiskit/circuit/library/generalized_gates/unitary.py

+
+            cmat_def = qs_decomposition(cmat, opt_a1=True, opt_a2=False)
+            if not matrix_equal(Operator(cmat_def).to_matrix(), cmat, atol=1e-7):
+                self.definition = Isometry(cmat, 0, 0).definition


Do you know what are the typical numerical errors when running the Isometry code?

qiskit/synthesis/unitary/qsd.py

test/python/circuit/test_controlled_gate.py

ShellyGarion · 2025-05-21T13:30:40Z

See: #14422

alexanderivrii

Thanks @ShellyGarion, LGTM!

* add test of block extration wrt qubit * passing tests. Seems mcx synthesis could be more optimal. * replace isometry by qsd in unitary control method * remove qsd tests from test_synthesis * move qsd synthesis tests * fix random seed. update tolerance in matrices differences * formatting, clean tests * extend tollerance in test * add multi-controlled tests * extend tollerance * extend tollerance * reduce number of controls in tests * update docs * add release notes * formtting * update tollerance * update qsd following review * update release notes following review * update tests following review * change tollerance * improve layout following review * fix svd, Co-authoed by: Alexander Ivrii <alexi@il.ibm.com> * raise atol * update atol * remove assertion * remove assertion * update cos_sin_decomp tolerance * update tollerance * linting * if the Operaotr is not the same as the original matrix, we use Isometery instead of QSD * update atol * move import line * update the tests to allow using Isometry * disable cyclic imports * handle ctrl_index following review --------- Co-authored-by: ShellyGarion <shelly@il.ibm.com>

ewinston added 2 commits January 8, 2025 10:15

add test of block extration wrt qubit

abf20fd

passing tests. Seems mcx synthesis could be more optimal.

0943ddd

ewinston requested review from alexanderivrii, ShellyGarion and a team as code owners January 18, 2025 04:42

ShellyGarion added the synthesis label Jan 21, 2025

ShellyGarion added this to the 2.0.0 milestone Jan 21, 2025

1ucian0 assigned ShellyGarion Jan 30, 2025

ShellyGarion modified the milestones: 2.0.0, 2.1.0 Feb 26, 2025

ShellyGarion added 3 commits April 1, 2025 04:53

replace isometry by qsd in unitary control method

b820147

remove qsd tests from test_synthesis

62c0b42

move qsd synthesis tests

3c74151

alexanderivrii mentioned this pull request Apr 2, 2025

Problems with scipy's cosine-sine decomposition #14157

Closed

merge main branch

930f1ca

ShellyGarion mentioned this pull request Apr 28, 2025

Port qs_decomposition to Rust #12213

Open

ShellyGarion added 4 commits April 29, 2025 02:19

fix random seed. update tolerance in matrices differences

7811cab

formatting, clean tests

90c904c

extend tollerance in test

a0abf44

add multi-controlled tests

3ca41a8

ShellyGarion mentioned this pull request May 5, 2025

[WIP] Improve controlled UnitaryGate() (replace #10320) #12779

Closed

ShellyGarion linked an issue May 5, 2025 that may be closed by this pull request

UnitaryGate.control implementation high gate count #10313

Closed

ShellyGarion assigned alexanderivrii May 5, 2025

ShellyGarion added 2 commits May 9, 2025 07:56

Merge branch 'main' into qsd_block_diagonal

ac37832

fix svd,

b4443c3

Co-authoed by: Alexander Ivrii <alexi@il.ibm.com>

ShellyGarion requested a review from alexanderivrii May 11, 2025 09:03

ShellyGarion added 7 commits May 11, 2025 06:53

raise atol

483412b

update atol

416c7f7

remove assertion

4944fb9

remove assertion

97ff9e2

update cos_sin_decomp tolerance

a98fde2

update tollerance

3034410

linting

d213699

ShellyGarion added 2 commits May 18, 2025 08:58

if the Operaotr is not the same as the original matrix, we use Isomet…

9f28f96

…ery instead of QSD

update atol

861db5f

ShellyGarion reviewed May 18, 2025

View reviewed changes

ShellyGarion added 3 commits May 19, 2025 03:26

move import line

f2db71a

update the tests to allow using Isometry

22bc34f

disable cyclic imports

22c9869

alexanderivrii reviewed May 20, 2025

View reviewed changes

handle ctrl_index following review

6fffbd9

ShellyGarion mentioned this pull request May 21, 2025

Improve tolerance in cosine-sine decomposition #14422

Open

alexanderivrii approved these changes May 21, 2025

View reviewed changes

alexanderivrii added this pull request to the merge queue May 21, 2025

Merged via the queue into Qiskit:main with commit 83d85a0 May 21, 2025
24 checks passed

eliarbel added the Changelog: New Feature Include in the "Added" section of the changelog label Jun 3, 2025

ShellyGarion mentioned this pull request Jun 9, 2025

Faster controlled unitary operations #14555

Closed

block diagonal optimized quantum shannon decomposition #13688

block diagonal optimized quantum shannon decomposition #13688

Uh oh!

Conversation

ewinston commented Jan 18, 2025

Summary

Details and comments

Uh oh!

qiskit-bot commented Jan 18, 2025

Uh oh!

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

Uh oh!

Pull Request Test Coverage Report for Build 15163180521

Warning: This coverage report may be inaccurate.

Details

💛 - Coveralls

Uh oh!

ShellyGarion commented Jan 28, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jakelishman commented Apr 28, 2025

Uh oh!

ShellyGarion commented May 5, 2025

Uh oh!

ShellyGarion commented May 5, 2025

Uh oh!

ShellyGarion commented May 5, 2025

Uh oh!

alexanderivrii commented May 13, 2025

Uh oh!

ShellyGarion commented May 13, 2025

Uh oh!

ShellyGarion May 18, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alexanderivrii May 20, 2025

Choose a reason for hiding this comment

Uh oh!

ShellyGarion May 18, 2025

Choose a reason for hiding this comment

Uh oh!

alexanderivrii May 20, 2025

Choose a reason for hiding this comment

Uh oh!

ShellyGarion May 21, 2025

Choose a reason for hiding this comment

Uh oh!

alexanderivrii left a comment

Choose a reason for hiding this comment

Uh oh!

alexanderivrii May 20, 2025

Choose a reason for hiding this comment

Uh oh!

alexanderivrii May 20, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ShellyGarion commented May 21, 2025

Uh oh!

alexanderivrii left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

coveralls commented Jan 18, 2025 •

edited

Loading

ShellyGarion commented Jan 28, 2025 •

edited

Loading

ShellyGarion May 18, 2025 •

edited

Loading