QuICS seminar

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 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.

Resource theories have mushroomed in quantum information theory over the past decade. Resource theories are simple models for situations in which constraints limit the operations performable and the systems accessible. In a fixed-temperature environment, for instance, the first law of thermodynamics constrains operations to preserve energy, and thermal states can be prepared easily.  Scores of resource-theory theorems have been proved. Can they inform science beyond quantum information theory?

We derive general results relating revivals in the dynamics of quantum many-body systems to the entanglement properties of energy eigenstates. For a lattice system of N sites initialized in a low-entangled and short-range correlated state, our results show that a perfect revival of the state after a time at most poly(N) implies the existence of "quantum many-body scars", whose number grows at least as the square root of N up to poly-logarithmic factors.

I will present our recent advances in the formal verification of post-quantum security. Our framework includes a logic for reasoning about quantum programs (qRHL, quantum relational Hoare logic) and a tool for computer-aided verification in qRHL. We have used this framework to verify the post-quantum security of the Fujisaki-Okamoto transform for building encryption schemes. I will give an overview of the logical foundations and of our experiences when verifying a real-life cryptosystem.

Quantum computing, once just a theoretical field, is quickly advancing as physical quantum technology increases in size, capability, and reliability. In order to fully harness the power of a general quantum computer or an application-specific device, compilers and tools must be developed that optimize specifications and map them to a realization on a specific architecture. In this talk, a technique and prototype tool for synthesizing algorithms into a quantum computer is described.

Zero-knowledge proofs are a fundamental building block in classical Cryptography, having far-reaching applications. Recently, there has been some effort in improving our understanding of Zero-knowledge for quantum complexity classes, that will hopefully lead us to striking objects as in the classical case.

According to Feynman, quantum computers will be the most suitable platforms to simulate nature. Although as of today, quantum computers with capability and reliability comparable or beyond those of classical computers do not exist, rapid progress in quantum technologies, and a vast growth in interest and resources in quantum information sciences, promise a future in which quantum computation may play an important role in addressing computationally-challenging problems in all areas of sciences and technology.