Introduction to Quantum Computing
Introduction to Quantum Computing
Contact
Introduction to Quantum Computing
Introduction to Quantum Computing

Introduction to Quantum Computing

Fall 2024 Peking University

Announcement

📖
Sep 20, 2024
Lecture notes in one volume: (updated 2024-11-06)
Lecture_Notes.pdf
5531.8KB

Basic Information

  • Lecture time:
    • Wednesday 1:00-2:50 pm (Weeks 1, 3, 5, 7, 9, 11, 13, 15)
    • Friday 1:00-2:50 pm (Every week except 4 due to holidays)
  • Lecture location: 二教 406
  • Office hour: Friday 3:15-4:45 pm or by reservation, 静园五院 103-1

Evaluation

Assignments

💡
25%: 5 assignments, 5% each
  • Each assignment will be given around two weeks to finish.
  • Late assignments will NOT be accepted.
  • You are encouraged to discuss assignment problems with your peers, with the TA, and with the course instructor. However, your solutions should be based on your own understanding and should be written independently. For each assignment, if you discussed the problems with other students in the class, you must include a list of the students' name.

Project

💡
35%: 5% proposal, 20% final report, 10% presentation
Our course project will:
  • Explore a topic in in depth, especially considering that quantum computing is a rapidly advancing area;
  • Give you experience in reading research literature and identifying possible future research directions;
  • Practice your scientific communication skills through both a written report and an in-class presentation.
You may work either on your own or in a group of two students. Project types include:
  • An expository paper on a quantum computing topic that is not covered in the course, or
  • An original research project on a theoretical aspect of quantum computing.
The project is composed of a proposal (1 page), a final report (no more than 10 pages), and a presentation (around 10-15 minutes, depending on the number of groups).
 
A suggested range of topics will be given around the middle of the semester.
The final report will be required to be written in a given LaTeX template. Reference:
The evaluation of the final report will mainly depend on:
  • Contents: The range and the level of details that the report covers.
  • Novelty: Catch the up-to-date trend for expository papers and implementation projects. Full score on novelty for original research projects.
  • Clarity: The clarity of the contents discussed in the report, whether those are intuitive and understandable.
  • Quality: Grammars, choice of words, typos, expression of mathematical formulas, etc.
The evaluation of the presentation will mainly depend on contents and clarity.

Final Exam

💡
40% Jan 5, 2025, afternoon
Students are allowed to take one page of A4 paper (with two sides). No other notes, books, devices, etc. are allowed.
The problems will follow similar styles to assignment problems.

Tools & Links

LaTeX中文文档.pdf
1418.4KB

Lectures

Lecture 1

💡
Sep 11, 2024
Lecture 1 - Introduction.pdf
7070.6KB
 
 
 
Introduction to IBM Qiskit, credit to IBM
 
 
 
 

Lecture 2

💡
Sep 13, 2024
Handwriting-QC-Lecture 2.pdf
5101.8KB
 
 
 
 

Lecture 3

💡
Sep 20, 2024
Handwriting-QC-Lecture 3.pdf
5236.4KB
 
 
 
 

Lecture 4

💡
Sep 25, 2024
Handwriting-QC-Lecture 4.pdf
5442.4KB
 
 
 
 
 

Lecture 5

💡
Sep 27, 2024
Handwriting-QC-Lecture 5.pdf
5517.6KB
 
 
 
 
 

Lecture 6

💡
Oct 9, 2024
Handwriting-QC-Lecture 6.pdf
6469.1KB
 
 
 
 
 

Lecture 7

💡
Oct 11, 2024
Handwriting-QC-Lecture 7.pdf
6325.9KB
 
 
 
 
 

Lecture 8

💡
Oct 18, 2024
Handwriting-QC-Lecture 8.pdf
6548.9KB
 
 
 
 
 

Lecture 9

💡
Oct 23, 2024
Handwriting-QC-Lecture 9.pdf
3916.5KB
 
 
 
 
 

Lecture 10

💡
Oct 25, 2024
Handwriting-QC-Lecture 10.pdf
5148.3KB
 
 
 
 
 

