Natural argument is represented as the limit, to which an infinite Turing process converges. A Turing machine, in which the bits are substituted with qubits, is introduced. That quantum Turing machine can recognize two complementary natural arguments in any data. That ability of natural argument is interpreted as an intellect featuring any quantum computer. The property is valid only within a quantum computer: To utilize it, the observer should (...) be sited inside it. Being outside it, the observer would obtain quite different result depending on the degree of the entanglement of the quantum computer and observer. All extraordinary properties of a quantum computer are due to involving a converging infinite computational process contenting necessarily both a continuous advancing calculation and a leap to the limit. Three types of quantum computation can be distinguished according to whether the series is a finite one, an infinite rational or irrational number. -/- . (shrink)

Pattern recognition is represented as the limit, to which an infinite Turing process converges. A Turing machine, in which the bits are substituted with qubits, is introduced. That quantum Turing machine can recognize two complementary patterns in any data. That ability of universal pattern recognition is interpreted as an intellect featuring any quantum computer. The property is valid only within a quantum computer: To utilize it, the observer should be sited inside it. Being (...) outside it, the observer would obtain quite different result depending on the degree of the entanglement of the quantum computer and observer. All extraordinary properties of a quantum computer are due to involving a converging infinite computational process contenting necessarily both a continuous advancing calculation and a leap to the limit. Three types of quantum computation can be distinguished according to whether the series is a finite one, an infinite rational or irrational number. (shrink)

Quantum computer is considered as a generalization of Turing machine. The bits are substituted by qubits. In turn, a "qubit" is the generalization of "bit" referring to infinite sets or series. It extends the consept of calculation from finite processes and algorithms to infinite ones, impossible as to any Turing machines (such as our computers). However, the concept of quantum computer mets all paradoxes of infinity such as Gödel's incompletness theorems (1931), etc. A philosophical (...) reflection on how quantum computer might implement the idea of "infinite calculation" is the main subject. (shrink)

A definition of quantum computer is supposed: as a countable set of Turing machines on the ground of: quantum parallelism, reversibility, entanglement. Qubit is the set of all the i–th binary location cells transforming in parallel by unitary matrices. The Church thesis is suggested in the form relevat to quantum computer. The notion of the non–finite (but not infinite) potency of a set is introduced .

This book provides a general survey of the main concepts, questions and results that have been developed in the recent interactions between quantum information, quantum computation and logic. Divided into 10 chapters, the books starts with an introduction of the main concepts of the quantum-theoretic formalism used in quantum information. It then gives a synthetic presentation of the main “mathematical characters” of the quantum computational game: qubits, quregisters, mixtures of quregisters, quantum logical gates. Next, (...) the book investigates the puzzling entanglement-phenomena and logically analyses the Einstein–Podolsky–Rosen paradox and introduces the reader to quantum computational logics, and new forms of quantum logic. The middle chapters investigate the possibility of a quantum computational semantics for a language that can express sentences like “Alice knows that everybody knows that she is pretty”, explore the mathematical concept of quantum Turing machine, and illustrate some characteristic examples that arise in the framework of musical languages. The book concludes with an analysis of recent discussions, and contains a Mathematical Appendix which is a survey of the definitions of all main mathematical concepts used in the book. (shrink)

The GOOGLE and XPRIZE $5,000,000 for the practical and socially useful utilization of the quantum computer is the starting point for ontomathematical reflections for what it can really serve. Its “output by measurement” is opposed to the conjecture for a coherent ray able alternatively to deliver the ultimate result of any quantum calculation immediately as a Dirac -function therefore accomplishing the transition of the sequence of increasingly narrow probability density distributions to their limit. The GOOGLE and XPRIZE problem’s (...) solution needs the initial understanding that the result of any quantum calculation is a wave function, or respectively, a probability (density or not) distribution unlike the Turing machine one, and only a “calculating ray” is able to transform the former into the later without any “curving” disturbances. Thus, the unique capability of the quantum computer due to its inherent quantum parallelism can be conserved for all Gödel unresolvable problems, only on the fast “NP” track of which the quantum computer “Achilles” is able practically to overrun the Turing machine “Tortoise” since the latter can “sprint” only by any “P” calculating speed even on it and unlike “Achilles” himself able for “NP” velocities as well. The way for any material body to “calculate” the certain trajectory of least action also resolves the “traveling salesman problem” in fact, therefore illustrating furthermore what the “NP” output of a quantum computer by a “calculating ray” should mean. Another example is the problem of the number of all prime numbers less than “N”, which is suggested to visualize once again the quantum computer capability to resolve problems by a “NP” speed and thus qualitatively to overrun any competing Turing machine. The technically implemented idea of laser is now reinterpreted to “radiate a wave function” in order to explain the “calculating ray” option for a quantum computer “NP” output. The generalization of an entanglement “trigger ray” described by any non-Hermitian operator (unlike a laser) is suggested as well as those “sci-fi” horizons which it reveals. One of them is meant for elucidating the practical meaning of the “Yang-Mills existence and mass gap problem”, one more of the CMI “Millennium Problems” after that of “P vs NP”. -/- . (shrink)

