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
For Quantum Phase Estimation, we need a Unitary Matrix $ U $ such that
$$ U~|\psi\rangle = e^{2 \pi i \theta}~|\psi\rangle $$
Using QPE, we can find the phase $\theta$.
My question is about the size of the Unitary $U$. What if the size of the matrix $U$ is not a power of 2? Will QPE still work??
Much of the magic of the discrete Fourier transform, be it classical or quantum, lies in the fact that a large $N\times N$ matrix can be factored into a tensor product of $\mathcal{O}(\log N)$ smaller matrices. This much was worked out by Cooley and Tukey back in the 60's, with antecedents even earlier going back to Gauss.
Perhaps it's best to think of the QFT as a tensor product of $n$ single-qubit ($d=2$) gates - thus the size of the matrix is $2^n\times 2^n$. The radix of $2$ is convenient and not required. For example one can also think of a tensor product of $n$ qutrit ($d=3$) gates, in which case the matrix is $3^n\times 3^n$, or any other qudit gates. Indeed, Shor's original algorithm used a mixed-radix Fourier transform - this was quickly improved to the familiar form we see today.
But perhaps you're asking whether the input vector itself, $|\psi\rangle$, needs to be a power of two. Thinking about the (classical) Fast Fourier Transform of a dataset that is not a power of two, this is addressed with "zero-padding" the input data set to the next nearest power of two. This link may be helpful. Thus you can always zero-pad your vector $|\psi\rangle$ to be a power of two. But, the computational costs associated with this padding may not be trivial.
In more general terms, quantum phase estimation will be the task of estimating the action of any unitary $U = e^{-iA\theta}$ for a parameter $\theta$ that we want to know and any Hermitian operator $A$.
There is no restriction on the form/size of the unitary besides encoding the parameter $\theta$ in the evolution according to the Stones Theorem. Quantum Parameter Estimation will work; different protocols will be less/more efficient and use different nonclassical resources for such.
Remark: Other assumptions may be relevant for non-triviality, given protocol, etc., for instance it is also relevant that "$A$ is not totally degenerate, in case all eigenvalues of $A$ are identical the unitary would not imprint the parameter onto the state in a relative phase." A bit before Eq. 4.
