# Quantum Information 2018 at the CMSA

On April 23-24, 2018, Zhengwei Liu and Arthur Jaffe from the Picture Language Project at Harvard organized a workshop on Quantum Information at the Center of Mathematical Sciences and Application, under the auspices of Shing-Tung Yau. Although this workshop focused mostly on local Cambridge, Massachusetts participation, a small number of key speakers came both nationally and internationally. The scheduled list of talks is below.

However, because of logistical reasons which prevented some speakers from attending, additional speakers were added. These added talks include:

1. Kaifeng Bu spoke on Resource theory of magic states.

Schedule

Monday April 23

 Time Speaker Title/Abstract 8:30 – 9:00am Breakfast 9:00 – 10:00am Fernando G.S.L Brandão   Caltech Title: New Directions in Quantum Algorithms: Thermalization meets Convex Optimization Abstract: I will discuss recent results on quantum algorithms for semidefinite programming, an important class of convex optimization problems with widespread applications (from resource allocation to approximating hard combinatorial problems). I will present a connection of the task of solving semidefinite programs (SDPs) to the task of quantum Gibbs sampling (which consists of computing properties of thermal states at finite temperature on a quantum computer). I will then discuss results on the time of thermalization of many-body quantum systems and show that they directly give quantum speed-ups for SDPs. I will also argue that the quantum algorithm for SDPs can be seen as a generalization of quantum annealing and is a good candidate for realisation on small quantum computers. 10:00 – 10:20am Break 10:20 – 11:20am Iris Cong   Harvard Title: Universal Quantum Computation with Gapped Boundaries   Abstract: In this talk, I will discuss topological quantum computation with gapped boundaries of two-dimensional topological phases. I will first introduce the algebraic framework for topological quantum computation and gapped boundaries. Next, I will present systematic methods to encode quantum information topologically using gapped boundaries, and to perform topologically protected operations on this encoding. In particular, I will introduce a new computational primitive of topological charge measurement and present a symmetry-protected implementation of this primitive. Throughout the talk, a concrete physical example – the case of bilayer fractional quantum Hall 1/3 systems [mathematically, D(Z3)], will be discussed. For this example, we have a qutrit encoding and an abstract universal gate set. If a practical implementation is found for the required topological charge measurement, these boundaries will give rise to a direct physical realization of a universal quantum computer based on a purely Abelian topological phase. 11:20 – 1:20pm Lunch 1:20 – 2:20pm Isaac Chuang   MIT Title: The enduring surprises of SU(2)   Abstract: The dynamics of a qubit have long been understood to be at the heart of quantum algorithms and quantum protocols, from search to one-qubit teleportation. And cascaded single-qubit operations, known as composite quantum gates, have provided powerful ways to correct systematic errors. Here, we generalize these understandings based on new results addressing the nonlinearity of single qubit dynamics: a methodology for solving the inverse mathematical problem, to find a sufficient gate sequence, given a desired response function.We apply this methodology to show how single qubits and “qubitized” systems may be harnessed for Heisenberg-limited sensing, and optimal quantum simulation of multi-qubit Hamiltonians. 2:20 – 2:40pm Break 2:40 – 3:40pm Renato Renner   ETH Zürich Title: Quantum information and foundations   Abstract: The black hole information paradox is a prominent example of a thought experiment which indicates that the law that quantum states evolve unitarily may not be valid universally. In this talk, I will present another information-theoretic thought experiment, which also leads to contradictions if one takes the universal validity of unitary state evolution for granted. However, in contrast to the black hole information paradox, the experiment does not require any assumptions about gravity. 3:40 – 4:00pm Break 4:00 – 5:00pm Emil KhabiboullineHarvard Title: Nonlocal Interferometry with Quantum Networks   Abstract: We propose a method for optical interferometry in telescope arrays connected via networks consisting of entangled quantum mechanical nodes. In our approach, the quantum states of photons from weak distant sources, including their arrival time, are stored in quantum memories in a binary qubit encoding. These stored states are subsequently interrogated via coherent, nonlocal readout by means of entanglement-assisted parity checks across the array, which effectively circumvents transmission losses between the nodes, allowing for imaging of faint sources with improved angular resolution. The state transfer to memory enables processing such as a quantum Fourier transform applied over the network. Compared with prior proposals, our scheme offers an exponential decrease in required entanglement resources, making its experimental implementation feasible with near-term technology.