Combining physics, mathematics and computer science, quantum computing and its sister discipline of quantum information have developed in the past few decades from visionary ideas to two of the most fascinating areas of quantum theory. General interest and excitement in quantum computing was initially triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially “speed-up” classical computation and factor large numbers into primes far more efficiently than any (known) classical algorithm. Shor’s algorithm (...) was soon followed by several other algorithms that aimed to solve combinatorial and algebraic problems, and in the years since theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Common belief has it that the implementation of Shor’s algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premise that all known classical worst-case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in attempts to tackle the technological difficulties that prevent the realisation of a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995; Ekert and Jozsa 1996; Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts. -/- The philosophical interest in quantum computing is manifold. From a social-historical perspective, quantum computing is a domain where experimentalists find themselves ahead of their fellow theorists. Indeed, quantum mysteries such as entanglement and nonlocality were historically considered a philosophical quibble, until physicists discovered that these mysteries might be harnessed to devise new efficient algorithms. But while the technology for harnessing the power of 50–100 qubits (the basic unit of information in the quantum computer) is now within reach (Preskill 2018), only a handful of quantum algorithms exist, and the question of whether these can truly outperform any conceivable classical alternative is still open. From a more philosophical perspective, advances in quantum computing may yield foundational benefits. For example, it may turn out that the technological capabilities that allow us to isolate quantum systems by shielding them from the effects of decoherence for a period of time long enough to manipulate them will also allow us to make progress in some fundamental problems in the foundations of quantum theory itself. Indeed, the development and the implementation of efficient quantum algorithms may help us understand better the border between classical and quantum physics (Cuffaro 2017, 2018a; cf. Pitowsky 1994, 100), and perhaps even illuminate fundamental concepts such as measurement and causality. Finally, the idea that abstract mathematical concepts such as computability and complexity may not only be translated into physics, but also re-written by physics bears directly on the autonomous character of computer science and the status of its theoretical entities—the so-called “computational kinds”. As such it is also relevant to the long-standing philosophical debate on the relationship between mathematics and the physical world. (shrink)

The paper addresses Leon Hen.kin's proposition as a " lighthouse", which can elucidate a vast territory of knowledge uniformly: logic, set theory, information theory, and quantum mechanics: Two strategies to infinity are equally relevant for it is as universal and t hus complete as open and thus incomplete. Henkin's, Godel's, Robert Jeroslow's, and Hartley Rogers' proposition are reformulated so that both completeness and incompleteness to be unified and thus reduced as a joint property of infinity and of all (...) class='Hi'>infinite sets. However, only Henkin's proposition equivalent to an internal position to infinity is consistent . This can be retraced back to set theory and its axioms, where that of choice is a key. Quantum mechanics is forced to introduce infinity implicitly by Hilbert space, on which is founded its formalism. One can demonstrate that some essential properties of quantum information, entanglement, and quantum computer originate directly from infinity once it is involved in quantum mechanics. Thus, these phenomena can be elucidated as both complete and incomplete, after which choice is the border between them. A special kind of invariance to the axiom of choice shared by quantum mechanics is discussed to be involved that border between the completeness and incompleteness of infinity in a consistent way. The so-called paradox of Albert Einstein, Boris Podolsky, and Nathan Rosen is interpreted entirely in the same terms only of set theory. Quantum computer can demonstrate especially clearly the privilege of the internal position, or " observer'' , or "user" to infinity implied by Henkin's proposition as the only consistent ones as to infinity. An essential area of contemporary knowledge may be synthesized from a single viewpoint. (shrink)

For over a decade, the hypercomputation movement has produced computational models that in theory solve the algorithmically unsolvable, but they are not physically realizable according to currently accepted physical theories. While opponents to the hypercomputation movement provide arguments against the physical realizability of specific models in order to demonstrate this, these arguments lack the generality to be a satisfactory justification against the construction of any information-processing machine that computes beyond the universal Turing machine. To this end, I present a (...) more mathematically concrete challenge to hypercomputability, and will show that one is immediately led into physical impossibilities, thereby demonstrating the infeasibility of hypercomputers more generally. This gives impetus to propose and justify a more plausible starting point for an extension to the classical paradigm that is physically possible, at least in principle. Instead of attempting to rely on infinities such as idealized limits of infinite time or numerical precision, or some other physically unattainable source, one should focus on extending the classical paradigm to better encapsulate modern computational problems that are not well-expressed/modeled by the closed-system paradigm of the Turing machine. I present the first steps toward this goal by considering contemporary computational problems dealing with intractability and issues surrounding cyber-physical systems, and argue that a reasonable extension to the classical paradigm should focus on these issues in order to be practically viable. (shrink)

Arthur Clark and Michael Kube–McDowell (“The Triger”, 2000) suggested the sci-fi idea about the direct transformation from a chemical substance to another by the action of a newly physical, “Trigger” field. Karl Brohier, a Nobel Prize winner, who is a dramatic persona in the novel, elaborates a new theory, re-reading and re-writing Pauling’s “The Nature of the Chemical Bond”; according to Brohier: “Information organizes and differentiates energy. It regularizes and stabilizes matter. Information propagates through matter-energy and mediates the interactions of (...) matter-energy.” Dr Horton, his collaborator in the novel replies: “If the universe consists of energy and information, then the Trigger somehow alters the information envelope of certain substances –“. “Alters it, scrambles it, overwhelms it, destabilizes it” Brohier adds. There is a scientific debate whether or how far chemistry is fundamentally reducible to quantum mechanics. Nevertheless, the fact that many essential chemical properties and reactions are at least partly representable in terms of quantum mechanics is doubtless. For the quantum mechanics itself has been reformulated as a theory of a special kind of information, quantum information, chemistry might be in turn interpreted in the same terms. Wave function, the fundamental concept of quantum mechanics, can be equivalently defined as a series of qubits, eventually infinite. A qubit, being defined as the normed superposition of the two orthogonal subspaces of the complex Hilbert space, can be interpreted as a generalization of the standard bit of information as to infinite sets or series. All “forces” in the Standard model, which are furthermore essential for chemical transformations, are groups [U(1),SU(2),SU(3)] of the transformations of the complex Hilbert space and thus, of series of qubits. One can suggest that any chemical substances and changes are fundamentally representable as quantum information and its transformations. If entanglement is interpreted as a physical field, though any group above seems to be unattachable to it, it might be identified as the “Triger field”. It might cause a direct transformation of any chemical substance by from a remote distance. Is this possible in principle? (shrink)

