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

Better decomposition for multi-controlled 1-qubit gates #13514

Open
ACE07-Sev opened this issue Dec 2, 2024 · 2 comments
Open

Better decomposition for multi-controlled 1-qubit gates #13514

ACE07-Sev opened this issue Dec 2, 2024 · 2 comments
Labels
synthesis

Comments

@ACE07-Sev
Copy link

ACE07-Sev commented Dec 2, 2024 •
edited
Loading

Greetings there,

Hope all are well. I am creating this issue as requested by Dr. Garrion to summarize the discussion we had on the decomposition of multi-controlled 1-qubit gates, and the need for some of them to have their own dedicated decomposition, i.e., MCU3.

To provide some data, I transpiled the multi-controlled gates to U3 and CX, and have created the table below to showcase the cost of each gate as we scale the number of control qubits from 2 to 10 inclusive.

Gate Number of controls Depth Number of CX and U3 gates
_SingletonXGate 1 1 OrderedDict([('cx', 1)])
_SingletonXGate 2 11 OrderedDict([('u3', 8), ('cx', 6)])
_SingletonXGate 3 27 OrderedDict([('u3', 16), ('cx', 14)])
_SingletonXGate 4 65 OrderedDict([('u3', 41), ('cx', 36)])
_SingletonXGate 5 131 OrderedDict([('u3', 98), ('cx', 84)])
_SingletonXGate 6 193 OrderedDict([('u3', 159), ('cx', 140)])
_SingletonXGate 7 333 OrderedDict([('u3', 248), ('cx', 220)])
_SingletonXGate 8 501 OrderedDict([('u3', 369), ('cx', 324)])
_SingletonXGate 9 705 OrderedDict([('u3', 506), ('cx', 444)])
_SingletonXGate 10 937 OrderedDict([('u3', 659), ('cx', 580)])
_SingletonYGate 1 3 OrderedDict([('u3', 2), ('cx', 1)])
_SingletonYGate 2 43 OrderedDict([('u3', 28), ('cx', 24)])
_SingletonYGate 3 89 OrderedDict([('u3', 61), ('cx', 60)])
_SingletonYGate 4 166 OrderedDict([('u3', 133), ('cx', 112)])
_SingletonYGate 5 313 OrderedDict([('u3', 237), ('cx', 208)])
_SingletonYGate 6 449 OrderedDict([('u3', 372), ('cx', 336)])
_SingletonYGate 7 803 OrderedDict([('u3', 582), ('cx', 520)])
_SingletonYGate 8 1155 OrderedDict([('u3', 857), ('cx', 752)])
_SingletonYGate 9 1598 OrderedDict([('u3', 1147), ('cx', 1008)])
_SingletonYGate 10 2086 OrderedDict([('u3', 1469), ('cx', 1296)])
_SingletonZGate 1 3 OrderedDict([('u3', 2), ('cx', 1)])
_SingletonZGate 2 11 OrderedDict([('u3', 8), ('cx', 6)])
_SingletonZGate 3 33 OrderedDict([('u3', 24), ('cx', 20)])
_SingletonZGate 4 68 OrderedDict([('u3', 53), ('cx', 44)])
_SingletonZGate 5 131 OrderedDict([('u3', 98), ('cx', 84)])
_SingletonZGate 6 193 OrderedDict([('u3', 159), ('cx', 140)])
_SingletonZGate 7 333 OrderedDict([('u3', 248), ('cx', 220)])
_SingletonZGate 8 501 OrderedDict([('u3', 369), ('cx', 324)])
_SingletonZGate 9 705 OrderedDict([('u3', 506), ('cx', 444)])
_SingletonZGate 10 937 OrderedDict([('u3', 659), ('cx', 580)])
_SingletonHGate 1 3 OrderedDict([('u3', 2), ('cx', 1)])
_SingletonHGate 2 35 OrderedDict([('cx', 22), ('u3', 21)])
_SingletonHGate 3 81 OrderedDict([('cx', 58), ('u3', 53)])
_SingletonHGate 4 158 OrderedDict([('u3', 125), ('cx', 110)])
_SingletonHGate 5 305 OrderedDict([('u3', 229), ('cx', 206)])
_SingletonHGate 6 441 OrderedDict([('u3', 364), ('cx', 334)])
_SingletonHGate 7 795 OrderedDict([('u3', 574), ('cx', 518)])
_SingletonHGate 8 1147 OrderedDict([('u3', 849), ('cx', 750)])
_SingletonHGate 9 1590 OrderedDict([('u3', 1139), ('cx', 1006)])
_SingletonHGate 10 2078 OrderedDict([('u3', 1461), ('cx', 1294)])
_SingletonSGate 1 5 OrderedDict([('u3', 4), ('cx', 2)])
_SingletonSGate 2 11 OrderedDict([('u3', 7), ('cx', 6)])
_SingletonSGate 3 33 OrderedDict([('u3', 24), ('cx', 20)])
_SingletonSGate 4 68 OrderedDict([('u3', 53), ('cx', 44)])
_SingletonSGate 5 131 OrderedDict([('u3', 98), ('cx', 84)])
_SingletonSGate 6 193 OrderedDict([('u3', 159), ('cx', 140)])
_SingletonSGate 7 333 OrderedDict([('u3', 248), ('cx', 220)])
_SingletonSGate 8 501 OrderedDict([('u3', 369), ('cx', 324)])
_SingletonSGate 9 705 OrderedDict([('u3', 506), ('cx', 444)])
_SingletonSGate 10 937 OrderedDict([('u3', 659), ('cx', 580)])
_SingletonSdgGate 1 7 OrderedDict([('u3', 5), ('cx', 3)])
_SingletonSdgGate 2 11 OrderedDict([('u3', 7), ('cx', 6)])
_SingletonSdgGate 3 33 OrderedDict([('u3', 24), ('cx', 20)])
_SingletonSdgGate 4 68 OrderedDict([('u3', 53), ('cx', 44)])
_SingletonSdgGate 5 131 OrderedDict([('u3', 98), ('cx', 84)])
_SingletonSdgGate 6 193 OrderedDict([('u3', 159), ('cx', 140)])
_SingletonSdgGate 7 333 OrderedDict([('u3', 248), ('cx', 220)])
_SingletonSdgGate 8 501 OrderedDict([('u3', 369), ('cx', 324)])
_SingletonSdgGate 9 705 OrderedDict([('u3', 506), ('cx', 444)])
_SingletonSdgGate 10 937 OrderedDict([('u3', 659), ('cx', 580)])
_SingletonTGate 1 5 OrderedDict([('u3', 3), ('cx', 2)])
_SingletonTGate 2 11 OrderedDict([('u3', 7), ('cx', 6)])
_SingletonTGate 3 33 OrderedDict([('u3', 24), ('cx', 20)])
_SingletonTGate 4 68 OrderedDict([('u3', 53), ('cx', 44)])
_SingletonTGate 5 131 OrderedDict([('u3', 98), ('cx', 84)])
_SingletonTGate 6 193 OrderedDict([('u3', 159), ('cx', 140)])
_SingletonTGate 7 333 OrderedDict([('u3', 248), ('cx', 220)])
_SingletonTGate 8 501 OrderedDict([('u3', 369), ('cx', 324)])
_SingletonTGate 9 705 OrderedDict([('u3', 506), ('cx', 444)])
_SingletonTGate 10 937 OrderedDict([('u3', 659), ('cx', 580)])
_SingletonTdgGate 1 5 OrderedDict([('u3', 3), ('cx', 2)])
_SingletonTdgGate 2 11 OrderedDict([('u3', 7), ('cx', 6)])
_SingletonTdgGate 3 33 OrderedDict([('u3', 24), ('cx', 20)])
_SingletonTdgGate 4 68 OrderedDict([('u3', 53), ('cx', 44)])
_SingletonTdgGate 5 131 OrderedDict([('u3', 98), ('cx', 84)])
_SingletonTdgGate 6 193 OrderedDict([('u3', 159), ('cx', 140)])
_SingletonTdgGate 7 333 OrderedDict([('u3', 248), ('cx', 220)])
_SingletonTdgGate 8 501 OrderedDict([('u3', 369), ('cx', 324)])
_SingletonTdgGate 9 705 OrderedDict([('u3', 506), ('cx', 444)])
_SingletonTdgGate 10 937 OrderedDict([('u3', 659), ('cx', 580)])
RXGate 1 5 OrderedDict([('u3', 3), ('cx', 2)])
RXGate 2 13 OrderedDict([('cx', 8), ('u3', 7)])
RXGate 3 29 OrderedDict([('cx', 20), ('u3', 15)])
RXGate 4 35 OrderedDict([('u3', 29), ('cx', 24)])
RXGate 5 63 OrderedDict([('u3', 45), ('cx', 40)])
RXGate 6 75 OrderedDict([('u3', 61), ('cx', 56)])
RXGate 7 153 OrderedDict([('u3', 89), ('cx', 80)])
RXGate 8 171 OrderedDict([('u3', 121), ('cx', 104)])
RXGate 9 210 OrderedDict([('u3', 137), ('cx', 120)])
RXGate 10 235 OrderedDict([('u3', 153), ('cx', 136)])
RYGate 1 4 OrderedDict([('u3', 2), ('cx', 2)])
RYGate 2 21 OrderedDict([('u3', 15), ('cx', 12)])
RYGate 3 28 OrderedDict([('cx', 20), ('u3', 14)])
RYGate 4 35 OrderedDict([('u3', 29), ('cx', 24)])
RYGate 5 63 OrderedDict([('u3', 45), ('cx', 40)])
RYGate 6 75 OrderedDict([('u3', 61), ('cx', 56)])
RYGate 7 153 OrderedDict([('u3', 89), ('cx', 80)])
RYGate 8 171 OrderedDict([('u3', 121), ('cx', 104)])
RYGate 9 210 OrderedDict([('u3', 137), ('cx', 120)])
RYGate 10 235 OrderedDict([('u3', 153), ('cx', 136)])
RZGate 1 4 OrderedDict([('u3', 2), ('cx', 2)])
RZGate 2 8 OrderedDict([('cx', 4), ('u3', 4)])
RZGate 3 21 OrderedDict([('u3', 17), ('cx', 14)])
RZGate 4 35 OrderedDict([('u3', 29), ('cx', 24)])
RZGate 5 63 OrderedDict([('u3', 45), ('cx', 40)])
RZGate 6 75 OrderedDict([('u3', 61), ('cx', 56)])
RZGate 7 153 OrderedDict([('u3', 89), ('cx', 80)])
RZGate 8 171 OrderedDict([('u3', 121), ('cx', 104)])
RZGate 9 210 OrderedDict([('u3', 137), ('cx', 120)])
RZGate 10 235 OrderedDict([('u3', 153), ('cx', 136)])
PhaseGate 1 5 OrderedDict([('u3', 3), ('cx', 2)])
PhaseGate 2 12 OrderedDict([('u3', 7), ('cx', 6)])
PhaseGate 3 33 OrderedDict([('u3', 24), ('cx', 20)])
PhaseGate 4 68 OrderedDict([('u3', 53), ('cx', 44)])
PhaseGate 5 131 OrderedDict([('u3', 98), ('cx', 84)])
PhaseGate 6 193 OrderedDict([('u3', 159), ('cx', 140)])
PhaseGate 7 333 OrderedDict([('u3', 248), ('cx', 220)])
PhaseGate 8 501 OrderedDict([('u3', 369), ('cx', 324)])
PhaseGate 9 705 OrderedDict([('u3', 506), ('cx', 444)])
PhaseGate 10 937 OrderedDict([('u3', 659), ('cx', 580)])
U3Gate 1 5 OrderedDict([('u3', 4), ('cx', 2)])
U3Gate 2 43 OrderedDict([('u3', 28), ('cx', 24)])
U3Gate 3 89 OrderedDict([('u3', 61), ('cx', 60)])
U3Gate 4 166 OrderedDict([('u3', 133), ('cx', 112)])
U3Gate 5 313 OrderedDict([('u3', 237), ('cx', 208)])
U3Gate 6 449 OrderedDict([('u3', 372), ('cx', 336)])
U3Gate 7 803 OrderedDict([('u3', 582), ('cx', 520)])
U3Gate 8 1155 OrderedDict([('u3', 857), ('cx', 752)])
U3Gate 9 1598 OrderedDict([('u3', 1147), ('cx', 1008)])
U3Gate 10 2086 OrderedDict([('u3', 1469), ('cx', 1296)])
@ACE07-Sev
Copy link
Author

