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


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.