Lecture 11

💡
Nov 1, 2024
Handwriting-QC-Lecture 11.pdf
5461.0KB
 
 
 
 
 

Lecture 12

💡
Nov 6, 2024
Handwriting-QC-Lecture 12.pdf
5439.9KB
 
 
 
 
 

Lecture 13

💡
Nov 8, 2024
Handwriting-QC-Lecture 13.pdf
6695.0KB
 
 
 
 

Assignments

Assignment 1

📖
Sep 25, 2024
Due: 1 pm, Wednesday, October 9
Assignment 1.pdf
224.9KB

Assignment 2

📖
Oct 9, 2024
Due: 1 pm, Wednesday, October 23
Assignment 2.pdf
151.2KB

Assignment 3

📖
Oct 23, 2024
Due: 1 pm, Wednesday, November 6
Assignment 3.pdf
142.4KB

Assignment 4

📖
Nov 6, 2024
Due: 1 pm, Wednesday, November 20
Assignment 4.pdf
157.0KB

Project

Project Proposal

📖
Nov 3, 2024
pp-template-quantum.pdf
74.7KB
pp-template-quantum.tex
2.8KB

Final Project Template

📖
Dec 29, 2024
final-report-template-quantum.tex
4.1KB
final-report-template-quantum.pdf
90.6KB

Topics List

The following is a list of possible project topics, organized by subject. Though very long, this list is far from exhaustive. You are welcome to choose a topic not on this list.
Each topic has a short description to give you a very rough idea what it is about, together with a few references to get you started. Often the choice of references is somewhat arbitrary, so you should only treat the given references as a possible starting point. You should consult other related papers to form a more complete picture of the topic. Please do not hesitate to ask for help finding additional references.
Many of these references are links to published articles that may not be accessible from outside the university. If you have difficulty accessing any of these references, please let Tongyang know. If a topic uses mathematical concepts that go beyond the typical scope of the course, this is noted in the topic description.
Quantum algorithms: A survey.
There is a nicely-written survey that you can use as a starting point - read the chapters and find the one that interests you the most. (Dalzell et al.)
Quantum algorithms: Circuits
  • The Solovay-Kitaev algorithm. This algorithm provides and efficient method to approximate any unitary with gates from a specified (universal) gate set, and therefore allows conversion between universal gate sets. Uses some concepts from group theory, specifically facts regarding the Lie group SU(d). (Dawson and Nielsen; Trung, Van Meter, Horsman)
  • Exact circuit synthesis. Characterizes when unitary operations can be implemented exactly using a specific gate set, and gives an algorithm for finding such an implementation. Uses concepts from algebraic number theory. (Giles and Selinger; Giles and Selinger)
  • Quantum state preparation with optimal circuit depth. Characterizes how to prepare an arbitrary quantum state or an arbitrary sparse quantum state with optimal circuit depth, with tradeoff the number of ancilla qubits. Uses only mathematics commonly appeared in quantum computing. (Zhang, Li, and Yuan; Yuan and Zhang)
