Zhengfeng Ji: Compression of quantum multi-prover interactive proofs
521
17.4
Microsoft Research330 тыс
Следующее
01.02.17 – 81237:30Популярные
217 дней – 1 5191:07:34Опубликовано 1 февраля 2017, 0:31
"We present a protocol that transforms any quantum multi-prover
interactive proof into a nonlocal game in which questions consist of
logarithmic number of bits and answers of constant number of bits.
As a corollary, this proves that the promise problem corresponding to
the approximation of the nonlocal value to inverse polynomial accuracy
is complete for QMIP, and therefore NEXP-hard.
This establishes that nonlocal games are provably harder than
classical games without any complexity theory assumptions.
Our result also provides a strong negative evidence for the multi-prover
variant of the quantum PCP conjecture."
interactive proof into a nonlocal game in which questions consist of
logarithmic number of bits and answers of constant number of bits.
As a corollary, this proves that the promise problem corresponding to
the approximation of the nonlocal value to inverse polynomial accuracy
is complete for QMIP, and therefore NEXP-hard.
This establishes that nonlocal games are provably harder than
classical games without any complexity theory assumptions.
Our result also provides a strong negative evidence for the multi-prover
variant of the quantum PCP conjecture."
Свежие видео
Случайные видео
256 дней – 1 345 36122:17
343 дня – 18 53532:23
18.07.23 – 4 7530:38
20.04.23 – 6211:33
15.02.22 – 100 2877:11
01.04.21 – 35 7070:49
3 дня – 18 0230:57
6 дней – 7614:17
8 дней – 9010:34
9 дней – 2 1320:52
9 дней – 2165:42
2 дня – 1208:04