Workshop on Quantum Algorithms and Devices – Part 3

1:10PM – 1:50PMQuantum Information in Space and Time Patrick Hayden (Stanford University)

Abstract: What can quantum information theory teach us about spacetime? This talk will describe two examples in which the information theoretic viewpoint has revealed unexpected and beautiful structure in spacetime.

The first example will address a basic question: where and when can a qubit be? While the no-cloning theorem of quantum mechanics prevents quantum information from being copied in space, the reversibility of microscopic physics actually requires that the information be copied in time. In spacetime as a whole, therefore, quantum information is widely replicated but in a restricted fashion. There is a simple and complete description of where and when a qubit can be located in spacetime, revealing a remarkable variety of possibilities.

The second example comes from holography. The AdS/CFT correspondence provides a concrete realization of the holographic principle, in which the physics of a “bulk” spacetime volume is completely encoded onto its boundary surface. A dictionary relates the physics of the boundary to the physics of the bulk, but the boundary interpretation of the bulk’s extra dimension has always been a bit fuzzy. I’ll explain one precise interpretation of that extra dimension as the amount of entanglement required to perform a specific boundary communications task.

1:50PM – 2:30PMWhat Condensed Matter Physicists Would Rather Not Talk About Mario Szegedy (Rutgers University)

Abstract: In the talk we discuss issues about mean field value calculations in the thermodynamic limit.

2:30PM – 3:10PMQuantum Chemistry by Quantum Simulation: Algorithms and Estimates Matthew Hastings (QuArC Team at Microsoft Research)

Abstract: Simulation of quantum chemistry is a natural application for a quantum computer. It has long been known that there are many examples of such simulation problems where the best known classical algorithm takes exponential time but a quantum computer can take polynomial time. However, the actual value of the polynomial will be very important in practice. In this talk, I will explain several improvements that reduce this polynomial, using improved circuits and term ordering. Further I explain improved estimates of the errors in these simulations, giving us a better understanding of the step size required. This work is in collaboration with Bauer, Clark, Doherty, Poulin, Troyer, Wecker, and Wiebe.

3:10PM – 3:40PMCoffee Break

Speaker Details

Patrick Hayden is a professor of physics at Stanford University. His research focuses on quantum information theory, particularly in the context of communication and cryptography. He has recently been exploring the intersection between quantum information and quantum gravity, including the black hole information paradox as well as the relationship between spacetime and entanglement.

Mario Szegedy’s research areas include computational complexity theory and quantum computing. He was awarded the Goedel Prize twice, in 2001 and 2005, for his work on probabilistically checkable proofs and on the space complexity of approximating the frequency moments in streamed data. Currently he is a distinguished professor in the Computer Science department, Rutgers University.

Matthew Hastings received his PhD in physics from MIT in 1997. He later moved into mathematical physics and quantum information. Notable results include the proof of the higher-dimensional Lieb-Schultz-Mattis theorem, the first general area law bound in one dimension, and disproving the additivity conjecture. Matthew Hastings is a principal researcher at Microsoft Research in Station Q.

Date:
Speakers:
Patrick Hayden, Mario Szegedy, and Matt Hastings
Affiliation:
Stanford University, Rutgers University, Microsoft