Квантовые вычисления со времен Демокрита - Скотт Ааронсон

or All Languages in NP have Zero-Knowledge Proof Systems,» Journal of the ACM 38 (3):691–729, 1991.

101

Она коротко называется PCP Theorem, и ей посвящена обширная литература; не менее дюжины людей внесли существенный вклад в открытие и совершенствование доказательства. Можно ознакомиться с недавним популярным обзором Dana Moshkovitz, «The Tale of the PCP Theorem,» ACM Crossroads 18 (3):23–26, 2012. http://people.csail.mit.edu/dmoshkov/XRDS.pdf

102

http://www.scottaaronson.com/papers/qchvpra.pdf

103

G. Brassard, P. Høyer, and A. Tapp, Quantum cryptanalysis of hash and claw-free functions, SIGACT News 28:2 (1997), 14–19. http://arxiv.org/abs/quant-ph/9705002

104

S. Aaronson, Quantum Lower Bound for the Collision Problem, Proceedings of ACM Symposium on Theory of Computing, (2002), 635–642. http://www.scottaaronson.com/papers/collision.pdf

105

Y. Shi, Quantum Lower Bounds for the Collision and the Element Distinctness Problems, Proceedings of IEEE Symposium on Foundations of Computer Science, (2002), 513–519. http://arxiv.org/abs/quant-ph/0112086

106

См., например, J. Kempe, A. Kitaev, and O. Regev, The Complexity of the local Hamiltonian problem. SIAM Journal on Computing 35:5 (2006), 1070–1097. http://arxiv.org/abs/quant-ph/0406180

107

J. Watrous, Succinct quantum proofs for properties of finite groups. In Proceedings of IEEE Symposium on Foundations of Computer Science (2000), pp. 537–46. http://arxiv.org/abs/cs.CC/0009002

108

S. Aaronson and G. Kuperberg, Quantum Versus Classical Proofs and Advice, Theory of Computing 3:7 (2007), 129–157. http://arxiv.org/abs/quant-ph/0604056

109

http://arxiv.org/abs/1107.0321

110

См.: A. Ambainis, A. Nayak, A. Ta-Shma, and U. V. Vazirani, Dense quantum coding and quantum finite automata, Journal of the ACM, 49:4 (2002), 496–511. Эта статья содержит также последующее продвижение Наяка.

111

То, о чем мы говорим здесь, на другом языке физик Якир Ааронов и его сотрудники называют концепцией «слабых измерений».

112

Красивое доказательство этого дал М. Н. Вялый, см. eccc.hpi-web.de/eccc-reports/2003/TR03-021/

113

См., например, статью Хайтина http://www.cs.auckland.ac.nz/CDMTCS/chaitin/sciamer3.html, где имеется хорошее популярное описание Ω.

114

S. Aaronson, Limitations of Quantum Advice and One-Way Communication, Theory of Computing 1 (2005), 1–28. http://theoryofcomputing.org/articles/v001a001/v001a001.pdf

115

S. Aaronson and A. Drucker, A full characterization of quantum advice. In Proceedings of Annual ACM Symposium on Theory of Computing (2010), pp. 131–40. http://arxiv.org/abs/1004.0377

116

См., например, http://www.cs.bu.edu/fac/lnd/expo/qc.htm and http://www.wisdom.weizmann.ac.il/~oded/on-qc.html

117

Впоследствии Дэвис опубликовал этот довод; см. http://arxiv.org/abs/quant-ph/0703041

118

Англоязычное издание выпущено Basic Books в 2006 г.

119

Мягкое введение в теорему о пороговом значении можно найти, например, в работе Джона Прескилла http://arxiv.org/abs/quant-ph/9705031 или Дорит Ааронов http://arxiv.org/abs/quant-ph/9812037

120

www.cs.berkeley.edu/~vazirani/pubs/bv.ps

121

См. http://arxiv.org/abs/quant-ph/0610117, или более свежую http://arxiv.org/abs/1212.3562

122

См. в http://www.scottaaronson.com/blog/?p=1211 недавнюю дискуссию о скептицизме в отношении квантовых вычислений.

123

L. Valiant, A Theory of the Learnable, Communications of the ACM 27:11 (1984), 1134–1142. http://www.mpi-inf.mpg.de/~mehlhorn/SeminarEvolvability/ValiantLearnable.pdf. Хорошее введение в тему можно найти в An Introduction to Computational Learning Theory by Michael Kearns and Umesh Vazirani, MIT Press, 1994.

124

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, Learnability and the Vapnik-Chernonenkis dimension, Journal of the ACM 36:4 (1989), 929–965.

125

S. Aaronson, The learnability of quantum states. Proceedings of the Royal Society, A463 (2088), 2007. http://arxiv.org/abs/quant-ph/0608142

126

J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby, A Pseudorandom Generator from any One-way Function. SIAM Journal on Computing 28:4 (1999), 1364–1396.

127

O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions. Journal of the ACM, 33:4 (1986), 792–807.

128

Больше об этом см.: How the Mind Works by Steven Pinker (W. W. Norton & Company, reissue edition, 2009).

129

D. Deutsch, The Fabric of Reality: The Science of Parallel Universes — and Its Implications (London: Penguin, 1998). В русском переводе издана под названием «Структура реальности».

130

R. Impagliazzo and A. Wigderson, P=BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of ACM Symposium on Theory of Computing (1997), pp. 220–229.

131

L. Fortnow and M. Sipser, Are there interactive protocols for CO-NP languages? Information Processing Letters, 28:5 (1988), 249–51.

132

C. Lund, L. Fortnow, H. J. Karloff, and N. Nisan, Algebraic methods for interactive proof systems. Journal of the ACM, 39:4 (1992), 859–68.

133

L. G. Valiant, The complexity of enumeration and reliability problems, SIAM Journal on Computing, 8:3 (1979), 410–421.

134

За эту работу Сэйносукэ Тода получил Гёделевскую премию 1998 г. — Прим. пер.

135

Красивое доказательство можно найти, например, в статье Lance Fortnow «A Simple Proof of Toda's Theorem» (http://theoryofcomputing.org/articles/v005a007/v005a007.pdf) или в книге Gems of Theoretical Computer Science by Uwe Schöning (Springer, 1998).

136

A. Shamir, IP = PSPACE. Journal of the ACM, 39:4 (1992), 869–77.

137

N. V. Vinodchandran, A note on the circuit complexity of PP. Theoretical Computer Science, 347:1/2 (2005), 415–18.

138

S. Aaronson, Oracles are subtle but not malicious. In Proceedings of IEEE Conference on Computational Complexity (2006), pp. 340–54. http://arxiv.org/pdf/cs.CC/0504048.pdf