Search Talks

I will review work by myself and others in recent years on the use of randomization in quantum circuit optimization.  I will present general results showing that any deterministic compiler for an approximate synthesis problem can be lifted to a better random compiler.  I will discuss the subtle issue of what "better" means and how it is sensitive to the metric and computation task at hand.  I will then review specific randomized algorithms for quantum simulations, including randomized Trotter (Su & Childs) and my group's work on the qDRIFT and SPARSTO algorithms.  The qDRIFT algorithm is of particular interest as it gave the first proof that Hamiltonian simulation is possible with a gate complexity that is independent of the number of terms in the Hamiltonian.  Since quantum chemistry Hamiltonians have a very large ( ~N^4) number of terms, randomization is especially useful in that setting. I will conclude by commenting on a recent Caltech paper with interesting results on the derandomization of random algorithms!  Some of the relevant preprints include:

https://arxiv.org/abs/1910.06255

https://arxiv.org/abs/1811.08017

https://arxiv.org/abs/1612.02689

Discriminating between unknown objects in a given set is a fundamental task in experimental science. Suppose you are given a quantum system which is in one of two given states with equal probability. Determining the actual state of the system amounts to doing a measurement on it which would allow you to discriminate between the two possible states. It is known that unless the two states are mutually orthogonal, perfect discrimination is possible only if you are given arbitrarily many identical copies of the state.

In this talk we consider the task of discriminating between quantum channels, instead of quantum states. In particular, we discriminate between a pair of unitary channels acting on a quantum system whose underlying Hilbert space is infinite-dimensional. We prove that in contrast to state discrimination, one only needs a finite number of uses of these channels in order to discriminate perfectly between them. Furthermore, no entanglement is needed in the discrimination task. The measure of discrimination is given in terms of the energy-constrained diamond norm, and a key ingredient of the proofs of these results is a generalization of the Toeplitz-Hausdorff Theorem of convex analysis . Moreover, we employ our results to study a novel type of quantum speed limits which apply to pairs of quantum evolutions. This work was done jointly with Simon Becker (Cambridge), Ludovico Lami (Ulm) and Cambyse Rouze (Munich).

Unitary t-designs are the bread and butter of quantum information theory and beyond. An important issue in practice is that of efficiently constructing good approximations of such unitary t-designs. Building on results by Aubrun (Comm. Math. Phys. 2009), we prove that sampling dtpoly(t,logd,1/ϵ) unitaries from an exact t-design provides with positive probability an ϵ-approximate t-design, if the error is measured in one-to-one norm. As an application, we give a randomized construction of a quantum encryption scheme that has roughly the same key size and security as the quantum one-time pad, but possesses the additional property of being non-malleable against adversaries without quantum side information. Joint work with Cécilia Lancien.

To analyze the performance of adaptive measurement protocols for the detection and quanti cation of state resources, we introduce the framework of quantum preparation games. A preparation game is a task whereby a player sequentially sends a number of quantum states to a referee, who probes each of them and announces the measurement result. The measurement setting at each round, as well as the final score of the game, are decided by the referee based on the past history of settings and measurement outcomes. We show how to compute the maximum average score that a player can achieve under very general constraints on their preparation devices and provide practical methods to carry out optimizations over n-round preparation games. We apply our general results to devise new adaptive protocols for entanglement detection and quanti cation. Given a set of experimentally available local measurement settings, we provide an algorithm to derive, via convex optimization, optimal n-shot protocols for entanglement detection using these settings. We also present families of non-trivial adaptive protocols for multiple-target entanglement detection with arbitrarily many rounds. Surprisingly, we find that there exist instances of entanglement detection problems with just one target entangled state where the optimal adaptive protocol supersedes all non-adaptive alternatives.

The Petz recovery channel plays an important role in quantum information science as an operation that approximately reverses the effect of a quantum channel. The pretty good measurement is a special case of the Petz recovery channel, and it allows for near-optimal state discrimination. A hurdle to the experimental realization of these vaunted theoretical tools is the lack of a systematic and efficient method to implement them. We rectify this lack using the recently developed tools of quantum singular value transformation and oblivious amplitude amplification, providing a quantum algorithm to implement the Petz recovery channel. Our quantum algorithm also provides a procedure to perform pretty good measurements when given multiple copies of the states that one is trying to distinguish.

Using the same toolbox, we also develop a quantum algorithm for enacting the polar decomposition, a workhorse in linear algebra. This provides an alternative route to implementing a pretty-good measurements for the special case of pure states, which speeds up the general-purpose algorithm developed above.

Zero-knowledge proofs are one of the cornerstones of modern cryptography. It is well known that any language in NP admits a zero-knowledge proof. In the quantum setting, it is possible to go beyond NP. Zero-knowledge proofs for QMA have first been studied in a work of Broadbent et al (FOCS'16). There, the authors show that any language in QMA has an (interactive) zero-knowledge proof. In this talk, I will describe an idea, based on quantum teleportation, to remove interaction at the cost of adding an instance-independent preprocessing step. Assuming the Learning With Errors problem is hard for quantum computers, the resulting protocol is a non-interactive zero-knowledge argument for QMA, with a preprocessing step that consists of (i) the generation of a Common Reference String and (ii) a single (instance-independent) quantum message from the verifier to the prover.

This is joint work with Thomas Vidick and Tina Zhang

We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm.
Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest.

Joint work with Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi Soleimanifar

We reconsider the black hole firewall puzzle, emphasizing that quantum error-correction, computational complexity, and pseudorandomness are crucial concepts for understanding the black hole interior. We assume that the Hawking radiation emitted by an old black hole is pseudorandom, meaning that it cannot be distinguished from a perfectly thermal state by any efficient quantum computation acting on the radiation alone. We then infer the existence of a subspace of the radiation system which we interpret as an encoding of the black hole interior. This encoded interior is entangled with the late outgoing Hawking quanta emitted by the old black hole, and is inaccessible to computationally bounded observers who are outside the black hole. Specifically, efficient operations acting on the radiation, those with quantum computational complexity polynomial in the entropy of the remaining black hole, commute with a complete set of logical operators acting on the encoded interior, up to corrections which are exponentially small in the entropy. Thus, under our pseudorandomness assumption, the black hole interior is well protected from exterior observers as long as the remaining black hole is macroscopic. On the other hand, if the radiation is not pseudorandom, an exterior observer may be able to create a firewall by applying a polynomial-time quantum computation to the radiation.