Theory of Quantum Computation and Philosophy of Mathematics. Part II

Krzysztof Wójtowicz

doi:10.12775/LLP.2018.006

Authors

Krzysztof Wójtowicz Warsaw University, Institute of Philosophy

DOI:

https://doi.org/10.12775/LLP.2018.006

Keywords

quantum computation, quantum-assisted proofs, indispensability argument, mathematical realism, quasi-empiricismfs, quasi-empiricism

Abstract

In the article, the philosophical significance of quantum computation theory for philosophy of mathematics is discussed. In particular, I examine the notion of “quantum-assisted proof” (QAP); the discussion sheds light on the problem of the nature of mathematical proof; the potential empirical aspects of mathematics and the realism-antirealism debate (in the context of the indispensability argument). I present a quasi-empiricist account of QAP’s, and discuss the possible impact on the discussions centered around the Enhanced Indispensabity Argument (EIA).

References

Aaronson, S., 2005, “NP-complete problems and physical reality”, Electronic Colloquium on Computational Complexity, Report no. 26. arXiv:quant-ph/0502072v2.

Aaronson, S., 2013, Quantum Computing Since Democritus, Cambridge University Press, Cambridge, New York. DOI: http://dx.doi.org/10.1017/CBO9780511979309

Andréka, H., I. Németi and P. Németi, 2009, “General relativistic hypercomputing and foundation of mathematics”, Natural Computing 8 (3): 499–516. DOI: http://dx.doi.org/10.1007/s11047-009-9114-3

Appel, K., and W. Haken, 1977, ”Every planar map is four colorable. Part I: discharging”, Illinois Journal of Mathematics 21: 429–490.

Appel, K., W. Haken and J. Koch, 1977, “Every planar map is four colorable. Part II: reducibility”, Illinois Journal of Mathematics 21: 491–567.

Baker, A., 2005, “Are there genuine mathematical explanations of physical phenomena?”, Mind 114 (454): 223–238. DOI: http://dx.doi.org/10.1093/mind/fzi223

Baker, A., 2008, “Experimental mathematics”, Erkenntnis 68: 331–344. DOI: http://dx.doi.org/10.1007/s10670-008-9109-y

Baker, A., 2009, “Mathematical explanation in science”, British Journal for the Philosophy of Science 60 (3): 611–633. DOI: http://dx.doi.org/10.1093/bjps/axp025

Baker, A., and A. Colyvan, 2011, “Indexing and mathematical explanation”, Philosophia Mathematica 19: 232–224. DOI: http://dx.doi.org/10.1093/philmat/nkr026

Balaguer, M., 1998, Platonism and Anti-Platonism in Mathematics, Oxford University Press, New York, Oxford.

Bangu, S., 2013, “Indispensability and explanation”, British Journal for the Philosophy of Science 64 (2): 255–277. DOI: http://dx.doi.org/10.1093/bjps/axs026

Baron, S., 2014, “Optimisation and mathematical explanation: doing the Lévy Walk”, Synthese 191: 459-479. DOI: http://dx.doi.org/10.1007/s11229-013-0284-2

Bender, C.M., D.C. Brody and M.P. Müller, 2017, “Hamiltonian for the zeros of the Riemann zeta function”, Physical Review Letters 118, 130201. DOI: http://dx.doi.org/10.1103/PhysRevLett.118.130201 (available as: href="https://journals.aps.org/prl/pdf/10.1103/PhysRevLett.118.130201">https://journals.aps.org/prl/pdf/10.1103/PhysRevLett.118.130201)

Bennett, C., E. Bernstein, G. Brassard and U. Vazirani, 1997, “Strengths and weaknesses of quantum computing” , SIAM J. Comput. 26 (5): 1510–1523; arXiv:quant-ph/9701001. DOI: http://dx.doi.org/10.1137/S0097539796300933

Berry, M.V., and J.P. Keating, 1999, “H = xp and the Riemann zeros”, pages 355–367 in J.P. Keating, D.E. Khmelnitski and I.V. Lerner (eds.), Supersymmetry and Trace Formulae: Chaos and Disorder, Kluwer Academic/Plenum, New York. DOI: http://dx.doi.org/10.1007/978-1-4615-4875-1_19

Colyvan, M., 1999, “Confirmation theory and indispensability”, Philosophical Studies 96: 1–19.

Colyvan, M., 2001, The Indispensability of Mathematics, New York, Oxford University Press. DOI: http://dx.doi.org/10.1093/019513754X.001.0001

Colyvan, M., 2008, “The ontological commitments of inconsistent theories”, Philosophical Studies 141: 115–123. DOI: http://dx.doi.org/10.1007/s11098-008-9266-5

Chihara, C., 1990, Constructibility and Mathematical Existence, Clarendon Press, Oxford. DOI: http://dx.doi.org/10.1093/0198239750.001.0001

Daly, C., and S. Langford, 2009, “Mathematical explanation and indispensability arguments”, The Philosophical Quarterly 59: 641–658. DOI: http://dx.doi.org/10.1111/j.1467-9213.2008.601.x

Detlefsen, M., and M. Luker, 1980, “The four color-problem and mathematical proof‘”, Journal of Philosophy 77: 803–820. DOI: http://dx.doi.org/10.1111/10.2307/2025806

Field, H., 1980, Science Without Numbers, Basil Blackwell, Oxford. DOI: dx.doi.org/10.1093/acprof:oso/9780198777915.001.0001

