Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0412143

Limits on Efficient Computation in the Physical World

Scott Aaronson

Published Dec 20, 2004• 25 citations
arXivHTMLPDF

Abstract

More than a speculative technology, quantum computing seems to challenge our most basic intuitions about how the physical world should behave. In this thesis I show that, while some intuitions from classical computer science must be jettisoned in the light of modern physics, many others emerge nearly unscathed; and I use powerful tools from computational complexity theory to help determine which are which.

DOI
10.48550/arxiv.quant-ph/0412143

Related papers

On the Theory of Quantum and Towards Practical Computation

Robert Kudelić

Quantum computing exposes the brilliance of quantum mechanics through computer science and, as such, gives oneself a marvelous and exhilarating journey to go through. This article leads along that journey with a historical and current outlook on quantum computation that is geared toward computer experts but also to experts from other disciplines as well. It is an article that will bridge the vast gap between classical and quantum computation and open an entering wedge through which one will be able to both bring himself up to speed on quantum computation and, intrinsically, in a straightforward manner, become acquainted with it. We are indeed in luck to be living in an age where computing is being reinvented, and not only seeing history in the making firsthand but, in fact, having the opportunity to be the ones who are reinventing--and that is quite a thought.

arXiv:2403.09682•Feb 7, 2024•3 citations

Quantum computing : problems and exercises

Santiago Torres, P. Bruna, Pietro Massignan

Quantum technology is one of the most promising and challenging fields in contemporary science. Quantum computing, quantum cryptography, and more generally quantum information technologies claim that they, in the short term, will change our paradigm of classical computing and communications. Concepts such as duality, superposition, entanglement, teleportation and many others seem to be closer to magic or science fiction than to everyday human experience. However, herein lies also the unlimited power of human thought, which mathematics and physics help us to go beyond our immediate experience of the world. This book, oriented toward undergraduate students pursuing Bachelor’s Degrees in Engineering, draws on the experience of the authors during nearly ten years of work in this field. The book consists of a comprehensive list of exercises with increasing degrees of dificulty. Additional material such as solved problems and a basic compilation of theory is also included in each chapter. The list of topics, which include among others, quantum computing, quantum teleportation, superdense coding, quantum processors or quantum communication protocols, intended for opening doors that will motivate students to continue delving into the field of quantum technologies, which has only just begun to be explored.

Iniciativa Digital Politècnica. Oficina de Publicacions Acadèmiques Digitals de la UPC eBooks•Jul 1, 2020•0 citations

Physics and Speculative Philosophy

Through both an historical and philosophical analysis of the concept of possibility, we show how including both potentiality and actuality as part of the real is both compatible with experience and contributes to solving key problems of fundamental process and emergence. The book is organized into four main sections that incorporate our routes to potentiality: (1) potentiality in modern science [history and philosophy; quantum physics and complexity]; (2) Relational Realism [ontological interpretation of quantum physics; philosophy and logic]; (3) Process Physics [ontological interpretation of relativity theory; physics and philosophy]; (4) on speculative philosophy and physics [limitations and approximations; process philosophy]. We conclude that certain fundamental problems in modern physics require complementary analyses of certain philosophical and metaphysical issues, and that such scholarship reveals intrinsic features and limits of determinism, potentiality and emergence that enable, among others, important progress on the quantum theory of measurement problem and new understandings of emergence.

De Gruyter eBooks•Feb 20, 2016•6 citations

Keynote Speech: Quantum Physics and the Nature of Computation

Umesh V. Vazirani

Quantum physics is a fascinating area from a computational viewpoint. The features that make quantum systems prohibitively hard to simulate classically are precisely the aspects exploited by quantum computation to obtain exponential speedups over classical computers. In this talk I will survey our current understanding of the power (and limits) of quantum computers, and prospects for experimentally realizing them in the near future. I will also touch upon insights from quantum comuptation that have resulted in new classical algorithms for efficient simulation of certain important quantum systems.

IEEE International Parallel and Distributed Processing Symposium (IPDPS)•Mar 1, 2007•2 citations

Quantum Computing

Mrinal Narang, Jayant Marwaha, Gurpreet Kaur +2 more

Abstract: Quantum computing is a modern calculation method that is based on the science of quantum mechanics. These phenomena include the bizarre behavior of particles at the atomic and subatomic levels, and the way that these particles can be in multiple states simultaneously. The field of computer science is a great mix of physics, math, and information theory. This technology provides high computing power, low power consumption, and exponential speed by controlling the behavior of small physical objects, such as atoms. Atoms, electrons, photons, etc. are all elements of the physical world. We would like to introduce the basics of quantum computing, and some of the ideas behind it. This article begins with the origins of the classical computer and discusses all the improvements and transformations that have been made due to its limitations thus far, then moves on to the basic operations of quantum computing and results in quantum properties such as superposition, entanglement, and interference.

