I discuss the philosophical implications that the rising new science of quantum computing may have on the philosophy of computer science. While quantum algorithms leave the notion of Turing-Computability intact, they may re-describe the abstract space of computational complexity theory hence militate against the autonomous character of some of the concepts and categories of computer science.

Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. In effect, they follow the same logical paradigm as (multi-particle) interferometers. We show how most known quantum algorithms for factorising and counting, may be cast in this manner. Quantum searching is described as inducing a desired relative phase between two eigenvectors to yield constructive interference on the sought elements and destructive interference on the remaining terms.

The ideas of quantum simulation and advances in quantum algorithms to solve quantum chemistry problems have been discussed. Theoretical proposals and experimental investigations both have been studied to gauge the extent to which quantum computation has been applied to solve quantum chemical problems till date. The distinctive features and limitations of the application of quantum simulation on chemical systems and current approaches to define and improve upon standard quantum algorithms have been studied in (...) detail. The possibility and consequences of designing an efficient quantum computer that can address chemical problems have been assessed. The experimental realization of quantum supremacy defies the conventional belief of chemists, that millions of qubits would be required to solve fundamental chemistry problems. It is predicted that quantum simulation of quantum chemistry problems will radically revolutionize this field. (shrink)

In many real-life situations, we are interested in the value of a physical quantity y that is difficult or impossible to measure directly. To estimate y, we find some easier-to-measure quantities x1, … , xn which are related to y by a known relation y = f. Measurements are never 100% accurate; hence, the measured values equation image are different from xi, and the resulting estimate equation image is different from the desired value y = f. How different can it (...) be? Traditional engineering approach to error estimation in data processing assumes that we know the probabilities of different measurement errors equation image. In many practical situations, we only know the upper bound Δi for this error; hence, after the measurement, the only information that we have about xi is that it belongs to the interval equation image. In this case, it is important to find the range y of all possible values of y = f when xi ∈ xi. We start the paper with a brief overview of the computational complexity of the corresponding interval computation problems: Most of the related problems turn out to be, in general, at least NP-hard. In this paper, we show how the use of quantum computing can speed up some computations related to interval and probabilistic uncertainty. We end the paper with speculations on whether “hypothetic” physical devices can compute NP-hard problems faster than in exponential time. Most of the paper's results were first presented at NAFIPS'2003 [30]. (shrink)

The usual representation of quantum algorithms, limited to the process of solving the problem, is physically incomplete. We complete it in three steps: extending the representation to the process of setting the problem, relativizing the extended representation to the problem solver to whom the problem setting must be concealed, and symmetrizing the relativized representation for time reversal to represent the reversibility of the underlying physical process. The third steps projects the input state of the representation, where the problem solver (...) is completely ignorant of the setting and thus the solution of the problem, on one where she knows half solution. Completing the physical representation shows that the number of computation steps required to solve any oracle problem in an optimal quantum way should be that of a classical algorithm endowed with the advanced knowledge of half solution. (shrink)

In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can …nd a single marked object in a database of size N by using only O(pN ) queries of the oracle that identi…es the object. His result was generalized to the case of …nding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either M or K, (...) M < K, our task is to determine which is the case. We show how to solve this problem with a high probability of success using only iterations of Grover’s basic step (and no other algorithm). Let m be the required number of iterations; we prove that under certain restrictions on the sizes of M and K the estimation.. (shrink)

This article analyzes current attitudes toward artificial intelligence (AI) and quantum computing and argues that they represent a modern‐day form of magical thinking. It proposes that AI and quantum computing are thus excellent examples of the ways that traditional distinctions between religion, science, and magic fail to account for the vibrancy and energy that surround modern technologies.

In the same way as the quantum no-cloning theorem and quantum key distribution in two preceding papers, entanglement-assisted quantum teleportation and Grover’s search algorithm are generalized by transferring them to an abstract setting, including usual quantum mechanics as a special case. This again shows that a much more general and abstract access to these quantum mechanical features is possible than commonly thought. A non-classical extension of conditional probability and, particularly, a very special type of (...) state-independent conditional probability are used instead of Hilbert spaces and wavefunctions. (shrink)

