CS Seminar

Quantum computing’s potential relies heavily on innovative software that bridges the gaps between algorithms, hardware, and system support, and between current capabilities and the future vision for the field.

Minimizing the energy of a many-body system is a fundamental problem in many fields. Although we hope a quantum computer can help us solve this problem faster than classical computers, we have a very limited understanding of where a quantum advantage may be found. In this talk, I will present some recent theoretical advances that shed light on quantum advantages in this domain. First, I describe rigorous analyses of the Quantum Approximate Optimization Algorithm applied to minimizing energies of classical spin glasses.

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.

It is an exciting time for quantum computing where prototypes of early-stage quantum computers are becoming available at your fingertips through clouds.  Conventional computer science study of quantum computing has been focusing on its algorithm and complexity perspective.

Quantum computing is at an exciting moment in its history, with some high-profile experimental successes in building programmable quantum devices.  That said, these quantum devices (at least in the near term) will be restricted in several ways, raising questions about their power relative to classical computers. In this talk, I will present three results which give us a better understanding of these near-term quantum devices, revealing key features which make them superior to their classical counterparts.

Over the last half-century, theoreticians have outlined a quantum path to provably secure communication, unprecedented sensor sensitivities, and a quantum advantage to solving problems that are classically hard. However, cutting-edge research in quantum algorithms is often detached from exciting progress in quantum hardware engineering. This has created a gap between algorithmic requirements and hardware capabilities.

Quantum computers will reshape the landscape of cryptography. On the one hand, they threaten the security of most modern cryptosystems. On the other, they offer fundamentally new ways to realize tasks that were never before thought to be possible. Crucially, cryptography is also a powerful lens through which to understand quantum computation. In this talk, I will explore the interplay between quantum computation and cryptography, and the many exciting questions at this intersection.

The software system is one essential and critical component in a quantum computing system. However, existing quantum software infrastructures are mainly designed for small-scale quantum computers while they cannot effectively accommodate large-scale quantum computing systems. In this talk, I will first summarize the challenges in designing quantum software systems as the sizes of quantum computer systems continue to grow.

Interactive proof systems are a classic idea in theoretical computer science, and have led to fundamental advances in complexity theory (hardness of approximation and the PCP theorem) and cryptography. Remarkably, in quantum information, interactive proof systems with multiple provers have become an important tool for studying quantum entanglement, extending the pioneering work of Bell in the 1960s. In this talk I will discuss recent progress in characterizing the power of the complexity class MIP* of such proof systems where the provers share entanglement.

The "curse of dimensionality" is a central bottleneck in efficient processing of quantum information.  It arises from the existence of highly complicated quantum states on a modest number of qubits, and the freedom of running intricate protocols with such states. Developing ways to overcome this bottleneck is an outstanding problem in several domains of quantum information theory. The leading proposal in two such domains, quantum communication complexity  and quantum Hamiltonian complexity, advances the role of entropy in the analysis of underlying quantum objects.