Tuesday January 24, 2017 12:00 PM

Overlapping Qubits

Speaker: Thomas Vidick, Computing and Mathematical Sciences, California Institute of Technology
Location: Annenberg 105

Small- to medium-scale quantum computers, and larger-scale quantum optimization devices, are now being built. What tests should be run to verify the behavior of these systems? This is not a trivial problem. The systems are large enough to simulate interesting quantum physics, but too large to simulate using classical computers, so we cannot check their answers. The systems are also too small and too noisy to run quantum algorithms with easily verified answers, such as Shor's factoring algorithm. Full tomography of a quantum system with more than eight to ten qubits is too complex.

We focus on certifying the dimensionality of a quantum system. Qubits in a real physical system are generally not perfectly independent, but might have small pairwise overlaps. We give both positive and negative results (which is which depends on your perspective!):
On the one hand, we show that allowing for even only slight overlaps, n qubits can fit in just polynomially many dimensions. Thus, even before considering issues like noise, a physical system of n qubits might inherently lack any potential for exponential power.
On the other hand, we give a test to certify exponential dimensionality. The test is simple enough that it could potentially be run in experiments.

Joint work with Rui Chao, Ben Reichardt, and Chris Sutherland.

Series IST Lunch Bunch

Contact: Diane Goodfellow