- Ramis Movassagh, IBM
- Unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling
- 10/04/2018
- 11:00 AM - 12:00 PM
- C304 Wells Hall
Demonstration of computational advantages of Noisy Intermediate-Scale Quantum (NISQ) computers over classical computers is an imperative near-term goal, especially with the exuberant experimental frontier in academia and industry. Because of a large industrial push (e.g., from IBM and Google), NISQ computers with hundred(s) of qubits are at the brink of existence with the promise of outperforming any classical computer.
A goal-post is to demonstrate the so called {\it quantum computational supremacy}, which is to show that a NISQ computer can perform a computational task that is tremendously difficult for any classical (super-)computer. The foremost candidate problem to show quantum supremacy is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. For example, this is Google's primary current objective, whose delivery is promised within the next few months.
In this work, we first develop a mathematical framework for and prove various useful facts applicable to random circuits such as construction of rational function valued unitary paths that interpolate between two arbitrary unitaries, an extension of Berlekamp-Welch algorithm that efficiently and exactly interpolates rational functions, and construction of probability distributions over unitaries that are arbitrarily close to the Haar measure. Lastly, we then prove that the exact sampling from the output distribution of random circuits is $\#P$-Hard on {\it average}; we also prove that this is necessary for proving the quantum supremacy conjecture.
