Rephase gate in implementaion of QFT of arbitray size

Question

Talking about how exact size of QFT is achieved, both paper 1 and paper 2 skipped the implementation of gate $U$ that can do:

$$U|\alpha, \beta⟩ \mapsto exp\left(\frac{i2\pi}{N} \alpha\beta\right)|\alpha, \beta⟩$$

for arbitrary $N$ and arbitrary $\alpha,\beta \in \left\{0,..., 2^n-1\right\}$ (they believe this gate is easy).

Here is how I implement it:

I use the fact that $\text{CONTROL}-P(\theta)|a, b⟩\mapsto e^{i\theta a b}|a, b⟩$ , where $P(\theta)=\begin{pmatrix} 1 & 0 \\ 0 & e^{i\theta} \end{pmatrix}$ and $a,b\in \left\{0, 1\right\}$. Then,

$$ \begin{align} exp&\left(\frac{i2\pi}{N} \alpha\beta\right)|\alpha, \beta⟩ \\ &=exp\left(\frac{i2\pi}{N} \sum_{i,j} 2^{i+j} \alpha_i \beta_j\right)|\alpha_0...\alpha_{n-1} , \beta_0...\beta_{n-1}⟩ \\ &=\bigotimes_{i, j} exp\left(\frac{i2\pi}{N}2^{i+j}\alpha_i \beta_j\right)|\alpha_i, \beta_j⟩ \\ &=\bigotimes_{i, j} \text{CONTROL}-P(\phi_{ij})|\alpha_i, \beta_j⟩, \text{ where } \phi_{ij}=\frac{2\pi}{N}2^{i+j}. \end{align} $$

Therefore, I apply $\text{CONTROL}-P(\theta)$ to $|\alpha_i, \beta_j⟩$ $\forall$ $i,j\in\left\{0,..., n-1\right\}$ and hence complete implementation of gate $U$.

Is this implementaion about $U$ correct?

Or more specficially, how do we achieve the operation $|x, \Phi_0⟩\mapsto|x, \Phi_x⟩$？ Here $$ |\Phi_n⟩=\text{QFT} |n⟩=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}exp(\frac{i2\pi}{N}nk)|k⟩ $$

Answer 1

cphase accumulation construction

Apply a CPHASE to each bit pair. This has T cost $O(n^2 \log(1/\epsilon))$.

def prod_mod_phase(a, b, modulus):
    for q1 in range(len(a)):
        for q2 in range(len(b)):
            CPHASE(a[q1], b[q2], theta=(q1 * q2 % modulus) / modulus * 2 * pi)

I think this might be what you're describing in your question. It's hard to tell because you don't define $C$.

amortized phase gradient state construction

It's possible to amortize the error tolerance term $\log(1/\epsilon)$ over many operations, so that the amortized T cost of the gradient operation is $O(n^2 + \text{[tedious negligible stuff]}/m)$ where $m$ is the number of applications you're amortizing over and the constant factors hiding behind the $O$ notation are quite low.

1. Prepare an $n+O(\log(m/\epsilon))$ qubit register $g$ with all qubits in the $|+\rangle$ state. Then apply $Z^{2^k/N}$ to the position at offset $k$ in the register, for each offset $k$. $g$ is now a modular phase gradient state that has been encoded into Zalka's coset representation. I call it a phase gradient state because you can use it to perform phase gradient operations. The coset representation allows you to use non-modular operations on the register and have them behave almost exactly like modular operations. The amount of padding $O(\log(m/\epsilon))$ is chosen to ensure you can use the state $m$ times while still meeting your desired error tolerance $\epsilon$.

2. You can now apply $|a,b\rangle \rightarrow e^{\frac{ab}{N} i\theta} |a,b\rangle$ via phase kickback by using a multiply-accumulation operation $g \mathrel{-}= a \cdot b$.