Feynman, R.P., 1982, “Simulating physics with computers”, International Journal of Theoretical Physics 21 (6/7): 467–488. DOI: http://dx.doi.org/10.1007/BF02650179

Hales, T.C., 2000, “Cannonballs and honeycombs”, Notices of the American Mathematical Society 47 (4): 440–449.

Hales, T.C., 2005, “A proof of the Kepler conjecture”, Annals of Mathematics. Second Series 162 (3): 1065–1185. DOI: http://dx.doi.org/10.4007/annals.2005.162.1065

Harrow, A., A. Hassidim and S. Lloyd, 2009, “Quantum algorithm for linear systems of equations”, Phys. Rev. Lett. 15 (103): 150502, arXiv:0811.3171. DOI: http://dx.doi.org/10.1103/PhysRevLett.103.150502

Hellman, G., 1989, Mathematics Without Numbers, Clarendon Press, Oxford. DOI: http://dx.doi.org/10.1093/0198240341.001.0001

Krakowski, I., 1980, “The four-color problem reconsidered”, Philosophical Studies 38: 91–96. DOI: http://dx.doi.org/10.1007/BF00354531

Lange, M., 2013, “What makes a scientific explanation distinctively mathematical?”, British Journal for the Philosophy of Science 64 (3): 485–511. DOI: http://dx.doi.org/10.1093/bjps/axs012

Levin, M.A., 1981, “On Tymoczko’s argument for mathematical empiricism”, Philosophical Studies 39: 79–86. DOI: http://dx.doi.org/10.1007/BF00354815

Liggins, D., 2014, “Abstract expressionism and the communication problem”, British Journal for the Philosophy of Science 65: 599-620.

Lipton, P., 2004, “What good is an explanation”, pages 1-21 in J. Cornwell (ed.), Explanations. Styles of Explanation in Science, Oxford: Oxford University Press. DOI: http://dx.doi.org/10.1007/978-94-015-9731-9_2

Lyon, A., 2012, “Mathematical explanations of empirical facts, and mathematical realism”, Australasian Journal of Philosophy 90 (3): 559–578. DOI: http://dx.doi.org/10.1080/00048402.2011.596216

Lyon, A., and M. Colyvan, 2008, “The explanatory power of phase spaces”, Philosophia Mathematica 16 (2): 227–243. DOI: http://dx.doi.org/10.1093/philmat/nkm025

Montanaro, A., 2015, “Quantum algorithms: an overview”, https://www.nature.com/articles/npjqi201523 (also: arXiv:1511.04206v2). DOI: http://dx.doi.org/10.1038/npjqi.2015.23

Németi, I., and G. Dávid, 2006, “Relativistic computers and the Turing barrier”, Journal of Applied Mathematics and Computation 178 (1): 118–142. DOI: http://dx.doi.org/10.1016/j.amc.2005.09.075

Nielsen, M.A., and I.L. Chuang, 2000, Quantum Computation and Quantum Information, Cambridge University Press. DOI: http://dx.doi.org/10.1017/CBO9780511976667

Quine, W.V.O., 1953, “Two dogmas of empiricism”, pages 20–46 in From a Logical Point of View, Harvard University Press, Cambridge, Mass.

Quine, W.V.O., 1981, “Things and their place in theories”, pages 1–23 in Theories and Things, The Belknap Press of Harvard University Press, Cambridge, Mass.

Rav, Y., 1999, “Why do we prove theorems?”, Philosophia Mathematica 7: 5–41. DOI: http://dx.doi.org/10.1093/philmat/7.1.5

Shor, P., 1994, “Algorithms for quantum computation: Discrete logarithms and factoring”, pages 124–134 in Proc. 35th Annual Symposium on Foundations of Computer Science, IEEE. DOI: http://dx.doi.org/10.1109/SFCS.1994.365700

Swart, E.R., 1980, “The philosophical implications of the four-color problem”, American Mathematical Monthly 87: 697–707. DOI: http://dx.doi.org/10.2307/2321855

Teller, P., 1980, “Computer proof”’, The Journal of Philosophy 77: 797–803. DOI: http://dx.doi.org/10.2307/2025805

Tymoczko, T., 1979, “The four-color problem and its philosophical significance”, The Journal of Philosophy 76 (2): 57–83. DOI: http://dx.doi.org/10.2307/2025976

Yablo, S., 2005, “The myth of the seven”, pages 90–115 in M.E. Kalderon (ed.), Fictionalism in Metaphysics, Oxford, Oxford University Press. DOI: http://dx.doi.org/10.1093/acprof:oso/9780199266487.003.0010

Yablo, S., 2012, “Explanation, extrapolation, and existence”, Mind 121 (484): 1007–1029. DOI: http://dx.doi.org/10.1093/mind/fzs120

Wójtowicz, K., 2009, “Theory of quantum computation and philosophy of mathematics. Part I”, Logic and Logical Philosophy 18 (3–4): 313–332. DOI: http://dx.doi.org/10.12775/LLP.2009.016

Wójtowicz, K., 2015, “Could empirical facts become mathematical truths?”, pages 213–230 in J. Ladyman, S. Presnell, G. McCabe, M. Eckstein and S.J. Szybka (eds.), Road to Reality with Roger Penrose, Copernicus Center Press, Kraków.