Seminar Archive:

2021.04.22. & 05.06. -- Speaker: Bálint Tóth (University of Bristol & Rényi Institute)

Title: A Bird's-Eye View on the Quantum Heisenberg Model (Part I & II)

Abstract: The quantum Heisenberg model is the emblematic model of quantum statistical physics. Despite its relative simplicity (at the level of definition) it exhibits most interesting physical phenomena, like emergence of so-called off diagonal long range order at low temperatures, in dimension 3 or more. This phase transition is closely related to the notorious Bose-Einstein condensation. From a mathematical point of view, these phenomena are only partly established with full rigour. There are plenty of challenges left for next generations of mathematicians and mathematical physicists. I will define the model, state the problems, present some of the existing main mathematical results, open problems and conjectures.

Warning: All results and conjectures presented are about 30 years old, or older. These seem to be truly hard problems.

2021.04.08. -- Speaker: András Gilyén (Caltech)

Title: (Sub)Exponential advantage of adiabatic quantum computation with no sign problem

Abstract: We demonstrate the possibility of (sub)exponential quantum speed-up via a quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with no sign problem. This strengthens the quasipolynomial separation recently proved by Hastings. The Hamiltonian that exhibits this speed-up comes from the adjacency matrix of an undirected graph whose vertices are labeled by n-bit strings, and we can view the adiabatic evolution as an efficient O(poly(n))-time quantum algorithm for finding a specific "EXIT" vertex in the graph given the "ENTRANCE" vertex. On the other hand we show that if the graph is given via an adjacency-list oracle, there is no classical algorithm that finds the "EXIT" with probability greater than exp(-n^delta) using at most \exp(n^delta) queries for delta = 1/5 - o(1).

Our construction of the graph is somewhat similar to the "welded-trees" construction of Childs et al., but uses additional ideas of Hastings for achieving a spectral gap and a short adiabatic path.

2021.03.25. -- Speaker: Andrea Basso (University of Birmingham)

Title: Lattice-based cryptography and SABER

Abstract: Post-quantum cryptography represents the future of cryptographic research. One of the most promising approaches involves lattices. Lattice-based cryptosystems offer security, performance, and low communication costs. Indeed, one of the NIST standards is guaranteed to be lattice-based.

There are two main families of lattice-based protocols: those based on the NTRU problem and those based on the Learning With Errors (LWE) problem. The security of both can be reduced to long-studied problems in lattice theory. There are also several variations to each problem, with partial reductions between each other. Interestingly, lattice-based cryptography has also opened up new possibilities. A fully homomorphic encryption protocol was developed based on lattice problems, paving the way for the development of several new schemes that offer interesting properties. Homomorphic encryption thus has the potential to deeply transform several fields and impact privacy-focused applications, which makes it an exciting area of research.

On the public-key encryption side, one of the four finalists for the NIST standardization process is Saber, a key exchange mechanism based on a derandomized module variant of LWE. Saber consists of a Diffie-Hellman-like key exchange protocol, which is then transformed into an IND-CPA encryption scheme, and finally into an IND-CCA secure key encapsulation mechanism. The design of Saber relies on small secrets and power-of-two moduli. This contributes to high performance, but it also poses interesting implementation challenges. Research on Saber is still ongoing, and new techniques and implementations are being developed. In particular, side-channel security and masking performance are being studied, and the results will determine the future of the protocol.

2021.03.11. -- Speaker: Richard Küng (Johannes Kepler University, Linz)

Title: The classical shadow formalism and (some) implications for quantum machine learning

Abstract: Extracting important information from a quantum system as efficiently and tractably as possible is an important subroutine in most near-term applications of quantum hardware. We present an efficient method for constructing an approximate classical description of a quantum state using very few measurements of the state. This description, called a classical shadow, can be used to predict many different properties. The required number of measurements is independent of the system size and saturates information-theoretic lower bounds. Subsequently, we combine classical shadows with machine learning (ML). This combination showcases that training data obtained from quantum experiments can be very empowering for classical ML methods. More precisely, we study the complexity of training classical and quantum ML models for predicting outcomes of physical experiments. We prove that, a classical ML model can provide accurate predictions on average by accessing measurement outcomes of quantum experiments a number of times comparable to the optimal quantum ML model. Exponential quantum ML advantages do, however, remain possible if we insist on accurate worst-case prediction.

2021.02.25. -- Speaker: Géza Tóth (University of the Basque Country, Bilbao)

Title: Quantum metrology from a quantum information science perspective

Abstract: We discuss how quantum systems can be used for parameter estimation. We present the central notions of the field such as the quantum Fisher information and the Cramér-Rao bound. We review basic findings on how the precision of the parameter estimation scales with the number of particles in a linear interferometer. The best scaling achievable is quadratic, however, quantum entanglement is needed to surpass the linear or shot-noise scaling. Finally, we explain how uncorrelated noise limits the highest achievable precision in practice. We present the theory of quantum metrology based on concrete setups using highly entangled quantum states, such as Greenberger-Horne-Zeilinger states, spin squeezed states, Dicke states and singlet states.

2021.02.11. -- Speaker: Katalin Friedl (Budapest University of Technology and Economics)

Title: Bevezetés a rejtett részcsoportok problémájába (inaugural lecture in Hungarian)

Abstract: Több jól ismert kvantumalgoritmus (pl. Simon, Shor) lényege a rejtett részcsoport probléma egy speciális esetének megoldása, amiben nagy szerepet kap a Fourier-transzformáció is. Látni fogjuk, hogyan értelmezik a Fourier-transzformációt általában véges csoportokra, és hogyan segít ez a rejtett részcsoport megtalálásában a kommutatív esetben. Szó lesz nemkommutatív csoportokról is - ahol csak néhány esetben ismert hatékony kvantumalgoritmus (de ezek részleteiről most nem lesz szó). Megmutatom a rejtett részcsoport probléma és a gráfizomorfizmus közötti kapcsolatot - sajnos itt nemkommutatív csoporton kellene megoldani a problémát.