Considering the highly complex structure of quantum chaos and the nonstationary characteristics of speech signals, this paper proposes a quantum chaotic encryption and quantum particle swarm extraction method based on an underdetermined model. The proposed method first uses quantum chaos to encrypt the speech signal and then uses the local mean decomposition method to construct a virtual receiving array and convert the underdetermined model to a positive definite model. Finally, the signal is extracted using the Levi (...) flight strategy based on kurtosis and the quantum particle swarm optimization optimized by the greedy algorithm. The bit error rate and similarity coefficient of the voice signal are extracted by testing the source voice signal SA1, SA2, and SI943 under different SNR, and the similarity coefficient, uncertainty, and disorder of the observed signal and the source voice signal SA1, SA2, and SI943 verify the effectiveness of the proposed speech signal extraction method and the security of quantum chaos used in speech signal encryption. (shrink)

Multiple sequence alignment is one of the major problems that can be encountered in the bioinformatics field. MSA consists in aligning a set of biological sequences to extract the similarities between them. Unfortunately, this problem has been shown to be NP-hard. In this article, a new algorithm was proposed to deal with this problem; it is based on a quantum-inspired cuckoo search algorithm. The other feature of the proposed approach is the use of a randomized progressive alignment (...) method based on a hybrid global/local pairwise algorithm to construct the initial population. The results obtained by this hybridization are very encouraging and show the feasibility and effectiveness of the proposed solution. (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)

A quantum algorithm succeeds not because the superposition principle allows ‘the computation of all values of a function at once’ via ‘quantum parallelism’, but rather because the structure of a quantum state space allows new sorts of correlations associated with entanglement, with new possibilities for information‐processing transformations between correlations, that are not possible in a classical state space. I illustrate this with an elementary example of a problem for which a quantum algorithm is more (...) efficient than any classical algorithm. I also introduce the notion of ‘pseudotelepathic’ games and show how the difference between classical and quantum correlations plays a similar role here for games that can be won by quantum players exploiting entanglement, but not by classical players whose only allowed common resource consists of shared strings of random numbers (common causes of the players’ correlated responses in a game). *Received October 2008. †To contact the author, please write to: Department of Philosophy, University of Maryland, College Park, MD 20742; e‐mail: [email protected]. (shrink)

We explore the possibility of using quantum mechanical principles for hypercomputation through the consideration of a quantum algorithm for computing the Turing halting problem. The mathematical noncomputability is compensated by the measurability of the values of quantum observables and of the probability distributions for these values. Some previous no-go claims against quantum hypercomputation are then reviewed in the light of this new positive proposal.

We study the question of how to decompose Hilbert space into a preferred tensor-product factorization without any pre-existing structure other than a Hamiltonian operator, in particular the case of a bipartite decomposition into "system" and "environment." Such a decomposition can be defined by looking for subsystems that exhibit quasi-classical behavior. The correct decomposition is one in which pointer states of the system are relatively robust against environmental monitoring (their entanglement with the environment does not continually and dramatically increase) and remain (...) localized around approximately-classical trajectories. We present an in-principle algorithm for finding such a decomposition by minimizing a combination of entanglement growth and internal spreading of the system. Both of these properties are related to locality in different ways. This formalism could be relevant to the emergence of spacetime from quantum entanglement. (shrink)

An original quantum foundations concept of a deep learning computational Universe is introduced. The fundamental information of the Universe (or Triuniverse)is postulated to evolve about itself in a Red, Green and Blue (RGB) tricoloured stable self-mutuality in three information processing loops. The colour is a non-optical information label. The information processing loops form a feedback-reinforced deep learning macrocycle with trefoil knot topology. Fundamental information processing is driven by ψ-Epistemic Drive, the Natural appetite for information selected for advantageous knowledge. From (...) its substrate of Mathematics, the knotted information processing loops determine emergent Physics and thence the evolution of super-emergent Life (biological and artificial intelligence). RGB-tricoloured information is processed in sequence in an Elemental feedback loop (R), then an Operational feedback loop (G), then a Structural feedback loop (B) and back to an Elemental feedback loop (R), and so on around the trefoil in deep learning macrocycles. It is postulated that hierarchical information correspondence from Mathematics through Physics to Life is mapped and conserved within each colour. The substrate of Mathematics has RGB-tricoloured feedback loops which are respectively Algebra (R), Algorithms (G) and Geometry (B). In Mathematics, the trefoil macrocycle is Algebraic Algorithmic Geometry and its correlation system is a Tensor Neural Knot Network enabling Qutrit Entanglement. Emergent Physics has corresponding RGB-tricoloured feedback loops of Quantum Mechanics (R), Quantum Deep Learning (G) and Quantum Geometrodynamics(B). In Physics, the trefoil macrocycle is Quantum Intelligent Geometrodynamics and its correlation system is Quantum Darwinism. Super-emergent Life has corresponding RGB-tricoloured loops of Variation (R), Selection (G) and Heredity (B). In the evolution of Life, the trefoil macrocycle is Variational Selective Heredity and its correlation ecosystem is Darwin’s ecologically “Entangled Bank”. (shrink)

A recent attempt to compute a (recursion‐theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion‐theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.

We discuss two qualities of quantum systems: various correlations existing between their subsystems and the distinguishability of different quantum states. This is then applied to analysing quantum information processing. While quantum correlations, or entanglement, are clearly of paramount importance for efficient pure state manipulations, mixed states present a much richer arena and reveal a more subtle interplay between correlations and distinguishability. The current work explores a number of issues related with identifying the important ingredients needed for (...) quantum information processing. We discuss the Deutsch-Jozsa algorithm, the Shor algorithm, the Grover algorithm and the power of a single qubit class of algorithms. In the latter, a quantity called discord is seen to be more important than entanglement. One section is dedicated to cluster states where entanglement is crucial, but its precise role is highly counter-intuitive. Here we see that the notion of distinguishability becomes a more useful concept. (shrink)

A recent proposal to solve the halting problem with the quantum adiabatic algorithm is criticized and found wanting. Contrary to other physical hypercomputers, where one believes that a physical process “computes” a (recursive-theoretic) non-computable function simply because one believes the physical theory that presumably governs or describes such process, believing the theory (i.e., quantum mechanics) in the case of the quantum adiabatic “hypercomputer” is tantamount to acknowledging that the hypercomputer cannot perform its task.

Is quantum mechanics about ‘states’? Or is it basically another kind of probability theory? It is argued that the elementary formalism of quantum mechanics operates as a well-justified alternative to ‘classical’ instantiations of a probability calculus. Its providing a general framework for prediction accounts for its distinctive traits, which one should be careful not to mistake for reflections of any strange ontology. The suggestion is also made that quantum theory unwittingly emerged, in Schrödinger’s formulation, as a ‘lossy’ (...) by-product of a quantum-mechanical variant of the Hamilton-Jacobi equation. As it turns out, the effectiveness of quantum theory qua predictive algorithm makes up for the computational impracticability of that master equation. (shrink)

The paper describes an algorithm for semantic representation of behavioral contexts relative to a dichotomic decision alternative. The contexts are represented as quantum qubit states in two-dimensional Hilbert space visualized as points on the Bloch sphere. The azimuthal coordinate of this sphere functions as a one-dimensional semantic space in which the contexts are accommodated according to their subjective relevance to the considered uncertainty. The contexts are processed in triples defined by knowledge of a subject about a binary situational (...) factor. The obtained triads of context representations function as stable cognitive structure at the same time allowing a subject to model probabilistically-variative behavior. The developed algorithm illustrates an approach for quantitative subjectively-semantic modeling of behavior based on conceptual and mathematical apparatus of quantum theory. (shrink)

In quantum computation non classical features such as superposition states and entanglement are used to solve problems in new ways, impossible on classical digital computers.We illustrate by Deutsch algorithm how a quantum computer can use superposition states to outperform any classical computer. We comment on the view of a quantum computer as a massive parallel computer and recall Amdahls law for a classical parallel computer. We argue that the view on quantum computation as a massive (...) parallel computation disregards the presence of entanglement in a general quantum computation and the non classical way in which parallel results are combined to obtain the final output. (shrink)

Marchildon’s (favorable) assessment (quant-ph/0303170, to appear in Found. Phys.) of the Pondicherry interpretation of quantum mechanics raises several issues, which are addressed. Proceeding from the assumption that quantum mechanics is fundamentally a probability algorithm, this interpretation determines the nature of a world that is irreducibly described by this probability algorithm. Such a world features an objective fuzziness, which implies that its spatiotemporal differentiation does not “go all the way down”. This result is inconsistent with the existence (...) of an evolving instantaneous state, quantum or otherwise. (shrink)

The standard axiomatization of quantum mechanics (QM) is not fully explicit about the role of the time-parameter. Especially, the time reference within the probability algorithm (the Born Rule, BR) is unclear. From a probability principle P1 and a second principle P2 affording a most natural way to make BR precise, a logical conflict with the standard expression for the completeness of QM can be derived. Rejecting P1 is implausible. Rejecting P2 leads to unphysical results and to a conflict (...) with a generalization of P2, a principle P3. All three principles are shown to be without alternative. It is thus shown that the standard expression of QM completeness must be revised. An absolutely explicit form of the axioms is provided, including a precise form of the projection postulate. An appropriate expression for QM completeness, reflecting the restrictions of the Gleason and Kochen-Specker theorems is proposed. (shrink)

Quantum invariance designates the relation of any quantum coherent state to the corresponding statistical ensemble of measured results. The adequate generalization of ‘measurement’ is discussed to involve the discrepancy, due to the fundamental Planck constant, between any quantum coherent state and its statistical representation as a statistical ensemble after measurement. A set-theory corollary is the curious invariance to the axiom of choice: Any coherent state excludes any well-ordering and thus excludes also the axiom of choice. It should (...) be equated to a well-ordered set after measurement and thus requires the axiom of choice. Quantum invariance underlies quantum information and reveals it as the relation of an unordered quantum “much” (i.e. a coherent state) and a well-ordered “many” of the measured results (i.e. a statistical ensemble). It opens up to a new horizon, in which all physical processes and phenomena can be interpreted as quantum computations realizing relevant operations and algorithms on quantum information. All phenomena of entanglement can be described in terms of the so defined quantum information. Quantum invariance elucidates the link between general relativity and quantum mechanics and thus, the problem of quantum gravity. (shrink)

Standard quantum theory is inadequate to explain the mechanisms by which potential becomes actual. It is inadequate and therefore unable to describe generation of events. Niels Bohr emphasized long ago that the classical part of the world is necessary. John Bell stressed the same point: that “measurement≓ cannot even be defined within the standard quantum theory, and he sought a solution within hidden variable theories and his concept of “beables.≓Today it is customary to try to explain emergence of (...) the classical world through a decoherence mechanism due to “environment.≓ But, we believe, as it was with the concept of measurement, “environment≓ itself cannot be defined within the standard quantum theory.We have proposed a semiphenomenological solution to this problem by introducing explicitly, from the very beginning, classical degrees of freedom, and by coupling these degrees of freedom, through a Lindblad type coupling, to the quantum world. The resulting theory, we call “event-enhanced quantum theory.≓ EEQT allows us to describe an event-generating mechanism for individual quantum systems under continuous observation. The objections of John Bell are met and precise definitions of an “experiment≓ and of a “measurement≓ have been given within EEQT. However EEQT is, essentially, a nonrelativistic theory.In the present paper we extend the ideas of L. P. Horwitz and C. Piron and we propose a relativistic version of EEQT, with an event-generating algorithm for spin one-half particle detectors. The algorithm is based on proper time formulation of the relalivistic quantum theory. Although we use indefinite metric, all the probabilities controlling the random process of the detector clicks are nonnegative. (shrink)

This book gives an overview for practitioners and students of quantum physics and information science. It provides ready access to essential information on quantum information processing and communication, such as definitions, protocols and algorithms. Quantum information science is rarely found in clear and concise form. This book brings together this information from its various sources. It allows researchers and students in a range of areas including physics, photonics, solid-state electronics, nuclear magnetic resonance and information technology, in their (...) applied and theoretical branches, to have this vital material directly at hand. (shrink)

We consider a quaternionic quantum formalism for the description of quantum states and quantum dynamics. We prove that generalized quantum measurements on physical systems in quaternionic quantum theory can be simulated by usual quantum measurements with positive operator valued measures on complex Hilbert spaces. Furthermore, we prove that quaternionic quantum channels can be simulated by completely positive trace preserving maps on complex matrices. These novel results map all quaternionic quantum processes to algorithms (...) in usual quantum information theory. (shrink)

The paper begins with a general introduction to the nature of human consciousness and outlines several different philosophical approaches. A critique of traditional reductionist and dualist positions is offered and it is suggested that consciousness should be viewed as an emergent property of physical systems. However, although consciousness has its origin in distributed brain processes it has macroscopic properties - most notably the `unitary sense of self', non-deterministic free will, and non-algorithmic `intuitive' processing - which can best be described by (...) quantum-mechanical principles. (shrink)

The Ghirardi–Rimini–Weber (GRW) theory of spontaneous wave function collapse is known to provide a quantum theory without observers, in fact two different ones by using either the matter density ontology (GRWm) or the flash ontology (GRWf). Both theories are known to make predictions different from those of quantum mechanics, but the difference is so small that no decisive experiment can as yet be performed. While some testable deviations from quantum mechanics have long been known, we provide here (...) something that has until now been missing: a formalism that succinctly summarizes the empirical predictions of GRWm and GRWf. We call it the GRW formalism. Its structure is similar to that of the quantum formalism but involves different operators. In other words, we establish the validity of a general algorithm for directly computing the testable predictions of GRWm and GRWf. We further show that some well-defined quantities cannot be measured in a GRW world, for example the number of collapses in a system during a chosen time interval. (shrink)

A primary goal of quantum computer science is to find an explanation for the fact that quantum computers are more powerful than classical computers. In this paper I argue that to answer this question is to compare algorithmic processes of various kinds and to describe the possibility spaces associated with these processes. By doing this, we explain how it is possible for one process to outperform its rival. Further, in this and similar examples little is gained in subsequently (...) asking a how-actually question. Once one has explained how-possibly, there is little left to do. (shrink)

The Ghirardi–Rimini–Weber (GRW) theory of spontaneous wave function collapse is known to provide a quantum theory without observers, in fact two different ones by using either the matter density ontology (GRWm) or the flash ontology (GRWf). Both theories are known to make predictions different from those of quantum mechanics, but the difference is so small that no decisive experiment can as yet be performed. While some testable deviations from quantum mechanics have long been known, we provide here (...) something that has until now been missing: a formalism that succinctly summarizes the empirical predictions of GRWm and GRWf. We call it the GRW formalism. Its structure is similar to that of the quantum formalism but involves different operators. In other words, we establish the validity of a general algorithm for directly computing the testable predictions of GRWm and GRWf. We further show that some well-defined quantities cannot be measured in a GRWm or GRWf world. (shrink)

The purpose of this book is to initiate a new discipline, namely a formalized epistemological method drawn from the cognitive strategies practised in the most effective among the modern scientific disciplines, as well as from general philosophical thinking. Indeed, what is lacking in order to improve our knowledge and our domination of the modes which nowadays are available for the generation and communication of knowledge, thoroughly and rapidly and with precision and detail? It is a systematic explication of the epistemological (...) essence encrypted in the specialized languages and algorithms of the major modern scientific approaches, a systematic cross-referencing of the explicated results, and a final elaboration of a new coherent whole. Quantum mechanics, like a diver, can take us down to the level of the very first actions of our conceptualization of reality. And starting from there, it can induce an explicit understanding of certain fundamental features of the new scientific thinking. A formalized epistemology should not be mistaken for a crossdisciplinary or a multidisciplinary project. The latter projects are designed to offer to nonspecialists access to information, to results obtained inside specialized disciplines, as well as a certain understanding of these results; whereas a formalized epistemology should equip anyone with a framework for conceptualizing himself in whatever domain and direction he or she might choose. A formalized epistemology should not be mistaken either for an approach belonging to the modern cognitive sciences. These try to establish as neutrally as possible descriptions of how the human body-and-mind work spontaneously when knowledge is generated; whereas a method of conceptualization should establish what conceptual-operational deliberate procedures have to be applied in order to represent and to achieve processes of generation of knowledge optimized accordingly to any definite aims. This book addresses philosophers of science, physicists, mathematicians, logicians, computer scientists, researchers in cognitive sciences, and biologists, as well as any intellectual who is interested in scientific and philosophical thinking. (shrink)

Because intelligent agents employ physically embodied cognitive systems to reason about the world, their cognitive abilities are constrained by the laws of physics. Scientists have used digital computers to develop and validate theories of physically embodied cognition. Computational theories of intelligence have advanced our understanding of the nature of intelligence and have yielded practically useful systems exhibiting some degree of intelligence. However, the view of cognition as algorithms running on digital computers rests on implicit assumptions about the physical world that (...) are incorrect. Recently, the view is emerging of computing systems as goal-directed agents, evolving during problem solving toward improved world models and better task performance. A full realization of this vision requires a new logic for computing that incorporates learning from experience as an intrinsic part of the logic, and that permits full exploitation of the quantum nature of the physical world. This paper proposes a theory of physically embodied cognitive agents founded upon first-order logic, Bayesian decision theory, and quantum physics. An abstract architecture for a physically embodied cognitive agent is presented. The cognitive aspect is represented as a Bayesian decision theoretic agent; the physical aspect is represented as a quantum process; and these aspects are related through von Neumann’s principle of psycho-physical parallelism. Alternative metaphysical positions regarding the meaning of quantum probabilities and the role of efficacious choices by agents are discussed in relation to the abstract agent architecture. The concepts are illustrated with an extended example from the domain of science fiction. (shrink)

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

The algorithmic theory of laws claims that the laws of nature are the algorithms in the best possible compression of all empirical data. This position assumes that the universe is compressible and that data received from observing it is easily reproducible using a simple set of rules. However, there are three sources of evidence that suggest that the universe as a whole is incompressible. The first comes from the practice of science. The other two come from the nature of the (...) universe itself: the presence of chaotic behavior and the nature of quantum systems also suggests that the universe is incompressible. This paper evaluates these sources and argues that none provides a convincing case to reject the algorithmic theory of laws. (shrink)

Quantum computing technologies have become a hot topic in academia and industry receiving much attention and financial support from all sides. Building a quantum computer that can be used practically is in itself an outstanding challenge that has become the ‘new race to the moon’. Next to researchers and vendors of future computing technologies, national authorities are showing strong interest in maturing this technology due to its known potential to break many of today’s encryption techniques, which would have (...) significant and potentially disruptive impact on our society. It is, however, quite likely that quantum computing has beneficial impact on many computational disciplines. In this article we describe our vision of future developments in scientific computing that would be enabled by the advent of software-programmable quantum computers. We thereby assume that quantum computers will form part of a hybrid accelerated computing platform like GPUs and co-processor cards do today. In particular, we address the potential of quantum algorithms to bring major breakthroughs in applied mathematics and its applications. Finally, we give several examples that demonstrate the possible impact of quantum-accelerated scientific computing on society. (shrink)

The following analysis attempts to provide a general account of the multiple solutions given to the quantum measurement problem in terms of causality. Leaving aside instrumentalism which restricts its understanding of quantum mechanics to the algorithmic prediction of measurement outcomes, the many approaches which try to give an answer can be distinguished by their explanation based on the efficient cause —recovering in this way a classical physical description— or based on the final cause —which goes back to the (...) hylomorphic tradition. Going beyond the limits of these two schemes we call the attention to an ‘inversion of the measurement problem’ and its proposed solution based on the immanent cause. By replacing both the final and efficient causes by the immanent cause we attempt to lay down new conditions for representing quantum superpositions in a realist way which coherently relates the quantum formalism with outcomes. (shrink)

In previous works we have established that the spacetime probabilistic organization of the quantum theory is determined by the spacetime characteristics of the operations by which the observer produces the objects to be studied (“states” of microsystems) and obtains qualifications of these. Guided by this first conclusion, we have then built a “general syntax of relativized conceptualization” where any description is explicitly and systematically referred to the two basic epistemic operations by which the conceptor introduces the object to be (...) qualified and then obtains qualifications of it. Inside this syntax there emerges a general typology of the relativized descriptions. Here we show that with respect to this typology the type of the predictive quantum mechanical descriptions acquires a precise definition. It appears that the quantum mechanical formalism has captured and has expressed directly in a mathematical language the most complex form in which can occur a first descriptional phase that lies universally at the bottom of any chain of conceptualization. The main features of the Hilbert-Dirac algorithms are decoded in terms of the general syntax of relativized conceptualization. This renders explicit the semantical contents of the quantum mechanical representations relating each one of these to its mathematical quantum mechanical expression. Basic insufficiencies are thus identified and, correlatively, false problems as well as answers to these, or guides toward answers. Globally the results obtained provide a basis for future attempts at a general mathematical representation of the processes of conceptualization. “Il pourrait, en effet, être dangereux pour l'avenir de la Physique qu'elle se contente trop facilement de purs formalismes, d'images floues et d'explications toutes verbales s'exprimant par des mots à signification imprécise”—Louis de Broglie,Certitudes et Incertitudes de la Science (Albin Michel, Paris, 1965). (shrink)

As a compact representation of joint probability distributions over a dependence graph of random variables, and a tool for modelling and reasoning in the presence of uncertainty, Bayesian networks are of great importance for artificial intelligence to combine domain knowledge, capture causal relationships, or learn from incomplete datasets. Known as a NP-hard problem in a classical setting, Bayesian inference pops up as a class of algorithms worth to explore in a quantum framework. This paper explores such a research direction (...) and improves on previous proposals by a judicious use of the utility function in an entangled configuration. It proposes a completely quantum mechanical decision-making process with a proven computational advantage. A prototype implementation in Qiskit (a Python-based program development kit for the IBM Q machine) is discussed as a proof-of-concept. (shrink)

We investigate the first-order theory of closed subspaces of complex Hilbert spaces in the signature \\), where ‘\’ is the orthogonality relation. Our main result is that already its quasi-identities are undecidable: there is no algorithm to decide whether an implication between equations and orthogonality relations implies another equation. This is a corollary of a recent result of Slofstra in combinatorial group theory. It follows upon reinterpreting that result in terms of the hypergraph approach to quantum contextuality, for (...) which it constitutes a proof of the inverse sandwich conjecture. It can also be interpreted as stating that a certain quantum satisfiability problem is undecidable. (shrink)