The characteristic holistic features of the quantum theoretic formalism and the intriguing notion of entanglement can be applied to a field that is far from microphysics: logical semantics. Quantum computational logics are new forms of quantum logic that have been suggested by the theory of quantum logical gates in quantum computation. In the standard semantics of these logics, sentences denote quantum information quantities: systems of qubits (quregisters) or, more generally, mixtures of quregisters (qumixes), while (...) logical connectives are interpreted as special quantum logical gates (which have a characteristic reversible and dynamic behavior). In this framework, states of knowledge may be entangled, in such a way that our information about the whole determines our information about the parts; and the procedure cannot be, generally, inverted. In spite of its appealing properties, the standard version of the quantum computational semantics is strongly “Hilbert-space dependent”. This certainly represents a shortcoming for all applications, where real and complex numbers do not generally play any significant role (as happens, for instance, in the case of natural and of artistic languages). We propose an abstract version of quantum computational semantics, where abstract qumixes, quregisters and registers are identified with some special objects (not necessarily living in a Hilbert space), while gates are reversible functions that transform qumixes into qumixes. In this framework, one can give an abstract definition of the notions of superposition and of entangled pieces of information, quite independently of any numerical values. We investigate three different forms of abstract holistic quantum computational logic. (shrink)

The finite age of the universe and the existence of cosmological horizons provides a strong argument that the observable universe represents a finite causal region with finite material and informational resources. A similar conclusion follows from the holographic principle. In this paper I address the question of whether the cosmological information bound has implications for fundamental physics. Orthodox physics is based on Platonism: the laws are treated as infinitely precise, perfect, immutable mathematical relationships that transcend the physical universe and (...) remain totally unchanged by physical processes, however extreme. If instead the laws of physics are regarded as akin to computer software, with the physical universe as the corresponding hardware, then the finite computational capacity of the universe imposes a fundamental limit on the precision of the laws and the specifiability of physical states. That limit depends on the age of the universe. I examine how the imprecision of the laws impacts on the evolution of highly entangled states and on the problem of dark energy. (shrink)

Does Nature permit the implementation of behaviours that cannot be simulated computationally? We consider the meaning of physical computation in some detail, and present arguments in favour of physical hypercomputation: for example, modern scientific method does not allow the specification of any experiment capable of refuting hypercomputation. We consider the implications of relativistic algorithms capable of solving the (Turing) Halting Problem. We also reject as a fallacy the argument that hypercomputation has no relevance because non-computable values are indistinguishable (...) from sufficiently close computable approximations. In addition to considering the nature of computability relative to any given physical theory, we can consider the relationship between versions of computability corresponding to different models of physics. Deutsch and Penrose have argued on mathematical grounds that quantum computation and Turing computation have equivalent formal power. We suggest this equivalence is invalid when considered from the physical point of view, by highlighting a quantum computational behaviour that cannot meaningfully be considered feasible in the classical universe. (shrink)

Quantum Information Theory and the Foundations of Quantum Mechanics is a conceptual analysis of one of the most prominent and exciting new areas of physics, providing the first full-length philosophical treatment of quantum information theory and the questions it raises for our understanding of the quantum world. -/- Beginning from a careful, revisionary, analysis of the concepts of information in the everyday and classical information-theory settings, Christopher G. Timpson argues for an ontologically deflationary account of the (...) nature of quantum information. Against what many have supposed, quantum information can be clearly defined (it is not a primitive or vague notion) but it is not part of the material contents of the world. Timpson's account sheds light on the nature of nonlocality and information flow in the presence of entanglement and, in particular, dissolves puzzles surrounding the remarkable process of quantum teleportation. In addition it permits a clear view of what the ontological and methodological lessons provided by quantum information theory are; lessons which bear on the gripping question of what role a concept like information has to play in fundamental physics. Topics discussed include the slogan 'Information is Physical', the prospects for an informational immaterialism (the view that information rather than matter might fundamentally constitute the world), and the status of the Church-Turing hypothesis in light of quantum computation. -/- With a clear grasp of the concept of information in hand, Timpson turns his attention to the pressing question of whether advances in quantum information theory pave the way for the resolution of the traditional conceptual problems of quantum mechanics: the deep problems which loom over measurement, nonlocality and the general nature of quantum ontology. He marks out a number of common pitfalls to be avoided before analysing in detail some concrete proposals, including the radical quantum Bayesian programme of Caves, Fuchs, and Schack. One central moral which is drawn is that, for all the interest that the quantum information-inspired approaches hold, no cheap resolutions to the traditional problems of quantum mechanics are to be had. (shrink)

Any computer can create a model of reality. The hypothesis that quantum computer can generate such a model designated as quantum, which coincides with the modeled reality, is discussed. Its reasons are the theorems about the absence of “hidden variables” in quantum mechanics. The quantum modeling requires the axiom of choice. The following conclusions are deduced from the hypothesis. A quantum model unlike a classical model can coincide with reality. Reality can be interpreted as a (...) quantum computer. The physical processes represent computations of the quantum computer. Quantum information is the real fundament of the world. The conception of quantum computer unifies physics and mathematics and thus the material and the ideal world. Quantum computer is a non-Turing machine in principle. Any quantum computing can be interpreted as an infinite classical computational process of a Turing machine. Quantum computer introduces the notion of “actually infinite computational process”. The discussed hypothesis is consistent with all quantum mechanics. The conclusions address a form of neo-Pythagoreanism: Unifying the mathematical and physical, quantum computer is situated in an intermediate domain of their mutual transformation. (shrink)

