Theory of quantum computation and philosophy of mathematics. Part I
DOI:
https://doi.org/10.12775/LLP.2009.016Keywords
quantum algorithm, Shor’s algorithm, quantum computation theory, Deutsch’s algorithm, philosophy of mathematicsAbstract
The aim of this paper is to present some basic notions of the theory of quantum computing and to compare them with the basic notions of the classical theory of computation. I am convinced, that the results of quantum computation theory (QCT) are not only interesting in themselves, but also should be taken into account in discussions concerning the nature of mathematical knowledge. The philosophical discussion will however be postponed to another paper. QCT seems not to be well-known among philosophers (at least not to the degree it deserves), so the aim of this paper is to provide the necessary technical preliminaries presented in a way accessible to the general philosophical audience.References
Aharonov, D., 1998, “Quantum computing”, Annual Review of Computational Physics VI, Singapore: World Scientific. Available on-line: http://arxiv.org/PS_cache/quant-ph/pdf/9812/9812037v1.pdf
Davis, M., 2006, “Why there is no such discipline as hypercomputation”, Applied Mathematics and Computation 178, 1: 4-7 (Special Issue on Hypercomputation).
Deutsch D., A. Ekert, and R. Lupacchini, 2000, “Machines, Logic and Quantum Physics”, The Bulletin of Symbolic Logic 6, 3: 265–283.
Feynman, R.P., 1982, “Simulating physics with computers”, International Journal of Theoretical Physics 21: 467–488.
Garey, M.R., and D.S. Johnson, 1979, Computers and Intractability. A Guide to the Theory of NP-completeness, New York, WH Freeman.
Hirvensalo, M., 2001, Quantum Computing, Springer-Verlag.
Hogarth, M., 1994 “Non-Turing computers and non-Turing computability”, PSA 94, 1: 126–138.
Hopcroft, J.E., and J.D. Ullman, 1979, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley.
Laraudogoitia, J.P., 1996, “A beautiful supertask”, Mind 105: 81-83.
Nielsen, M.A., and I.L. Chuang, 2000, Quantum Computation and Quantum Information, Cambridge University Press.
Pitowsky, I., 1990, “The physical Church thesis and physical computational complexity”, Iyyun 39: 81–99.
Shor, P., 1994, “Algorithms for quantum computation. Discrete logarithms and factoring”, pp. 124–134 in: Proc. 35th Annual Symposium on Foundations of Computer Science.
Stannett, M., 2006, “The case for hypercomputation”, Applied Mathematics and Computation 178, 1 (Special Issue on Hypercomputation).
Stolze, J., and D. Suter, 2004, Quantum Computing. A Short Course from Theory to Experiment, Wiley-VCH, Weinheim.
Downloads
Published
How to Cite
Issue
Section
Stats
Number of views and downloads: 280
Number of citations: 0
