# Are multi-qubit control RX gates scaling exponentially?

In https://arxiv.org/pdf/quant-ph/0303063.pdf it a method shown for implementing a multi-qubit controlled phase shift gate thath scales exponentially with n.

Are there new methods to implement these gates in polynomial time?

And does anybody know if there is a paper descring the method for impelemnting a multi-qubit controlled gate that Qiskit uses for its MCMT gate? https://qiskit.org/documentation/stubs/qiskit.circuit.library.MCMT.html

An $$n$$-qubit controlled phase gate with error $$\epsilon$$ takes $$O(n + \lg \frac{1}{\epsilon})$$ gates to achieve.
The $$O(n)$$ dependence is easiest to understand in the case where you have $$n$$ ancillae:
The $$O(\lg \frac{1}{\epsilon})$$ dependence is from the need to decompose the single qubit phase rotation into the gateset that is actually supported, e.g. using repeat-until-success circuits.
Only a single ancilla is actually required. And if you're willing to increase the cost to $$O(n \cdot \lg \frac{1}{\epsilon})$$ and use $$n$$ arbitrary single qubit phase rotations instead of one then no ancillae are needed at all.