David Lewis is a natural target for those who believe that findings in quantum physics threaten the tenability of traditional metaphysical reductionism. Such philosophers point to allegedly holistic entities they take both to be the subjects of some claims of quantum mechanics and to be incompatible with Lewisian metaphysics. According to one popular argument, the non-separability argument from quantum entanglement, any realist interpretation of quantum theory is straightforwardly inconsistent with the reductive conviction that (...) the complete physical state of the world supervenes on the intrinsic properties of and spatio-temporal relations between its point-sized constituents. Here I defend Lewis's metaphysical doctrine, and traditional reductionism more generally, against this alleged threat from quantum holism. After presenting the non-separability argument from entanglement, I show that Bohmian mechanics, an interpretation of quantum mechanics explicitly recognized as a realist one by proponents of the non-separability argument, plausibly rejects a key premise of that argument. Another holistic worry for Humeanism persists, however, the trouble being the apparently holistic character of the Bohmian pilot wave. I present a Humean strategy for addressing the holistic threat from the pilot wave by drawing on resources from the Humean best system account of laws. (shrink)

My life as a quantum physicist / M. Nakahara -- A review on operator quantum error correction - Dedicated to Professor Mikio Nakahara on the occasion of his 60th birthday / C.-K. Li, Y.-T. Poon and N.-S. Sze -- Implementing measurement operators in linear optical and solid-state qubits / Y. Ota, S. Ashhab and F. Nori -- Fast and accurate simulation of quantum computing by multi-precision MPS: Recent development / A. Saitoh -- Entanglement properties of a (...) class='Hi'>quantum lattice-gas model on square and triangular ladders / S. Tanaka, R. Tamura and H. Katsura -- On signal amplification from weak-value amplification / Y. Shikano -- Topological protection of quantum information / K. Fujii -- Quantum annealing with antiferromagnetic fluctuations for mean-field models / Y. Seki and H. Nishimori -- A method to change phase transition nature - Toward annealing methods / R. Tamura and S. Tanaka -- Computational analysis of the first stage of the photosynthetic system, the light-dependent reaction, by quantum chemical simulation method / M. Tada-Umezaki -- Two-qubit gate operation on selected nearest neighboring qubits in a neutral atom quantum computer / E. Hosseini Lapasar... [et al.] -- A simple operator quantum error correction scheme avoiding fully correlated errors / C. Bagnasco, Y. Kondo and M. Nakahara -- Black hole predictability, classical and quantum / A. Ishibashi -- Classical field simulation of finite-temperature Bose gases / T. Sato -- Atomic quantum simulations of lattice gauge theory: Effect of gauge symmetry breaking / K. Kasamatsu, I. Ichinose and T. Matsui -- Recursive construction of noiseless subsystem for qudits / U. Gungordu... [et al.] -- Composite quantum gates for precise quantum control / M. Bando... [et al.] -- New formulation of statistical mechanics using thermal pure quantum states / S. Sugiura and A. Shimizu -- Thermodynamics in unitary time evolution / T. N. Ikeda -- Second law of thermodynamics with QC-mutual information / T. Sagawa. (shrink)

Non-commuting quantities and hidden parameters – Wave-corpuscular dualism and hidden parameters – Local or nonlocal hidden parameters – Phase space in quantum mechanics – Weyl, Wigner, and Moyal – Von Neumann’s theorem about the absence of hidden parameters in quantum mechanics and Hermann – Bell’s objection – Quantum-mechanical and mathematical incommeasurability – Kochen – Specker’s idea about their equivalence – The notion of partial algebra – Embeddability of a qubit into a bit – Quantum computer is (...) not Turing machine – Is continuality universal? – Diffeomorphism and velocity – Einstein’s general principle of relativity – „Mach’s principle“ – The Skolemian relativity of the discrete and the continuous – The counterexample in § 6 of their paper – About the classical tautology which is untrue being replaced by the statements about commeasurable quantum-mechanical quantities – Logical hidden parameters – The undecidability of the hypothesis about hidden parameters – Wigner’s work and и Weyl’s previous one – Lie groups, representations, and psi-function – From a qualitative to a quantitative expression of relativity − psi-function, or the discrete by the random – Bartlett’s approach − psi-function as the characteristic function of random quantity – Discrete and/ or continual description – Quantity and its “digitalized projection“ – The idea of „velocity−probability“ – The notion of probability and the light speed postulate – Generalized probability and its physical interpretation – A quantum description of macro-world – The period of the as-sociated de Broglie wave and the length of now – Causality equivalently replaced by chance – The philosophy of quantum information and religion – Einstein’s thesis about “the consubstantiality of inertia ant weight“ – Again about the interpretation of complex velocity – The speed of time – Newton’s law of inertia and Lagrange’s formulation of mechanics – Force and effect – The theory of tachyons and general relativity – Riesz’s representation theorem – The notion of covariant world line – Encoding a world line by psi-function – Spacetime and qubit − psi-function by qubits – About the physical interpretation of both the complex axes of a qubit – The interpretation of the self-adjoint operators components – The world line of an arbitrary quantity – The invariance of the physical laws towards quantum object and apparatus – Hilbert space and that of Minkowski – The relationship between the coefficients of -function and the qubits – World line = psi-function + self-adjoint operator – Reality and description – Does a „curved“ Hilbert space exist? – The axiom of choice, or when is possible a flattening of Hilbert space? – But why not to flatten also pseudo-Riemannian space? – The commutator of conjugate quantities – Relative mass – The strokes of self-movement and its philosophical interpretation – The self-perfection of the universe – The generalization of quantity in quantum physics – An analogy of the Feynman formalism – Feynman and many-world interpretation – The psi-function of various objects – Countable and uncountable basis – Generalized continuum and arithmetization – Field and entanglement – Function as coding – The idea of „curved“ Descartes product – The environment of a function – Another view to the notion of velocity-probability – Reality and description – Hilbert space as a model both of object and description – The notion of holistic logic – Physical quantity as the information about it – Cross-temporal correlations – The forecasting of future – Description in separable and inseparable Hilbert space – „Forces“ or „miracles“ – Velocity or time – The notion of non-finite set – Dasein or Dazeit – The trajectory of the whole – Ontological and onto-theological difference – An analogy of the Feynman and many-world interpretation − psi-function as physical quantity – Things in the world and instances in time – The generation of the physi-cal by mathematical – The generalized notion of observer – Subjective or objective probability – Energy as the change of probability per the unite of time – The generalized principle of least action from a new view-point – The exception of two dimensions and Fermat’s last theorem. (shrink)

In this paper we explore the possibility of giving a justification of the “semantic information” content and measure, in the framework of the recent coalgebraic approach to quantum systems and quantum computation, extended to QFT systems. In QFT, indeed, any quantum system has to be considered as an “open” system, because it is always interacting with the background fluctuations of the quantum vacuum. Namely, the Hamiltonian in QFT always includes the quantum system and its inseparable (...) thermal bath, formally “entangled” like an algebra with its coalgebra, according to the principle of the “doubling” of the degrees of freedom between them. This is the core of the representation theory of cognitive neuroscience based on QFT. Moreover, in QFT, the probabilities of the quantum states follow a Wigner distribution, based on the notion and measure of quasiprobability, where regions integrated under given expectation values do not represent mutually exclusive states. This means that a computing agent, either natural or artificial, in QFT, against the quantum Turing machine paradigm, is able to change dynamically the representation space of its computations. This depends on the possibility of interpreting QFT system computations within the framework of category theory logic and its principle of duality between opposed categories, such as the algebra and coalgebra categories of QFT. This allows us to justify and not only to suppose, like in the “theory of strong semantic information” of L. Floridi, the definition of modal “local truth” and the notion of semantic information as a measure of it, despite both measures being defined on quasiprobability distributions. (shrink)

The nature of quantum computation is discussed. It is argued that, in terms of the amount of information manipulated in a given time, quantum and classical computation are equally efficient. Quantum superposition does not permit quantum computers to ''perform many computations simultaneously'' except in a highly qualified and to some extent misleading sense. Quantum computation is therefore not well described by interpretations of quantum mechanics which invoke the concept of vast numbers of parallel universes. (...) Rather, entanglement makes available types of computation processes which, while not exponentially larger than classical ones, are unavailable to classical systems. The essence of quantum computation is that it uses entanglement to generate and manipulate a physical representation of the correlations between logical entities, without the need to completely represent the logical entities themselves. (shrink)

Alternate View Column AV-112 Keywords: quantum mechanics entangled states computer computing 7 qubits prime number factoring Schor algorithm NMR nuclear magnetic resonance fast parallel decryption coherence wave-function collapse many-worlds transactional interpretation Published in the June-2002 issue of Analog Science Fiction & Fact Magazine ; This column was written and submitted 12/19/2001 and is copyrighted ©2001 by John G. Cramer.

In lieu of an abstract, here is a brief excerpt of the content:Reviewed by:Ad Infinitum: The Ghost in Turing’s Machine: Taking God Out of Mathematics and Putting the Body Back InTony E. JacksonAd Infinitum: The Ghost in Turing’s Machine: Taking God Out of Mathematics and Putting the Body Back In, by Brian Rotman; xii & 203 pp. Stanford: Stanford University Press, 1993, $39.50 cloth, $12.95 paper.Brian Rotman’s book attempts to pull mathematics—the last, most solid home of metaphysical thought—off (...) its absolutist foundations and into the roiling current of postmodernism. His argument works in what has by now become a rather standard manner. He shows how the grounding ideas of mathematics rest upon the insupportable assumption of a realm of absolute truth, “truth perfect, truth outside time, outside space, outside the material world of matter, energy, and entropy, truth somehow able to be discovered or apprehended but never invented” (p. 19). Rotman questions this Platonic grounding in a number of ways.First, with the help of linguistics (de Saussure, Benveniste, Wittgenstein, and Peirce) he provides a semiotic analysis of mathematical arguments as real-world linguistic events. Proof he looks at “not as a form of inference engaged in preserving eternal truths, but as an historically conditioned species of rhetoric” (p. 35). Secondly, Rotman argues that one idea has most secured the fortress-like solidity of mathematical Platonism: the idea of ad infinitum or infinite iteration. Mathematics takes off from the givenness of the natural numbers, our everyday 1, 2, 3 and so on to infinity. It is the “so on to infinity” that frames up the house of arithmetic as it has stood since Euclid. (Euclidean in this context is equivalent to Platonic in the context of philosophy.) But what is the referent of these numbers? Ultimately they are said to be the symbolic representation of the action of counting, which is the “mathematical ur-cognition” (p. 51). And yet we cannot imagine any material human situation in which counting could actually go on to infinity. Therefore, some impossible, supernatural agent (the ghost of the title) must be projected in order for this conception to exist. Similarly, Rotman argues against the assumption of “perfect repeatability” because this notion depends upon some purely imaginary, ideal identity of object or action that could possibly be repeated. Ad infinitum requires and assumes both a disembodied, metaphysical counter and a disembodied, metaphysical counted.So Rotman sets about putting the body back into this symbolic system by rejecting the idea of ad infinitum. Instead of assuming the existence of counting activities that run, in principle, out to infinity without changing their nature, Rotman posits what he calls “realizable iteration,” that is, counting that admits the necessary dissolution or change of whatever repetitive function you begin with. Put simply, he includes the fact that quantitative accumulation or repetition always eventually brings about a qualitative change: at some point in everyday life a difference of degree of the “same” thing or action inevitably becomes a difference of kind. The natural numbers and the ad infinitum [End Page 390] remain blissfully sheltered from this inescapable real world truth, but Rotman reformulates mathematics so as to include this truth in the very idea of numbering.In fact (and he acknowledges this) he theorizes counting after the model of chaos or complexity theory in the physical sciences. Realizable iteration, he says, will bring in the “qualitative differences” forgotten or repressed (the language of Nietzsche, Heidegger, and Freud runs throughout) in the metaphysical version of number, and “display [the qualitative differences] as the emergent effects of repetition” (p. 131). Even numerical addition, for instance, which had been the most linearly continuous of activities, now will be linear beginning from some initial point, but will become increasingly nonlinear as quantitative increase tends towards some point of qualitative discontinuity with what had come before. The point of discontinuity, though certain to appear, is by its nature not specifiable beyond a horizon of probability, and in this, Rotman aligns his arithmetic not only with chaos theory, but also with quantum mechanics. In an appendix, Rotman elaborates at least to a degree the “pre-elements” of his non-Euclidean arithmetic.As chaos theory does not destroy everyday cause... (shrink)

EPR-type measurements on spatially separated entangled spin qubits allow one, in principle, to detect curvature. Also the entanglement of the vacuum state is affected by curvature. Here, we ask if the curvature of spacetime can be expressed entirely in terms of the spatial entanglement structure of the vacuum. This would open up the prospect that quantum gravity could be simulated on a quantum computer and that quantum information techniques could be fully employed in the study of (...) class='Hi'>quantum gravity. (shrink)

The paper aims to make а fair supplement to the concept of "metaphysics of relations" (bу М. Esfeld) with а coгrect coгresponding interpretation of the dispositional natшe of characteristics within Е. J. Lowe's ontology. А reasoning from science to philosophy leads М. Esfeld to the conclusion that "quantum entanglement understood in terms of non-separability of states speaks for the metaphysics of relations that denies the presence of intrinsic characteristics of the related systems". The same naturalistic argument provides rationale (...) for the Е. J. Lowe's claim that "the attribution of а characteristics to а given kind could bе metaphysically contingent" for "the laws of nature can bе exactly what they are revealed to us, only because there are no other substantial kinds that could instantiate objects". As а heuristics for the intentional interpretation ofE. J. Lowe's dispositionalism we deal with the requirements of "time-relativeness" and "relevance to causality" from W. Malzkorn's list of criteria of satisfactory representation of dispositions. (shrink)

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

A set theory model of reality, representation and language based on the relation of completeness and incompleteness is explored. The problem of completeness of mathematics is linked to its counterpart in quantum mechanics. That model includes two Peano arithmetics or Turing machines independent of each other. The complex Hilbert space underlying quantum mechanics as the base of its mathematical formalism is interpreted as a generalization of Peano arithmetic: It is a doubled infinite set of doubled Peano (...) arithmetics having a remarkable symmetry to the axiom of choice. The quantity of information is interpreted as the number of elementary choices (bits). Quantum information is seen as the generalization of information to infinite sets or series. The equivalence of that model to a quantum computer is demonstrated. The condition for the Turing machines to be independent of each other is reduced to the state of Nash equilibrium between them. Two relative models of language as game in the sense of game theory and as ontology of metaphors (all mappings, which are not one-to-one, i.e. not representations of reality in a formal sense) are deduced. (shrink)

If r is a reducibility between sets of numbers, a natural question to ask about the structure ? r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by showing (...) that every tt-incomplete computably enumerable truth-table degree a is branching in ? tt . The fact that every Turing-incomplete computably enumerable truth-table degree is branching has been known for some time. This fact can be shown using a technique of Ambos-Spies and, as noticed by Nies, also follows from a relativization of a result of Degtev. We give a proof here using the Ambos-Spies technique because it has not yet appeared in the literature. The proof uses an infinite injury argument. Our main result is the proof when a is Turing-complete but tt-incomplete. Here we are able to exploit the Turing-completeness of a in a novel way to give a finite injury proof. (shrink)

A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed (...) in Section I. Many modifications of Turing machines cum quantum ones are researched in Section II for the Halting problem and completeness, and the model of two independent Turing machines seems to generalize them. Then, that pair can be postulated as the formal definition of reality therefore being complete unlike any of them standalone, remaining incomplete without its complementary counterpart. Representation is formal defined as a one-to-one mapping between the two Turing machines, and the set of all those mappings can be considered as “language” therefore including metaphors as mappings different than representation. Section III investigates that formal relation of “reality”, “representation”, and “language” modeled by (at least two) Turing machines. The independence of (two) Turing machines is interpreted by means of game theory and especially of the Nash equilibrium in Section IV. Choice and information as the quantity of choices are involved. That approach seems to be equivalent to that based on set theory and the concept of actual infinity in mathematics and allowing of practical implementations. (shrink)

In this commentary, arguments are made for a dendritic code being preferable to a temporal synaptic code as a model of conscious experience. A temporal firing pattern is a product of an ongoing neural computation; hence, it is based on a neural algorithm and an algorithm may not provide the most suitable model for conscious experience. Reiteration of a temporal firing code as suggested in a preceding article (Helekar, 1999) does not necessarily improve the situation. The alternative model presented here (...) is that certain synaptic activity patterns, possibly those possessing universal features as suggested by Helekar, can become encoded in the dendritic structure. Following dendritic encoding, quantum phenomena in those specific dendrite sets could illuminate the static image of that encoded synaptic activity. It is the activation of the static image that would be equivalent to conscious experience; thus, conscious awareness would not be directly affiliated with synaptic activity. This dendrite encoding model may go farther than other models to explain the gestalt nature of consciousness, insofar as quantum entanglement could produce an interconnectedness between specific sets of dendrites-an interconnectedness that need not be based on neural computation or neural connections. (shrink)

The concepts of choice, negation, and infinity are considered jointly. The link is the quantity of information interpreted as the quantity of choices measured in units of elementary choice: a bit is an elementary choice between two equally probable alternatives. “Negation” supposes a choice between it and confirmation. Thus quantity of information can be also interpreted as quantity of negations. The disjunctive choice between confirmation and negation as to infinity can be chosen or not in turn: This corresponds to set-theory (...) or intuitionist approach to the foundation of mathematics and to Peano or Heyting arithmetic. Quantum mechanics can be reformulated in terms of information introducing the concept and quantity of quantum information. A qubit can be equivalently interpreted as that generalization of “bit” where the choice is among an infinite set or series of alternatives. The complex Hilbert space can be represented as both series of qubits and value of quantum information. The complex Hilbert space is that generalization of Peano arithmetic where any natural number is substituted by a qubit. “Negation”, “choice”, and “infinity” can be inherently linked to each other both in the foundation of mathematics and quantum mechanics by the meditation of “information” and “quantum information”. (shrink)

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). (shrink)

