Welcome to Hidden Subgroups and Quantum Computation. This summer we will study the
- rudiments of group (representation) theory and linear algebra.
- axiomatic foundations of quantum theory.
- circuit model via unitary gates on \(\mathcal{H} \simeq (\mathbb{C}^2)^{\otimes n}\).
- quantum Fourier transform \(F_n\) on \(\mathbb{Z}/n\).
- abelian hidden subgroup problem.
- results toward the nonabelian hidden subgroup problem.
We will take a rigorous approach to the relevant mathematics, but our focus will be on developing quantum computing intuition from the algebra.
Beautiful mathematics can be found in every corner of quantum research. But, it is hard. My hope is that by the end of these lectures, you will be well-equipped to break into the literature, whether textbooks or papers. In particular, we will close out our discussion by working through some research papers ourselves.
It is worth noting that while my quantum computation background has mostly been via mathematics, people from physics, computer science, and electrical engineering are working on these problems. I will do my best to incorporate as many of these perspectives as I can into lecture. If you are partial to some flavor of the subjects above, I will point you towards references. You will also have the freedom to choose hidden subgroup problem papers to read, and occasionally present, based on your interests.
Textbook
No textbook is required. I will prepare weekly slides in \(\LaTeX\) and occasionally lecture at the board. There is a wealth of literature on the underlying mathematics and the hidden subgroup problem. Some of my favorites include
- The Hidden Subgroup Problem: Review and Open Problems by Chris Lomont. This survey is thorough and has a great list of references for the subject. The appendices are also nice.
- The Hidden Subgroup Problem by Frédéric Wang. The technical foundations of the hidden subgroup problem are detailed out in this wonderful Master's project. Further, it dips into research-level results and novel contributions, which would be a good first taste before jumping into the literature.
- Quantum Computation and Quantum Information "Mike and Ike" by Michael Nielsen and Isaac Chuang. This is a very standard text which does its best to balance all aspects of introductory quantum information. I think it does a good job.
- Linear Algebra by Stephen Friedberg, Arnold Insel, and Lawrence Spence. This is my favorite of the "quintessential" linear algebra texts. The treatment is rigorous, while not trying too hard to be an abstract algebra book.
- Abstract Algebra by David Dummit and Richard Foote. If you want to learn algebra, Dummit and Foote will carry you through the fundamentals, and further.
Assignments and Deliverables
This minicourse will have regular problem sets. Notably, I will include a handful exercises to be done as homework between lectures These will be pretty brief and should be easy after sitting through lecture. If not, I am happy to work through them with you!
You will also prepare a review paper detailing interesting results from lecture and your own reading. The assigned paper is A subexponential-time quantum algorithm for the dihedral hidden subgroup problem by Greg Kuperberg (SIAM).
Lectures and Problem Sets
- Lecture 08
After defining the general quantum Fourier transform, we learned about dihedral groups and finding hidden reflections. Complete Problem Set 08.
- Lecture 07
We saw a solution to the general abelian hidden subgroup problem. We then looked at Simon's and Shor's algorithms. Complete Problem Set 07.
- Lecture 06
After defining complex representations of finite groups, we used characters to define the abelian quantum Fourier transform. Complete Problem Set 06.
- Lecture 05
We defined the cyclic quantum Fourier transform, which we then used to work out the cyclic hidden subgroup problem. Complete Problem Set 05.
- Lecture 04
Motivated by the quantum axioms, we loosely defined a quantum circuit and defined the hidden subgroup problem. Complete Problem Set 04.
- Lecture 03
We discussed tensor products, abstractly and using the Kronecker product. We then covered the four quantum axioms. Complete Problem Set 03.
- Lecture 02
After mentioning the essentials of vector spaces, we talked about inner products and Dirac's bra-ket notation. Complete Problem Set 02.
- Lecture 01
We covered the relevant basics of sets, groups, and the classification of finitely generated abelian groups (without proof). Complete Problem Set 01.
Catalog Description
The idea for this minicourse on the hidden subgroup problem is due to IMSA alumnus Doug Strain at Google Research. Below is his original description for the course.
Much of quantum computing's advantage comes from the foundations of the hidden subgroup problem. Textbook algorithms such as Deutsch-Jozsa, Simon's problem, and Shor's algorithm can all be phrased using the language of abstract algebra as the hidden subgroup problem. Students will learn basic concepts in group theory and how quantum computing can be thought of in terms of groups. Students will learn Shor's algorithm in terms of the abelian HSP and will explore progress in exploring the HSP for nonabelian groups.
Acknowledgements
This minicourse would not exist without
- Anastasia Perry, whose quantum computation intersession while I was at IMSA gave me my first look at the subject.
- Eric Chitambar, Roy Araiza, and Jihong Cai, from whom I learned all my quantum fundamentals.