23 Dezembro 2015, 11:55 • Paulo Alexandre Carreira Mateus
[Shor97] P. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 (5): 1484–1509, 1997.
[AR06] A. Ambainis and O. Regev. An elementary proof of the quantum adiabatic theorem. arXiv:quant-ph/0411152.
[CGW13] A. Childs, D. Gosset and Z. Webb. Universal Computation by Multiparticle Quantum Walk. Science 339(6121):791-794, 2013.
[AW09] S. Aaronson and A. Wigderson; Algebrization. A new barrier in Complexity Theory. ACM Trans. Comput. Theory 1: 2-54, 2009.
[GMW91] O. Goldreich, S. Micali and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of ACM 38(3):690-728, 1991.
[CGW15] T. Cubitt, D. Perez-Garcia and M. Wolf. Undecidability of the spectral gap. Nature 528 (7581): 207-211,2015.
[AFPS12] L. Antunes, L. Fortnow, A. Pinto, A.Souto: low depth witnesses are easy to find, Computationla Complexity, 21:479-497, 2012
[BDL01] A. Berthiaume W. van Dam S. Laplante, Quantum Kolmogorov complexity, Journal of Computer and System Sciences, 63(2): 201-221, 2001
[BFKL10] H. Buhrman, L. Fortnow, M. Koucky, and B. Loff: Derandomizing from random strings. In Proceedings of the 25th IEEE Conference on Computational Complexity, pages 58-63. IEEE, 2010.