QuICS seminar

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f : {-1, 1}^n to {-1, 1}, the two-party bounded-error quantum communication complexity of 2-bit distributed versions of f is O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is in contrast to the classical randomized analogue of this statement, where the log n factor is absent. A natural question is if this O(log n) factor can be avoided. Aaronson and Ambainis (FOCS'03) showed that this factor is avoidable when f = OR.

Interference is an essential part of quantum mechanics.  However, an important class of Hamiltonians considered are those with "no sign problem", where all off-diagonal matrix elements of the Hamiltonian are non-negative.  This means that the ground state wave function can be chosen to have all amplitudes real and positive.  In a sense, no destructive interference is possible for these Hamiltonians so that they are "almost classical", and there are several simulation algorithms which work well in practice on classical computers today.  In this talk, I'll discuss what ha

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.