Quantum Information

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.

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.