ACE07-Sev commented Dec 2, 2024 •
edited
Loading

Given the natural difficulty of assessing from the table, I have made the following simple lists for each gate with respect to their depth:

X
[1, 11, 27, 65, 131, 193, 333, 501, 705, 937, 1205, 1501, 1833, 2193, 2589]
Y
[3, 43, 89, 166, 313, 449, 803, 1155, 1598, 2086, 2658, 3274, 3974, 4718, 5546]
Z
[3, 11, 33, 68, 131, 193, 333, 501, 705, 937, 1205, 1501, 1833, 2193, 2589]
H
[3, 35, 81, 158, 305, 441, 795, 1147, 1590, 2078, 2650, 3266, 3966, 4710, 5538]
S
[5, 11, 33, 68, 131, 193, 333, 501, 705, 937, 1205, 1501, 1833, 2193, 2589]
Sdg
[7, 11, 33, 68, 131, 193, 333, 501, 705, 937, 1205, 1501, 1833, 2193, 2589]
T
[5, 11, 33, 68, 131, 193, 333, 501, 705, 937, 1205, 1501, 1833, 2193, 2589]
Tdg
[5, 11, 33, 68, 131, 193, 333, 501, 705, 937, 1205, 1501, 1833, 2193, 2589]
RX
[5, 13, 29, 35, 63, 75, 153, 171, 210, 235, 274, 299, 338, 363, 402]
RY
[4, 21, 28, 35, 63, 75, 153, 171, 210, 235, 274, 299, 338, 363, 402]
RZ
[4, 8, 21, 35, 63, 75, 153, 171, 210, 235, 274, 299, 338, 363, 402]
Phase
[5, 12, 33, 68, 131, 193, 333, 501, 705, 937, 1205, 1501, 1833, 2193, 2589]
U3
[5, 43, 89, 166, 313, 449, 803, 1155, 1598, 2086, 2658, 3274, 3974, 4718, 5546]

As you can see, certain gates, such as MCY, MCH, and MCU3 seem to be overly expensive. Reason for using "overly" is that we can make any gate using ZYZ decomposition. Ergo, we can make any controlled version of them using MCRY, MCRZ, MCRY approach. Now, isn't it odd that all the other gates themselves are much more expensive than the ZYZ approach?

I feel a better decomposition for MCU3 should remedy all of these, and would be consistent with how you utilize U3Gate in the _define of each singleton gate to define these controlled versions. Personally speaking, I am not a fan of explicit decomposition for specific gates as it goes against the abstraction created by MCG. Therefore, I feel this emphasized focus should provide the means to create a factory of sorts for generating efficient decompositions for these controlled gates and should be efficient enough to produce the explicit decompositions as a byproduct.

@ACE07-Sev
Copy link
Author

In conclusion, whilst I am myself working on finding better decompositions, I felt it would be beneficial as Dr. Garrion suggested to mention this to those much more experienced than I in this area.

@ShellyGarion ShellyGarion mentioned this issue Dec 5, 2024
Merged
2 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
synthesis
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@ShellyGarion @ACE07-Sev