  Recently Brakerski, Christiano, Mahadev, Vazirani and Vidick (FOCS 2018) have
shown how to construct a test of quantumness based on the learning with errors
(LWE) assumption: a test that can be solved efficiently by a quantum computer
but cannot be solved by a classical polynomial-time computer under the LWE
assumption. This test has lead to several cryptographic applications. In
particular, it has been applied to producing certifiable randomness from a
single untrusted quantum device, self-testing a single quantum device and
device-independent quantum key distribution.
  In this paper, we show that this test of quantumness, and essentially all the
above applications, can actually be implemented by a very weak class of quantum
circuits: constant-depth quantum circuits combined with logarithmic-depth
classical computation. This reveals novel complexity-theoretic properties of
this fundamental test of quantumness and gives new concrete evidence of the
superiority of small-depth quantum circuits over classical computation.
