Better decomposition for multi-controlled 1-qubit gates #13514
Description
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)]) |