Department of Mathematics

Mathematical Physics and Operator Algebras

  •  Ramis Movassagh, IBM
  •  Proof of average-case #P- hardness of random circuit sampling with some robustness, and a protocol for blind quantum computation
  •  09/05/2019
  •  11:00 AM - 12:00 PM
  •  C304 Wells Hall

A one-parameter unitary-valued interpolation between any two unitary matrices (e.g., quantum gates) is constructed based on the Cayley transformation. We prove that this path induces probability measures that are arbitrarily close to the Haar measure and prove the simplest known average-case # P -hardness of random circuit sampling (RCS). RCS is the task of sampling from the output distribution of a quantum circuit whose local gates are random Haar unitaries, and is the lead candidate for demonstrating quantum supremacy in the "noisy intermediate scale quantum (NISQ)" computing era. Here we also prove exp(-Θ(n^4 )) robustness with respect to additive error. This overcomes issues that arise for extrapolations based on the truncations of the power series representation of the exponential function. (Dis)Proving the quantum supremacy conjecture requires an extension of this analysis to noise that is polynomially small in the system's size. This remains an open problem. Lastly, an efficient and private protocol for blind quantum computation is proposed that uses the Cayley deformations proposed herein for encryption. This is an efficient protocol that only requires classical communication between Alice and Bob. ** The talk is self-contained and does not require any pre-req beyond basic linear algebra (e.g, knowing what a unitary matrix is).



Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science