Take two registers.
Regsiter 1 contains $t$ Qubits in state $\ket{0}$.
- $t$ is chosen based on two criterias:
-
Number of accurate digits with which $\theta$ is to be estimated:
i.e. $\theta = 0.\theta_1\theta_2\dots\theta_t$
-
(Normally, accuracy is acheived up to $n \le t$) The probability with which the method is to be successful:
To obtain $\theta$ accurate to n-bits (prior to measurement) with probability of success $\ge (1 - \epsilon)$
$t = n + \lceil{log(2 + \frac{1}{2\epsilon})}\rceil$
Probability of success is $\ge 1 - \epsilon = 1 - \large \frac{1}{2(2^{t-n} - 1)}$
-
Register 2 is intialized with $\ket{\psi}$ having as many Qubits as required to store $\ket{\psi}$.
The overall circuit implementation consists of the 3 steps as illustrated below:
Stage 1 : Hadamard on all qubits of first register followed by controlled (by state in second register) unitary $U^{2^j}$ operations on qubit $j$.
Stage 2 : Inverse Quantum Fourier Transform on the first qubit register.
Stage 3 : Measurement on each qubit of first register
We shall now discuss all stages one by one:
STAGE 1 (Phase Kickback Circuit)
- Pre-requisite
applying the Hadamard gates on register 1:
$\ket{\psi_1} = (H\ket{0})^{\otimes t} = \left (\large \frac{\ket{0} + \ket{1}}{\sqrt{2}} \right)^{\otimes t}$
now, applying the controlled (by state in second register) unitary $U^{2^j}$ operations on qubit $j$, we have:
$\ket{\psi_1}\ket{\psi} = \otimes_{j=0}^{t-1}\left (\large \frac{\ket{0} + \ket{1}}{\sqrt{2}} \right)U^{2^j}\ket{\psi}$
using the result we derived at the start of this stage, we obtain:
$\ket{\psi_1}\ket{\psi} = \otimes_{j=0}^{t-1}\left (\large \frac{\ket{0} + e^{2^j * 2\pi i\theta}\ket{1}}{\sqrt{2}} \right)\ket{\psi}$
⇒ $\boxed{\ket{\psi_1} = \large \frac{1}{\sqrt{2^t}}\normalsize\otimes_{j=0}^{t-1}(\ket{0} + e^{2^{j} * 2\pi i\theta}\ket{1})}$ // Stage 1 Output Eqn 1
now, taking $k$ to denote the integer representation of $n$-bit binary numbers (intuition: sum of geometric progression), we can rewrite the above equation as:
⇒ $\boxed{\ket{\psi_1} = \large \frac{1}{\sqrt{2^t}}\normalsize\sum_{k=0}^{2^n-1}(e^{2\pi i\theta k}\ket{k})}$ // Stage 1 Output Eqn 2
- Another simplification:
Substituting this in our obtained result, we get:
⇒ $\ket{\psi_1} = \large \frac{1}{\sqrt{2^t}}\normalsize\otimes_{k=0}^{t-1}(\ket{0} + e^{2\pi i(0.\theta_{k+1}\dots\theta_{t})}\ket{1})$
STAGE 2
hmm, this output looks same as what we obtain post applying Quantum Fourier Transform !.
- Inverse Quantum Fourier Transform
Notice now, that the obtained representation for the first qubit register can be re-written in terms of:
$k_x = \Large\frac{1}{\sqrt{2}}\normalsize(\ket{0} + e^{2i\pi[0.\theta_{t-x}\dots j\theta_{t-1}]})$ //synonymous to what we discussed
as:
$\ket{\psi_1} = \ket{k_{t-1}k_{t-2}\dots k_0}$
which, then upon applying Inverse Quantum Fourier Transform will give us:
$\boxed{FT^\dagger\ket{k_{t-1}k_{t-2}\dots k_0} = \ket{\theta_1\theta_2\dots \theta_t}}$
let’s now actually apply the transform on our Stage 1 Output Equation 2:
$FT^\dagger\ket{\psi_1} = \left(\frac{1}{\sqrt{2^t}}\sum_{j,\widetilde{\theta} = 0}^{2^t - 1}\large e^{\frac{-2\pi i}{2^n}j.\widetilde{\theta}}\normalsize\ket{\widetilde{\theta}}\bra{j}\right)\left(\large \frac{1}{\sqrt{2^t}}\normalsize\sum_{j=0}^{2^n-1}(e^{2\pi i\theta j}\ket{j})\right)$
$= \frac{1}{2^t}\sum_{j,\widetilde{\theta} = 0}^{2^t - 1}\large e^{\frac{-2\pi i}{2^n}j.\widetilde{\theta} + 2\pi i \theta j}\normalsize\ket{\widetilde{\theta}}$
$= \boxed{\frac{1}{2^t}\sum_{j,\widetilde{\theta} = 0}^{2^t - 1}\large e^{ 2\pi ij(\theta - \frac{\widetilde{\theta}}{2^t})}\normalsize\ket{\widetilde{\theta}}}$
Notice that, the probability of measuring a given $\widetilde{\theta}$ as output is given by:
$\boxed{p_{\widetilde{\theta}} = \frac{1}{2^{2t}}\left|\sum_{j,\widetilde{\theta} = 0}^{2^t - 1}\large e^{ 2\pi ij(\theta - \frac{\widetilde{\theta}}{2^t})}\normalsize\right|^2}$
Finally, we can write that the probability of measuring $\theta$ accurate upto $n$ $(n \lt t)$ bits after completion of Phase estimation algorithm (post measurement):
$\ge p_{\widetilde{\theta}}(1 - \epsilon)$
$= \frac{1}{2^{2t}}\left|\sum_{j,\widetilde{\theta} = 0}^{2^t - 1}\large e^{ 2\pi ij(\theta - \frac{\widetilde{\theta}}{2^t})}\normalsize\right|^2 \left(1 - \large \frac{1}{2(2^{t-n} - 1)}\right)$
$= 0.4\left(1 - \large \frac{1}{2(2^{t-n} - 1)}\right)$
<aside> 📌 Note:
-
To obtain (pre-measurement) $\theta$ accurate to n-bits with probability of success $\ge (1 - \epsilon)$ is based on the appropriate choice of $t$:
$t = n + \lceil{log(2 + \frac{1}{2\epsilon})}\rceil$
-
On the other hand, the probability of measuring $\theta$ accurate upto $n$ $(n \lt t)$ bits after completion of Phase estimation algorithm (post measurement) is given by:
$0.4\left(1 - \large \frac{1}{2(2^{t-n} - 1)}\right)$
</aside>
CIRCUIT FOR INVERSE FOURIER TRANSFORM
As, we have discussed above, the inputs to our “Inverse Fourier Transform” Section of the circuit are of the form (number of accurate digits we wish to estimate = $t$):
$\ket{\psi_1} = \ket{k_{t-1}k_{t-2}\dots k_0}$
where,
$k_x = \Large\frac{1}{\sqrt{2}}\normalsize(\ket{0} + e^{2i\pi[0.\theta_{t-x}\dots j\theta_{t-1}]})$
Here, $R_t^\dagger$ is given by:
$R_t^\dagger = \begin{pmatrix}1 & 0 \\ 0 & e^{\frac{-2\pi i}{2^t}}\end{pmatrix} = \begin{pmatrix}1 & 0 \\ 0 & e^{-2\pi i * 10^{-t}}\end{pmatrix}$ //binary decimal representation
Following up, we shall look at a detailed case of the Quantum Fourier Circuit, given:
- $t=3$