New notes on Fourier transforms. Also note that the old notes have some typos fixed. Almost to factoring!
Lecture Notes
Lecture Notes 1: Introduction and Basics of Quantum Theory
Lecture Notes 2: Dirac Notation and Basic Linear Algebra for Quantum Computing
Lecture Notes 3: One Qubit, Two Qubit
Lecture Notes 4: The No-Cloning Theorem, Classical Teleportation and Quantum Teleportation, Superdense Coding
Lecture Notes 5: The Quantum Circuit Model and Universal Quantum Computation
Lecture Notes 6: Reversible Classical Circuits and the Deutsch-Jozsa Algorithm
Lecture Notes 7: The Recursive and Nonrecursive Bernstein-Vazirani Algorithm
Lecture Notes 8: Simon’s Algorithm
Lecture Notes 9: The Quantum Fourier Transform and Jordan’s Algorithm
Lecture Notes 10: Quantum Phase Estimation and Arbitrary Size Quantum Fourier Transforms
Homework
Homework 1
Homework 2
Handouts
Syllabus
O brave new quantum world!
The last 2 lecture pdf’s have incorrectly linked URLs.
Thanks Li! Also note that I have corrected some, but not nearly all, of the typoes in the previous notes. This weekend I’m planning on doing a more thorough proof reading to fix them up a bit.
Could you please discuss the following
issues regarding Jordan’s algorithm, lecture 9
(1)This algorithm seems to be incomplete and
useless to a QC programmer until
you tell him/her how to produce a
an initial state of the form you “assume”.
You seem to be saying, assume that a
magical black box has done 99% of the work.
Now I will show you how to do the last 1%.
(2)The estimate of O(d) for the classical time-complexity
and O(1) for the quantum time-complexity doesn’t seem
very fair or relevant to me. (apart from the fact that an
improvement by a factor of d is totally under-whelming.)
Unless you estimate the time complexity of
the task done by the oracle, how can you say that the
Jordan algorithm is better than a classical algorithm
with respect to time-complexity. (A related question is,
what is the classical time-complexity for calculating a
partial derivative using distributed classical
computing?)
(1) Which state? The QFTed |1> state? For an easy way to produce this (or pretty much any other state) see Kaye and Mosca http://arxiv.org/abs/quant-ph/0407102
(2) Of course this is a query complexity separation. But if you don’t dream about turning such a separation into a cool algorithm, then what’s the point of coming up with anything new at all? By the reasoning you are using there would be no reason for Bernstein and Vazirani to show there seperation and if there was not reason for them to write up their result, then would Simon has found his separation, and if Simon hadn’t found his separation would Shor have found factoring? And if Shor hadn’t found factoring, would Grover have found his algorithm? I’m just saying, always look on the bright side of life. I think it is a cool preminitive and wouldn’t be surprised is someone smarter than me figures out how to use it in a way that would make you happy!
Hi Dave!
I was delighted and flattered to see gradient estimation appear in your lecture notes. This reminds me that I should perhaps put an updated version on the arxiv since the published version of the paper has slightly clearer presentation in response to helpful reviewer comments.
Regarding comments on query complexity versus total complexity, it is of course true that the total complexity of the gradient estimation is proportional to the dimension d. A practical speedup is obtained only if the dominant cost is the function evaluations themselves. It is often the case that evaluating the objective function is the dominant cost in numerical optimization problems, for example. David Bulger recently wrote an interesting paper applying gradient estimation and Grover search to numerical optimization in the presence of many basin-like local minima.
Incidentally, the next time you are at MIT be sure to stop by the quantum computing reading group if you have time. We’ve got a lively group and we’d be happy for you to join us.
See you,
Stephen Jordan