Speaker: Ramis Movassagh, IBMTitle: Proof of average-case #P- hardness of random circuit sampling with some robustness, and a protocol for blind quantum computationDate: 09/05/2019Time: 11:00 AM - 12:00 PMPlace: 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

- People
- All
- Regular Faculty
- Postdocs
- Fixed Term/Visiting Faculty
- Specialists and Instructors
- Adjunct Faculty
- Emeriti
- Graduate Students
- Teaching Assistants
- Staff
- Administration
- Diversity, Equity, Inclusiveness
- Faculty Honors

- Research
- Faculty Research Interests
- Seminars
- Seminars by Week
- Geometry & Topology
- MCIAM
- MathSciNet
- Institute of Mathematical Physics
- Math Library
- Phillips Lecture

- Undergraduate
- Undergraduate Program
- Class Pages
- Student Portal
- Webwork
- Math Learning Center
- Actuarial Science
- Advising Information
- Override Request
- Math Placement Service
- Herzog Competition
- Scholarships
- Exchange Program
- Sample Finals
- Multicultural Center Feasibility