Computing $e^{i\phi Z}$ in polynomial time

Question

A lot of papers and algorithms make use of phase shift unitaries such as $\exp(i \phi Z)$ (see, e.g., Quantum Fourier Transform). But is that really a thing that you can compute in polynomial time? I can understand that it is physically implementable by other means (e.g., letting an Hamiltonian evolve for a precise amount of time), but this solution doesn't really satisfy me from a complexity theory point of view.

Edit: let me give an example on the QFT. The QFT algorithm uses gates $$ \exp\left(i \frac{2\pi}{2^d} Z\right) $$

where $d = 1, \ldots, n$ where $n$ is the number of qubits (i.e. $N = 2^n$ is the period of the FT). This clearly depends on the size of the input $n$.

Answer 1

"From a complexity theoretic point of view" possibly needs a little more careful definition. If you're talking about complexity theory, then you're thinking about the scaling of circuit size with respect to the size of an input parameter. But how do you measure circuit size? You need a base set of gates from which everything is constructed. That might include $\exp(i\phi Z)$, in which case there's no question!

This, then, is where the concept of universality comes in - that any two universal gate sets can approximate each other (up to arbitrary accuracy) with only finite overhead.

Thus, perhaps the gate set you're thinking about is controlled-not + Hadamard + T. It's enough to know that there are gate synthesis algorithms that can decompose any single qubit unitary to accuracy $\epsilon$ in $O(\log\frac{1}{\epsilon})$ gates. So, any circuit you write initially using $\exp(i\phi Z)$ can be converted into one using that gate set and it does not affect the behaviour of the scaling, only the precise coefficients. In other words, polynomial time versus super-polynomial is not affected.

Answer 2

Your question concerns one of the most important issues regarding the feasibility of fault-tolerant quantum computation: How can we implement arbitrary unitary operations with a finite set of basis gates? The answer to this question is provided by the Solovay-Kitaev theorem, which states that, for any single-qubit operation $U \in SU(2)$, there is a sequence $S$ of length $\mathcal{O}(\log^c(1/\epsilon))$ of gates from a particular kind of finite set (e.g., $\{ H, T\}$) that approximates $U$ to error $\epsilon$, $||S-U|| \leq \epsilon$.

Fault-tolerant quantum computation is only possible if the number of basis gates is finite. As you rightly point out, we cannot rely on gates defined in terms of continuous parameters such as those resulting from the time-evolution under some Hamiltonian over some arbitrary duration, as these operations would not allow for quantum error correction. This PRX Quantum Perspective paper by Ivan Deutsch discusses this point very clearly.

Incidentally, the problem of reducing the number of T gates (or T-count, for short) in the implementation of the quantum Fourier transform is an active field of research precisely because of these $R_z$ rotations over tiny angles (cf., e.g., this paper by Nam, Su and Maslov).