Quantum algorithms: Algebraic problems
  • Algorithm for decomposing Abelian groups. Decomposing an Abelian group into cyclic subgroups is a prerequisite for applying Shor’s algorithm. Uses only elementary group theory. (Cheung, Mosca; Zhang)
  • Algorithms for solvable groups. This topic concerns quantum algorithms for computing the order of an element, and related problems such as group membership and equality of subgroups, for solvable groups. Nontrivial but standard techniques from group theory are employed. (Watrous; Ivanyos, Magniez, Santha)
  • Query complexity non-Abelian HSPs. The hidden subgroup problem is a generalization of the period-finding problem solved by Shor’s algorithm. This problem can be solved with only polynomially many quantum queries (though efficient quantum algorithms remain elusive for many groups). (Ettinger, Høyer, Knill; Ettinger, Høyer)
  • The Kuperberg sieve. A subexponential algorithm to solve the hidden subgroup problem for dihedral groups. Use only a little group theory. (Kuperberg; Regev)
  • The hidden shift problem. In the hidden shift problem, we are given functions f and g with the promise that f(x) = g(x+s), and would like to find s. While this problem seems hard in general, for certain groups and functions solutions are known. Uses some group theory and number theory. (van Dam, Hallgren, Ip; Friedl, Ivanyos, Magniez, Santha, Sen)
  • Solving Pell’s equation. Generalizations of Shor’s algorithm lead to efficient quantum algorithms for a variety of hard computational problems in algebraic number theory. Uses some sophisticated ideas from rings and fields. (Hallgren)
  • Unit group and class group of an arbitrary degree number field. This further extends the Pell’s equation result (on a quadratic field) and in general give polynomial-time quantum algorithms for computing the unit group and class group of an arbitrary (constant) degree number field. Also requires sophisticated ideas from rings and fields. (Eisenträger, Hallgren, Kitaev, Song; Biasse, Song; de Boer, Ducas, Fehr)
  • Gate-efficient version of Shor’s algorithm. Recently, the Shor’s algorithm has been improved to a version with gate complexity ~O(n^1.5) and ~O(n^0.5) executions. (Regev; Ragavan, Vaikuntanathan)
Quantum algorithms: Discrete mathematics
  • Algorithms for graph properties. This topic concerns upper and lower bounds on the complexity of computing certain graph or network flow properties in terms of number of queries to the adjacency matrix of a graph. Uses some graph terminology but no advanced mathematical concepts. (Dürr, Heiligman, Høyer, Mhalla; Ambainis, Špalek; Dörn).
  • Graph property testing problems with exponential quantum speedup. This topic studies property testing problems where either a graph satisfies a property, or far from that property. For certain graph property testing problems, there can be exponential quantum speedup compared to the classical counterpart. Requires elementary group theory, basic graph terminology, and the glued tree example. (Ben-David, Childs, Gilyen, Kretschmer, Podder, Wang)
  • Pathfinding in graphs with exponential speedup. Finding a path between two vertices in a connected graph is a fundamental question. There is a recent paper that finds a class of graphs that allows for exponential quantum-classical separation for the pathfinding problem with the adjacency list oracle. (Li and Tong)
  • Quantum walk on the line. Random walks provide a framework for analyzing and developing randomized algorithms. This topic considers a quantum analog of a random walk and studies its behavior. Concepts from quantum mechanics are used heavily. (Ambainis, Bach, Nayak, Vishwanath, Watrous)
  • Quantum walk for finding marked vertices on graphs. Although deciding whether there is a marked vertex or not in a graph can be achieved with quadratic speedup in a straightforward sense, finding such a marked vertex requires more advanced techniques in quantum walks. (Ambainis, Gilyen, Jeffery, Kokainis)
  • Quantum oracle interrogation. Examines how many quantum queries to a black-box function are necessary to learn the entire function. (van Dam, Boneh, Zhandry)
  • k-distinctness. Generalizing element distinctness, the problem k-distinctness is to decide if an input list of integers contains k copies of the same integer. The state-of-the-art algorithm proposes a multi-dimensional quantum walk and also gives the best-known quantum algorithm for solving the guled-tree problem. (Jeffery, Zur; Belovs)
