Classical computing, quantum computing, and Shor's factoring algorithm

 Access to full text

 Full (PDF)

1. [BCDP] D. Beckman, A.N. Chari, Sr. Devabhaktuni, J. Preskill - Efficient networks for quantum computing. Phys. Rev.A, 54:2 (1996), 1034-1063. MR1404473
2. [Ben1] P. Benioff - The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines, J. Stat. Phys., 22 (1980), 563-591. MR574722
3. [Ben2] P. Benioff - Quantum mechanical Hamiltonian models of Turing machines that dissipate no energy, Phys. Rev. Lett., 48 (1980), 1581-1585. MR660412
4. [BoL] D. Boneh, R. Lipton - Quantum cryptoanalysis of hidden linear functions, Proc. of Advances in Cryptology — CRYPTO '95, Springer LN in Computer Science, vol. 963 (1995), 424-437. Zbl0876.94023MR1445578
5. [BoyBHT] M. Boyer, G. Brassard, P. Høyer, A. Tapp - Tight bounds on quantum searching, Preprint, 1996. 
6. [CZ] J. Cirac, P. Zoller - Quantum computation with cold trapped ions, Phys. Rev. Lett., 74:20 (1995), 4091-4094. 
7. [Deu] D. Deutsch - Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. R. Soc. Lond.A400 (1985), 97-117. Zbl0900.81019MR801665
8. [DeuJ] D. Deutsch, R. Jozsa - Rapid solutions of problems by quantum computation, Proc. Roy. Soc. London, Ser. A, 449 (1992), 553-558. Zbl0792.68058MR1196433
9. [Fe1] R. Feynman - Simulating physics with computers, Int. J. of Theor. Phys., 21 (1982), 467-488. MR658311
10. [Fe2] R. Feynman. Quantum mechanical computers, Found. Phys., 16 (1986), 507-531. MR895035
11. [Fr1] M. Freedman - Topological views on computational complexity, In Proc. ICMBerlin1998, vol. II, 453-464. Zbl0967.68520MR1648095
12. [Fr2] M. Freedman - Limit, logic, and computation, Proc. Nat. Ac. Sci. USA, 95 (1998), 95-97. Zbl0891.68041MR1612421
13. [Fr3] M. Freedman - P/NP, and the quantum field computer, Proc. Nat. Ac. Sci. USA, 95 (1998), 98-101. Zbl0895.68053MR1612425
14. [GaJ] M. Garey, D. Johnson - Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San-Francisco, 1979. Zbl0411.68039MR519066
15. [GeC] N. Gershenfield, I. Chuang - Bulk spin-resonance quantum computation, Science275 (1997), 350-355. MR1429853
16. [Gri] D. Grigoriev - Testing the shift-equivalence of polynomials using quantum mechanics, In: Manin's Festschrift, Journ. of Math. Sci., 82:1 (1996), 3184-3193. Zbl0999.12017MR1423635
17. [Gro] L.K. Grover - Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett.79 (1997), 325-328. 
18. [Ki1] A. Kitaev - Quantum computations: algorithms and error correction, Russian Math. Surveys, 52:6 (1997), 53-112. Zbl0917.68063MR1611329
19. [Ki2] A. Kitaev - Classical and quantum computations, Lecture notes, Independent University, Moscow, 1998. 
20. [Ma1] Yu. Manin - A Course in Mathematical Logic, Springer Verlag, 1977, pp. xiii+286. Zbl0383.03002MR457126
21. [Ma2] Yu. Manin - Computable and uncomputable (in Russian), Moscow, Sovetskoye Radio, 1980. MR611681
22. [Mu] D. Mumford - The statistical description of visual signals, Preprint. 
23. [Po] R.P. Poplavskii - Thermodynamical models of information processing (in Russian), Uspekhi Fizicheskikh Nauk, 115:3 (1975), 465-501. 
24. [Sa] A. Salomaa - Computation and Automata, Cambridge UP, 1985. Zbl0565.68046MR801724
25. [Sh] P.W. Shor - Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26:5 (1997), 1484-1509. Zbl1005.11065MR1471990
26. [Si] D. Simon - On the power of quantum computation, Proc. of the 35th Ann. Symp. on Foundations of Comp. Sci. (1994), 116-123. MR1489241
27. [Ts] B. Tsirelson - Quantum information processing, Lecture notes, Tel-Aviv University, 1997.