This post concerns the online class meetings for MTAT.05.118 Quantum Computing 1.
I will update the post with the details of how we are organizing them… as soon as we figure it out 😄 or when we change things that haven’t worked well.
How we are currently doing it:
- Streaming video:
The preferred way would be to stream the video with whiteboard write-down from out of the Delta building but ATI has declared Delta a no-go-zone except in emergencies (so no support staff etc). We tried video conferencing / streaming of written notes from Rafieh’s Magic Desk (actually a normal desk, but writing on it can be erased) — it worked surprisingly well.
The link to the Skype channel will be posted in a comment to this post shortly before the class starts.
Everybody’s mic must be muted! - Slides:
Slides will be shared directly via the Slides.com-presentation link.
The presentation link will be posted in a comment to this post shortly before the class starts. - Student interaction:
Since LaTeX formulas don’t work in Skype, for discussions with and among students we will use Telegram (web.telegram.org) with MathJax.
Please, everybody, get yourself a Telegram account!
The link to the Telegram discussion group will be posted in a comment to this post shortly before the class starts.
Get you gear ready
Make sure you have this set up properly on your computer:
- Skype: For video streaming. Get an account.
- Telegram (web.telegram.org): For LaTeX-capable chat with editing of previous messages. Get an account.
- MathJax for LaTeX math formulas in the posts and comments:
Go here, follow the instructions: https://www.math.ucla.edu/~robjohn/math/mathjax.html .
See if it works: $$i\frac{d|\psi\rangle}{dt} = \hbar H|\psi\rangle.$$
(I recommend to use the “render MathJax” bookmark whenever there’s new LaTeX source on the screen; reloading the page switches it off.)
$$\chi_\xi(x) = \frac{1}{2^{-n/2}} e^{2\pi i \sum_{j=1}^n \xi_j x_j /2} = 2^{-n/2} (-1)^{\sum_j x_j \xi_j} = 2^{-n/2} \prod_{j=1}^n (-1)^{\xi_j x_j}.$$
$\bigl( f(* + a) \bigr)^\wedge = $?? There’s the normal proof.
But here’s a “I’m coro-bored” proof.
The mapping $T\colon f\mapsto f(*+a)$ is a linear operator on the Hilbert space $\mathbb{C}^G$. So it has an adjoint operator. Let’s figure out what it is. First of all, $( f \mid Tg) = \sum_x f(x)(Tg)(x) = \sum_x f(x)g(x+a)$.
Now, the trick is this: The sum is over $x\in G$ and $G$ is a group. Let’s set $y := x+a$ then summing over $x$ is the same as summing over $y$. So:
$$(f \mid Tg) = \sum_x f(x)g(x+a) = \sum_y f(y-a) g(y) = \sum_y (S f)(y) g(y) = (Sf \mid g),$$
with $S\colon f\mapsto f(*-a)$. So $T^\dagger = f\mapsto f(*-a)$.
Now let’s apply this.
$$(Tf)^\wedge(\xi) = (\chi_\xi \mid Tf) = (T^\dagger\chi_\xi \mid f) = (\chi_\xi(*-a)\mid f).$$
We have $\chi_\xi(*-a) = |G|^{-1/2} e^{2\pi i \xi \bullet (*-a)} = e^{-2\pi i \xi\bullet a} |G|^{-1/2} e^{2\pi i \xi \bullet *} = e^{-2\pi i \xi\bullet a} \chi_\xi$.
So, we conclude:
$$\bigl( f(*+a) \bigr)^\wedge(\xi) = (Tf)^\wedge(\xi) = (e^{-2\pi i \xi\bullet a} \chi_\xi \mid f) =
e^{2\pi i \xi\bullet a} (\chi_\xi \mid f) = e^{2\pi i \xi\bullet a} \hat f(\xi)$$
Done. (Slide has been corrected.)
Classical Fourier transform:
Input: Array of $f$-values
Output: Array of $\hat f$-values
Let’s assume it can be computed in no time at all. 🙂
Now: What’s your algorithm for Fourier Sampling?
👍
Remember: QFT does this (by definition):
$$QFT\left( \sum_x h(x)|x\rangle \right)= \sum_\xi \hat h(\xi) |\xi\rangle$$
This is unitary by Parseval (remember that a linear operator $U$ is unitary iff $\lVert U\psi \rVert = \lVert \psi \rVert$ holds for all $\psi$).
What should QFT on $\mathbb{Z}_2^n$ for $n=1$ do in the computational basis?
$$QFT|0\rangle = QFT|h_0\rangle = \text{ ???}$$
$$QFT|1\rangle =\text{ ???}$$
For $|0\rangle$: Take $h_0 = \delta_0$ — the function which is one in 0 and zero everywhere else. $\hat h_0 = $???
$$\hat h_0(\xi) = \tfrac{1}{\sqrt 2} \sum_{x=0,1} h_0(x) (-1)^{x\cdot \xi} = \frac{1}{\sqrt 2}$$
So
$$QFT|0\rangle = \tfrac{1}{\sqrt2}|0\rangle + \tfrac{1}{\sqrt2}|1\rangle$$
Similarly, let’s define $h_1$ so that $|1\rangle = h_1(0)|0\rangle + h_1(1)|1\rangle$, i.e., $h_1 = \delta_1$.
$$\hat h_1(\xi) = \tfrac{1}{\sqrt 2} \sum_{x=0,1} h_1(x) (-1)^{x\cdot \xi} = \begin{cases} \frac{1}{\sqrt{2}},&\text{if $\xi=0$}\\-\frac{1}{\sqrt2},&\text{if $\xi=1$}\end{cases}$$
So $QFT|1\rangle = |-\rangle$
$\LaTeX$ help:
$$\begin{pmatrix} \frac{1}{\sqrt 2} & \dots & 0\\ & \ddots & \\ 0 & \dots & \frac{a}{b} \end{pmatrix}$$