Quantum algorithms: Optimization
  • Quantum adiabatic optimization. Uses the quantum adiabatic theorem as a method for preparing ground states, thereby solving optimization problems. There has been considerable interest in this approach, although its performance remains difficult to analyze. (Farhi, Goldstone, Gutmann, Sipser)
  • Quantum approximate optimization algorithm. Quantum algorithm to find solutions to combinatorial optimization problems, such as SAT, that satisfy many (but not necessarily all) constraints. (Farhi, Goldstone, Gutmann)
  • Gradient computation. For a smooth function, there is a quantum algorithm that can compute its gradient using quantum Fourier transform with fewer queries compared to the classical counterpart. (Jordan; Gilyen, Arunachalam, Wiebe; Cornelissen)
  • No quantum speedup for convex optimization in eps-dependence. On the other hand, there exist instances for nonsmooth convex functions with quantum lower bound matching the classical optimal bound in finding eps-approximate minimum, hence having no quantum speedup. (Garg, Kothari, Netrapalli, Sherif; Garg, Kothari, Netrapalli, Sherif)
  •  No quantum speedup for nonconvex optimization in eps-dependence. Furthermore, for nonconvex optimization, the problem of finding stationary points may also have no quantum speedup in eps-dependence. (Zhang and Li)
  • Volume estimation of convex bodies. This is a fundamental problem in high-dimensional geometry, and there is a quantum algorithm with polynomial quantum speedup. (Chakrabarti, Childs, Hung, Li, Wang, Wu)
  • Approximately convex functions. Since there is quantum speedup on general convex optimization, it is also natural to study optimization of approximately convex functions. Polynomial quantum speedup is also proved is this case. (Li and Zhang)
  • Escaping from saddle points. Beyond convex optimization, quantum algorithms also enjoy advantage for nonconvex optimization problems. A first problem is to escape from saddle points in nonconvex landscapes, and this can be solved by simulating the evolution of the Schrodinger equation. (Zhang, Leng, Li; Childs, Leng, Li, Liu, Zhang)
Quantum algorithms: Machine learning
  • Quantum principal component analysis. Compare two quantum algorithms for principal component analysis: one uses phase estimation, whereas the other describes how to evolve according to a Hamiltonian proportional to the density matrix of a quantum state. (Lloyd, Mohseni, Rebentrost; Daskin)
  • Classification. This considers some most basic problems in supervised learning. It is proved that quantum algorithms can achieve quadratic speedup in dimension for linear and kernel-based classification. (Li, Chakrabarti, Wu; Li, Wang, Chakrabarti, Wu)
  • Learning statistical properties. A fundamental problem in statistical learning and information theory is to learn statistical properties of probability distribution. For many important properties including entropies and distances between probability distributions, there is quantum advantage. (Li and Wu; Gilyen and Li)
  • Bandits. Bandits constitute one of the most basic models in reinforcement learning. For important models especially multi-arm bandits, quantum advantages of exploration and exploitation have been studied. (Wang, You, Li, Childs; Wan, Zhang, Li, Zhang, Sun)
  • PAC learning. PAC learning is a basic model in computational learning theory. It is shown that there is no quantum speedup for PAC learning in general. (Arunachalam and de Wolf)
  • Learning Hamiltonians. An important question motivated by statistical physics is to give copies of the Gibbs state e^{-H}/Tr[e^{-H}], and the goal is to learn the Hamiltonian H. This problem has recently been studied with polynomial-time algorithms. (Haah, Kothari, Tang; Bakshi, Liu, Moitra, Tang)
