Notes - Quantum Information HT24, Shor's algorithm
Flashcards
How is Shor’s algorithm useful for factoring numbers if it just finds the period of a function?
Period finding algorithms can be used to factor numbers efficiently.
The period finding game between Alice and Bob can be described as:
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.
What is the query complexity of the problem given a classical oracle, and what is the query complexity given a quantum oracle?
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.
The query complexity given a classical oracle is $\Theta(d)$, given a quantum oracle it is $\Theta(1)$.
The period finding game between Alice and Bob can be described as:
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.
What additional condition does the simplified version of Shor’s algorithm use?
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.
- The period is a divisor of $d$, i.e. $\exists M$ such that $d = Mt$.
The simplified period finding game between Alice and Bob, ready for a solution with the simplified version of Shor’s algorithm, can be described as:
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
- The period is a divisor of $d$, i.e. $\exists M$ such that $d = Mt$.
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.
The simplified version of Shor’s algorithm doesn’t directly compute the period of $d$, it instead outputs integers of the form
\[n = j \frac d t\]
where $t$ is the period and $j$ is an integer between $0$ and $t - 1$, chosen with probability $\frac 1 t$. How can this be used to find the period?
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
- The period is a divisor of $d$, i.e. $\exists M$ such that $d = Mt$.
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.
We run the algorithm multiple times to get integers $n _ 1$ and $n _ 2$, where
\[n_1 = j_1 \frac d t, \quad n_2 = j_2 \frac d t\]If $j _ 1$ and $j _ 2$ are coprime, then
\[\frac d t = \gcd(n_1, n_2)\]So we can calculate
\[t = \frac{d}{\gcd(n_1, n_2)}\]Since we don’t have access the actual $j _ 1$ and $j _ 2$, we can just try this value of $t$ using the classical oracle. Since the probability of two integers being coprime is $>0.5$, repeating this several times will tell us the period with high probability.
The simplified period finding game between Alice and Bob, ready for a solution with the simplified version of Shor’s algorithm, can be described as:
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic with period $t$, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
- The period is a divisor of $d$, i.e. $\exists M$ such that $d = Mt$.
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.
The simplified version of Shor’s algorithm doesn’t directly compute the period of $d$, it instead outputs integers of the form
\[n = jM\]
where $j$ is some integer between $\{0, \cdots, t-1\}$ chosen with equal probability.
This can be used to find the period since if $n _ 1 = j _ 1M$ and $n _ 2 = j _ 2 M$ are outputs of the algorithm and $j _ 1$ and $j _ 2$ happen to be coprime, then
\[t = \frac{d}{\gcd(n_1, n_2)}\]
Since we don’t have access the actual $j _ 1$ and $j _ 2$, we can just try this value of $t$ using the classical oracle. Since the probability of two integers being coprime is $>0.5$, repeating this several times give us the period with high probability.
This simplified version of Shor’s algorithm is implemented as so:
- Prepare system $A$ in the Fourier state $ \vert e _ 0\rangle$, where this is a $d$-dimensional quantum system
- Prepare system $B$ in the computational state $ \vert 0\rangle$.
- Apply $U _ f$ to the composite system.
- Measure $B$ in the computational basis.
- Measure $A$ in the Fourier basis.
Quickly prove that the outcome in the Fourier basis is always an integer $n$ of the form $jM$ for some $j$ from $0$ to $t-1$.
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic with period $t$, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
- The period is a divisor of $d$, i.e. $\exists M$ such that $d = Mt$.
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.
We have the initial state
\[|e_ 0\rangle \otimes |0\rangle = \frac{1}{\sqrt d} \sum^{d-1}_ {x = 0} |x\rangle \otimes |0\rangle\]Applying $U _ f$ to the composite system, we get the state $ \vert \Psi\rangle$, defined by
\[\begin{aligned} |\Psi\rangle &:= U_ f(|e_ 0\rangle \otimes |0\rangle) \\\\ &= \frac{1}{\sqrt d} \sum^{d-1}_ {x = 0} |x\rangle \otimes |f(x)\rangle \\\\ &= \frac{1}{\sqrt {Mt} } \sum^{M-1}_ {m = 0} \sum^{t - 1}_ {x = 0} |x + mt\rangle \otimes |f(x + mt)\rangle &&(1\star)\\\\ &= \frac{1}{\sqrt {Mt} } \sum^{M-1}_ {m = 0} \sum^{t-1}_ {x = 0} |x + mt\rangle \otimes |f(x)\rangle && (2\star) \\\\ &= \frac{1}{\sqrt t}\sum^{t-1}_{x=0} \left(\frac{1}{\sqrt M} \sum^{M-1}_ {m = 0} |x+mt\rangle\right) \otimes |f(x)\rangle \\\\\ &= \frac{1}{\sqrt t} \sum^{t - 1}_ {x = 0} |\phi_ x\rangle \otimes |f(x)\rangle &&(3\star) \end{aligned}\]where:
- $(1\star)$: We split up the sum over $d$ into the sum over the periods, since $d = Mt$
- $(2\star)$: We use the periodicity of $f$
- $(3\star)$: We define
Measuring $B$ in the computational basis gives outcome $ \vert f(x)\rangle$ for some $x$ and $A$ is steered into the state $ \vert \phi _ x\rangle$. So it remains to show that measuring $A$ in the Fourier basis gives an integer of the form $n = jM$. Consider the probabilities of obtaining outcome $n$:
\[\begin{aligned} p_ A(n \mid x) &= |\langle e_ n | \phi_ x\rangle|^2 \\\\ &= |\langle \phi_x | e_ n \rangle|^2 \\\\ &= \left| \left( \frac{1}{\sqrt M} \sum^{M-1}_ {m = 0}\langle x + mt | \right)\left( \frac{1}{\sqrt d} \sum^{d-1}_ {k = 0} e^{\frac{2\pi i n k}{d} } |k\rangle \right)\right|^2 \\\\ &= \left| \frac{1}{\sqrt{Md} } \sum^{M-1}_ {m = 0} e^{\frac{2\pi i (x + mt)n}{d} } \right|^2 \\\\ &= \left| \frac{1}{\sqrt{Md} } \cdot e^{\frac{2\pi nx}{d} } \sum^{M-1}_ {m=0} e^{\frac{2\pi i m t n}{d} }\right| \\\\ &= \left| \frac{e^{\frac{2\pi i x n}{d} } }{\sqrt{Md} } \sum^{M - 1}_ {m = 0} \omega^m\right|^2 && (1,2\star) \\\\ &= \begin{cases} \left| \frac{e^{\frac{2\pi i x n}{d} } }{\sqrt{Md} } M \right|^2 &\text{ if } n \text{ is a multiple of }M \\\\ 0 &\text{ otherwise} \end{cases} &&(3\star) \\\\ &= \begin{cases} \frac 1 t &\text{ if } n \text{ is a multiple of }M \\\\ 0 &\text{otherwise} \end{cases} &&(4\star) \end{aligned}\]where:
- $(1\star)$: $\omega := e^{\frac {2\pi i n m t} d} = e^{\frac{2\pi i n} M}$ since $t/d = 1/m$.
- $(2\star)$: We use the relationship that $t/d = 1/m$.
- $(3\star)$: If $n$ is a multiple of $M$, then $\omega = 1$. If $n$ is not a multiple of $M$, then the sum is equal to $\frac{1 - \omega^M}{1-\omega} = 0$ since $\omega^M = 1$
- $(4\star)$: $ \vert e^{2\pi x n / d} \vert = 1$ and $M^2 / Md = M/d = 1/t$.
Hence the measurement can only give outcomes where $n$ is a multiple of $M$, and since $M = d/t$, this is exactly what we want.
The simplified period finding game between Alice and Bob, ready for a solution with the simplified version of Shor’s algorithm, can be described as:
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
- The period is a divisor of $d$, i.e. $\exists M$ such that $d = Mt$.
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.
The simplified version of Shor’s algorithm doesn’t directly compute the period of $d$, it instead outputs integers of the form
\[n = j \frac d t\]
This be used to find the period since we can run the algorithm twice to get integers $n _ 1$ and $n _ 2$, where
\[n_1 = j_1 \frac d t, \quad n_2 = j_2 \frac d t\]
If $j _ 1$ and $j _ 2$ are coprime, then
\[\frac d t = \gcd(n_1, n_2)\]
So we can calculate
\[t = \frac{d}{\gcd(n_1, n_2)}\]
Since we don’t have access the actual $j _ 1$ and $j _ 2$, we can just try this value of $t$ using the classical oracle. Since the probability of two integers being coprime is $>0.5$, repeating this several times will tell us the period with high probability.
How is this version of Shor’s algorithm implemented?
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
- The period is a divisor of $d$, i.e. $\exists M$ such that $d = Mt$.
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.
- Prepare system $A$ in the Fourier state $ \vert e _ 0\rangle$
- Prepare system $B$ in the computational state $ \vert 0\rangle$.
- Apply the quantum oracle $U _ f$ to the composite system.
- Measure $B$ in the computational basis.
- Measure $A$ in the Fourier basis.
The outcome in the Fourier basis is an integer $n = j \frac d t$.
Describe the simplified period finding game between Alice and Bob.
Alice picks a function $f : \mathbb N \to \mathbb N$ and promises:
- The function is strongly periodic, i.e. it is periodic and if two inputs $x$ and $y$ satisfy $f(x) = f(y)$, then the difference between $x$ and $y$ must be a multiple of the period
- The period is smaller than some fixed integer $d$, known to you
- The period is a divisor of $d$, i.e. $\exists M$ such that $d = Mt$.
Bob, given access to an oracle for $f$, has to determine the period using a minimum number of queries.