Quantum Computation

Takes students and researchers on a tour through some of the deepest ideas of maths, computer science and physics.

This Växjö conference was devoted to the reconsideration of quantum foundations. Due to increasing research in quantum information theory, especially on quantum computing and cryptography, many questions regarding the foundations of quantum mechanics, which have long been considered to be exclusively of philosophical interest, nowadays play an important role in theoretical and experimental quantum physics.

Entangled states provide the necessary tools for conceptual tests of quantum mechanics and other alternative theories. These tests include local hidden variables theories, pre- and postselective quantum mechanics, QND measurements, complementarity, and tests of quantum mechanics itself against, e.g., the so-called causal communication constraint. We show how to produce various nonlocal entangled states of multiple cavity fields that are useful for these tests, using cavity QED techniques. First, we discuss the generation of the Bell basis states in two entangled cavities, (...) when there is at most one photon in either of the cavities, and then a straightforward generalization to similar N-cavity states. We then show how to produce a nonlocal entangled state when there is precisely one photon hiding in three cavities. These states can be produced by sending appropriately prepared atoms through the cavities. As applications we briefly review two proposals: one to test quantum mechanics against the causal communication constraint using a two-cavity entangled state and the other to test pre- and postselective quantum mechanics using a three-cavity entangled state. The outcome of the latter experiment can be discussed from the viewpoint of the consistent histories interpretation of quantum mechanics and therefore provides an opportunity to subject quantum cosmological ideas to laboratory tests. Finally, we point out the relation between these schemes and the schemes suggested for quantum computing, teleportation, and quantum copying. (shrink)

Bennett and Schumacher’s postselected quantum teleportation is a model of closed timelike curves (CTCs) that leads to results physically different from Deutsch’s model. We show that even a single qubit passing through a postselected CTC (P-CTC) is sufficient to do any postselected quantum measurement with certainty, and we discuss an important difference between “Deutschian” CTCs (D-CTCs) and P-CTCs in which the future existence of a P-CTC might affect the present outcome of an experiment. Then, based on a suggestion of Bennett (...) and Smith, we explicitly show how a party assisted by P-CTCs can distinguish a set of linearly independent quantum states, and we prove that it is not possible for such a party to distinguish a set of linearly dependent states. The power of P-CTCs is thus weaker than that of D-CTCs because the Holevo bound still applies to circuits using them, regardless of their ability to conspire in violating the uncertainty principle. We then discuss how different notions of a quantum mixture that are indistinguishable in linear quantum mechanics lead to dramatically differing conclusions in a nonlinear quantum mechanics involving P-CTCs. Finally, we give explicit circuit constructions that can efficiently factor integers, efficiently solve any decision problem in the intersection of NP and coNP, and probabilistically solve any decision problem in NP. These circuits accomplish these tasks with just one qubit traveling back in time, and they exploit the ability of postselected closed timelike curves to create grandfather paradoxes for invalid answers. (shrink)

The conference Quantum Africa 2010 addressed recent advances, both theoretical and experimental, in the rapidly progressing field of quantum technologies. In particular progress in the foundations of quantum cryptography, quantum computing as well as quantum metrology was reported.

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: jbub@umd.edu. (shrink)

In The Philosophy of Information, Luciano Floridi presents an ontological theory of Being qua Being, which he calls “Informational Structural Realism”, a theory which applies, he says, to every possible world. He identifies primordial information (“dedomena”) as the foundation of any structure in any possible world. The present essay examines Floridi’s defense of that theory, as well as his refutation of “Digital Ontology” (which some people might confuse with his own). Then, using Floridi’s ontology as a starting point, the present (...) essay adds quantum features to dedomena, yielding an ontological theory for our own universe, Quantum Informational Structural Realism, which provides a metaphysical interpretation of key quantum phenomena, and diminishes the “weirdness” or “spookiness” of quantum mechanics. (shrink)

In both the search for ever smaller and faster computational devices, and the search for a computational understanding of biological systems such as the brain, one is naturally led to consider the possibility of computational devices the size of cells, molecules, atoms, or on even smaller scales. Indeed, it has been pointed out Braunstein, 1995] that if trends over the last forty years continue, we may reach atomic-scale computation by the year 2010 Keyes, 1988]. This move down in scale takes (...) us from systems that can be understood (to a good enough approximation) using classical mechanics alone, to those which require a quantum mechanical understanding. Thus, it should not be surprising to nd that the idea of quantum computation is not new (see, e.g.,Error: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMapError: Illegal entry in bfrange block in ToUnicode CMap Deutsch, 1985] and Feynman, 1982]).. (shrink)

A set of qubit channels has a classical representation when it is isomorphic to the convex closure of a group of classical channels. From Crowder and Martin (Proceedings of Quantum Physics and Logic, Electronic Notes in Theoretical Computer Science, 2009), we know that up to isomorphism there are five such sets, each corresponding to either a subgroup of the alternating group on four letters, or a subgroup of the symmetric group on three letters. In this paper, we show that the (...) classical representation of a qubit channel also carries its information theoretic data—in particular, both the Holevo capacity and the scope of a unital qubit channel can be completely calculated from a systematically determined classical channel. (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)

