Rephase gate in implementaion of QFT of arbitray size

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⟩$$

• It may be helpful to specify how $C$ is defined Jun 24, 2021 at 4:25
• Nielsen's Quantum computation and quantum information, chap 5 might be helpful. Jun 24, 2021 at 4:47
• I am sorry for the confusion made. C here means |a> is used as the control qubit to decide whether P should be applied to |b> Jun 24, 2021 at 9:44

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$$.

• What if 2^k is not divisible by N for all k? The reason why I am looking for implementation of exact size of QFT, is to consider the case when N is not the power of 2. Jun 25, 2021 at 1:27
• @Cloudwin.ZL That's why $g$ is padded. The maximum chance of observing an error goes down exponentially with the amount of padding you add to $g$, even for values of $N$ that are not powers of 2. Jun 25, 2021 at 5:27
• I am still confused about what g looks like ... Can you specify the definition of "offset"? How does applying Z gate making g in the Zalka's coset representation? And, what "multiply-accumulation operation" do you refer to? Appreiate your answer. Jun 25, 2021 at 6:02
• @Cloudwin.ZL It's a uniform superposition where each state is phased by $2 \pi /N$ more radians than the previous one. Jun 25, 2021 at 17:40