Infinite time Turing machines represent a model of computability that extends the operations of Turing machines to transfinite ordinal time by defining the content of each cell at limit steps to be the lim sup of the sequences of previous contents of that cell. In this paper, we study a computational model obtained by replacing the lim sup rule with an ‘eventually constant’ rule: at each limit step, the value of each cell is defined if and only (...) if the content of that cell has stabilized before that limit step and is then equal to this constant value. We call these machines weak infinite time Turing machines. We study different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. We show that some of these models are equivalent to each other concerning their computational strength. We show that wITTMs decide exactly the arithmetic relations on natural numbers. (shrink)

This paper proposes an extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system. Chaitin's Ω is defined as the probability that the universal self-delimiting Turing machine U halts, and plays a central role in the development of algorithmic information theory. In the theory, there are two equivalent ways to define the program-size complexity H of a given finite binary string s. In the standard way, H is defined as the length (...) of the shortest input string for U to output s. In the other way, the so-called universal probability m is introduced first, and then H is defined as –log2m without reference to the concept of program-size.Mathematically, the statistics of outcomes in a quantum measurement are described by a positive operator-valued measure in the most general setting. Based on the theory of computability structures on a Banach space developed by Pour-El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called a universal semi-POVM. We also give another characterization of Chaitin's Ω numbers by universal probabilities. Then, based on this characterization, we propose to define an extension of Ω as a sum of the POVM elements of a universal semi-POVM. The validity of this definition is discussed.In what follows, we introduce an operator version equation image of H in a Hilbert space of infinite dimension using a universal semi-POVM, and study its properties. (shrink)

Of the many and varied applications of quantum information theory, perhaps the most fascinating is the sub-field of quantum computation. In this sub-field, computational algorithms are designed which utilise the resources available in quantum systems in order to compute solutions to computational problems with, in some cases, exponentially fewer resources than any known classical algorithm. While the fact of quantum computational speedup is almost beyond doubt, the source of quantum speedup is still a matter of (...) debate. In this paper I argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Cleve et al.'s solution to Deutsch's problem, Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill & Laflamme's deterministic quantum computation with one qubit model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play. (shrink)

The primary resource for quantum computation is Hilbert-space dimension. Whereas Hilbert space itself is an abstract construction, the number of dimensions available to a system is a physical quantity that requires physical resources. Avoiding a demand for an exponential amount of these resources places a fundamental constraint on the systems that are suitable for scalable quantum computation. To be scalable, the effective number of degrees of freedom in the computer must grow nearly linearly with the number of qubits (...) in an equivalent qubit-based quantum computer. (shrink)

A. N. Turing’s 1936 concept of computability, computing machines, and computable binary digital sequences, is subject to Turing’s Cardinality Paradox. The paradox conjoins two opposed but comparably powerful lines of argument, supporting the propositions that the cardinality of dedicated Turing machines outputting all and only the computable binary digital sequences can only be denumerable, and yet must also be nondenumerable. Turing’s objections to a similar kind of diagonalization are answered, and the implications of the paradox (...) for the concept of a Turing machine, computability, computable sequences, and Turing’s effort to prove the unsolvability of the Entscheidungsproblem, are explained in light of the paradox. A solution to Turing’s Cardinality Paradox is proposed, positing a higher geometrical dimensionality of machine symbol-editing information processing and storage media than is available to canonical Turing machine tapes. The suggestion is to add volume to Turing’s discrete two-dimensional machine tape squares, considering them instead as similarly ideally connected massive three-dimensional machine information cells. Three-dimensional computing machine symbol-editing information processing cells, as opposed to Turing’s two-dimensional machine tape squares, can take advantage of a denumerably infinite potential for parallel digital sequence computing, by which to accommodate denumerably infinitely many computable diagonalizations. A three-dimensional model of machine information storage and processing cells is recommended on independent grounds as better representing the biological realities of digital information processing isomorphisms in the three-dimensional neural networks of living computers. (shrink)

In this Short Communication we will discuss the role played by quantum computing within the emerging morphological paradigm in the unconventional natural computing. We intend merely introduce the main reasons why a coherent representation of Universality in morphological natural computing needs to be grounded on a version of Quantum Field Theory independent, in many senses, from the Quantum Mechanics formalism in fundamental physics, namely formulated as a thermal field theory. This theory describes the “emergence” of (...) natural information and computation’s complexity at a quantum level, thus overcoming the trivializing argument against the so-called “pancomputationalism” in morphological natural computing. (shrink)

Summary Proposed by Einstein, Podolsky, and Rosen (EPR) in 1935, the entangled state has played a central part in exploring the foundation of quantum mechanics. At the end of the twentieth century, however, some physicists and mathematicians set aside the epistemological debates associated with EPR and turned it from a philosophical puzzle into practical resources for information processing. This paper examines the origin of what is known as quantum information. Scientists had considered making quantum computers and employing (...) entanglement in communications for a long time. But the real breakthrough only occurred in the 1980s when they shifted focus from general-purpose systems such as Turing machines to algorithms and protocols that solved particular problems, including quantum factorization, quantum search, superdense code, and teleportation. Key to their development was two groups of mathematical manipulations and deformations of entanglement—quantum parallelism and ‘feedback EPR’—that served as conceptual templates. The early success of quantum parallelism and feedback EPR was owed to the idealized formalism of entanglement researchers had prepared for philosophical discussions. Yet, such idealization is difficult to hold when the physical implementation of quantum information processors is at stake. A major challenge for today's quantum information scientists and engineers is thus to move from Einstein et al.'s well-defined scenarios into realistic models. (shrink)

I advocate a theory of syntactic semantics as a way of understanding how computers can think (and how the Chinese-Room-Argument objection to the Turing Test can be overcome): (1) Semantics, considered as the study of relations between symbols and meanings, can be turned into syntax – a study of relations among symbols (including meanings) – and hence syntax (i.e., symbol manipulation) can suffice for the semantical enterprise (contra Searle). (2) Semantics, considered as the process of understanding one domain (...) (by modeling it) in terms of another, can be viewed recursively: The base case of semantic understanding –understanding a domain in terms of itself – is syntactic understanding. (3) An internal (or narrow ), first-person point of view makes an external (or wide ), third-person point of view otiose for purposes of understanding cognition. (shrink)

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko [19] et al. Although this definition of TIME as the maximum of a generally infinite family of numbers looks straightforward, at first glance, examples for which this maximum exists seem to be very rare. It is the main purpose of this paper to prove that, (...) nevertheless, the definition has a large number of important applications. Using the framework of TTE [40], we introduce computable metric spaces and computability on the compact subsets. We prove that every computable metric space has a c-proper c-admissible representation. We prove that Turing machine time complexity of a function computable relative to c-admissible c-proper representations has a computable bound on every computable compact subset. We prove that computably compact computable metric spaces have concise c-proper c-admissible representations and show by examples that many canonical representations are of this kind. Finally, we compare our definition with a similar one by Labhalla et al. [22]. Several examples illustrate the concepts. By these results natural and realistic definitions of computational complexity are now available for a variety of numerical problems such as image processing, integration, continuous Fourier transform or wave propagation. (shrink)

We describe in some detail how to build an infinite computing machine within a continuous Newtonian universe. The relevance of our construction to the Church-Turing thesis and the Platonist-Intuitionist debate about the nature of mathematics is also discussed.

A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. (...) This yields that the realization of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis. (shrink)

Traditionally, many writers, following Kleene (1952), thought of the Church-Turing thesis as unprovable by its nature but having various strong arguments in its favor, including Turing’s analysis of human computation. More recently, the beauty, power, and obvious fundamental importance of this analysis, what Turing (1936) calls “argument I,” has led some writers to give an almost exclusive emphasis on this argument as the unique justification for the Church-Turing thesis. In this chapter I advocate an (...) alternative justification, essentially presupposed by Turing himself in what he calls “argument II.” The idea is that computation is a special form of mathematical deduction. Assuming the steps of the deduction can be stated in a first order language, the Church-Turing thesis follows as a special case of Gödel’s completeness theorem (first order algorithm theorem). I propose this idea as an alternative foundation for the Church-Turing thesis, both for human and machine computation. Clearly the relevant assumptions are justified for computations presently known. Other issues, such as the significance of Gödel’s 1931 Theorem IX for the Entscheidungsproblem, are discussed along the way. (shrink)

The quantum information introduced by quantum mechanics is equivalent to a certain generalization of classical information: from finite to infinite series or collections. The quantity of information is the quantity of choices measured in the units of elementary choice. The “qubit”, can be interpreted as that generalization of “bit”, which is a choice among a continuum of alternatives. The axiom of choice is necessary for quantum information. The coherent state is transformed into a well-ordered series of (...) results in time after measurement. The quantity of quantum information is the transfinite ordinal number corresponding to the infinity series in question. The transfinite ordinal numbers can be defined as ambiguously corresponding “transfinite natural numbers” generalizing the natural numbers of Peano arithmetic to “Hilbert arithmetic” allowing for the unification of the foundations of mathematics and quantum mechanics. (shrink)

A classical analogy of quantum mechanical entanglement is presented, using classical light beams. The analogy can be pushed a long way, only to reach its limits when we try to represent multiparticle, or nonlocal, entanglement. This demonstrates that the latter is of exclusive quantum nature. On the other hand, the entanglement of different degrees of freedom of the same particle might be considered classical. The classical analog cannot replace Einstein-Podolsky-Rosen type experiments, nor can it be used to build (...) a quantum computer. Nevertheless, it does provide a reliable guide to the intuition and a tool for visualizing abstract concepts in low-dimensional Hilbert spaces. (shrink)

Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the (...) theoretical limits of computability. Contrary to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)

In discussions regarding models of cognition, the very mention of “computationalism” often incites reactions against the insufficiency of the Turing machine model, its abstractness, determinism, the lack of naturalist foundations, triviality and the absence of clarity. None of those objections, however, concerns models based on natural computation or computing nature, where the model of computation is broader than symbol manipulation or conventional models of computation. Computing nature consists of physical structures that form layered computational architecture, with computation processes (...) ranging from quantum to chemical, biological/cognitive and social-level computation. It is argued that, on the lower levels of information processing in the brain, finite automata or Turing machines may still be adequate models, while, on the higher levels of whole-brain information processing, natural computing models are necessary. A layered computational architecture of the mind based on the intrinsic computing of physical systems avoids objections against early versions of computationalism in the form of abstract symbols manipulation. (shrink)

Two strategies to infinity are equally relevant for it is as universal and thus complete as open and thus incomplete. Quantum mechanics is forced to introduce infinity implicitly by Hilbert space, on which is founded its formalism. One can demonstrate that essential properties of quantum information, entanglement, and quantum computer originate directly from infinity once it is involved in quantum mechanics. Thus, thеse phenomena can be elucidated as both complete and incomplete, after which choice is the (...) border between them. A special kind of invariance to the axiom of choice shared by quantum mechanics is discussed to be involved that border between the completeness and incompleteness of infinity in a consistent way. The so-called paradox of Albert Einstein, Boris Podolsky, and Nathan Rosen is interpreted entirely in the same terms only of set theory. Quantum computer can demonstrate especially clearly the privilege of the internal position, or “observer”, or “user” to infinity implied by Henkin’s proposition as the only consistent ones as to infinity. (shrink)