Fall 2024 Peking University
Announcement
Sep 20, 2024
Lecture notes in one volume: (updated 2024-12-18)
Basic Information
- Instructor name: Tongyang Li
- Assistant Professor, Center on Frontiers of Computing Studies, Peking University
- Email: tongyangli@pku.edu.cn
- Teaching assistants:
- Rui Yang: ypyangrui@pku.edu.cn
- Yuexin Su: 2401112039@stu.pku.edu.cn
- Ziyi Yang: 2100010833@stu.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 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
- Photos to PDF: https://www.camscanner.com
- ChatGPT: https://chat.openai.com
- Maths Q&A: https://math.stackexchange.com
- Wolfram Alpha: https://www.wolframalpha.com
Lectures
Lecture 1
Sep 11, 2024
Introduction to IBM Qiskit, credit to IBM
Lecture 2
Sep 13, 2024
Lecture 3
Sep 20, 2024
Lecture 4
Sep 25, 2024
Lecture 5
Sep 27, 2024
Lecture 6
Oct 9, 2024
Lecture 7
Oct 11, 2024
Lecture 8
Oct 18, 2024
Lecture 9
Oct 23, 2024
Lecture 10
Oct 25, 2024
Lecture 11
Nov 1, 2024
Lecture 12
Nov 6, 2024
Lecture 13
Nov 8, 2024
Lecture 14
Nov 15, 2024
Lecture 15
Nov 20, 2024
Lecture 16
Nov 22, 2024
Lecture 17
Nov 29, 2024
Lecture 18
Dec 4, 2024
Lecture 19
Dec 6, 2024
Lecture 20
Dec 13, 2024
Lecture 21
Dec 18, 2024
Assignments
Assignment 1
Sep 25, 2024
Due: 1 pm, Wednesday, October 9
Assignment 2
Oct 9, 2024
Due: 1 pm, Wednesday, October 23
Assignment 3
Oct 23, 2024
Due: 1 pm, Wednesday, November 6
Assignment 4
Nov 6, 2024
Due: 1 pm, Wednesday, November 20
Assignment 5
Project
Project Proposal
Final Project Template
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)
- 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)
- 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)
- Nonconvex optimization. Recently, there have been several proposals for solving general nonconvex optimization problems based on quantum dynamics. (Liu, Su, Li; Leng, Hickman, Li, Wu; Chen, Lu, Wang, Liu, Li)
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.)
- 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
- 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 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)