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

  • $\begingroup$ It may be helpful to specify how $C$ is defined $\endgroup$
    – epelaaez
    Jun 24, 2021 at 4:25
  • $\begingroup$ Nielsen's Quantum computation and quantum information, chap 5 might be helpful. $\endgroup$
    – narip
    Jun 24, 2021 at 4:47
  • 1
    $\begingroup$ 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> $\endgroup$ Jun 24, 2021 at 9:44

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

  • $\begingroup$ 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. $\endgroup$ Jun 25, 2021 at 1:27
  • $\begingroup$ @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. $\endgroup$ Jun 25, 2021 at 5:27
  • $\begingroup$ 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. $\endgroup$ Jun 25, 2021 at 6:02
  • $\begingroup$ @Cloudwin.ZL It's a uniform superposition where each state is phased by $2 \pi /N$ more radians than the previous one. $\endgroup$ Jun 25, 2021 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.