Welcome to the 19th TQC Conference!

Potential and Limitations of Near-Term Quantum Computing

Quantum computers promise the efficient solution of some highly structured computational problems that are classically intractable. While for many years they have been primarily objects of theoretical study, only recently have efforts to build intermediate-scale quantum computers taken off. This creates an interesting state of affairs, but at the same time, it begs the question of what such devices are, practically speaking, good for. In this talk, we will present some encouraging as well as—emphasizing the latter—discouraging insights into near-term quantum computing. We will discuss rigorous quantum advantages in paradigmatic problems [1,2] and explore the use of quantum computers in machine learning [3,4] and optimization [5]. The second part of the talk will focus on the significant limitations that arise. We will emphasize identifying limitations to quantum error mitigation for shallow quantum circuits in the worst case [6]. Interestingly, it may depend on the nuances of non-unital quantum noise to what extent quantum computing without error correction may be feasible [7]. We will also provide efficient classical algorithms for instances of quantum algorithms, hence "de-quantizing" them [7-9]. The talk will conclude with the note that quantum simulation remains, to date, one of the most promising applications of near-term quantum devices [10,11].

[1] Rev. Mod. Phys. 95, 035001 (2023).
[2] arXiv:2307.14424, Nature Comm. (2024).
[3] Nature Comm. 15, 434 (2024).
[4] Nature Comm. 15, 2277 (2024).
[5] Science Adv. 10, eadj5170 (2024).
[6] arXiv:2210.11505, Nature Phys. (2024).
[7] arXiv:2403.13927 (2024).
[8] arXiv:2309.11647 (2023).
[9] Phys. Rev. Lett. 131, 100803 (2023).
[10] Nature Comm. 14, 3895 (2023).
[11] arXiv:2108.08319, Nature Comm. (2024).

Forward and Backward Mappings for Quantum Graphical Models

Graphical models offer a unifying framework for various statistical learning algorithms and models. Central to these models are the forward and backward mapping problems, which have been studied through both exact and approximate algorithms. This talk explores these mapping problems within the context of quantum graphical models, where quantum states generalize classical probability distributions.
The forward mapping problem involves deriving mean parameters from model parameters and is closely linked to approximating the partition function---a typically challenging task often requiring heuristics and approximations. We'll discuss quantum belief propagation, which has shown success in one-dimensional systems, as well as variational methods such as Markov entropy decomposition that tackle the problem from an optimization perspective.
The task of the backward mapping problem aims to compute model parameters from mean parameters. It is related to the Hamiltonian learning problem, a topic of growing interest in quantum information science lately. We'll review some existing algorithms and introduce the quantum iterative scaling (QIS) algorithm that reduces the backward mapping problem to a series of forward mapping problems. We'll present a convergence proof for QIS and demonstrate its advantages over gradient descent methods. Furthermore, we'll explore how quasi-Newton methods can enhance QIS and gradient descent algorithms, showcasing significant efficiency improvements.

Understanding Cryptographic Hardness in a Quantum World

A flurry of exciting, recent work has shown that the mathematical hardness required to realize cryptosystems such as bit commitments and secure computation in a quantum world can be significantly weaker than the hardness required for classical cryptography. This talk will discuss recent progress and some remaining challenges in understanding the assumptions that enable cryptography in a quantum world.

Quantum cryptography without one-way functions

The existence of one-way functions is the minimum assumption in classical cryptography. On the other hand, in quantum cryptography where quantum computing and quantum communications are possible, recent studies have demonstrated that the existence of one-way functions is not necessarily the minimum assumption.
Several new fundamental primitives have been introduced, such as pseudorandom unitaries, pseudorandom states, one-way state generators, EFI pairs, and one-way puzzles. They seem to be weaker than one-way functions, but still imply many useful applications, such as secret-key encryption, message authentication codes, digital signatures, private-key quantum money, commitments, and multiparty computations, etc. In this talk, I explain the basics of this “quantum cryptography without one-way functions” and give many open problems that I want to know the answers to.