I argue that our judgements regarding the locally causal models which are compatible with a given quantum no-go theorem implicitly depend, in part, on the context of inquiry. It follows from this that certain no-go theorems, which are particularly striking in the traditional foundational context, have no force when the context switches to a discussion of the physical systems we are capable of building with the aim of classically reproducing quantum statistics. I close with a general discussion of the possible (...) implications of this for our understanding of the limits of classical description, and for our understanding of the fundamental aim of physical investigation. (shrink)

According to the Gottesman–Knill theorem, quantum algorithms that utilize only the operations belonging to a certain restricted set are efficiently simulable classically. Since some of the operations in this set generate entangled states, it is commonly concluded that entanglement is insufficient to enable quantum computers to outperform classical computers. I argue in this article that this conclusion is misleading. First, the statement of the theorem is, on reflection, already evident when we consider Bell’s and related inequalities in the context of (...) a discussion of computational machines. This, in turn, helps us to understand that the appropriate conclusion to draw from the Gottesman–Knill theorem is not that entanglement is insufficient to enable a quantum performance advantage, but rather that if we limit ourselves to the operations referred to in the Gottesman–Knill theorem, we will not have used the resources provided by an entangled quantum system to their full potential. (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 aim of this dissertation is to clarify the debate over the explanation of quantum speedup and to submit, for the reader's consideration, a tentative resolution to it. In particular, I argue, in this dissertation, that the physical explanation for quantum speedup is precisely the fact that the phenomenon of quantum entanglement enables a quantum computer to fully exploit the representational capacity of Hilbert space. This is impossible for classical systems, joint states of which must always be representable as product (...) states. I begin the dissertation by considering, in Chapter 2, the most popular of the candidate physical explanations for quantum speedup: the many worlds explanation of quantum computation. I argue that, although it is inspired by the neo-Everettian interpretation of quantum mechanics, unlike the latter it does not have the conceptual resources required to overcome objections such as the so-called `preferred basis objection'. I further argue that the many worlds explanation, at best, can serve as a good description of the physical process which takes place in so-called network-based computation, but that it is incompatible with other models of computation such as cluster state quantum computing. I next consider, in Chapter 3, a common component of most other candidate explanations of quantum speedup: quantum entanglement. I investigate whether entanglement can be said to be a necessary component of any explanation for quantum speedup, and I consider two major purported counter-examples to this claim. I argue that neither of these, in fact, show that entanglement is unnecessary for speedup, and that, on the contrary, we should conclude that it is. In Chapters 4 and 5 I then ask whether entanglement can be said to be sufficient as well. In Chapter 4 I argue that despite a result that seems to indicate the contrary, entanglement, considered as a resource, can be seen as sufficient to enable quantum speedup. Finally, in Chapter 5 I argue that entanglement is sufficient to explain quantum speedup as well. (shrink)

I argue that the many worlds explanation of quantum computation is not licensed by, and in fact is conceptually inferior to, the many worlds interpretation of quantum mechanics from which it is derived. I argue that the many worlds explanation of quantum computation is incompatible with the recently developed cluster state model of quantum computation. Based on these considerations I conclude that we should reject the many worlds explanation of quantum computation.

Shi and Aharonov have shown that the Toffoli gate and the Hadamard gate give rise to an approximately universal set of quantum computational gates. The basic algebraic properties of this system have been studied in Dalla Chiara et al. (Foundations of Physics 39(6):559–572, 2009), where we have introduced the notion of Shi-Aharonov quantum computational structure. In this paper we propose an algebraic abstraction from the Hilbert-space quantum computational structures, by introducing the notion of Toffoli-Hadamard algebra. From an intuitive point of (...) view, such abstract algebras represent a natural quantum generalization of both classical and fuzzy-like structures. (shrink)

Of John Wheeler’s ‘Really Big Questions’, the one on which the most progress has been made is It From Bit? – does information play a significant role at the foundations of physics? It is perhaps less ambitious than some of the other Questions, such as How Come Existence?, because it does not necessarily require a metaphysical answer. And unlike, say, Why The Quantum?, it does not require the discovery of new laws of nature: there was room for hope that it (...) might be answered through a better understanding of the laws as we currently know them, particularly those of quantum physics. And this is what has happened: the better understanding is the quantum theory of information and computation. (shrink)

It has been argued, partly from the lack of any widely accepted solution to the measurement problem, and partly from recent results from quantum information theory, that measurement in quantum theory is best treated as a black box. However, there is a crucial difference between ‘having no account of measurement' and ‘having no solution to the measurement problem'. We know a lot about measurements. Taking into account this knowledge sheds light on quantum theory as a theory of information and computation. (...) In particular, the scheme of ‘one-way quantnum computation' takes on a new character in light of the role that reference frames play in actually carrying out any one-way quantum comptuation. ‡Thanks to audiences at the PSA and the Centre for Time, University of Sydney, for helpful comments and questions. †To contact the author, please write to: Department of Philosophy, University of South Carolina, Columbia, SC 29208; e-mail: dickson@sc.edu. (shrink)

The foundations of quantum mechanics are attracting new and significant interest in the scientific community due to the recent striking experimental and technical progress in the fields of quantum computation, quantum teleportation and quantum information processing. However, at a more fundamental level the understanding and manipulation of these novel phenomena require not only new laboratory techniques but also new understanding, development and interpretation of the formalism of quantum mechanics itself, a mathematical structure whose connection to what happens in physical reality (...) continues to present puzzles and engender debate.The present issue of Foundations of Physics considers, from physical, philosophical and logical perspectives, a range of problems: these range from the meaning of quantum identity and individuality, through probability and complementarity, to decoherence and gauge theories.The idea of preparing this special issue was conceived in connection with the Workshop .. (shrink)

We provide an alternative view of the efficient classical simulatibility of fermionic linear optics in terms of Slater determinants. We investigate the generic effects of two-mode measurements on the Slater number of fermionic states. We argue that most such measurements are not capable (in conjunction with fermion linear optics) of an efficient exact implementation of universal quantum computation. Our arguments do not apply to the two-mode parity measurement, for which exact quantum computation becomes possible.

David Deutsch and others have suggested that the Many-Worlds Interpretation of quantum mechanics is the only interpretation capable of explaining the special efficiency quantum computers seem to enjoy over classical ones. I argue that this view is not tenable. Using a toy algorithm I show that the Many-Worlds Interpretation must crucially use the ontological status of the universal state vector to explain quantum computational efficiency, as opposed to the particular ontology of the MWI, that is, the computational histories of worlds. (...) As such, any other interpretation that treats the state vector as representing real ontological features of a system can explain quantum speedup too. ‡Thanks to Soazig Le Bihan for her critical comments on this paper. †To contact the author, please write to: Department of Philosophy, Liberal Arts 101, University of Montana, Missoula, MT 59812; e-mail: armond. duwell @umontana.edu. (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)

The physical limitations, due to quantum mechanics, on the functioning of computers are analyzed.

Quantum probability theory offers a viable alternative to classical probability, although there are some ambiguities inherent in transferring the quantum formalism to a less determined realm. A number of physicists are now looking at the applicability of quantum ideas to the assessment of physics learning, an area particularly suited to quantum probability ideas.

In this paper we investigate a categorical equivalence between square root qMV-algehras (a variety of algebras arising from quantum computation) and a category of preordered semigroups.

M. Gams et al. (Eds.) IOS Press, "Strong AI": an Adolescent Disorder Donald Michie Professor Emeritus, University of Edinburgh, UK Associate ...

The relationship between quantum collapse and consciousness is reconsidered under the assumption that quantum collapse is an objective dynamical process. We argue that the conscious observer can have a distinct role from the physical measuring device during the process of quantum collapse owing to the intrinsic nature of consciousness; the conscious observer can know whether he is in a definite state or a quantum superposition of definite states, while the physical measuring device cannot “know”. As a result, the consciousness observer (...) can distinguish the definite states and their quantum superposition, while the physical measuring device without consciousness cannot do. This provides a possible quantum physical method to distinguish man and machine. The new result also implies that consciousness has causal efficacies in the physical world when considering the existence of quantum collapse. Accordingly consciousness is not reducible or emergent, but a new fundamental property of matter. This may establish a quantum basis for panpsychism, and make it be a promising solution to the hard problem of consciousness. Furthermore, it is suggested that a unified theory of matter and consciousness includes two parts: one is the psychophysical principle or corresponding principle between conscious content and matter state, and the other is the complete quantum evolution of matter state, which includes the definite nonlinear evolution element introduced by consciousness and relating to conscious content. Lastly, some experimental schemes are presented to test the proposed quantum theory of consciousness. (shrink)

In this paper we try to make a clear distinction between quantum mysticism and quantum mind theory. Quackery always accompanies science especially in controversial and still under development areas and since the quantum mind theory is a science youngster it must clearly demarcate itself from the great stuff of pseudo-science currently patronized by the term "quantum mind". Quantum theory has attracted a big deal of attention and opened new avenues for building up a physical theory of mind because its principles (...) and experimental foundations are as strange as the phenomenon of consciousness itself. Yet, the unwarranted recourse to paranormal phenomena as supporting the quantum mind theory plus the extremely bad biological mismodeling of brain physiology lead to great scepticism about the viability of the approach. We give as an example the Hameroff-Penrose Orch OR model with a list of twenty four problems not being repaired for a whole decade after the birth of the model in 1996. In the exposition we have tried not only to pesent critique of the spotted flaws, but to provide novel possibilities towards creation of neuroscientific quantum model of mind that incorporates all the available data from the basic disciplines (biochemistry, cell physiology, etc.) up to the clinical observations (neurology, neurosurgery, molecular psychiatry, etc.). Thus in a concise fashion we outline what can be done scientifically to improve the Q-mind theory and start a research programme (in Lakatos sense) that is independent on the particular flaws in some of the existing Q-mind models. (shrink)