International Journal for Research in Applied Science and Engineering Technology•Dec 15, 2022•1 citation

Quantum computers

David Deutsch

Abstract A number of research programs with widely different motivations have, during the last few years been coming to a conclusion that is startling to some, and which others say they have suspected all along: that the theory of computation is connected at many levels, including the most fundamental, to physics. In particular it has connections with our deepest and most powerful physical theory, quantum theory.

ITNOW•Jun 1, 1987•0 citations
More than a speculative technology, quantum computing seems to challenge our most basic intuitions about how the physical world should behave. In this thesis I show that, while some intuitions from classical computer science must be jettisoned in the light of modern physics, many others emerge nearly unscathed; and I use powerful tools from computational complexity theory to help determine which are which.
Quantum computing exposes the brilliance of quantum mechanics through computer science and, as such, gives oneself a marvelous and exhilarating journey to go through. This article leads along that journey with a historical and current outlook on quantum computation that is geared toward computer experts but also to experts from other disciplines as well. It is an article that will bridge the vast gap between classical and quantum computation and open an entering wedge through which one will be able to both bring himself up to speed on quantum computation and, intrinsically, in a straightforward manner, become acquainted with it. We are indeed in luck to be living in an age where computing is being reinvented, and not only seeing history in the making firsthand but, in fact, having the opportunity to be the ones who are reinventing--and that is quite a thought.
Quantum technology is one of the most promising and challenging fields in contemporary science. Quantum computing, quantum cryptography, and more generally quantum information technologies claim that they, in the short term, will change our paradigm of classical computing and communications. Concepts such as duality, superposition, entanglement, teleportation and many others seem to be closer to magic or science fiction than to everyday human experience. However, herein lies also the unlimited power of human thought, which mathematics and physics help us to go beyond our immediate experience of the world. This book, oriented toward undergraduate students pursuing Bachelor’s Degrees in Engineering, draws on the experience of the authors during nearly ten years of work in this field. The book consists of a comprehensive list of exercises with increasing degrees of dificulty. Additional material such as solved problems and a basic compilation of theory is also included in each chapter. The list of topics, which include among others, quantum computing, quantum teleportation, superdense coding, quantum processors or quantum communication protocols, intended for opening doors that will motivate students to continue delving into the field of quantum technologies, which has only just begun to be explored.
Through both an historical and philosophical analysis of the concept of possibility, we show how including both potentiality and actuality as part of the real is both compatible with experience and contributes to solving key problems of fundamental process and emergence. The book is organized into four main sections that incorporate our routes to potentiality: (1) potentiality in modern science [history and philosophy; quantum physics and complexity]; (2) Relational Realism [ontological interpretation of quantum physics; philosophy and logic]; (3) Process Physics [ontological interpretation of relativity theory; physics and philosophy]; (4) on speculative philosophy and physics [limitations and approximations; process philosophy]. We conclude that certain fundamental problems in modern physics require complementary analyses of certain philosophical and metaphysical issues, and that such scholarship reveals intrinsic features and limits of determinism, potentiality and emergence that enable, among others, important progress on the quantum theory of measurement problem and new understandings of emergence.
Quantum physics is a fascinating area from a computational viewpoint. The features that make quantum systems prohibitively hard to simulate classically are precisely the aspects exploited by quantum computation to obtain exponential speedups over classical computers. In this talk I will survey our current understanding of the power (and limits) of quantum computers, and prospects for experimentally realizing them in the near future. I will also touch upon insights from quantum comuptation that have resulted in new classical algorithms for efficient simulation of certain important quantum systems.
Abstract: Quantum computing is a modern calculation method that is based on the science of quantum mechanics. These phenomena include the bizarre behavior of particles at the atomic and subatomic levels, and the way that these particles can be in multiple states simultaneously. The field of computer science is a great mix of physics, math, and information theory. This technology provides high computing power, low power consumption, and exponential speed by controlling the behavior of small physical objects, such as atoms. Atoms, electrons, photons, etc. are all elements of the physical world. We would like to introduce the basics of quantum computing, and some of the ideas behind it. This article begins with the origins of the classical computer and discusses all the improvements and transformations that have been made due to its limitations thus far, then moves on to the basic operations of quantum computing and results in quantum properties such as superposition, entanglement, and interference.