Tuesday, April 24

 Time Speaker Title/Abstract 8:30 – 9:00am Breakfast 9:00 – 10:00am Aram Harrow   MIT Title: Small quantum computers and large classical data sets   Abstract: Can we use Grover’s algorithm to quadratically speed up finding the best model fitting a data set? What about adiabatic optimization, quantum variational methods, or other more sophisticated algorithms? The answer is not obvious if we are not given the ability to query the data set in superposition. One approach is to choose a representative subset of the data and run quantum optimization algorithms on this subset. This talk will explore methods for doing so that use a classical computer either offline or in an interactive protocol together with the quantum computer. These methods allow Grover-like speedups for problems that include clustering in metric spaces and saddle-point optimization. 10:00 – 10:20am Break 10:20 – 11:20am Adam Bene Watts   MIT Title : Algorithms and Bounds for XOR Games.   Abstract : The entangled value of an XOR game is the maximal win probability obtained by players who cannot communicate, but share a quantum state of possibly unbounded dimension. Studying gives us a precise tool for characterizing the power of entanglement. For any two player XOR game is easy to compute, as Tsirelson gave an efficient semidefinite program which exactly computes a game’s value. Conversely, for XOR games with three or more players computing is at least NP-hard, and the best known algorithm runs with no guarantee on its convergence time.In this talk we introduce a necessary — and efficiently computable — linear algebraic criterion for an XOR game with any number of players to have , then show this criterion is also sufficient for a important subclass of XOR games. To prove these results we first consider ncSoS proofs that an XOR game has entangled value less than one, then show these proofs have a straightforward combinatorial interpretation. We also introduce a simple class of strategies which exist dual to this condition, so a game admits a value one strategy exactly when this condition is not satisfied. These results allow us to construct XOR games with interesting properties, characterize the value of random XOR games, and may provide a first step for developing a poly-time algorithm to decide if for arbitrary XOR games. 11:20 – 1:20pm Lunch 1:20 – 2:20pm Mikhail D. Lukin   Harvard Title: Quantum machines based on Rydberg atom arrays 2:20 – 2:40pm Break 2:40 – 3:40pm Jacob Biamonte   Skoltech Title: Quantum Machine Learning Matrix Product States Abstract: Matrix product states minimize bipartite correlations to compress the classical data representing quantum states. Matrix product state algorithms and similar tools—called tensor network methods—form the backbone of modern numerical methods used to simulate many-body physics. Matrix product states have a further range of applications in machine learning. Finding matrix product states is in general a computationally challenging task, a computational task which we show quantum computers can accelerate. We present a quantum algorithm which returns a classical description of a $k$-rank matrix product state approximating an eigenvector given black-box access to a unitary matrix. Each iteration of the optimization requires $O(n\cdot k^2)$ quantum gates, yielding sufficient conditions for our quantum variational algorithm to terminate in polynomial-time. Implications include: (i) Applications of quantum random access memory are severely limited from the general restriction imposed by quantum theory in which a quantum memory itself is modified by access. Our method recursively optimizes a rank-$k$ description of a quantum state: this in turn can be accessed {\it in situ} and hence our results augment the efficiency of quantum random access memory. (ii) Recently low-depth quantum circuits for various tasks have taken center stage. We augment these studies by providing a missing theoretical backbone, both quantifying algorithms in terms of entanglement and providing lower bounds for the gate-depth needed for a computation to generate specific quantities of entanglement. (iii) Matrix product structure allows many operations to be done efficiently classically (provided one has the matrix product state to begin with). Hence, our method opens the door for hybrid quantum/classical algorithms which utilize quantum effects to determine a matrix product state and then utilizes various classical/quantum subroutines to calculate properties of matrix product states. This brings with it a host of applications in the simulation of physics and chemistry as well as in machine learning. (iv) The algorithm is general in that it works given only black-box access to a unitary matrix. In the discussion however, we drop this restriction and cast the steps needed to perform a meaningful near-term demonstration of this algorithm on a quantum computer, providing a low-rank approximation to eigenvectors of the quantum computers free- (or closely related effective) Hamiltonian, taking a large step towards a practically useful task with low-gate counts. 3:40 – 4:00pm Break 4:00 – 5:00pm Peter Shor   MIT Title: Quantum information, black holes, and scrambling time Abstract: The scrambling time of a black hole is the amount of time it takes for the black hole to evolve from a nearly unentangled state — a state where there is not much entanglement between two hemisphered to a Haar-random state, where there is nearly maximal entanglement between the two hemispheres.Recently, the conjecture has been made that the scrambling time of a black hole is order M log M, where M is the mass of the black hole in naturalunits. We present an argument that implies that for this conjecture to be true, there must be non-standard physics occuring well outside the stretched horizon of a black hole.