# 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 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.