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

Cambridge University Press eBooks

Physics and Computation

Armond Duwell

Published Aug 20, 2021• 35 citations
Publisher

Abstract

This Element has three main aims. First, it aims to help the reader understand the concept of computation that Turing developed, his corresponding results, and what those results indicate about the limits of computational possibility. Second, it aims to bring the reader up to speed on analyses of computation in physical systems which provide the most general characterizations of what it takes for a physical system to be a computational system. Third, it aims to introduce the reader to some different kinds of quantum computers, describe quantum speedup, and present some explanation sketches of quantum speedup. If successful, this Element will equip the reader with a basic knowledge necessary for pursuing these topics in more detail.

DOI
10.1017/9781009104975

Related papers

Basics of Quantum Computation (Part 1)

Elemér Elad Rosinger

The aim of this textbook is to bridge in regard of quantum computation what proves to be a considerable threshold even to the usual science trained readership between the level of science popularization, and on the other hand, the presently available more encyclopedic textbooks. In this respect the present textbook is aimed to be a short, simple, rigorous and direct introduction, addressing itself only to quantum computation proper.

arXiv:quant-ph/0407064•Jul 8, 2004•3 citations

Quantum Speedups, Turing’s Barrier and Computational Emergence: Revisit and Generalize Physical Computing for Generative Realties, Intelligence

Hua Chen

Abstract. What mathematical or physicalmechanism that exactly empowers quantumcomputing over classical computers is still an openquestion. By reexamining physics-based methodsand computational primitives, we study quantumspeedups and limitations related to problems’structure, physical resources and no-go laws. Weaim at some fundamental issues by seeking nonclassicalresolutions on the puzzle via rigorousproofs or evidences: 1) Is quantum entanglement themagic? General physical theories show that theconcept is generic for all non-classical systems, yettoo rare as the computation resource for exponentialquantum speedups in various entanglementquantifications. We reinforce that entanglementalone is insufficient as the characteristic measure. 2)Then, what is the physical dynamic behind? howmuch underlying structure is necessary forexponential quantum speedups? We prove that anyquantum search with cumulative memory such asin Darvin’s evolution, instead of ergodic process, ismathematically sufficient to overcome theexponential NP hardness gap. 3) Can quantummechanics compute beyond Turing machines?Quantum adiabatic process and Brownian diffusionmodel are constructed explicitly to demonstrate thatlaws of physics and emergences offer extendedcomputability in principle. We argue that the openquestion on super Turing computing is independentof physical infinities.Based on quantitative analyses and fundamentalconstraints, we arrive at a few theoretical claimstoward generalized computing: a) Exponentialquantum speedups, ranging from minimal to groupstructures, broadly allow utilizations andgeneralizations of quantum methods to any processwith specific dynamic. Namely, there exist degreesof computational jump. b) Inductive and emergentcomputing are necessary to complement logical,deductive computing; where natural laws arereversely captured by compression or emergencevia observation, interaction. Fundamental rules areapplied forward by nature or observer as generativecomputing. c) Generalized physical computing forpartially describable processes is needed to study,understand and control generative realities, generalAI, mental process and emerging social phenomena;that seem beyond conventional logic or physics, yetare computationally unifiable.The article reviews basic concepts, key logic onselect topics in quantum computing, and integratesseminal results, proof sketches and open questionsto offer ranges of handles, bounds and outlooks indevising a unified framework. Basic elements areoutlined toward a powerful computing theory ofnovel applications for generic systems andprocesses, with convergent capacities of universalTuring machine, general physical theories andendless evolution. It lays out a foundation for followup initiatives on specific problems in computation,physics and intelligence by applying with existingphysical methods and computing models.

•Jul 24, 2023•1 citation

Elements of Quantum Computing: History, Theories and Engineering Applications

Seiki Akama

Springer eBooks•Jul 14, 2014•37 citations

Principles of quantum computation and information volume II

Pieter Kok

