Demonstrating exponential speedups for current quantum computational devices is a central challenge in quantum computation. The key obstacle is that such devices are noisy, and hence cannot demonstrate such speedups via Shor's algorithm or similar approaches.

In this high-level talk we will take a unified view of two lines of work that are typically studied separately:

1) "Quantum computational supremacy" - involving experiments sampling from a probability distribution using a noisy quantum circuit.

2) "Quantum optimization" - involving experiments using a local quantum algorithm such as QAOA for combinatorial optimization. 

We consider both as attempting to show that quantum devices can beat classical algorithms with respect to a certain *benchmark*. For the speedup to be certifiable, we need computing the benchmark to be at least sample efficient, and ideally computationally efficient too. 

Current quantum supremacy experiments use the linear cross-entropy (XEB) benchmark, which is sample efficient but not computationally efficient. We present a classical algorithm to spoof XEB, achieving values about an order of magnitude worse than Google's quantum device. Crucially, our algorithm bypasses fully simulating the noisy quantum circuit.

We also discuss the question of whether there exists *any* family  of instances of a constraint optimization problems for which local quantum algorithms offer exponential speedups over classical algorithms. We give a very preliminary negative result on the power of 1-local quantum algorithms for maximum cut, and discuss whether this can be generalized further.

Based on joint works with Soonwon Choi, Chi-Ning Chou, Xun Gao,  Marcin Kalinowski, Misha Lukin, and Kunal Marwaha.