Decompose CnXGate grows exponentially in terms of CX, instead of linear

[1ucian0]

@anedumla noticed that theorem 5 in https://arxiv.org/abs/1501.06911 bounds the amount of CNOTs needed to decompose a SU(2) gate when (n-1)-controlled.

The bound of resulting CNOTs in the decomposition grows linearly with respect to the amount of controlled qubits. However, the decomposition of MCX groups exponentially:

number_of_qubits = []
result = []
boundery = []
for k in range(1, 10):
    n = k+1
    circuit = QuantumCircuit(k+1)
    circuit.append(XGate().control(k), list(range(k+1)))
    unroller = Unroller(basis_gates)
    qc = unroller(circuit)
    number_of_qubits.append(n)
    result.append(qc.count_ops()['cx'])
    boundery.append(28*n-88)

What is the expected enhancement?

A non-ancilla decomposition of QuantumCircuit.mcx() should result in a linear amount of CNOTs. https://arxiv.org/abs/1501.06911 refers to https://arxiv.org/abs/quant-ph/9503016 for calculating A-B-C, that can be precomputed.

In it's generic form, Theorem 5 can be applied any multi-controlled-W, where W \in SU(2). Therefore, I assume is can be generalised to fix the example #5840 by creating a possible decomposition.

[anedumla]

How to decompose a gate in SU(2) into A, B, C : https://arxiv.org/abs/quant-ph/9503016

From Lemma 4.1., every element of SU(2) can be expressed as

Then, from the proof of Lemma 4.3.:

[georgios-ts]

For a general unitary, not in SU(2), (i.e X gate) Theorem 4[1] seems to be applicable that gives a CNOT count that scales quadratic. According to the upper bound they give, it's beneficial to use their scheme only when n > 10. (however the bound they give seems not to be tight and i can think it can be improved).

Even ancilla decompositions of mcx can be proved (according to section 1 of the appendix A[1]) when:

• mode=recursion. Current implementation uses 1 ancilla and has exponential CNOT count. With one ancilla qubit, it can be done with linear cost (16n - 40) (n: total no. of qubits)
• mode=v-chain-dirty. Current implementation uses (12k - 22) CNOTs (k: no. of controls). It can be reduced to (8k - 6) that is better for k > 4.

Can i work on this?

[1] https://arxiv.org/pdf/1501.06911.pdf

[1ucian0]

Can i work on this?

Sure!

[1ucian0]

Hi @georgios-ts ! Any news?

[1ucian0]

I'm cleaning the assignees so it can be back to the pool of available short projects.

[adjs]

Hi @1ucian0 ,

Can I work on this?

[1ucian0]

Sounds good! @mtreinish should a synthesis interface be used for this?

[adjs]

Hi @1ucian0 ,

We have been working on this issue. Instead of using theorem 5 in https://arxiv.org/abs/1501.06911 , this issue motivated us to develop a new decomposition that requires a smaller number of gates for SU(2) multi-controlled gates https://arxiv.org/abs/2302.06377. PR #8710 is the first step to solve this issue and reduces the number of gates in the MCXRecursive (that now is not recursive).

[jakelishman]

@AlexisRalli: this issue and all the PRs that link to it above are what I was trying to find when you asked me about them the other day. For others' reference: Alexis had also had some ideas about the generalised MCU constructions (see #9574 for one part, but I think he had more in the works as well), who I then told @alexanderivrii and @ShellyGarion about.

I don't have much to contribute myself to the discussion, just trying to link up all the folks I know about working on this, or things adjacent to this.

[adjs]

Thanks @jakelishman,

We intend to contribute with an n-qubit multi-controlled su(2) decomposition that requires ~16n cx if the gate has one real diagonal and ~20n for any other su2 gate.

[adjs]

Hi everyone,

I am reporting what we have done up until now about this issue.

We found some problems that need a fix concerning multi-controlled gates: multi-controlled rotations grow exponentially #9741; MCXVChain with dirty ancilla not optimal #9740; and MCXRecursive not optimal #9743.

We fixed the MCXVChain with dirty auxiliary qubits #9687 and the MCXRecursive #8710. We also fixed mcry and mcrx #9688. There is a conflict PR about multi-controlled rotations #9574. However, #9688 produces circuits with fewer cx gates because it implements our recent work about su(2) multi-controlled gates.

We did not fix mcrz because the actual implementation of mcrz applies an mcp gate (not su(2)) #9202. I do not know if we should open a PR with a fix to mcrz because this will impact several test cases and other users.

