Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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.
