Seminar

Quantum circuits are believed to be hard to simulate by classical computers. In realistic situations, there is always noise, which makes the quantum gates imperfect. In this talk, I consider classical simulation of several different ensembles of quantum circuits without fault-tolerance, such that the strength of the noise is regarded as a constant (not scaling with the system size). The noise model we consider is mixture of Pauli errors, which includes depolarizing noise as a special case.

This talk is about certifying high-dimensional entanglement in the setting of non-local games. In a non-local game, two or more non-communicating, but entangled, players cooperatively try to win a game consisting of a one-round interaction with a classical referee. In this talk, I will describe a strikingly simple two-player non-local game with the property that an epsilon-close to optimal strategy requires the two players to share an entangled state of dimension 2^{1/poly(epsilon)}.

This talk will discuss techniques that were used in the paper "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" to reduce the estimated spacetime cost of factoring integers using a quantum computer by over two orders of magnitude. Most of savings come from classical circuit optimization techniques that have been adjusted to work around limitations imposed by the quantum domain.

Quantum error-correcting codes are constructed that embed a finite-dimensional codespace in the infinite-dimensional Hilbert state space of the rotational degrees of freedom of a rigid body. Such codes allow for protection against diffusion in the body's orientation as well as small kicks in the body's angular momentum. We mention realizations of the logical states of such codes in molecules, atomic ensembles, and nanoparticles. Such states are part of a "partially Fourier-transformed" basis that interpolates between the position and momentum bases of the system.

I will begin by reviewing general results on the equilibration of isolated quantum systems, including sufficient conditions for equilibration and a discussion of the timescales of this equilibration process. I will then focus on new results on the dynamics of two-point correlation functions. These include conditions under which correlation functions factorize at late times, and bounds on their temporal fluctuations. For auto-correlation functions we provide an upper bound on the timescale at which they reach the factorized late time value.

In this paper, we construct a new scheme for delegating a large circuit family, which we call "C+P circuits". "C+P" circuits are the circuits composed of Toffoli gates and diagonal gates. Our scheme is non-interactive, only requires small quantum resources on the client side, and can be proved secure in the quantum random oracle model, without relying on additional assumptions, for example, the existence of fully homomorphic encryption.

Future efforts to build quantum networks are likely to rely on the ability to interface and entangle disparate quantum systems. Two systems of interest in the realm of quantum information are trapped ions and Rydberg atoms. These systems operate at vastly different wavelengths so direct photonic interaction has been a challenge, however, establishing a photonic link would open the door to hybrid protocols leveraging the advantages of each system.

Product formulas (aka Trotterization) provide a straightforward yet surprisingly efficient approach to quantum simulation. We show that this algorithm can simulate an $n$-qubit Hamiltonian with nearest-neighbor interactions evolving for time $t$ using only $(nt)^{1+o(1)}$ gates. While it is reasonable to expect this complexity---in particular, this was claimed without rigorous justification by Jordan, Lee, and Preskill---we are not aware of a straightforward proof.

This talk is motivated by three (seemingly unrelated) questions:1. For which tasks do quantum algorithms outperform classical computation? 2. Does parallel computing always offer a speed-up, or are some tasks inherently sequential? 3. Do randomized algorithms have deterministic counterparts with similar memory footprint?We make progress on all three questions by exploiting a common phenomenon at the core of their analysis: in all cases, the studied computational devices can be well-approximated by sparse multivariate polynomials.

When one develops quantum information processors with larger numbers of qubits, correlated dephasing errors and crosstalk can have an important effect on the overall accuracy of the device. Detecting these correlations can require a large number of measurements. We consider the special case where the correlations are sparse, i.e., for a system of n qubits, there are k pairs of qubits that are correlated, where k << n(n-1)/2.