Seminar

We explore the provable advantages and limitations of quantum computers in three contexts. First, we consider how to design quantum algorithms by studying a result on the regular languages. Next, we discuss unconditional quantum advantage in the context of shallow circuits. We give separations with relation problems and interactive problems. Finally, we explore the problem of efficiently learning quantum states.

Noise is widely regarded as a major obstacle to quantum computing. Fortunately, this problem can be solved efficiently due to the existence of the threshold theorem. It states that under sufficiently weak noise and universal assumptions, there always exists an active quantum error correction protocol with only logarithmic hardware overhead. One may ask: can a similar result be obtained for autonomous (passive) error correction, where noise is suppressed by natural or engineered dissipation?

In this talk, I will focus on the smallest quantum error-correcting code: the perfect 5 qubit code found by Laflamme et al. I will write down the codewords and the stabilizer generators. I will talk about which errors are correctable and how to identify and correct them via a syndrome lookup table. I will discuss the probability of getting a logical error when using a depolarizing noise channel and the resulting pseudo-threshold. Lastly I will talk about implementing logical gates via naturally fault-tolerant transversal gates.

In gradient descent dynamics of neural networks, the top eigenvalue of the Hessian of the loss (sharpness) displays a variety of robust phenomena throughout training. This includes early time regimes where the sharpness may decrease during early periods of training (sharpness reduction), and later time behavior such as progressive sharpening and edge of stability. We demonstrate that a simple $2$-layer linear network (UV model) trained on a single training example exhibits all of the essential sharpness phenomenology observed in real-world scenarios.

The goal of this talk is to go over some of the intuition that lies behind quantum cryptography protocols. We will begin by addressing the advantages that quantum cryptography protocols have over classical cryptography as well as the difference between quantum and post-quantum cryptography. We will then highlight one of the advantages that quantum cryptography has, no-cloning, and discuss why it allows us to construct primitives that are impossible in the classical setting (such as position verification and unclonable encryption).

The theory of noise, measurement, and amplification in quantum information processing devices deviates substantially from its counterparts in conventional engineering disciplines. Quantum-mechanical systems exhibit distinctly different behavior compared to their classical counterparts, necessitating a revised theoretical framework.

In order to simulate interacting fermionic systems on quantum computers, the first step is to encode the physical Hamiltonian into qubit operators. Existing encoding procedures such as the Jordan-Wigner transformation and Bravyi-Kitaev transformation are not resource efficient because they encode each second-quantized fermionic operator into a Pauli string without incorporating the structure of the Hamiltonian in question.

Light emitters within two-dimensional arrays have been demonstrated to exhibit various cooperative effects, including super- and sub-radiance, collective line-shift and linewidth, and topological features such as Chern bands and edge states. Motivated by these intriguing properties, the realization of emitter arrays has been attempted in cold atom experiments, which nevertheless cannot access the deep subwavelength regime.

Continuous optimization problems arise in virtually all disciplines of quantitative research, including applied mathematics, computer science, and operations research. While convex optimization has been well studied in the past decades, nonconvex optimization generally remains intractable in theory and practice. Quantum computers, an emerging technology that exploits quantum physics for information processing, could pave an unprecedented path toward nonconvex optimization.

We construct a total function which exhibits an exponential quantum parallel query advantage despite having no sequential query advantage. This is interesting for two reasons: (1) For total functions an exponential sequential query advantage is impossible, and was conjectured to not be possible in the parallel setting by Jeffery et al (2017)— our result refutes this conjecture.