تقرير
Interactive quantum advantage with noisy, shallow Clifford circuits
| العنوان: | Interactive quantum advantage with noisy, shallow Clifford circuits |
|---|---|
| المؤلفون: | Grier, Daniel, Ju, Nathan, Schaeffer, Luke |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Computer Science - Computational Complexity |
| الوصف: | Recent work by Bravyi et al. constructs a relation problem that a noisy constant-depth quantum circuit (QNC$^0$) can solve with near certainty (probability $1 - o(1)$), but that any bounded fan-in constant-depth classical circuit (NC$^0$) fails with some constant probability. We show that this robustness to noise can be achieved in the other low-depth quantum/classical circuit separations in this area. In particular, we show a general strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. As a consequence, we obtain an unconditional separation between noisy QNC$^0$ circuits and AC$^0[p]$ circuits for all primes $p \geq 2$, and a conditional separation between noisy QNC$^0$ circuits and log-space classical machines under a plausible complexity-theoretic conjecture. A key component of this reduction is showing average-case hardness for the classical simulation tasks -- that is, showing that a classical simulation of the quantum interactive task is still powerful even if it is allowed to err with constant probability over a uniformly random input. We show that is true even for quantum tasks which are $\oplus$L-hard to simulate. To do this, we borrow techniques from randomized encodings used in cryptography. Comment: 33 pages (minor edits) |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2102.06833 |
| رقم الأكسشن: | edsarx.2102.06833 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |