1
$\begingroup$

In the excellent paper "Step-by-Step HHL Algorithm Walkthough..., https://arxiv.org/abs/2108.09004, it makes a derivation that is not clear to me at all.

In Equation (15) it combines the effect of phase estimation and the inverse QFT into this close form: $$ \frac{1}{2^n} |b\rangle \sum_{y=0}^{2^n-1} \sum_{k=0}^{2^n-1} e^{2 \pi i k(\phi - y/N)} |y\rangle |0\rangle $$ So far so good, this just combines the closed form of QPE with $QFT^{-1}$. Then it says that only $|y\rangle$ for which is $\phi - y/N = 0$ will have an amplitude, all other amplitudes are 0. I know this is correct, because that's how it works during QPE, but I have difficulties deriving this result in this closed form.

In the next step (Equation 16), it further arrives at $|b\rangle |N \phi\rangle |0\rangle$, which is even more unclear to me. I'm not sure I understand what $|N \phi\rangle$ is supposed to mean here?

Any help with a precise derivation (actually step-by-step ;-) would be greatly appreciated.

$\endgroup$

2 Answers 2

1
$\begingroup$

Write \begin{align} \frac{1}{2^n} \sum_{y=0}^{2^n-1} \sum_{k=0}^{2^n-1} e^{2 \pi i k(\phi - y/N)} |y\rangle = \sum_{y=0}^{2^n-1} \left(\frac{1}{2^n} \sum_{k=0}^{2^n-1} e^{2 \pi i k(\phi - y/N)}\right) |y\rangle. \end{align} The stuff in the parentheses is just a coefficient of $|y\rangle$.

Suppose for some $y_0$, we have $\phi - y_0/N = 0$, then the coefficient of $|y_0\rangle$ is $$\left(\frac{1}{2^n} \sum_{k=0}^{2^n-1} e^{2 \pi i k(\phi - y_0/N)}\right) = \left(\frac{1}{2^n} \sum_{k=0}^{2^n-1} e^{2 \pi i k0}\right) = \frac{2^n}{2^n} = 1.$$ Since $\phi - y_0/N =0$, we can solve for $y_0$, \begin{align} \phi - y_0/N &=0\\ \phi &= y_0/N\\ \phi N &= y_0. \end{align} So we have $|y_0 \rangle = |\phi N\rangle$.

Addendum:
Even though this was not part of the question, I added it for completeness.

If $\phi - y/N \neq 0$, then $$\sum_{k=0}^{2^n-1} e^{2 \pi i k(\phi - y/N)} =0.$$ This follows from the geometric series formula: $$1 + \alpha + \alpha^2 + \ldots + \alpha^{n-1} = \begin{cases} \frac{1-\alpha^n}{1-\alpha}, \text{ if } \alpha \neq 1\\ n, \text{ if } \alpha =1 \end{cases}$$ Therefore, if $\phi - y/N \neq 0$, then $\alpha:=e^{2\pi i (\phi - y/N)} \neq 1$. It follows that $$\sum_{k=0}^{2^n-1} e^{2 \pi i k(\phi - y/N)} = \frac{1-e^{2\pi i (\phi - y/N)2^n}}{1-e^{2\pi i (\phi - y/N)}} = 0.$$ This is because we can write $$1-e^{2\pi i (\phi - y/N)2^n} = 1 - (e^{2\pi i 2^n})^{\phi - y/N} = 1 - (1)^{\phi - y/N} = 0.$$

$\endgroup$
4
  • $\begingroup$ Wonderful, Thanks! This explains most of my question. Still not clear why for cases where $\phi - y_0/N \ne 0$, the coefficient would be 0? $\endgroup$ Commented Sep 22, 2024 at 3:25
  • $\begingroup$ Hint: Quantum states have a unit norm. If one of the coefficients is 1, what does it leave for the rest of coefficients? $\endgroup$ Commented Sep 22, 2024 at 3:35
  • $\begingroup$ MonteNero - you rock ;-) (Thanks) $\endgroup$ Commented Sep 22, 2024 at 3:51
  • $\begingroup$ @rhundt, I've added something extra if you are after a more rigorous argument. $\endgroup$ Commented Sep 22, 2024 at 4:19
1
$\begingroup$

I'd just add how an amplitude of $|y \rangle$ behaves over $(\phi - y/N)$.

$ \sum_{k=0}^{2^n-1} e^{2 \pi i k(\phi - y/N)} \tag{1}$

Let $(\phi - y/N)$ be $\alpha$ then $(1)$ can be written as :

$ \sum_{k=0}^{2^n-1} e^{2 \pi i k\alpha} \tag{2}$

When $\alpha$(=$\phi - y/N$) is integer, e.g. 0, an amplitude becomes a finite value. When alpha is not integer an amplitude converges to 0 due to destructive interference. The diagram below shows the result of geometric sum of (2).

n = 6 (qubits) is used in the diagram:

enter image description here

import numpy as np import matplotlib.pyplot as plt n = 6 # num of qubits N = 2**n # N = 2^n alpha_vals = np.linspace(0, 2, 1000) # this is phi - y/N def geom_sum(alpha, N): #import pdb; pdb.set_trace() k = np.arange(N) sum = np.exp(2j * np.pi * k * alpha) # e^(2pi * i * k * alpha) return np.abs(np.sum(sum)) # calculate the sum for each alpha sums = [geom_sum(alpha, N) for alpha in alpha_vals] # Plot the results plt.figure(figsize=(10, 6)) plt.plot(alpha_vals, sums, label=f'Sum with N={N}') plt.axhline(y=N, color='r', linestyle='--', label='Constructive Interference (alpha integer)') plt.xlabel('Alpha (α)') plt.ylabel('|Sum|') plt.title('Behavior of the Sum for Non-integer and Integer alpha') plt.legend() plt.grid(True) plt.show() 
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.