4501
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Литература) |
||
Строка 132: | Строка 132: | ||
== Литература == | == Литература == | ||
1. Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51 (4), 595-605 (2004) | 1. Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51 (4), 595-605 (2004) | ||
2. Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210-239 (2007) | 2. Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210-239 (2007) | ||
3. Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theor. Comput. 1,37-46(2005) | 3. Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theor. Comput. 1,37-46(2005) | ||
4. Ambainis, A., Kempe, J., Rivosh, A.: In: Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA'06), 2006, pp. 1099-1108 | 4. Ambainis, A., Kempe, J., Rivosh, A.: In: Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA'06), 2006, pp. 1099-1108 | ||
5. Buhrman, H., Durr,C., Heiligman, M., Hayer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. SIAM J. Comput. 34(6), 1324-1330 (2005) | 5. Buhrman, H., Durr,C., Heiligman, M., Hayer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. SIAM J. Comput. 34(6), 1324-1330 (2005) | ||
6. Borodin, A., Fischer, M., Kirkpatrick, D., Lynch, N.: A time-space tradeoff for sorting on non-oblivious machines. J. Comput. Syst.Sci.22,351-364(1981) | 6. Borodin, A., Fischer, M., Kirkpatrick, D., Lynch, N.: A time-space tradeoff for sorting on non-oblivious machines. J. Comput. Syst.Sci.22,351-364(1981) | ||
7. Buhrman, H., Spalek, R.: Quantum verification of matrix products. In: Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA'06), 2006, pp. 880-889 | 7. Buhrman, H., Spalek, R.: Quantum verification of matrix products. In: Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA'06), 2006, pp. 880-889 | ||
8. Beame, P., Saks, M., Sun, X., Vee, E.: Time-space trade-off lower bounds for randomized computation of decision problems. J.ACM 50(2), 154-195(2003) | 8. Beame, P., Saks, M., Sun, X., Vee, E.: Time-space trade-off lower bounds for randomized computation of decision problems. J.ACM 50(2), 154-195(2003) | ||
9. Childs, A.M., Eisenberg, J.M.: Quantum algorithms for subset finding. Quantum Inf. Comput. 5,593 (2005) | 9. Childs, A.M., Eisenberg, J.M.: Quantum algorithms for subset finding. Quantum Inf. Comput. 5,593 (2005) | ||
10. Kutin, S.: Quantum lower bound for the collision problem with small range. Theor. Comput. 1, 29-36 (2005) | 10. Kutin, S.: Quantum lower bound for the collision problem with small range. Theor. Comput. 1, 29-36 (2005) | ||
11. Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. In: Proceedings of the International Colloquium Automata, Languages and Programming (ICALP'05), 2005, pp. 1312-1324 | 11. Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. In: Proceedings of the International Colloquium Automata, Languages and Programming (ICALP'05), 2005, pp. 1312-1324 | ||
12. Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 413^24 (2007) | 12. Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 413^24 (2007) | ||
13. Magniez, F., Nayak, A., Roland, J., Santha, M.: Search by quantum walk. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC'07), 2007, pp. 575-584 | 13. Magniez, F., Nayak, A., Roland, J., Santha, M.: Search by quantum walk. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC'07), 2007, pp. 575-584 | ||
14. Szegedy, M.: Quantum speed-up of Markov Chain based algorithms. In: Proceedings of the IEEE Conference on Foundations of Computer Science (FOCS'04), 2004, pp. 32^1 | 14. Szegedy, M.: Quantum speed-up of Markov Chain based algorithms. In: Proceedings of the IEEE Conference on Foundations of Computer Science (FOCS'04), 2004, pp. 32^1 | ||
15. Yao, A.: Near-optimal time-space tradeoff for element distinctness. SIAM J. Comput. 23(5), 966-975 (1994) | 15. Yao, A.: Near-optimal time-space tradeoff for element distinctness. SIAM J. Comput. 23(5), 966-975 (1994) |
правка