Contact Elucyda to upgrade your cybersecurity strategy in 3 stages:
Contact Konstantin for enquiries. Visit the Elucyda YouTube Channel for educational video series that elucidate mathematics & physics. Download Elucyda Educational Resources to view diagrams in PDF format. Explore the explanations below which elucidate quantum algorithms and provide context for the transition to post-quantum cryptography.
A uniform superpostion of all computational basis states in a \(\beta\)-qubit register is defined as \begin{align*} \ket{+}^\beta =H^{\otimes \beta}\ket{0}^\beta =\frac{1}{\sqrt{2^\beta}}\sum\limits_{v \in\mathbb{Z}_{2^\beta}} \ket{v}^\beta =\underbrace{\sqrt{\frac{|T|}{2^\beta}}}_{\sin \frac{\theta}{2}}\overbrace{\frac{1}{\sqrt{|T|}}\sum\limits_{t \in T} \ket{t}^\beta}^{\ket{T}^\beta} +\underbrace{\sqrt{1-\frac{|T|}{2^\beta}}}_{\cos \frac{\theta}{2}}\overbrace{\frac{1}{\sqrt{2^\beta -|T|}}\sum\limits_{u \notin T} \ket{u}^\beta}^{\ket{\perp}^\beta}, \end{align*} where \(|T|=C\) is the total number of targets in the set \(T\), \(\ket{T}^\beta\) is the target superposition and \(\ket{\perp}^\beta\) is the non-target superposition. For quantum search and counting, it is useful to consider the relationship, $$ \frac{|T|}{2^{\beta}}=\sin^2\left(\pi\frac{\theta}{2\pi}\right)=\sin^2\left(\pi\left(1-\frac{\theta}{2\pi}\right)\right) \approx\sin^2\left(\pi 2^{-\alpha}\left[\pm\frac{\theta}{2\pi}\right]\right).$$ \(\beta\) must be chosen such that \(|T|<2^{\beta -1}\) and \(\alpha\) determines the number of bits in the approximations \(\left[\pm\frac{\theta}{2\pi}\right]\). The search iteration operator is defined as \begin{align*} U_\theta=H^{\otimes\beta}\left(2\ket{0}^\beta\bra{0}-I_{2^\beta}\right)H^{\otimes\beta}\left(I_{2^\beta} - 2\sum\limits_{t\in T}\ket{t}^\beta\bra{t}\right) =H^{\otimes\beta}\left(2\ket{0}^\beta\bra{0} - \sum\limits_{v\in \mathbb{Z}_{2^\beta}}\ket{v}^\beta\bra{v}\right)H^{\otimes\beta}\left(\sum\limits_{u\notin T}\ket{u}^\beta\bra{u} - \sum\limits_{t\in T}\ket{t}^\beta\bra{t}\right), \end{align*} with the eigenstates \(\ket{\pm i}^\beta=\frac{1}{\sqrt{2}}\left(\ket{\perp}^\beta\pm i\ket{T}^\beta\right)\) satisfying \(U_\theta\ket{\pm i}^\beta=e^{\mp i \theta}\ket{\pm i}^\beta\). The search iteration can be thought of as the composition of 2 reflections, defined as $$R=H^{\otimes\beta}\left(2\ket{0}^\beta\bra{0}-I_{2^\beta}\right)H^{\otimes\beta}, \quad \Omega=I_{2^\beta} - 2\sum\limits_{t\in T}\ket{t}^\beta\bra{t},$$ where \(\Omega\) is the oracle that marks the target states with a phase factor, so that \(\Omega\ket{T}^\beta=-\ket{T}^\beta\) and \(\Omega\ket{\perp}^\beta=\ket{\perp}^\beta\). The oracle can be expressed with a function that outputs 1 for targets and 0 for non-targets, so that \(\forall t\in T, f(t)=1, \Omega\ket{t}^\beta=-\ket{t}^\beta\) and \(\forall u\notin T, f(u)=0, \Omega\ket{u}^\beta=\ket{u}^\beta\). Both cases can be expressed as \(\forall v\in \mathbb{Z}_{2^\beta}, \Omega\ket{v}^\beta=(-1)^{f(v)}\ket{v}^\beta\). To perform the quantum search algorithm, amplify the target state amplitudes by repeatedly applying the search iteration operator to produce the state, \begin{align*} U_\theta^q\ket{+}^\beta &=\cos\left(\theta\left(\frac{1}{2}+q\right)\right)\ket{\perp}^\beta +\sin\left(\theta\left(\frac{1}{2}+q\right)\right)\ket{T}^\beta \\ &=\frac{1}{\sqrt{2}}\left(e^{-i \theta\left(\frac{1}{2}+q\right)}\ket{+i}^\beta+e^{+i \theta\left(\frac{1}{2}+q\right)}\ket{-i}^\beta\right) =\frac{1}{\sqrt{2}}\sum\limits_{\zeta \in\{-1,+1\}}e^{\zeta i \theta\left(\frac{1}{2}+q\right)}\ket{-\zeta i}^\beta, \end{align*} where the number of iterations that maximizes target amplitudes is $$ q=\left\lfloor \frac{\pi}{2\theta} \right\rfloor=\left\lfloor \frac{\pi}{4\arcsin\left(\sqrt{|T|2^{-\beta}}\right)} \right\rfloor \leq \left\lceil \frac{\pi}{4}\sqrt{\frac{2^{\beta}}{|T|}} \right\rceil ,$$ then measure the state after amplitude amplification. Repeat amplitude amplification and measurement until all targets have been identified.
To estimate the number of targets (counting), repeatedly prepare then measure the state, \begin{align*} &\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}} F^\dagger_{2^\alpha} \ket{z}^\alpha U_\theta^z \ket{+}^\beta \\ &=\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\frac{1}{\sqrt{2^\alpha}}\sum\limits_{x \in\mathbb{Z}_{2^\alpha}} e^{-2\pi i zx 2^{-\alpha}} \ket{x}^\alpha \frac{1}{\sqrt{2}}\sum\limits_{\zeta \in\{-1,+1\}} e^{\zeta i\theta \left(\frac{1}{2}+z\right)}\ket{-\zeta i}^\beta \\ &=\frac{1}{\sqrt{2}}\sum\limits_{\zeta \in\{-1,+1\}}\sum\limits_{x \in\mathbb{Z}_{2^\alpha}} 2^{-\alpha}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\left(e^{2\pi i\left(\zeta \frac{\theta}{2\pi}-\left(x+\left[\zeta \frac{\theta}{2\pi}\right]\right)2^{-\alpha}\right)}\right)^z e^{\zeta i\frac{\theta}{2}} \ket{x+\left[\zeta \frac{\theta}{2\pi}\right]}^\alpha \ket{-\zeta i}^\beta \\ &\approx\frac{1}{\sqrt{2}}\sum\limits_{\zeta \in\{-1,+1\}} e^{\zeta i\frac{\theta}{2}} \ket{\left[\zeta \frac{\theta}{2\pi}\right]}^\alpha \ket{-\zeta i}^\beta =\frac{1}{\sqrt{2}}\left(e^{-i\frac{\theta}{2}} \ket{\left[-\frac{\theta}{2\pi}\right]}^\alpha \ket{+i}^\beta +e^{+i\frac{\theta}{2}} \ket{\left[+\frac{\theta}{2\pi}\right]}^\alpha \ket{-i}^\beta\right), \end{align*} to obtain the \(\alpha\)-bit approximations which can be used to compute \(C=|T|\approx 2^{\beta}\sin^2\left(\pi 2^{-\alpha}\left[\pm\frac{\theta}{2\pi}\right]\right)\), where \(\left[+\frac{\theta}{2\pi}\right]\) and \(\left[-\frac{\theta}{2\pi}\right]\) are \(\alpha\)-bit approximations of \(2^{\alpha}\frac{\theta}{2\pi}\) and \(2^{\alpha}\left(1-\frac{\theta}{2\pi}\right)\), respectively.
Order-finding: Given \(N,a,r\in \mathbb{N}\) such that \(1 < a < N\) and \(gcd(a,N)=1\), find the order \(r=|a|\) which is the smallest positive integer such that \(a^r=1 \, mod\, N\). Powers of \(a\) are computed \(mod \, N\).
If \(2|r\wedge a^{\frac{r}{2}}\neq -1\) compute \(gcd\left(a^{\frac{r}{2}}\pm 1, N\right)\) to find factors of \(N\). This works because \(\left(a^{\frac{r}{2}}-1\right)\left(a^{\frac{r}{2}}+1\right)=a^r-1=0\). Repeat with other choices of \(a\) until all prime factors of \(N\) have been identified.
Discrete logarithm: The discrete logarithm can be expressed as \(s=\log_a p \, mod \, N\), where \(s\in\mathbb{Z}_r\) satisfies \(1 < s < r\). The aim is to find \(s\) such that \(a^s=p\).
For \(z,k\in\mathbb{Z}\), the order-finding function is defined as \[f_1(z)=a^z=a^z\times (a^r)^k=a^{z+kr}=f_1(z+kr).\] For \((z,h)\in\mathbb{Z}_r\times\mathbb{Z}_r\) and \(l\in\mathbb{Z}_r\), the discrete logarithm function is defined as \[f_2(z,h)=a^{z+sh}=a^{(z-ls)+s(h+l)}=f_2(z-ls,h+l)=f_2(z+sh,0)=f_1(z+sh)=a^z\times(a^s)^h=a^z\times p^h.\] Both functions exhibit periodicity. They output 1 for the inputs, \[f_2(-ls,l)=f_2(0,0)=f_1(0)=f_1(kr)=a^r=1,\] and they output \(p\) for the inputs, \[f_2(0,1)=f_2(s,0)=f_1(s)=a^s=p.\] Order-finding and discrete logarithms can both be described as hidden subgroup problems.
Hidden subgroup problem: Find a generating set for the hidden subgroup \(H\leq G\) given the function \(f:G\longrightarrow X\) for which \(\forall g_1,g_2\in G, f(g_1)=f(g_2)\longleftrightarrow g_1 H=g_2 H\).
The \(a\)-multiplier \(U_a\) and \(p\)-multiplier \(U_p\) are operators with the properties, $$ U_a\ket{\underbrace{f_1(z)}_{a^z}}^\beta = \ket{\underbrace{f_1(z+1)}_{a^z\times a=a^{z+1}}}^\beta, \quad U_p\ket{\underbrace{f_1(z)}_{a^z}}^\beta = \ket{\underbrace{f_1(z+s)}_{a^z\times p=a^{z+s}}}^\beta, \quad U_a^s=U_p,$$ with the eigenstates, $$ U_a\ket{\lambda(\zeta)}^\beta = e^{2\pi i \zeta r^{-1}}\ket{\lambda(\zeta)}^\beta, $$ which can be combined in the superposition of \(a\)-multiplier eigenstates, \begin{align*} U_a^z\ket{f_1(0)}^\beta=\ket{f_1(z)}^\beta&= \frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} e^{2\pi i z\zeta r^{-1}}\ket{\lambda(\zeta)}^\beta. \end{align*} \(z\) iterations of the \(a\)-multiplier and \(h\) iterations of the \(p\)-multiplier can produce the state, \begin{align*} U_p^h U_a^z\ket{1}^\beta=\ket{a^z p^h}^\beta=\ket{f_2(z,h)}^\beta=\ket{f_1(z+sh)}^\beta =\frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} e^{2\pi i (z+sh)\zeta r^{-1}}\ket{\lambda(\zeta)}^\beta. \end{align*} To perform the quantum order-finding algorithm, repeatedly prepare and measure the quantum state, \begin{align*} &\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}} F^\dagger_{2^\alpha} \ket{z}^\alpha \ket{f_1(z)}^\beta \\ &=\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\frac{1}{\sqrt{2^\alpha}}\sum\limits_{x \in\mathbb{Z}_{2^\alpha}} e^{-2\pi i zx 2^{-\alpha}} \ket{x}^\alpha \frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} e^{2\pi i z\zeta r^{-1}}\ket{\lambda(\zeta)}^\beta \\ &=\frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}}\sum\limits_{x \in\mathbb{Z}_{2^\alpha}} 2^{-\alpha}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\left(e^{2\pi i\left(\zeta r^{-1}-\left(x+\left[\zeta r^{-1}\right]\right)2^{-\alpha}\right)}\right)^z \ket{x+\left[\zeta r^{-1}\right]}^\alpha \ket{\lambda(\zeta)}^\beta \\ &\approx\frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} \ket{\left[\zeta r^{-1}\right]}^\alpha \ket{\lambda(\zeta)}^\beta. \end{align*} To perform the quantum discrete logarithm algorithm, repeatedly prepare and measure the quantum state, \begin{align*} &\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}} F^\dagger_{2^\alpha} \ket{z}^\alpha \frac{1}{\sqrt{2^\alpha}}\sum\limits_{h \in\mathbb{Z}_{2^\alpha}} F^\dagger_{2^\alpha} \ket{h}^\alpha \ket{f_2(z,h)}^\beta \\ &=\frac{1}{\sqrt{2^\alpha}}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\frac{1}{\sqrt{2^\alpha}}\sum\limits_{x \in\mathbb{Z}_{2^\alpha}} e^{-2\pi i zx 2^{-\alpha}} \ket{x}^\alpha \frac{1}{\sqrt{2^\alpha}}\sum\limits_{h \in\mathbb{Z}_{2^\alpha}}\frac{1}{\sqrt{2^\alpha}}\sum\limits_{y \in\mathbb{Z}_{2^\alpha}} e^{-2\pi i hy 2^{-\alpha}} \ket{y}^\alpha \frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} e^{2\pi i (z+sh)\zeta r^{-1}}\ket{\lambda(\zeta)}^\beta \\ &=\frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} \sum\limits_{x \in\mathbb{Z}_{2^\alpha}} 2^{-\alpha}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\left(e^{2\pi i\left(\zeta r^{-1}-\left(x+\left[\zeta r^{-1}\right]\right)2^{-\alpha}\right)}\right)^z \ket{x+\left[\zeta r^{-1}\right]}^\alpha \\ &\quad\sum\limits_{y \in\mathbb{Z}_{2^\alpha}} 2^{-\alpha}\sum\limits_{h \in\mathbb{Z}_{2^\alpha}}\left(e^{2\pi i\left(s\zeta r^{-1}-\left(y+\left[s\zeta r^{-1}\right]\right)2^{-\alpha}\right)}\right)^h \ket{y+\left[s\zeta r^{-1}\right]}^\alpha \ket{\lambda(\zeta)}^\beta \\ &\approx\frac{1}{\sqrt{r}}\sum\limits_{\zeta \in\mathbb{Z}_{r}} \ket{\left[\zeta r^{-1}\right]}^\alpha \ket{\left[s\zeta r^{-1}\right]}^\alpha \ket{\lambda(\zeta)}^\beta. \end{align*} The order \(r\) and the discrete logarithm \(s\) can be determined after repeated measurement of the \(\alpha\)-qubit registers, since \(\left[\zeta r^{-1}\right]\) and \(\left[s\zeta r^{-1}\right]\) are \(\alpha\)-bit approximations of \(2^{\alpha}\zeta r^{-1}\) and \(2^{\alpha}s\zeta r^{-1}\), respectively. In the quantum algorithms for counting targets, order-finding and discrete logarithms, the amplitudes are described by an expression of the form, \[2^{-\alpha}\sum\limits_{z \in\mathbb{Z}_{2^\alpha}}\left(e^{2\pi i\left(\omega-\left(x+\left[\omega\right]\right)2^{-\alpha}\right)}\right)^z =2^{-\alpha}\frac{1-e^{2\pi i\left(\omega-\left(x+\left[\omega\right]\right)2^{-\alpha}\right)2^{\alpha}}}{1-e^{2\pi i\left(\omega-\left(x+\left[\omega\right]\right)2^{-\alpha}\right)}}\] where \(\omega=\pm\frac{\theta}{2\pi},\zeta r^{-1},s\zeta r^{-1}\) in these 3 examples. The absolute square of this expression is \[2^{-2\alpha}\frac{\left|\sin{\left(\pi \left(\omega-\left(x+\left[\omega\right]\right)2^{-\alpha}\right)2^{\alpha}\right)}\right|^2}{\left|\sin{\left(\pi \left(\omega-\left(x+\left[\omega\right]\right)2^{-\alpha}\right)\right)}\right|^2},\] which peaks when \(x=0\) for sufficient choice of \(\alpha\), leaving non-zero \(x\) values with negligible probabilities.
Explore a geometric visualization of the quantum search algorithm:
How does the quantum search algorithm work when the number of non-targets is 3 times the number of targets? Only a single iterative rotation is required to ensure a target state is measured. This is successful amplitude amplification. Explore a geometric visualization of this ideal example for quantum search:
Does the quantum search algorithm still work with an equal number of targets and non-targets? Iterative rotations preserve the original 1/2 probability for measuring a target state. Instead of amplitude amplification, there is amplitude preservation. This is why \(\beta\) must be chosen such that \(|T|<2^{\beta -1}\). Explore a geometric visualization of this limiting case for quantum search:
Explore this side-by-side comparison of quantum teleportation and superdense coding:
