Quantum Computing 2022

Announcement

Basic Information

• Instructor name: Tongyang Li
• Assistant Professor, Center on Frontiers of Computing Studies, Peking University
• Email: tongyangli@pku.edu.cn

• Teaching assistants:
• Shuo Zhou: AntiEntropy@pku.edu.cn
• Xinzhao Wang: wangxz@stu.pku.edu.cn
• Yecheng Xue: mycts@pku.edu.cn

• Assignment email: PKU.Quantum-Computing@outlook.com

• 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)

• Lecture location: 三教 403

• Office hour: Friday 3:15-4:45 pm or by reservation, 静园五院 103-1

Evaluation

Tools & Links

• Photos to PDF: https://www.camscanner.com/

• Tables to LaTeX: http://www.latex-tables.com/

• In search of references: https://www.jiumosearch.com/

Mathematics Stack Exchange

Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up. Sign up to join this community

https://math.stackexchange.com

Wolfram|Alpha: Making the world's knowledge computable

Uh oh! Wolfram|Alpha doesn't run without JavaScript. Please enable JavaScript. If you don't know how, you can find instructions . Once you've done that, refresh this page to start using Wolfram|Alpha.

https://www.wolframalpha.com

Lectures

Lecture 1

Lecture 2

Lecture 3

Lecture 4

Lecture 5

Lecture 6

Lecture 7

Lecture 8

Lecture 9

Lecture 10

Lecture 11

Lecture 12

Lecture 13

Lecture 14

Lecture 15

Lecture 16

Lecture 17

Lecture 18

Lecture 19

Lecture 20

Lecture 21

Assignments

Assignment 1

Assignment 2

Assignment 3

Assignment 4

Assignment 5

Project

Project Proposal

Final Project Template

Possible Topics List

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)

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)

• 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)

• Evaluating game trees. There is a quantum walk algorithm that uses scattering theory to optimally evaluate a balanced binary NAND tree. Subsequent work gave an optimal algorithm to evaluate any Boolean formula on a black-box input. (Farhi, Goldstone, Gutmann; Ambainis, Childs, Reichardt, Špalek, Zhang)

• Quantum oracle interrogation. Examines how many quantum queries to a black-box function are necessary to learn the entire function. (van Dam, Boneh, Zhandry)

• Ordered search. Quantum computers can achieve a constant-factor speedup over classical binary search for the problem of searching an ordered list (although the best possible constant remains unknown). (Farhi, Goldstone, Gutman, Sipser; Hoyer, Neerbek, Shi; Childs, Landahl, Parrilo)

• 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)

• Semidefinite programs. Polynomial quantum speedup in matrix dimension and number of constraints. Uses the idea of HHL’s algorithm for solving linear system (or more generally, under the QSVT framework) to perform Gibbs sampling, and then apply this to matrix multiplicative weight updates (commonly appeared in online learning). (Brandao and Svore; van Apeldoorn, Gilyen, Gribling, de Wolf; Brandao, Kalev, Li, Lin, Svore, Wu; van Apeldoorn and Gilyen)

• 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)

• Convex optimization. In general, quantum algorithms can give polynomial speedup in dimension for solving convex optimization problems. Requires basic knowledge in convex optimization. (van Apeldoorn, Gilyen, Gribling, de Wolf; Chakrabarti, Childs, Li, Wu)

• 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)

• 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

• Linear systems. This quantum algorithm produces a quantum state proportional to the solution of a (well-conditioned) system of linear equations. Requires calculus. (Harrow, Hassidim, Lloyd; Aaronson; Clader, Jacobs, Sprouse; Childs, Kothari, Somma)

• 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)

• Quantum generative adversarial networks (GANs). GAN is a very popular model in machine learning these days, especially in unsupervised learning. Quantum versions of GANs have been proposed to solve various quantum problems. (Lloyd and Weedbrook; Dallaire-Demers and Killoran; Chakrabarti, Huang, Li, Feizi, Wu)

• 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)

• Quantum boosting. Boosting is a standard strategy in online learning; a quantum version of boosting has also been proposed. (Arunachalam and Maity; Izdebski and de Wolf)

• Predicting quantum systems. A very natural direction between quantum computing and machine learning is to use machine learning tools to predict the measurement outcome of quantum systems. This has been systematically studied in a series of papers. (Huang, Kueng, Preskill; Huang, Kueng, Preskill; Huang et al.; Huang et al.; Huang et al.)

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)

• 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)

• 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.)

• 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 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)

• 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

• Superquadratic quantum query separations. Constructs total functions with large gaps between their classical and quantum query complexities, refuting a longstanding conjecture. (Aaronson, Ben-David, Kothari; Aaronson, Ben-David, Kothari, Rao, Tal)

• 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)

• Polynomial method. Uses a connection between quantum query algorithms and polynomials to establish lower bounds on query complexity. (Beals, Buhrman, Cleve, Mosca, de Wolf)

• 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 kSAT 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)