{
"id": "1911.02555",
"version": "v1",
"published": "2019-11-06T18:51:31.000Z",
"updated": "2019-11-06T18:51:31.000Z",
"title": "Interactive shallow Clifford circuits: quantum advantage against NC$^1$ and beyond",
"authors": [
"Daniel Grier",
"Luke Schaeffer"
],
"comment": "54 pages",
"categories": [
"quant-ph",
"cs.CC"
],
"abstract": "Recent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstrates a quantum advantage for shallow circuits: constant-depth quantum circuits can perform a task which constant-depth classical (i.e., AC$^0$) circuits cannot. Their results have the advantage that the quantum circuit is fairly practical, and their proofs are free of hardness assumptions (e.g., factoring is classically hard, etc.). Unfortunately, constant-depth classical circuits are too weak to yield a convincing real-world demonstration of quantum advantage. We attempt to hold on to the advantages of the above results, while increasing the power of the classical model. Our main result is a two-round interactive task which is solved by a constant-depth quantum circuit (using only Clifford gates, between neighboring qubits of a 2D grid, with Pauli measurements), but such that any classical solution would necessarily solve $\\oplus$L-hard problems. This implies a more powerful class of constant-depth classical circuits (e.g., AC$^0[p]$ for any prime $p$) unconditionally cannot perform the task. Furthermore, under standard complexity-theoretic conjectures, log-depth circuits and log-space Turing machines cannot perform the task either. Using the same techniques, we prove hardness results for weaker complexity classes under more restrictive circuit topologies. Specifically, we give QNC$^0$ interactive tasks on $2 \\times n$ and $1 \\times n$ grids which require classical simulations of power NC$^1$ and AC$^{0}[6]$, respectively. Moreover, these hardness results are robust to a small constant fraction of error in the classical simulation. We use ideas and techniques from the theory of branching programs, quantum contextuality, measurement-based quantum computation, and Kilian randomization.",
"revisions": [
{
"version": "v1",
"updated": "2019-11-06T18:51:31.000Z"
}
],
"analyses": {
"keywords": [
"interactive shallow clifford circuits",
"quantum advantage",
"constant-depth quantum circuit",
"constant-depth classical circuits",
"hardness results"
],
"note": {
"typesetting": "TeX",
"pages": 54,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}