The *fractional binary* representation makes a comeback for the QPE subroutine to depict the phase. For $n$ estimation wires, we have $n$ bits of precision $$ \theta = 0.\theta_1 \theta_2 \cdots \theta_n = \sum_{k=1}^n \frac{\theta_k}{2^k}, $$ where each $\theta_k$ can take a value of $0$ or $1$. Since we are discussing unitary operators having eigenvalues with a magnitude of 1, the phase angle will be between 0 and 1 and thus can be expressed in this representation. For example, a phase angle of $0.111$ represents the decimal value $$ \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} = 0.875. $$

Note.

Using fractional binary, we can only represent a certain set of numbers since we are limited to zeros and ones. What about decimal fractions like $0.\overline{3}$? This is what usually gives us rounding errors on classical compilers or interpreters and is why floating point arithmetic is such a big deal! In this node, we will first only consider phase angles that have an exact $t$-bit binary expansion. In later nodes, we will generalize the algorithm to phase angles for which this is not the case.

--- ***Exercise P.2.1.*** Prove that the *fractional binary* number $$ \theta = 0.\theta_1\theta_2 \cdots \theta_n $$ can only have a value between 0 and 1, i.e., $0 \leq \theta \leq 1$.

Solution.

The lowest number we can have is $\theta = 0.0 = 0$, which establishes the lower limit of the binary fraction. The highest number we can have is the infinitely repeating binary fraction, $0.\overline{1}$. For $n$ repetitions, $$ \theta = \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \cdots \frac{1}{2^n} = 1 - \frac{1}{2^n} $$ As $n \rightarrow \infty$, $\theta = 1$ which is the upper limit of the binary fraction, proving that $\theta \in [0, 1]$. ▢

--- For this node, we discuss the ideal case and assume the phase that we calculate can be written exactly with a $t$-bit binary expansion. We'll start with an example where the phase angle can be represented with two bits, i.e., $\theta = 0.\theta_1 \theta_2$. Applying $U$ to its eigenvector $\left\lvert \psi \right\rangle$ with eigenphase $\theta$ gives $$ U \vert \psi \rangle = e^ {2 \pi i \theta} \vert \psi \rangle = e^ {2 \pi i 0.\theta_1\theta_2} \vert \psi \rangle. $$ Let's see what happens when we apply $U$ multiple times to $\vert \psi \rangle$. --- ***Exercise P.2.2.*** Show that $$ U^2 \vert \psi \rangle = \exp {\left[2 \pi i 0.\theta_2 \right]} \vert\psi \rangle $$

Solution.

Applying $U$ once to the state $\vert \psi \rangle$, $$ U \vert \psi \rangle = \exp {\left[ 2 \pi i 0.\theta_1\theta_2 \right]} \vert \psi \rangle. $$ Applying $U$ another time, $$ \begin{align} U^2 \vert \psi \rangle &= U (\exp {\left[2 \pi i 0.\theta_1\theta_2\right]} \vert \psi \rangle) \\ &= \exp {\left[2 \pi i 0.\theta_1\theta_2\right]}\exp {\left[2 \pi i 0.\theta_1\theta_2\right]} \vert \psi \rangle \\ &= \exp {\left[2 \pi i 2(0.\theta_1\theta_2) \right]} \vert \psi \rangle \tag{1} \label{eq:fracbin} \end{align} $$ Expanding $2(0.\theta_1\theta_2)$, we get $$ \begin{align} 2(0.\theta_1\theta_2) &= 2 \left( \frac{\theta_1}{2} + \frac{\theta_2}{2^2}\right) \\ &= \theta_1 + \frac{\theta_1}{2} \\ &= \theta_1 + 0.\theta_2 \\ &= \theta_1.\theta_2 \end{align} $$ Note that $\theta_1 + 0.\theta_2$ makes $\theta_1$ the integral part and $0.\theta_2$ the fractional part of the number $\theta_1.\theta_2$ essentially meaning that the decimal point has moved one place to the right. Substituting this back in Eq.($\ref{eq:fracbin}$), $$ \begin{align} U^2 \vert \psi \rangle &= \exp {\left[2 \pi i 2(0.\theta_1\theta_2) \right]} \vert \psi \rangle \\ &= \exp {\left[2 \pi i (\theta_1 + 0.\theta_2)\right]} \vert \psi \rangle \\ \end{align} $$ Since $\theta_1$ is a binary integer $ \exp {\left[2 \pi i \theta_1\right]} = 1$, and therefore $$ \begin{align} U^2 \vert \psi \rangle &= \exp {\left[2 \pi i 0.\theta_2\right]} \vert \psi \rangle . \end{align} $$

▢

--- This is very similar to multiplication in base 10, where multiplying a number by 10 moves the decimal point one place to the right. The same is true for binary as well: multiplying a binary number by 2 moves the decimal point one place to the right! In this case, since this happens in the exponent, $e^{2 \pi i \theta_1}$ can be only 1 for $\theta_1 = 0$ or $1$. Logically, it follows that applying $U$ $2^2 = 4$ times would move the decimal place two places to the right (if you wonder "why not apply $U$ three times?", think about this in base 10, to move a decimal point two places to the right, you would multiply by $10^2 = 100$, and not $30$). This is where the $2^k$ in $U^{2^k}$ comes from! A phase with $t$ bit precision can be written as follows, $$ \theta = 0.\theta_1\theta_2 \cdots\theta_t. $$ By applying $U$ $2^k$ times, we are moving $k$ decimal places to the right, thereby giving us $$ \begin{align} U^{2^k} \vert \psi \rangle &= \exp {\left[2 \pi i \theta_1\theta_2\cdots\theta_k.\theta_{k+1} \cdots \theta_t \right]} \vert \psi \rangle, \\ &= \exp {\left[2 \pi i 0.\theta_{k+1} \cdots \theta_t \right]} \vert \psi \rangle. \tag{2} \label{eq:movingplaces} \end{align} $$ Moving the decimal places to the right to *somehow* extract bits of the phase into the qubits is the central idea behind QPE.

Codercise P.2.1 - Powers of U

Codercise P.2.2 - Controlled powers of U

Codercise P.2.3 - The full QPE circuit

Codercise P.2.4 - Computing the phase

Codercise P.2.5 - QPE in PennyLane

The phase estimation circuit

t-bit binary phases

Extracting the phase