Quantum algorithms: Quantum simulation
  • Early work on simulating Hamiltonian dynamics. Hamiltonian simulation is one of the most important topics in quantum computing. Early papers carefully studied how to use product formulae as well as other tools in quantum computing to improve the overall cost. (Berry, Ahokas, Cleve, Sanders; Berry, Childs, Cleve, Kothari, Somma)
  • Optimal quantum algorithm for Hamiltonian simulation. This is first achieved by a method called quantum signal processing. Requires knowledge in polynomial approximation. (Low and Chuang; Low and Chuang)
  • Trotter error. To make Hamiltonian simulation algorithms more practical, people pursues deeper understanding about how to utilize the structure of Hamiltonians to give quantum algorithms with better cost. In particular, the commutators between different local terms can be taken into account and give a much better analysis under the Trotter formula. (Childs, Su, Tran, Wiebe, Zhu)
  • Product formula for commutators. Most Hamiltonian simulation algorithms break the Hamiltonian by summation of sub-pieces; how about directly using commutators? In fact, such strategy can be combined with product formulae directly. (Chen, Childs, Hafezi, Jiang, Kim, Xu)
  • Low-energy subspace. In practice, it is plausible that the input state in a simulation procedure only lies in a low-energy subspace of the system Hamiltonian, and this can make the simulation more efficient. (Sahinoglu and Somma; Gong, Zhou, Li)
  • Random inputs. In practice, it is plausible that the input state does not take place in the worst case, but is sampled from a certain random distribution. In such cases, the Hamiltonian simulation can be made more efficient. (Zhao, Zhou, Shaw, Li, Childs)
  • Practical estimation of the cost of Hamiltonian simulation algorithms. Most Hamiltonian simulation algorithms are presented with asymptotic bounds; how do they perform in practice? This is compared in detailed with non-asymptotic bounds. (Childs, Maslov, Nam, Ross, Su)
  • Solving differential equations. Beyond Hamiltonian simulation under the Schrodinger equation, it is natural to consider quantum algorithms for solving more general differential equations. In fact, Hamiltonian simulation is the basic, while it requires more knowledge in ordinary and partial differential equations. (Berry, Childs, Ostrander, Wang; Childs, Liu, Ostrander)
  • Simulating open systems. Beyond Hamiltonian simulation in closed systems, it is also natural to study open systems having interaction with the environment. If the interaction is Markovian, it is called a Lindbladian. There are results that sparse Lindbladians can be efficiently simulated on quantum computers. (Childs and Li; Cleve and Wang; Li and Wang)
  • Simulating quantum field theories. A quantum algorithm for computing the scattering behavior of a scalar field theory with a quartic interaction. Uses concepts from quantum field theory. (Jordan, Lee, Preskill; Jordan, Lee, Preskill)
Quantum algorithms: Quantum supremacy and experiments
  • Random circuit sampling on superconducting quantum computers. This was the first quantum supremacy experiment, performed by Google. (Arute et al.)
  • Random circuit sampling on ion-trap quantum computers. More recently, random circuit sampling was implemented on Quantinuum’s ion-trap quantum computer. It can even apply gates between any two qubits. (DeCross et al.)
  • QAOA on superconducting quantum computers. Having the Sycamore chip, the Google further performed the quantum approximate optimization algorithm (QAOA) on their chips. (Harrigan et al.)
  • Improved classical algorithms for the Google supremacy experiment. On the other side, classical algorithms for random circuit sampling have been improving and the threshold of reaching quantum supremacy has been significantly increased. (Huang et al.; Pan and Zhang)
  • Quantum walks. Various experiments have also demonstrated the power of quantum walks, based on different platforms: The first paper was performed on a superconducting processor, the second on optical tweezers, and the third on a silicon quantum photonic chip. (Gong et al.; Young et al.; Wang et al.)
  • Boson sampling. The experiment group at USTC performed Boson sampling on a photonic quantum chip named as Jiuzhang, whose state space dimension is about 10^30. (Zhong et al.)
  • Are Boson sampling results quantum or classical? There have been concerns about the supremacy experiment based on Boson sampling, and people have been studying whether it is more quantum or classical. (Martinez-Cifuentes, Fonseca-Romero, Quesada)
  • Maximum independent set on Rydberg atom arrays. At Harvard, a 256-atom programmable quantum simulator based on Rydberg atom arrays was applied to solving the maximum independent set problem, and on the hardest graphs superlinear quantum speedup in finding exact solutions was observed. (Ebadi et al., Ebadi et al.)
  • Quantum error correction. There has been important progress on implementing quantum error correction codes on current quantum computers, including efforts from Google, Harvard, IBM, etc. (Acharya et al.; Bluvstein et al.; Bravyi et al.)
