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