Regular PapersNo Access

THE PHYSICAL CHURCH-TURING THESIS AND THE PRINCIPLES OF QUANTUM THEORY

PABLO ARRIGHI

Université de Grenoble, LIG, 220 rue de la chimie, 38400 SMH, France

École normale supérieure de Lyon, LIP, 46 allée d'Italie, 69008 Lyon, France

Search for more papers by this author

and

GILLES DOWEK

INRIA, 23 avenue d'Italie, CS 81321, 75214 Paris Cedex 13, France

Search for more papers by this author

https://doi.org/10.1142/S0129054112500153Cited by:12 (Source: Crossref)

Abstract

As was emphasized by Deutsch, quantum computation shatters complexity theory, but is innocuous to computability theory. Yet Nielsen and others have shown how quantum theory as it stands could breach the physical Church-Turing thesis. We draw a clear line as to when this is the case, in a way that is inspired by Gandy. Gandy formulates postulates about physics, such as homogeneity of space and time, bounded density and velocity of information — and proves that the physical Church-Turing thesis is a consequence of these postulates. We provide a quantum version of the theorem. Thus this approach exhibits a formal non-trivial interplay between theoretical physics symmetries and computability assumptions.

Keywords:

References

P. Arrighi and G. Dowek. Operational semantics for formal tensorial calculus. In Proceedings of QPL, volume 33, pages 21–38. Turku Centre for Computer Science General Publication, 2004. ArXiv pre-print , arXiv:quant-ph/0501150 . Google Scholar
P. Arrighi and G. Dowek, On the Completeness of Quantum Computation Models, Programs, Proofs, Processes: 6th Conference on Computability in Europe, Cie, 2010 (2010) p. 21. Google Scholar
P. Arrighi, V. Nesme, and R. Werner. Unitarity plus causality implies localizability. QIP 2010, ArXiv preprint, 2010 , arXiv:0711.3975 . Google Scholar
P. Arrighi, V. Nesme and R. Werner, Journal of Computer and System Sciences (2010). Google Scholar
P. Arrighi, V. Nesme and R. F. Werner, Quantum cellular automata over finite, unbounded configurations, Proceedings of MFCS5196, Lecture Notes in Computer Science (Springer, 2008) pp. 64–75. Google Scholar
D. Beckmanet al., Phys. Rev. A 64, (2001), DOI: 10.1103/PhysRevA.64.052309. Google Scholar
E. J. Beggs and J. V. Tucker, Applied Mathematics and Computation 178, 25 (2006), DOI: 10.1016/j.amc.2005.09.068. Crossref, Web of Science, Google Scholar
E. J. Beggs and J. V. Tucker, Theoretical Computer Science 371, 4 (2007), DOI: 10.1016/j.tcs.2006.10.010. Crossref, Web of Science, Google Scholar
E. J. Beggs and J. V. Tucker, Proceedings Royal Society Series A 463, 1541 (2007), DOI: 10.1098/rspa.2007.1835. Crossref, Web of Science, Google Scholar
J. S. Bell, Physics 1, 195 (1964). Crossref, Google Scholar
P. Benioff. New Gauge Fields from Extension of Space Time Parallel Transport of Vector Spaces to the Underlying Number Systems. Arxiv preprint, 2010 , arXiv:1008.3134 . Google Scholar
E. Bernstein and U. Vazirani, Quantum complexity theory, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing (ACM, New York NY, USA, 1993) pp. 11–20. Google Scholar
P. O. Boykinet al., On universal and fault-tolerant quantum computing: A novel basis and a new constructive proof of universality for shor's basis, FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (IEEE Computer Society, 1999) p. 486. Google Scholar
D. Buchholz, Lect. Notes Phys. 558, 4364 (2000). Google Scholar
C. S. Calude and B. Pavlov, Quantum Information Processing 1, 107 (2002), DOI: 10.1023/A:1019623616675. Crossref, Web of Science, Google Scholar
A. Connes. The Witt construction in characteristic one and Quantization. Arxiv preprint, 2010 , arXiv:1009.1769 . Google Scholar
B. J. Copeland and O. Shagrir, Minds and Machines 17(2), 217 (2007), DOI: 10.1007/s11023-007-9058-2. Crossref, Web of Science, Google Scholar
N. Dershowitz and Y. Gurevich, The Bulletin of Symbolic Logic 14(3), (2008). Google Scholar
D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences (1934-1990), 400(1818):97–117, 1985 . Google Scholar
T. Eggeling, D. Schlingemann and R. F. Werner, EPL (Europhysics Letters) 57, 782 (2002), DOI: 10.1209/epl/i2002-00579-4. Crossref, Google Scholar
G. Etesi and I. Németi, International Journal of Theoretical Physics 41(2), 341 (2002), DOI: 10.1023/A:1014019225365. Crossref, Web of Science, Google Scholar
R. Gandy , Church's thesis and principles for mechanisms , The Kleene Symposium ( North-Holland Publishing Company , 1980 ) . Google Scholar
M. Guet al., Physica D: Nonlinear Phenomena 238(10), 835 (2009), DOI: 10.1016/j.physd.2008.12.016. Crossref, Web of Science, Google Scholar
J. Henson. Comparing causality principles. Studies In History and Philosophy of Science Part B: Studies In History and Philosophy of Modern Physics, 36(3):519–543, 2005 . Google Scholar
M. Hogarth, Non-Turing computers and non-Turing computability, PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association (1994) pp. 126–138. Google Scholar
A. S. Holevo, Problemy Peredachi Informatsii 9(2), 31 (1973). Google Scholar
T. D. Kieu, Contemporary Physics 44(1), 51 (2003), DOI: 10.1080/00107510302712. Crossref, Web of Science, Google Scholar
M. A. Nielsen, Phys. Rev. Lett. 79(15), 2915 (1997), DOI: 10.1103/PhysRevLett.79.2915. Crossref, Web of Science, Google Scholar
A. Peres , Quantum theory: concepts and methods ( Kluwer Academic Publishers , 1993 ) . Google Scholar
B. Schumacher and R. Werner. Reversible quantum cellular automata. ArXiv pre-print, 2004 , arXiv:quant-ph/0405174 . Google Scholar
B. Schumacher and M. D. Westmoreland, Quantum Information Processing 4(1), 13 (2005), DOI: 10.1007/s11128-004-3193-y. Crossref, Web of Science, Google Scholar
W. Sieg and J. Byrnes, Monist 82, 150 (1999), DOI: 10.5840/monist19998213. Crossref, Web of Science, Google Scholar
W. D. Smith. Church's thesis meets quantum mechanics. Available on CiteSeerX doi=10.1.1.49.7057, 1999 . Google Scholar
R. Werner and V. Sholz. Church-Turing thesis and quantum mechanics. Private communication., 2010 . Google Scholar
M. Ziegler, Applied Mathematics and Computation 215(4), 1431 (2009), DOI: 10.1016/j.amc.2009.04.062. Crossref, Web of Science, Google Scholar