Basis Encoding

1. 1
   Step 1:

   $$n=1:\quad X^0\lvert0\rangle=\lvert0\rangle=\begin{pmatrix}1\\0\end{pmatrix}=e_0,\qquad X^1\lvert0\rangle=\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}0\\1\end{pmatrix}=\lvert1\rangle=e_1$$

   Base case: for one qubit $k(x_0)=x_0$, and $X\lvert0\rangle=\lvert1\rangle$ by direct matrix multiplication.
2. 2
   Step 2:

   $$\text{Hypothesis: }\Big(\bigotimes_{j=0}^{n-2}X^{x_j}\Big)\lvert0^{n-1}\rangle=e_{k(x')}\in\mathbb C^{2^{n-1}},\qquad x':=x_0x_1\cdots x_{n-2}$$

   Induction step: assume the claim for $n-1\ge1$ qubits and let $x'$ be $x$ without its last bit.
3. 3
   Step 3:

   $$\Big(\bigotimes_{j=0}^{n-1}X^{x_j}\Big)\lvert0^n\rangle=\Big(\Big(\bigotimes_{j=0}^{n-2}X^{x_j}\Big)\otimes X^{x_{n-1}}\Big)\big(\lvert0^{n-1}\rangle\otimes\lvert0\rangle\big)=\Big(\bigotimes_{j=0}^{n-2}X^{x_j}\Big)\lvert0^{n-1}\rangle\otimes X^{x_{n-1}}\lvert0\rangle$$

   Group the first $n-1$ factors, write $\lvert0^n\rangle=\lvert0^{n-1}\rangle\otimes\lvert0\rangle$, and use the mixed-product rule $(A\otimes B)(u\otimes v)=Au\otimes Bv$.
4. 4
   Step 4:

   $$=e_{k(x')}\otimes e_{x_{n-1}}$$

   Induction hypothesis for the first factor, base case for the last.
5. 5
   Step 5:

   $$(u\otimes v)_{2i+b}=u_i\,v_b\ \Rightarrow\ e_a\otimes e_b=e_{2a+b}\qquad(a<2^{n-1},\ b\in\{0,1\})$$

   Definition of the Kronecker product of a $2^{n-1}$-vector with a $2$-vector: entry $2i+b$ is $u_iv_b$, which is $1$ only for $i=a$, $b$ the given bit.
6. 6
   Step 6:

   $$k(x)=\sum_{j=0}^{n-1}x_j2^{n-1-j}=2\sum_{j=0}^{n-2}x_j2^{n-2-j}+x_{n-1}=2\,k(x')+x_{n-1}$$

   Split off the last term and factor $2$ out of the others (Horner's rule).
7. 7
   Step 7:

   $$\Big(\bigotimes_{j=0}^{n-1}X^{x_j}\Big)\lvert0^n\rangle=e_{2k(x')+x_{n-1}}=e_{k(x)}$$

   Combine the last three lines; by induction the claim holds for all $n\ge1$.
8. 8
   Step 8:

   $$\{\lvert x\rangle\}_{x\in\{0,1\}^n}=\{e_{k(x)}\}_{x}=\{e_0,\dots,e_{2^n-1}\}$$

   $x\mapsto k(x)$ is a bijection onto $\{0,\dots,2^n-1\}$, so the encoded states are all standard basis vectors, each exactly once.

∎

1. 1
   Step 1:

   $$U_x=\bigotimes_jX^{x_j}\ \text{contains one }X\ \text{per index }j\ \text{with }x_j=1\ \Rightarrow\ \#\text{gates}=\sum_jx_j=\lvert x\rvert\le n$$

   The factors with $x_j=0$ are identities and need no gate.
2. 2
   Step 2:

   $$X_jX_{j'}=X_{j'}X_j\ \ (j\ne j')\ \Rightarrow\ \text{all }X\text{ gates fit into one moment: depth }1$$

   Gates on disjoint qubits commute and can be executed in parallel, so the circuit has a single layer.
3. 3
   Step 3:

   $$X^{x_j}\lvert x'_j\rangle=\lvert x_j\oplus x'_j\rangle$$

   For $x_j=0$ nothing changes; for $x_j=1$, $X$ swaps $\lvert0\rangle\leftrightarrow\lvert1\rangle$, which is addition of $1$ modulo $2$.
4. 4
   Step 4:

   $$U_x\lvert x'\rangle=\bigotimes_jX^{x_j}\lvert x'_j\rangle=\bigotimes_j\lvert x_j\oplus x'_j\rangle=\lvert x\oplus x'\rangle$$

   Mixed-product rule on the product state $\lvert x'\rangle=\bigotimes_j\lvert x'_j\rangle$.
5. 5
   Step 5:

   $$U_x^2\lvert x'\rangle=\lvert x\oplus x\oplus x'\rangle=\lvert x'\rangle\ \ \forall x'\ \Rightarrow\ U_x^2=I$$

   $x\oplus x=0^n$; an operator that fixes every basis vector is the identity. In particular $U_x^\dagger=U_x$, so the same circuit also un-computes the encoding.

∎

1. 1
   Step 1:

   $$x-\tilde x=\sum_{k=\tau+1}^{\infty}b_k2^{-k}\ge0$$

   Subtract the first $\tau$ terms from the full expansion; every remaining term is non-negative.
2. 2
   Step 2:

   $$\sum_{k=\tau+1}^{\infty}b_k2^{-k}\le\sum_{k=\tau+1}^{\infty}2^{-k}$$

   Each digit satisfies $b_k\le1$.
3. 3
   Step 3:

   $$\sum_{k=\tau+1}^{\infty}2^{-k}=2^{-(\tau+1)}\sum_{i=0}^{\infty}2^{-i}=2^{-(\tau+1)}\cdot\frac{1}{1-\frac12}=2^{-\tau}$$

   Geometric series with first term $2^{-(\tau+1)}$ and ratio $\tfrac12$.
4. 4
   Step 4:

   $$x-\tilde x=2^{-\tau}\iff b_k=1\ \ \forall k>\tau$$

   Equality in the digit-wise bound requires every tail digit to be $1$, which the chosen expansion excludes; hence the inequality is strict: $x-\tilde x<2^{-\tau}$.
5. 5
   Step 5:

   $$2^\tau x=\sum_{k=1}^{\tau}b_k2^{\tau-k}+2^\tau(x-\tilde x),\qquad0\le2^\tau(x-\tilde x)<1\ \Rightarrow\ \lfloor2^\tau x\rfloor=2^\tau\tilde x$$

   Multiply by $2^\tau$: the first sum is an integer and the remainder lies in $[0,1)$, so it is the fractional part.
6. 6
   Step 6:

   $$\sup_{x\in[0,1)}(x-\tilde x)=2^{-\tau}\ \Rightarrow\ \big(x-\tilde x<\varepsilon\ \ \forall x\iff2^{-\tau}\le\varepsilon\iff\tau\ge\log_2\tfrac1\varepsilon\big)$$

   The supremum is approached by $x=1-2^{-K}$ with $K\to\infty$, whose error is $2^{-\tau}-2^{-K}$; so the guarantee holds exactly when $2^{-\tau}\le\varepsilon$, i.e. $\tau\ge\lceil\log_2(1/\varepsilon)\rceil$ by monotonicity of $\log_2$. For example $\varepsilon=10^{-3}$: $\log_2 1000\approx9.97$, so $\tau=10$ and $2^{-10}=\tfrac1{1024}<10^{-3}$, whereas $2^{-9}=\tfrac1{512}>10^{-3}$.

∎

1. 1
   Step 1:

   $$\lvert\tilde{\mathbf v}\rangle=\lvert\tilde v_0\rangle\otimes\lvert\tilde v_1\rangle\otimes\cdots\otimes\lvert\tilde v_{d-1}\rangle,\qquad\lvert\tilde v_j\rangle\in(\mathbb C^2)^{\otimes\tau}$$

   Concatenate the $d$ bit strings of length $\tau$; the register is the tensor product of $d$ blocks of $\tau$ qubits, i.e. $d\tau$ qubits.
2. 2
   Step 2:

   $$\#\text{gates}=\sum_j\lvert b(v_j)\rvert\le d\tau,\qquad\text{depth}=1$$

   Apply the cost proposition to the concatenated string of length $d\tau$.
3. 3
   Step 3:

   $$K=\sum_{j=0}^{d-1}\sum_{k=1}^{\tau}b_{j,k}\,2^{\,d\tau-1-(j\tau+k-1)}=\sum_{j=0}^{d-1}2^{\tau(d-1-j)}\sum_{k=1}^{\tau}b_{j,k}2^{\tau-k}$$

   Digit $b_{j,k}$ sits on qubit $j\tau+k-1$; apply the index map with $n=d\tau$ and factor $2^{\tau(d-1-j)}$.
4. 4
   Step 4:

   $$\sum_{k=1}^{\tau}b_{j,k}2^{\tau-k}=2^\tau\tilde v_j=\lfloor2^\tau v_j\rfloor$$

   The inner sum is the integer of the $\tau$-bit block (fixed-point theorem); the error bound applies to every component separately.

∎

1. 1
   Step 1:

   $$\langle D\vert D\rangle=\frac1M\sum_{m=0}^{M-1}\sum_{m'=0}^{M-1}\langle x^{(m)}\vert x^{(m')}\rangle$$

   Expand the inner product bilinearly (all coefficients are real and equal to $M^{-1/2}$).
2. 2
   Step 2:

   $$\langle x\vert x'\rangle=\delta_{xx'}\ \Rightarrow\ \langle D\vert D\rangle=\frac1M\,\#\{(m,m'):x^{(m)}=x^{(m')}\}$$

   Encoded states are orthonormal (they are distinct standard basis vectors by the basis-encoding theorem).
3. 3
   Step 3:

   $$\#\{(m,m'):x^{(m)}=x^{(m')}\}=\sum_x\#\{m:x^{(m)}=x\}^2=\sum_xc_x^2$$

   Group the ordered pairs by their common pattern $x$; there are $c_x\cdot c_x$ pairs for each $x$.
4. 4
   Step 4:

   $$c_x\in\mathbb Z_{\ge0}\ \Rightarrow\ c_x^2\ge c_x\ \Rightarrow\ \sum_xc_x^2\ge\sum_xc_x=M$$

   For a non-negative integer, $c^2-c=c(c-1)\ge0$, with equality iff $c\in\{0,1\}$.
5. 5
   Step 5:

   $$\langle D\vert D\rangle=1\iff c_x\in\{0,1\}\ \forall x\iff x^{(m)}\ \text{pairwise distinct}$$

   Equality holds term by term iff no pattern occurs twice.
6. 6
   Step 6:

   $$\frac1{\sqrt M}\sum_m\lvert x^{(m)}\rangle=\frac1{\sqrt M}\sum_xc_x\lvert x\rangle\ \longrightarrow\ \frac{\sum_xc_x\lvert x\rangle}{\sqrt{\sum_yc_y^2}}$$

   Collect equal kets and divide by the norm $\sqrt{\sum_yc_y^2/M}$. Its Born probabilities $c_x^2/\sum_yc_y^2$ are not the empirical frequencies $c_x/M$; to sample with frequencies one uses amplitudes $\sqrt{c_x/M}$ instead.

∎

1. 1
   Step 1:

   $$\lvert\Psi_0\rangle=\lvert0^n\rangle\lvert1\rangle_f=\sqrt{\tfrac MM}\,\lvert x^{(-1)}\rangle\lvert1\rangle_f$$

   After step 1 the invariant holds for $m=0$: the stored sum is empty and $x^{(-1)}=0^n$.
2. 2
   Step 2:

   $$\prod_{j:\,x^{(m)}_j\ne x^{(m-1)}_j}\mathrm{CNOT}(f\to j)=\lvert0\rangle\langle0\rvert_f\otimes I+\lvert1\rangle\langle1\rvert_f\otimes U_{x^{(m-1)}\oplus x^{(m)}}$$

   Each CNOT acts as the identity when the flag is $0$ and as $X_j$ when it is $1$; the product of the $X_j$ is the Pauli string $U_{x^{(m-1)}\oplus x^{(m)}}$.
3. 3
   Step 3:

   $$\text{Load}\,\lvert\Psi_m\rangle=\frac1{\sqrt M}\sum_{k<m}\lvert x^{(k)}\rangle\lvert0\rangle_f+\sqrt{\frac{M-m}{M}}\,\lvert x^{(m)}\rangle\lvert1\rangle_f$$

   Stored terms have flag $0$ and are unchanged; on the active term $U_{x^{(m-1)}\oplus x^{(m)}}\lvert x^{(m-1)}\rangle=\lvert x^{(m)}\rangle$ by the cost proposition.
4. 4
   Step 4:

   $$C_m=(I-P_m)\otimes I_f+P_m\otimes R_Y(-\theta_m),\qquad P_m=\lvert x^{(m)}\rangle\langle x^{(m)}\rvert,\qquad P_m\lvert x^{(k)}\rangle=0\ \ (k<m)$$

   The split is the rotation controlled on the data register equal to $x^{(m)}$. Distinctness gives $x^{(k)}\ne x^{(m)}$, so every stored term lies in the kernel of $P_m$ and is untouched.
5. 5
   Step 5:

   $$R_Y(-\theta)\lvert1\rangle=\begin{pmatrix}\cos\frac\theta2&\sin\frac\theta2\\-\sin\frac\theta2&\cos\frac\theta2\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix}=\sin\tfrac\theta2\lvert0\rangle+\cos\tfrac\theta2\lvert1\rangle$$

   Second column of $R_Y(-\theta)$, using $R_Y(\theta)=\begin{pmatrix}\cos\frac\theta2&-\sin\frac\theta2\\\sin\frac\theta2&\cos\frac\theta2\end{pmatrix}$.
6. 6
   Step 6:

   $$\sin\tfrac{\theta_m}2=\frac1{\sqrt{M-m}},\qquad\cos\tfrac{\theta_m}2=\sqrt{1-\frac1{M-m}}=\sqrt{\frac{M-m-1}{M-m}}$$

   Definition of $\theta_m$; $\theta_m/2\in(0,\tfrac\pi2]$, so the cosine is non-negative.
7. 7
   Step 7:

   $$\sqrt{\tfrac{M-m}{M}}\cdot\frac1{\sqrt{M-m}}=\frac1{\sqrt M},\qquad\sqrt{\tfrac{M-m}{M}}\cdot\sqrt{\tfrac{M-m-1}{M-m}}=\sqrt{\tfrac{M-m-1}{M}}$$

   Multiply the active amplitude by the two rotation coefficients: exactly the share $1/\sqrt M$ is split off.
8. 8
   Step 8:

   $$C_m\,\text{Load}\,\lvert\Psi_m\rangle=\frac1{\sqrt M}\sum_{k\le m}\lvert x^{(k)}\rangle\lvert0\rangle_f+\sqrt{\frac{M-(m+1)}{M}}\,\lvert x^{(m)}\rangle\lvert1\rangle_f=\lvert\Psi_{m+1}\rangle$$

   The new flag-$0$ term joins the stored sum; the invariant holds for $m+1$.
9. 9
   Step 9:

   $$\lvert\Psi_M\rangle=\frac1{\sqrt M}\sum_{k<M}\lvert x^{(k)}\rangle\lvert0\rangle_f+0=\lvert D\rangle\lvert0\rangle_f$$

   At $m=M$ the active amplitude $\sqrt{(M-M)/M}$ vanishes (the last rotation is $\theta_{M-1}=2\arcsin1=\pi$, which maps $\lvert1\rangle\mapsto\lvert0\rangle$).
10. 10
    Step 10:

    $$\mathrm{CCX}\ \text{ladder}\cdot\mathrm{CR}_Y\cdot\mathrm{CCX}\ \text{ladder}^{-1}\ \text{restores the ancillas to}\ \lvert0^{n-1}\rangle$$

    After the zero-controls are negated, the ladder writes the AND of data bits $0,\dots,k$ into ancilla $k$, so the last ancilla is $1$ exactly on the branch whose data register equals $x^{(m)}$; the controlled $R_Y$ does not touch the data or ancilla qubits, and the reversed ladder (Toffoli is self-inverse) restores every ancilla to $0$ on every branch, so the ancillas factor out.

∎

1. 1
   Step 1:

   $$\text{qubits}=\underbrace{n}_{\text{data}}+\underbrace{1}_{\text{flag}}+\underbrace{n-1}_{\text{ancillas}}=2n$$

   One ancilla per Toffoli of the AND ladder (none for $n=1$, where the single data qubit controls the rotation directly).
2. 2
   Step 2:

   $$\#\mathrm{CNOT}_m=d_H\big(x^{(m-1)},x^{(m)}\big)\le n$$

   Load step: one CNOT per differing bit (Hamming distance).
3. 3
   Step 3:

   $$\#X_m=2\big(n-\lvert x^{(m)}\rvert\big)\le2n,\qquad\#\mathrm{CCX}_m=2(n-1),\qquad\#\mathrm{CR}_{Y,m}=1$$

   Split step: negate and restore the zero-controls, compute and uncompute the ladder, one controlled rotation.
4. 4
   Step 4:

   $$\text{total}\le1+\sum_{m=0}^{M-1}\big(n+2n+2(n-1)+1\big)=1+M(5n-1)=O(Mn)$$

   Add the initial $X$ on the flag and sum over the $M$ iterations.
5. 5
   Step 5:

   $$\mathrm{CCX}=6\ \mathrm{CNOT}+9\ \text{one-qubit gates},\qquad\mathrm{CR}_Y(\theta)=R_Y(\tfrac\theta2)\,\mathrm{CNOT}\,R_Y(-\tfrac\theta2)\,\mathrm{CNOT}$$

   Standard decompositions: the Toffoli into $6$ CNOTs, $2$ Hadamards and $7$ $T$/$T^\dagger$ gates (cf. Nielsen–Chuang Fig. 4.9), and the controlled rotation into $2$ CNOTs and $2$ single-qubit rotations (Barenco et al. 1995). Each gate is replaced by a constant number of elementary gates, so the elementary count is also $O(Mn)$.