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

139

R. Santhanam, Circuit lower bounds for Merlin — Arthur classes. SIAM Journal on Computing, 39:3 (2009), 1038–61.

140

S. Aaronson and A. Wigderson, Algebrization: a new barrier in complexity theory. ACM Transactions on Computing Theory, 1:1 (2009), 2:1–54.

141

M. L. Furst, J. B. Saxe, and M. Sipser, Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17:1 (1984), 13–27.

142

M. Ajtai. Sigma_1ˆ1-formulae on finite structures. Annals of Pure and Applied Logic, 24 (1983), 1–48.

143

A. A. Razborov, On themethod of approximations. In Proceedings ofACMSymposium on Theory of Computing (New York: ACM, 1989), pp. 167–76.

144

R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of ACM Symposium on Theory of Computing (New York: ACM, 1987), pp. 77–82.

145

A. A. Razborov and S. Rudich, Natural proofs. Journal of Computer and System Sciences, 55:1 (1997), 24–35.

146

M. Naor and O. Reingold, Number-theoretic constructions of efficient pseudo-random functions. Journal of the ACM, 51:2 (2004), 231–62.

147

R. Williams, Non-uniform ACC circuit lower bounds. In Proceedings of IEEE Conference on Computational Complexity (Silver Springs, MD: IEEE Computer Society Press, 2011), pp. 115–25.

148

Более подробно см.: K. Mulmuley, The GCT program toward the P vs. NP problem. Communications of the ACM, 55:6 (2012), 98–107, http://ramakrishnadas.cs.uchicago.edu/, или прекрасную докторскую диссертацию Joshua Grochow, Symmetry and equivalence relations in classical and geometric complexity theory. Doctoral dissertation, University of Chicago (2012). http://people.cs.uchicago.edu/~joshuag/grochow-thesis.pdf).

149

http://www.cpsc.ucalgary.ca/~jwatrous/papers/qip2.ps

150

R. Jain, Z. Ji, S. Upadhyay, and J. Watrous, QIP = PSPACE. Journal of the ACM, 58:6 (2011), 30.

151

A. Kitaev and J. Watrous, Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of Annual ACM Symposium on Theory of Computing (New York: ACM, 2000), pp. 608–17.

152

Начиная с этой главы мы включили в текст некоторые диалоги со студентами, слушавшими данный курс.

153

См., напр.: Nick Bostrom, Anthropic Bias: Observation Selection Effects in Science and Philosophy, Routledge, 2010.

154

См., напр.: John Leslie, The End of the World: The Science and Ethics of Human Extinction, Routledge, 1998.

155

Об аргументе Судного дня существует обширная литература. Хорошим началом служат уже упомянутые книги Бострома и Лесли, рано как и статья http://en.wikipedia.org/wiki/Doomsday_argument.

156

J. R. Gott III, Implications of the Copernican principle for our future prospects. Nature, 363:6427 (1993), 315–319.

157

http://math.ucr.edu/home/baez/week246.html

158

BPPpath был введен в работе Y. Han, L. A. Hemaspaandra, and T. Thierauf, Threshold computation and cryptographic security. SIAM Journal on Computing, 26:1 (1997), 59–78.

159

L. M. Adleman, J. DeMarrais, and M.-D. A. Huang, Quantum computability. SIAM Journal on Computing, 26:5 (1997), 1524–40.

160

S. Aaronson, Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A, 461:2063 (2005), 3473–82. http://arxiv.org/abs/quant-ph/0412187

161

R. Beigel, N. Reingold, and D. A. Spielman, PP is closed under intersection. Journal of Computer and System Sciences, 50:2 (1995), 191–202.

162

M. Bremner, R. Jozsa, and D. Shepherd, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A, 467:2126 (2010), 459–72. http://arxiv.org/abs/1005.1407

163

S. Aaronson and A. Arkhipov, The computational complexity of linear optics. In Proceedings of Annual ACM Symposium on Theory of Computing (2011), pp. 333–42. http://arxiv.org/abs/1011.3245

164

В самом деле, когда проводилась финальная редактура американского издания этой книги, четыре группы в области квантовой оптики объявили о первых успешных демонстрациях предложенной нами с Архиповым «бозонной выборки», хотя пока лишь с тремя идентичными фотонами. См. дополнительную информацию http://www.scottaaronson.com/blog/?p=1177.

165

См., например, http://law2.umkc.edu/faculty/projects/ftrials/leoploeb/leopold.htm

166

http://www.complexityzoo.com

167

R. Nozick, Newcomb's problem and two principles of choice. In Essays in Honor of Carl G. Hempel, ed. N. Rescher, Synthese Library, Dordrecht, the Netherlands. (1969), pp. 114–115.

168

После того как я прочитал эти лекции в 2006 г., я узнал, что Рэдфорд Нил независимо от меня предложил сходную идею. См.: R. M. Neal, Puzzles of anthropic reasoning resolved using full non-indexical conditioning, http://www.cs.toronto.edu/~radford/ftp/anth.pdf

169

B. W. Libet, Do we have free will? Journal of Consciousness Studies, 6 (1999), 47–57.

170

C. S. Soon, M. Brass, H.-J. Heinze, and J.-D. Haynes, Unconscious determinants of free decisions in the human brain. Nature Neuroscience, 11 (2008), 543–45.

171

http://arxiv.org/abs/quant-ph/0604079

172

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

173

S. Wolfram, A New Kind of Science, Wolfram Media, 2002.

174

S. Pironio, A. Acın, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, Random numbers certified by Bell's