Seminar

Given the unprecedented effort by academia and industry (e.g., IBM and Google), quantum computers with hundred(s) of qubits are at the brink of existence with the promise of outperforming any classical computer. Demonstration of computational advantages of noisy near-term quantum computers over classical computers is an imperative near-term goal. The foremost candidate task for showing this is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit.

Can a quantum computer help us analyze a large classical data set? Data stored classically cannot be queried in superposition, which rules out direct Grover searches, and it can often be classically accessed with some level of parallelism, which would negate the advantage of Grover even if it were possible.

Given a nonlocal game, we'd like to be able to find the optimal quantum winning probability, and the set of optimal strategies. However, the recent MIP*=RE result implies that we cannot determine the quantum winning probability to within constant error.

Exactly solvable models are essential in physics. For many-body spin-1/2 systems, an important class of such models consists of those that can be mapped to free fermions hopping on a graph. We provide a complete characterization of models which can be solved this way. Specifically, we reduce the problem of recognizing such spin models to the graph-theoretic problem of recognizing line graphs, which has been solved optimally. A corollary of our result is a complete set of constant-sized commutation structures that constitute the obstructions to a free-fermion solution.

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.

The interaction of a single photon with an individual two-level system is the textbook example of quantum electrodynamics. Achieving strong coupling in this system has so far required confinement of the light field inside resonators or waveguides. Experiments with Rydberg superatoms [1,2] have demonstrated the ability to realize strong coupling to a propagating light pulse containing only a few photons in free space.

The past decade has seen a dramatic increase in the degree, quality, and sophistication of control over quantum-mechanical interactions available between artificial degrees of freedom in a variety of experimental platforms. The geometrical structure of these interactions, however, remains largely constrained by the underlying rectilinear geometry of three-dimensional Euclidean space.

Simulating the Hamiltonian dynamics of quantum systems is one of the most promising applications of digital quantum computers. In this dissertation, we develop an understanding of quantum simulation algorithms concerning their design, analysis, implementation, and application.

We are in the midst of a second quantum revolution fueled by the remarkable quantum mechanical properties of physical systems. Therefore, characterization and engineering of these quantum systems is vitally important in emerging quantum optical science and technology. The Wigner quasi-probability distribution function provides such a characterization.

Density matrices represent our knowledge about quantum systems. We can use them to calculate any physical property of quantum systems via the Born rule. Since the density matrix grows exponentially with the number of qubits, already at about 50 qubits, simply writing and storing the density matrix in a classical computer, becomes impossible, let alone calculating anything with it.