Any new textbook in quantum information has some pretty strong competition to contend with. Not only is there the classic text by Nielsen and Chuang from 2000 [1], but also John Preskill's lecture notes, available for free online [2]. Nevertheless, a proper textbook seems more enduring than online notes, and the field has progressed considerably in the seven years since Nielsen and Chuang was published. A new textbook is a great opportunity to give a snapshot of our current state of knowledge in quantum information. Therein also lies a problem: The field has expanded so much that it is impossible to cover everything at the undergraduate level. Quantum information theory is relevant to an extremely large portion of physics, from solid state and condensed matter physics to particle physics. Every discipline that has some relation to quantum mechanics is affected by our understanding of quantum information theory. Those who wish to write a book on quantum information therefore have to make some profound choices: Do you keep the ultimate aim of a quantum computer in mind, or do you focus on quantum communication and precision measurements as well? Do you describe how to build a quantum computer with all possible physical systems or do you present only the underlying principles? Do you include only the tried and tested ideas, or will you also explore more speculative directions? You don't have to take a black-or-white stance on these questions, but how you approach them will profoundly determine the character of your book. The authors of `Principles of Quantum Computation and Information (Volume II: Basic Tools and Special Topics)' have chosen to focus on the construction of quantum computers, but restrict themselves mainly to general techniques. Only in the last chapter do they explicitly address the issues that arise in the different implementations. The book is the second volume in a series, and consists of four chapters (labelled 5 to 8) called 'Quantum Information Theory', 'Decoherence', 'Quantum Error Correction', and 'First Experimental Implementations'. The first volume covers the basics of classical computation, quantum mechanics, quantum computation, and quantum communication. Chapter five starts with the density matrix formalism, and proceeds with the development of the Kraus representation, POVMs, von Neuman entropy, quantum data compression, the Holevo bound, the partial transpose criterion, and it ends with a very nice section on the various entropies that play a role in modern physics. This includes not only the thermodynamical and statistical entropy, but also the dynamical Kolmogorov–Sinai entropy, which is used in quantum chaos in chapter 6. On the whole, I think that this is a really clear and well-presented chapter. A minor drawback is that the concept of CP maps is not explained as well as it could have been, for example by relating it to the partial transpose criterion. Chapter six continues with the high standard set in chapter five, and presents a very thorough exposition of decoherence in general. It introduces the different decoherence channels, and gives truly excellent explanations of the master equation (tied in with the Kraus representation), quantum jumps, and the quantum trajectory formalism. It also has an elegant explanation for the sensitivity of Schroedinger cats to decoherence. I do miss a proper section on the fidelity of a quantum state, though. The chapter ends with two sections on quantum chaos. Since the authors are experts in this fascinating area, this is a welcome addition to the canon of topics typically covered in quantum information. Unfortunately, the section is quite hard to follow, and as a result it is a bit of a missed opportunity. There is a section on chaos in the first volume of this series, and this may provide the required background. However, for readers who posess only volume II this is of little use. Chapter seven on quantum error correction is disappointing, and I have the feeling that the authors went through the motions without a real passion for the subject matter. The chapter describes various error correction codes, including Hamming codes and CSS codes, but it is virtually silent on fault tolerance; it does not give examples of universal sets of fault tolerant gates, and it does not mention the Solovay–Kitaev theorem. Also, it does not present the stabilizer formalism. All of these are serious omissions in a textbook on quantum information theory. Chapter eight gives a rough sketch of the early simulations and implementations of quantum gates. The readers of this journal will have no trouble following this chapter, but the undergraduate in computer science or mathematics will be completely lost. Most (but not all) physics terms do get a brief explanation, but I doubt whether that is enough to keep non-physicists on board. The chapter covers NMR, cavity QED, ion traps, solid state qubits, and optical implementations of quantum communication. I would have liked to see a more bold choice for the topics covered in the last chapter. For example, whereas liquid-state NMR was an important step in the development of quantum technologies, and many current techniques were invented for it, it does no longer play a role in the design of quantum computers. It would have been better to introduce these techniques in a section on condensed matter systems. Also, as a snapshot of our current state of knowledge in quantum information, I really miss extensive sections on the one-way model of quantum computing [3] and topological quantum computing [4]. In conclusion, the second volume of 'Principles of Quantum Computation and Information' is a partial success. The first two chapters are very good, and I would happily pay £22 for these two chapters alone. However, for a text on quantum error correction the reader is better off with Nielsen and Chuang or Preskill's lecture notes. If the reader wants an overview of quantum information in specific physical systems, there are a host of review articles to choose from, which give more details and are generally more accessible. References [1]M A Nielsen and I L Chuang 2000 Quantum Computation and Quantum Information (Cambridge University Press) [2] J Preskill, http://www.theory.caltech.edu/~preskill/ph229/ [3] R Raussendorf and H J Briegel 2001 A One-Way Quantum Computer Phys. Rev. Lett. 86 5188 [4] A Yu Kitaev 2003 Fault-tolerant quantum computation by anyons Ann. Phys. 303 2

Journal of Physics A Mathematical and Theoretical•Sep 18, 2007•8 citations

Quantum Computation: An Introduction for Engineers and Computer Scientists

Andreas de Vries

•Mar 1, 2012•6 citations

A Quantum Model for Trend and Political Forecasting

Rubén Ibarrondo López

[EN] This work pursues three main objectives. The first one is to understand and explain quantum adiabatic computation, which requires mastering fundamental concepts on quantum mechanics and learning the practical steps to solve a problem with this technique. The second one is to see a particular example of the physical implementation of quantum computation, more precisely, the implementation with superconducting circuits. The third objective is to describe the procedure followed to develop and experimentally contrast the model in Ref. [6]. This required simulating quantum adiabatic processes and also getting familiar with the data retrieval using Twitter API, which was used to obtain the parameters of the model. This work is divided into three chapters. In the first chapter, I review the necessary background to understand quantum adiabatic computation. In the second one, I explain the most relevant concepts about the implementation of quantum adiabatic computation with superconducting circuits. In the third chapter, I explain the model for forecasting elections and the experimental realization followed to contrast its results.

•Dec 15, 2020•0 citations
This Element has three main aims. First, it aims to help the reader understand the concept of computation that Turing developed, his corresponding results, and what those results indicate about the limits of computational possibility. Second, it aims to bring the reader up to speed on analyses of computation in physical systems which provide the most general characterizations of what it takes for a physical system to be a computational system. Third, it aims to introduce the reader to some different kinds of quantum computers, describe quantum speedup, and present some explanation sketches of quantum speedup. If successful, this Element will equip the reader with a basic knowledge necessary for pursuing these topics in more detail.
Abstract. What mathematical or physicalmechanism that exactly empowers quantumcomputing over classical computers is still an openquestion. By reexamining physics-based methodsand computational primitives, we study quantumspeedups and limitations related to problems’structure, physical resources and no-go laws. Weaim at some fundamental issues by seeking nonclassicalresolutions on the puzzle via rigorousproofs or evidences: 1) Is quantum entanglement themagic? General physical theories show that theconcept is generic for all non-classical systems, yettoo rare as the computation resource for exponentialquantum speedups in various entanglementquantifications. We reinforce that entanglementalone is insufficient as the characteristic measure. 2)Then, what is the physical dynamic behind? howmuch underlying structure is necessary forexponential quantum speedups? We prove that anyquantum search with cumulative memory such asin Darvin’s evolution, instead of ergodic process, ismathematically sufficient to overcome theexponential NP hardness gap. 3) Can quantummechanics compute beyond Turing machines?Quantum adiabatic process and Brownian diffusionmodel are constructed explicitly to demonstrate thatlaws of physics and emergences offer extendedcomputability in principle. We argue that the openquestion on super Turing computing is independentof physical infinities.Based on quantitative analyses and fundamentalconstraints, we arrive at a few theoretical claimstoward generalized computing: a) Exponentialquantum speedups, ranging from minimal to groupstructures, broadly allow utilizations andgeneralizations of quantum methods to any processwith specific dynamic. Namely, there exist degreesof computational jump. b) Inductive and emergentcomputing are necessary to complement logical,deductive computing; where natural laws arereversely captured by compression or emergencevia observation, interaction. Fundamental rules areapplied forward by nature or observer as generativecomputing. c) Generalized physical computing forpartially describable processes is needed to study,understand and control generative realities, generalAI, mental process and emerging social phenomena;that seem beyond conventional logic or physics, yetare computationally unifiable.The article reviews basic concepts, key logic onselect topics in quantum computing, and integratesseminal results, proof sketches and open questionsto offer ranges of handles, bounds and outlooks indevising a unified framework. Basic elements areoutlined toward a powerful computing theory ofnovel applications for generic systems andprocesses, with convergent capacities of universalTuring machine, general physical theories andendless evolution. It lays out a foundation for followup initiatives on specific problems in computation,physics and intelligence by applying with existingphysical methods and computing models.
Any new textbook in quantum information has some pretty strong competition to contend with. Not only is there the classic text by Nielsen and Chuang from 2000 [1], but also John Preskill's lecture notes, available for free online [2]. Nevertheless, a proper textbook seems more enduring than online notes, and the field has progressed considerably in the seven years since Nielsen and Chuang was published. A new textbook is a great opportunity to give a snapshot of our current state of knowledge in quantum information. Therein also lies a problem: The field has expanded so much that it is impossible to cover everything at the undergraduate level. Quantum information theory is relevant to an extremely large portion of physics, from solid state and condensed matter physics to particle physics. Every discipline that has some relation to quantum mechanics is affected by our understanding of quantum information theory. Those who wish to write a book on quantum information therefore have to make some profound choices: Do you keep the ultimate aim of a quantum computer in mind, or do you focus on quantum communication and precision measurements as well? Do you describe how to build a quantum computer with all possible physical systems or do you present only the underlying principles? Do you include only the tried and tested ideas, or will you also explore more speculative directions? You don't have to take a black-or-white stance on these questions, but how you approach them will profoundly determine the character of your book. The authors of `Principles of Quantum Computation and Information (Volume II: Basic Tools and Special Topics)' have chosen to focus on the construction of quantum computers, but restrict themselves mainly to general techniques. Only in the last chapter do they explicitly address the issues that arise in the different implementations. The book is the second volume in a series, and consists of four chapters (labelled 5 to 8) called 'Quantum Information Theory', 'Decoherence', 'Quantum Error Correction', and 'First Experimental Implementations'. The first volume covers the basics of classical computation, quantum mechanics, quantum computation, and quantum communication. Chapter five starts with the density matrix formalism, and proceeds with the development of the Kraus representation, POVMs, von Neuman entropy, quantum data compression, the Holevo bound, the partial transpose criterion, and it ends with a very nice section on the various entropies that play a role in modern physics. This includes not only the thermodynamical and statistical entropy, but also the dynamical Kolmogorov–Sinai entropy, which is used in quantum chaos in chapter 6. On the whole, I think that this is a really clear and well-presented chapter. A minor drawback is that the concept of CP maps is not explained as well as it could have been, for example by relating it to the partial transpose criterion. Chapter six continues with the high standard set in chapter five, and presents a very thorough exposition of decoherence in general. It introduces the different decoherence channels, and gives truly excellent explanations of the master equation (tied in with the Kraus representation), quantum jumps, and the quantum trajectory formalism. It also has an elegant explanation for the sensitivity of Schroedinger cats to decoherence. I do miss a proper section on the fidelity of a quantum state, though. The chapter ends with two sections on quantum chaos. Since the authors are experts in this fascinating area, this is a welcome addition to the canon of topics typically covered in quantum information. Unfortunately, the section is quite hard to follow, and as a result it is a bit of a missed opportunity. There is a section on chaos in the first volume of this series, and this may provide the required background. However, for readers who posess only volume II this is of little use. Chapter seven on quantum error correction is disappointing, and I have the feeling that the authors went through the motions without a real passion for the subject matter. The chapter describes various error correction codes, including Hamming codes and CSS codes, but it is virtually silent on fault tolerance; it does not give examples of universal sets of fault tolerant gates, and it does not mention the Solovay–Kitaev theorem. Also, it does not present the stabilizer formalism. All of these are serious omissions in a textbook on quantum information theory. Chapter eight gives a rough sketch of the early simulations and implementations of quantum gates. The readers of this journal will have no trouble following this chapter, but the undergraduate in computer science or mathematics will be completely lost. Most (but not all) physics terms do get a brief explanation, but I doubt whether that is enough to keep non-physicists on board. The chapter covers NMR, cavity QED, ion traps, solid state qubits, and optical implementations of quantum communication. I would have liked to see a more bold choice for the topics covered in the last chapter. For example, whereas liquid-state NMR was an important step in the development of quantum technologies, and many current techniques were invented for it, it does no longer play a role in the design of quantum computers. It would have been better to introduce these techniques in a section on condensed matter systems. Also, as a snapshot of our current state of knowledge in quantum information, I really miss extensive sections on the one-way model of quantum computing [3] and topological quantum computing [4]. In conclusion, the second volume of 'Principles of Quantum Computation and Information' is a partial success. The first two chapters are very good, and I would happily pay £22 for these two chapters alone. However, for a text on quantum error correction the reader is better off with Nielsen and Chuang or Preskill's lecture notes. If the reader wants an overview of quantum information in specific physical systems, there are a host of review articles to choose from, which give more details and are generally more accessible. References [1]M A Nielsen and I L Chuang 2000 Quantum Computation and Quantum Information (Cambridge University Press) [2] J Preskill, http://www.theory.caltech.edu/~preskill/ph229/ [3] R Raussendorf and H J Briegel 2001 A One-Way Quantum Computer Phys. Rev. Lett. 86 5188 [4] A Yu Kitaev 2003 Fault-tolerant quantum computation by anyons Ann. Phys. 303 2
[EN] This work pursues three main objectives. The first one is to understand and explain quantum adiabatic computation, which requires mastering fundamental concepts on quantum mechanics and learning the practical steps to solve a problem with this technique. The second one is to see a particular example of the physical implementation of quantum computation, more precisely, the implementation with superconducting circuits. The third objective is to describe the procedure followed to develop and experimentally contrast the model in Ref. [6]. This required simulating quantum adiabatic processes and also getting familiar with the data retrieval using Twitter API, which was used to obtain the parameters of the model. This work is divided into three chapters. In the first chapter, I review the necessary background to understand quantum adiabatic computation. In the second one, I explain the most relevant concepts about the implementation of quantum adiabatic computation with superconducting circuits. In the third chapter, I explain the model for forecasting elections and the experimental realization followed to contrast its results.