Quantum mechanics (QM) predicts probabilities on the fundamental level which are, via Born probability law, connected to the formal randomness of infinite sequences of QM outcomes. Recently it has been shown that QM is algorithmic 1-random in the sense of Martin–Löf. We extend this result and demonstrate that QM is algorithmic $$\omega$$ -random and generic, precisely as described by the ’miniaturisation’ of the Solovay forcing to arithmetic. This is extended further to the result that QM becomes Zermelo–Fraenkel Solovay random (...) on infinite-dimensional Hilbert spaces. Moreover, it is more likely that there exists a standard transitive ZFC model M, where QM is expressed in reality, than in the universe V of sets. Then every generic quantum measurement adds to M the infinite sequence, i.e. random real $$r\in 2^{\omega }$$, and the model undergoes random forcing extensions M[r]. The entire process of forcing becomes the structural ingredient of QM and parallels similar constructions applied to spacetime in the quantum limit, therefore showing the structural resemblance of both in this limit. We discuss several questions regarding measurability and possible practical applications of the extended Solovay randomness of QM. The method applied is the formalization based on models of ZFC; however, this is particularly well-suited technique to recognising randomness questions of QM. When one works in a constant model of ZFC or in axiomatic ZFC itself, the issues considered here remain hidden to a great extent. (shrink)

Quantum probability is used to provide a new organization of basic quantum theory in a logical, axiomatic way. The principal thesis is that there is one fundamental time evolution equation in quantum theory, and this is given by a new version of Born’s Rule, which now includes both consecutive and conditional probability as it must, since science is based on correlations. A major modification of one of the standard axioms of quantum theory allows the implementation of (...) various mathematically distinct models (commonly called ‘pictures’) of them. A natural definition of isomorphism of models is presented next. For a given Hamiltonian the standard ‘pictures’ of quantum theory (e.g., Schrödinger, Heisenberg, interaction) are isomorphic models, whose probabilities are nonetheless model independent. The Schrödinger equation remains valid in one model of the axioms, even though it is no longer the fundamental equation of time evolution. All the usual calculations of standard, textbook quantum theory remain valid, but they are put in a new light. For example, the ‘collapse’ of the state is now viewed in the Schrödinger model as _one_ step in a _two_ step algorithm for calculating _one_ conditional probability. In the isomorphic Heisenberg model, where states are constant in time, one has the same conditional probability given by the same formula. Also, entanglement is defined in a new, more general model independent way as an aspect of quantum probability without using ‘collapse’ or tensor products. (shrink)