We would also like to contribute to #7505.

[ewinston]

@adjs On the mcrz implementation, I think your approach demonstrated in #9688 is probably preferable since it seems to scale better. Could you make another PR for that? That PR may need to go through a deprecation cycle in case other users are already working around the issue.

[adjs]

@ewinston. PR #9836 fix the mcrz. However it breaks backward compatibility tests. It is also necessary to include the multiplexer with a small number of control qubits as in #9574.

[ShellyGarion]

@adjs @rafaella-vale - I looked again at your PRs #9688 and #9836.
It seems that the code for linear number of cx gates only works for multi-controlled rotation gates mcrx, mcry, mcrz and not for mcx or mcp, for which the decomposition still grows exponentially in the number of cx gates.
Do you know how your code could be extended to include mcx or mcp?

for num_controls in range(3, 20, 2):
    q_controls = QuantumRegister(num_controls)
    q_target = QuantumRegister(1)
    qc = QuantumCircuit(q_controls, q_target)

    qc.mcx(q_controls, q_target[0])
    cqc = transpile(qc, basis_gates=['u', 'cx'])
    
    qc1 = QuantumCircuit(q_controls, q_target)
    qc1.mcrx(np.pi, q_controls, q_target[0], use_basis_gates=True)
    cqc1 = transpile(qc1, basis_gates=['u', 'cx'])
    print("num controls=", num_controls, "cx count in mcx:", cqc.count_ops()['cx'], "cx count in mcrx:", cqc1.count_ops()['cx']

gives:

num controls= 3 cx count in mcx: 14 cx count in mcrx: 20
num controls= 5 cx count in mcx: 92 cx count in mcrx: 40
num controls= 7 cx count in mcx: 380 cx count in mcrx: 80
num controls= 9 cx count in mcx: 1532 cx count in mcrx: 128
num controls= 11 cx count in mcx: 6140 cx count in mcrx: 176
num controls= 13 cx count in mcx: 24572 cx count in mcrx: 224
num controls= 15 cx count in mcx: 98300 cx count in mcrx: 272
num controls= 17 cx count in mcx: 393212 cx count in mcrx: 320
num controls= 19 cx count in mcx: 1572860 cx count in mcrx: 368

[ShellyGarion]

@adjs @rafaella-vale - according to your paper [1] and to the function _mcsu2_real_diagonal, this function should decompose any multi-controlled SU(2) gate with a real main diagonal or secondary diagonal, hence it should also be able to decompose mcx and mcp gates (*).

[1] https://arxiv.org/abs/2302.06377

However, this decomposition does not work properly, since it does not provide the expected operator:

from qiskit.circuit.library.standard_gates import multi_control_rotation_gates as mcrg 
for num_controls in range(3, 10, 2):
    qc = mcrg._mcsu2_real_diagonal(XGate().to_matrix(), num_controls, use_basis_gates=True)
    qc1 = QuantumCircuit(num_controls+1)
    qc1.mcx(list(range(num_controls)), num_controls)
    
    print (np.allclose(Operator(qc).to_matrix(), Operator(qc1).to_matrix() ))
    print (Operator(qc).equiv(Operator(qc1)))

gives False and False.
It also does not work for PhaseGate() and mcp.
But the same code seems to work for the pairs: RXGate() and mcrx, RYGate() and mcry, RZGate() and mcrz.

Moreover,

num_controls = 2
qc = mcrg._mcsu2_real_diagonal(XGate().to_matrix(), num_controls, use_basis_gates=True)
(Operator(qc).to_matrix()).round(decimals=0)

produces a wrong matrix for the Toffoli gate (in the last line it should be 1 and not -1):

array([[ 1.+0.j,  0.+0.j,  0.+0.j,  0.+0.j,  0.+0.j,  0.+0.j,  0.+0.j, 0.+0.j],
       [ 0.+0.j,  1.+0.j,  0.+0.j,  0.+0.j,  0.+0.j,  0.+0.j,  0.+0.j, 0.+0.j],
       [ 0.+0.j,  0.+0.j,  1.+0.j,  0.+0.j,  0.+0.j,  0.+0.j, -0.-0.j, 0.+0.j],
       [ 0.+0.j,  0.+0.j,  0.+0.j, -0.-0.j,  0.+0.j,  0.+0.j,  0.+0.j, 1.+0.j],
       [ 0.+0.j,  0.+0.j,  0.+0.j,  0.+0.j,  1.+0.j,  0.+0.j,  0.+0.j, 0.+0.j],
       [ 0.+0.j,  0.+0.j,  0.+0.j,  0.+0.j,  0.+0.j,  1.+0.j,  0.+0.j, 0.+0.j],
       [ 0.+0.j,  0.+0.j,  0.-0.j,  0.+0.j,  0.+0.j,  0.+0.j,  1.+0.j, 0.+0.j],
       [ 0.+0.j,  0.+0.j,  0.+0.j, -1.-0.j,  0.+0.j,  0.+0.j,  0.+0.j, 0.+0.j]])

(*) Actually x and p are not in SU(2) since their determinant is not 1. However, I would expect that the function _mcsu2_real_diagonal will check it and raise a QiskitError in this case.

[ShellyGarion]

Another synthesis method for MCX gates: if we also allow ancillas, then I think that the best method appears here:
https://arxiv.org/abs/1508.03273

[adjs]

Another synthesis method for MCX gates: if we also allow ancillas, then I think that the best method appears here: https://arxiv.org/abs/1508.03273

Hi @ShellyGarion, in this PR #9687 the mcx requires 8k-6 cnots (and k-2 ancillary qubits) to implement a k-controlled mcx. PR #8710 improves the number of cx gates with one auxiliary qubit (lemma 9 of https://arxiv.org/pdf/1501.06911.pdf).

It is also possible to decompose a multi controlled U(2) gate with linear circuit depth [1] and also with linear circuit size if we allow an approximation [2] .

[1] https://journals.aps.org/pra/abstract/10.1103/PhysRevA.106.042602
[2] https://arxiv.org/abs/2310.14974

[adjs]

The approximated multi controlled U(2) without ancillary qubits is implemented in qclib.

pip install qclib

import numpy as np
import qiskit
from qiskit.quantum_info import Operator
from qclib.gates.mcu import MCU

tol = 10**-2
n_controls = 11
X = np.array([[0, 1], [1, 0]])
qc = qiskit.QuantumCircuit(n_controls)
MCU.mcu(qc, X, list(range(n_controls-1)), n_controls-1, tol)
tqc = qiskit.transpile(qc, basis_gates=['u', 'cx'])

print('mcu # operations', tqc.count_ops())


qiskit_circuit = qiskit.QuantumCircuit(n_controls)
qiskit_circuit.mcx(list(range(n_controls-1)), n_controls-1)
qiskit_circuit.draw()

t_qiskit_circuit = qiskit.transpile(qiskit_circuit, basis_gates=['u', 'cx'])
print('qiskit # operations', t_qiskit_circuit.count_ops())

qc_matrix = Operator(qc).to_matrix()
qiskit_matrix = Operator(qiskit_circuit).to_matrix()

print(np.allclose(qc_matrix, qiskit_matrix, atol=tol))

will return

mcu # operations OrderedDict([('u', 395), ('cx', 360)])
qiskit # operations OrderedDict([('u', 3070), ('cx', 3068)])
True

[ShellyGarion]

It is also possible to decompose a multi controlled U(2) gate with linear circuit depth [1] and also with linear circuit size if we allow an approximation [2] .

[1] https://journals.aps.org/pra/abstract/10.1103/PhysRevA.106.042602
[2] https://arxiv.org/abs/2310.14974

Thank you @adjs for referring us to your recent manuscripts [1] and [2]. Would you be interested in contributing the code to Qiskit?

[adjs]

It is also possible to decompose a multi controlled U(2) gate with linear circuit depth [1] and also with linear circuit size if we allow an approximation [2] .
[1] https://journals.aps.org/pra/abstract/10.1103/PhysRevA.106.042602
[2] https://arxiv.org/abs/2310.14974

Thank you @adjs for referring us to your recent manuscripts [1] and [2]. Would you be interested in contributing the code to Qiskit?

@thiagom123 and @JeffersonDeyvis can you implement approximate multi-controlled gate in qiskit?

[ShellyGarion]

The primary focus of this issue is to decompose an MCXGate() using non-exponential number of CX gates, without using ancillas, thus fixing #11823. This is done in #11993.

However, I prefer to keep this issue open, as it discusses many algorithms to decompose an MCXGate() with various numbers of ancillas that can be contributed to Qiskit (some of them still have open PRs).

[ShellyGarion]

I am very happy to finally close this issue as all the PRs mentioned here have finally been merged!
I would like to thank @adjs and everyone who contributed to this enormous effort!
Feel free to open new issues and PRs with further synthesis algorithms for MCX with or without ancilla qubits if you think that they may be better than the current code.