Quantum algorithms: General methodology
  • Quantum singular value transformation (QSVT). QSVT is a general framework for quantum algorithms with applications to Hamiltonian simulation, solving linear systems, machine learning, etc. It requires understanding of the HHL algorithm and heavy calculus background, especially polynomial approximation. (Gilyen, Low, Su, Wiebe)
  • Quantum-inspired classical algorithms. A seminar work by Tang showed how to use tools from randomized linear algebra to give quantum-inspired classical algorithms for finding recommendation systems with cost poly-logarithmic in dimension (and polynomial in rank as well as the Frobenius norm of the input matrix). This was further extended to general quantum-inspired classical algorithms based on QSVT. (Tang; Chia, Gilyen, Li, Lin, Tang, Wang; Jethwani, Le Gall, Singh; Bakshi, Tang)
  • Span programs. Span programs are an alternate (algebraic) model of computation that in the quantum setting is equivalent to query complexity. They can be used to design new quantum algorithms: citations here provide some examples for graph problems. (Reichardt; Belovs, Reichardt; Gavinsky, Ito; Āriņš)
  • Adiabatic quantum computation. Motivated by the adiabatic optimization algorithm (see above), universal adiabatic computation is performed by constructing a Hamiltonian with an easily-prepared ground state, and slowly evolving to a Hamiltonian whose ground state encodes the desired computation. This is computationally equivalent to the circuit model. (Aharonov, van Dam, Kempe, Landau, Lloyd, Regev)
  • Measurement-based quantum computing. This “one-way” quantum computer relies on building a large array of entangled qubits. Computations are performed by making adaptive one-qubit measurements on the array. (Raussendorf, Browne, Briegel; Broadbent, Kashefi)
  • Computation by quantum walk. Shows that universal quantum computation can be encoded into transmission coefficients of a quantum walk scattered by a graph (see “Evaluating game trees” above). (Childs; Childs, Gosset, Webb)
  • Boson sampling. The behavior of non-interacting bosons lead to distributions that can be easy to sample using quantum effects, but classically hard (given some computational assumptions). Second reference is the extended version of the first. Uses notions from complexity theory. (Aaronson, Arkhipov; Aaronson, Arkhipov)
  • Variational quantum algorithms. Variational quantum algorithms constitute a main class of quantum algorithms that can be potentially performed on near-term quantum computers, where the quantum gates are parametrized by phase parameters and they are updated using optimization methods. (Cerezo et al.)
Lower bounds on quantum query complexity
  • Quantum adversary method. Lower bound method based on a measure of progress that can be made with each query, generalizing the search lower bound presented in class. More recent work shows that (an extension of) this method can always give optimal bounds due to a duality with span programs (see above). Uses semidefinite programming. (Ambainis)
  • Quantum lower bound for the collision problem. Applies the polynomial method to the problem of determining whether a function is 1-to-1 or 2-to-1. (Aaronson, Shi)
  • Quantum query complexity of symmetric functions. Quantum algorithms cannot give a large advantage for problems with certain symmetries. (Aaronson, Ambainis; Chailloux)
  • Quantum query complexity of state conversion. State conversion is the problem of using an oracle to convert one quantum state to another that depends on the oracle. This framework provides a more general perspective on the quantum adversary method. Uses semidefinite programming. (Lee, Mittal, Reichardt, Spalek, Szegedy)
Quantum computational complexity
  • QMA-completeness of the local Hamiltonian problem. A quantum analog of the Cook-Levin theorem (SAT is NP-complete). Can also be seen as characterizing the difficulty of finding ground states of quantum systems. (Kempe, Kitaev, Regev)
  • Strong error reduction for QMA. Method for reducing the error in a QMA proof system. (Marriott, Watrous)
  • Quantum satisfiability. Shows that a quantum analog of 2-SAT can be solved efficiently classically, and gives evidence for the hardness of quantum k-SAT with larger k. (Bravyi; Gosset, Nagaj)
  • Quantum communication complexity. Given an input shared between two parties, how much information must they exchange to compute some desired function (de Wolf)
  • Quantum computation with postselection. Studies the computational power of forcing a measurement to have a desired outcome. Gives an example of a classical problem for which quantum ideas give a simpler proof. (Aaronson)
  • QIP = PSPACE. Characterizes the power of quantum interactive proofs (equivalent to classical interactive proofs, or equivalently, polynomial-space computations). (Jain, Ji, Upadhyay, Watrous)
  • PreciseQMA = PSPACE. PreciseQMA, the version of QMA with exponentially small completeness-soundess gap, is equal to PSPACE. (Fefferman, Lin)
© 2022 Fernand. All Rights Reserved