Vlatko Vedral
- Published in print:
- 2006
- Published Online:
- January 2010
- ISBN:
- 9780199215706
- eISBN:
- 9780191706783
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199215706.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
In addition to treating quantum communication, entanglement, error correction, and algorithms in great depth, this book also addresses a number of interesting miscellaneous topics, such as Maxwell's ...
More
In addition to treating quantum communication, entanglement, error correction, and algorithms in great depth, this book also addresses a number of interesting miscellaneous topics, such as Maxwell's demon, Landauer's erasure, the Bekenstein bound, and Caratheodory's treatment of the second law of thermodynamics. All mathematical derivations are based on clear physical pictures which make even the most involved results — such as the Holevo bound — look comprehensible and transparent. Quantum information is a fascinating topic precisely because it shows that the laws of information processing are actually dependent on the laws of physics. However, it is also very interesting to see that information theory has something to teach us about physics. Both of these directions are discussed throughout the book. Other topics covered in the book are quantum mechanics, measures of quantum entanglement, general conditions of quantum error correction, pure state entanglement and Pauli matrices, pure states and Bell's inequalities, and computational complexity of quantum algorithms.Less
In addition to treating quantum communication, entanglement, error correction, and algorithms in great depth, this book also addresses a number of interesting miscellaneous topics, such as Maxwell's demon, Landauer's erasure, the Bekenstein bound, and Caratheodory's treatment of the second law of thermodynamics. All mathematical derivations are based on clear physical pictures which make even the most involved results — such as the Holevo bound — look comprehensible and transparent. Quantum information is a fascinating topic precisely because it shows that the laws of information processing are actually dependent on the laws of physics. However, it is also very interesting to see that information theory has something to teach us about physics. Both of these directions are discussed throughout the book. Other topics covered in the book are quantum mechanics, measures of quantum entanglement, general conditions of quantum error correction, pure state entanglement and Pauli matrices, pure states and Bell's inequalities, and computational complexity of quantum algorithms.
Vlatko Vedral
- Published in print:
- 2006
- Published Online:
- January 2010
- ISBN:
- 9780199215706
- eISBN:
- 9780191706783
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199215706.003.0011
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
As computers get faster and faster, the size of the circuitry imprinted onto silicon chips decreases. The size of the circuitry becomes so small that its behavior is governed by the laws of quantum ...
More
As computers get faster and faster, the size of the circuitry imprinted onto silicon chips decreases. The size of the circuitry becomes so small that its behavior is governed by the laws of quantum mechanics. Such a computer, whose computations would be fully quantum mechanical, is called a quantum computer. Any computational task such as addition, multiplication, displaying graphics, or updating databases is performed by a computer according to an algorithm — an abstract set of instructions. Quantum computers would accomplish tasks by performing quantum algorithms. A quantum algorithm is a sequence of unitary evolutions carried out on a quantum string made up of qubits, which can exist as a superposition of classical strings. This chapter discusses the computational complexity of a quantum algorithm, Deutsch's algorithm and its efficiency as quantified by the Holevo bound, Oracles, Grover's search algorithm, quantum factorisation, quantum Fourier transform, and phase estimation.Less
As computers get faster and faster, the size of the circuitry imprinted onto silicon chips decreases. The size of the circuitry becomes so small that its behavior is governed by the laws of quantum mechanics. Such a computer, whose computations would be fully quantum mechanical, is called a quantum computer. Any computational task such as addition, multiplication, displaying graphics, or updating databases is performed by a computer according to an algorithm — an abstract set of instructions. Quantum computers would accomplish tasks by performing quantum algorithms. A quantum algorithm is a sequence of unitary evolutions carried out on a quantum string made up of qubits, which can exist as a superposition of classical strings. This chapter discusses the computational complexity of a quantum algorithm, Deutsch's algorithm and its efficiency as quantified by the Holevo bound, Oracles, Grover's search algorithm, quantum factorisation, quantum Fourier transform, and phase estimation.
Dagmar Bruß and Chiara Macchiavello
- Published in print:
- 2011
- Published Online:
- September 2011
- ISBN:
- 9780199603657
- eISBN:
- 9780191729515
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199603657.003.0004
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter contains an introduction to the main concepts in quantum computation and entanglement. It starts with a brief introduction to computational complexity and then introduces quantum gates ...
More
This chapter contains an introduction to the main concepts in quantum computation and entanglement. It starts with a brief introduction to computational complexity and then introduces quantum gates and quantum networks, discussing the universality issue in quantum computation. A review on the main known quantum algorithms follows, including Deutsch's, Deutsch-Jozsa's, Grover's and Shor's algorithms. The basic concepts in the theory of quantum error correction are then reviewed. The second part of the chapter is devoted to entanglement. It starts by reminding the basic definitions of entanglement and entanglement criteria for bipartite and multipartite systems, and then discusses the role that entanglement plays in the quantum algorithms described before. The chapter ends with short descriptions of NMR quantum computing, the computational model DQC1, and one-way quantum computing.Less
This chapter contains an introduction to the main concepts in quantum computation and entanglement. It starts with a brief introduction to computational complexity and then introduces quantum gates and quantum networks, discussing the universality issue in quantum computation. A review on the main known quantum algorithms follows, including Deutsch's, Deutsch-Jozsa's, Grover's and Shor's algorithms. The basic concepts in the theory of quantum error correction are then reviewed. The second part of the chapter is devoted to entanglement. It starts by reminding the basic definitions of entanglement and entanglement criteria for bipartite and multipartite systems, and then discusses the role that entanglement plays in the quantum algorithms described before. The chapter ends with short descriptions of NMR quantum computing, the computational model DQC1, and one-way quantum computing.
Vlatko Vedral
- Published in print:
- 2006
- Published Online:
- January 2010
- ISBN:
- 9780199215706
- eISBN:
- 9780191706783
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199215706.003.0014
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This book has discussed the foundations of quantum information science as well as the relationship between physics and information theory in general. It has considered the quantum equivalents of the ...
More
This book has discussed the foundations of quantum information science as well as the relationship between physics and information theory in general. It has considered the quantum equivalents of the Shannon coding and channel capacity theorems. The von Neumann entropy plays a role analogous to the Shannon entropy, and the Holevo bound is the analogue of Shannon's mutual information used to quantify the capacity of a classical channel. Quantum systems can process information more efficiently than classical systems in a number of different ways. Quantum teleportation and quantum dense coding can be performed using quantum entanglement. Entanglement is an excess of correlations that can exist in quantum physics and is impossible to reproduce classically (with what is termed “separable” states). The book has also demonstrated how to discriminate entangled from separable states using entanglement witnesses, as well as how to quantify entanglement, and looked at quantum computation and quantum algorithms.Less
This book has discussed the foundations of quantum information science as well as the relationship between physics and information theory in general. It has considered the quantum equivalents of the Shannon coding and channel capacity theorems. The von Neumann entropy plays a role analogous to the Shannon entropy, and the Holevo bound is the analogue of Shannon's mutual information used to quantify the capacity of a classical channel. Quantum systems can process information more efficiently than classical systems in a number of different ways. Quantum teleportation and quantum dense coding can be performed using quantum entanglement. Entanglement is an excess of correlations that can exist in quantum physics and is impossible to reproduce classically (with what is termed “separable” states). The book has also demonstrated how to discriminate entangled from separable states using entanglement witnesses, as well as how to quantify entanglement, and looked at quantum computation and quantum algorithms.
Vlatko Vedral
- Published in print:
- 2006
- Published Online:
- January 2010
- ISBN:
- 9780199215706
- eISBN:
- 9780191706783
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199215706.003.00012
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter introduces a method that combines the concepts of quantum entanglement with those of quantum algorithms. In particular, some bounds are placed on the efficiency (speedup) of quantum ...
More
This chapter introduces a method that combines the concepts of quantum entanglement with those of quantum algorithms. In particular, some bounds are placed on the efficiency (speedup) of quantum computations by using the fact that there is a limit to how quickly entanglement can be generated with some operations. This method will truly exploit the “many-worlds” nature of quantum superpositions. By solving one problem using a superposition of qubits as well as solving a superposition of problems, the efficiency of some quantum tasks can be evaluated. This chapter demonstrates that a quantum search cannot be performed faster than the square root of the time of the corresponding classical search (winch is still very much faster). The use of entanglement to optimise quantum searches is discussed, along with a model for quantum measurement, similarity between quantum computation and a quantum measurement as described by von Neumann, correlations and quantum measurement, and the Bekenstein bound as an example of the ultimate limits of quantum computation.Less
This chapter introduces a method that combines the concepts of quantum entanglement with those of quantum algorithms. In particular, some bounds are placed on the efficiency (speedup) of quantum computations by using the fact that there is a limit to how quickly entanglement can be generated with some operations. This method will truly exploit the “many-worlds” nature of quantum superpositions. By solving one problem using a superposition of qubits as well as solving a superposition of problems, the efficiency of some quantum tasks can be evaluated. This chapter demonstrates that a quantum search cannot be performed faster than the square root of the time of the corresponding classical search (winch is still very much faster). The use of entanglement to optimise quantum searches is discussed, along with a model for quantum measurement, similarity between quantum computation and a quantum measurement as described by von Neumann, correlations and quantum measurement, and the Bekenstein bound as an example of the ultimate limits of quantum computation.
Andreas Bolfing
- Published in print:
- 2020
- Published Online:
- October 2020
- ISBN:
- 9780198862840
- eISBN:
- 9780191895463
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198862840.003.0008
- Subject:
- Mathematics, Computational Mathematics / Optimization, Logic / Computer Science / Mathematical Philosophy
This chapter gives a brief introduction to quantum computing, which is the discipline of studying algorithms based on the principles of quantum theory. It outlines the two fundamental quantum ...
More
This chapter gives a brief introduction to quantum computing, which is the discipline of studying algorithms based on the principles of quantum theory. It outlines the two fundamental quantum algorithms, which are known as Grover’s and Shor’s algorithm, which are able to solve number-theoretical problems that are intractable for present conventional computers. Thus, this chapter also shows the impact of these quantum algorithms on present cryptography under the assumption of the existence of a large-scale quantum computer, concluding that quantum computing poses a serious threat to public-key cryptosystems, because their underlying mathematical problems can be solved efficiently by using Shor’s algorithm.Less
This chapter gives a brief introduction to quantum computing, which is the discipline of studying algorithms based on the principles of quantum theory. It outlines the two fundamental quantum algorithms, which are known as Grover’s and Shor’s algorithm, which are able to solve number-theoretical problems that are intractable for present conventional computers. Thus, this chapter also shows the impact of these quantum algorithms on present cryptography under the assumption of the existence of a large-scale quantum computer, concluding that quantum computing poses a serious threat to public-key cryptosystems, because their underlying mathematical problems can be solved efficiently by using Shor’s algorithm.
Andreas Bolfing
- Published in print:
- 2020
- Published Online:
- October 2020
- ISBN:
- 9780198862840
- eISBN:
- 9780191895463
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198862840.003.0009
- Subject:
- Mathematics, Computational Mathematics / Optimization, Logic / Computer Science / Mathematical Philosophy
Bitcoin’s security relies solely on cryptographic primitives, namely on digital signatures, hash functions and Merkle trees. This chapter discusses the security of the Bitcoin system if some ...
More
Bitcoin’s security relies solely on cryptographic primitives, namely on digital signatures, hash functions and Merkle trees. This chapter discusses the security of the Bitcoin system if some primitives become weaker due to advances in cryptanalysis, an increasing computing power of the adversaries or improper software implementations. The chapter starts with a general overview of the primitives in use, explaining possible attack strategies against each of them, which is followed by combined attack strategies. The chapter closes by showing the consequences of Grover’s and Shor’s quantum algorithms for Bitcoin’s security.Less
Bitcoin’s security relies solely on cryptographic primitives, namely on digital signatures, hash functions and Merkle trees. This chapter discusses the security of the Bitcoin system if some primitives become weaker due to advances in cryptanalysis, an increasing computing power of the adversaries or improper software implementations. The chapter starts with a general overview of the primitives in use, explaining possible attack strategies against each of them, which is followed by combined attack strategies. The chapter closes by showing the consequences of Grover’s and Shor’s quantum algorithms for Bitcoin’s security.
Alice Flarend and Robert Hilborn
- Published in print:
- 2022
- Published Online:
- June 2022
- ISBN:
- 9780192857972
- eISBN:
- 9780191948763
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780192857972.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
Quantum Computing: From Alice to Bob provides a distinctive and accessible introduction to the rapidly growing fields of quantum information science (QIS) and quantum computing (QC). The book is ...
More
Quantum Computing: From Alice to Bob provides a distinctive and accessible introduction to the rapidly growing fields of quantum information science (QIS) and quantum computing (QC). The book is designed for undergraduate students and upper-level secondary school students with little or no background in physics, computer science, or mathematics beyond secondary school algebra and trigonometry. While broadly accessible, the book provides a solid conceptual and formal understanding of quantum states and entanglement—the key ingredients in quantum computing. The authors give detailed treatments of many of the classic quantum algorithms that demonstrate how and when QC has an advantage over classical computers. The book provides a solid explanation of the physics of QC and QIS and then weds that knowledge to the mathematics of QC algorithms and how those algorithms deploy the principles of quantum physics to solve the problem. This book connects the physics concepts, the computer science vocabulary, and the mathematics, providing a complete picture of how QIS and QC work. The authors give multiple representations of the concept—textual, graphical, and symbolic (state vectors, matrices, and Dirac notation)—which are the lingua franca of QIS and QC. Those multiple representations allow the readers to develop a broader and deeper understanding of the fundamental concepts and their applications. In addition, the book provides examples of recent experimental demonstrations of quantum teleportation and the applications of quantum computational chemistry. The last chapter connects to the growing commercial world of QC and QIS and provides recommendations for further study.Less
Quantum Computing: From Alice to Bob provides a distinctive and accessible introduction to the rapidly growing fields of quantum information science (QIS) and quantum computing (QC). The book is designed for undergraduate students and upper-level secondary school students with little or no background in physics, computer science, or mathematics beyond secondary school algebra and trigonometry. While broadly accessible, the book provides a solid conceptual and formal understanding of quantum states and entanglement—the key ingredients in quantum computing. The authors give detailed treatments of many of the classic quantum algorithms that demonstrate how and when QC has an advantage over classical computers. The book provides a solid explanation of the physics of QC and QIS and then weds that knowledge to the mathematics of QC algorithms and how those algorithms deploy the principles of quantum physics to solve the problem. This book connects the physics concepts, the computer science vocabulary, and the mathematics, providing a complete picture of how QIS and QC work. The authors give multiple representations of the concept—textual, graphical, and symbolic (state vectors, matrices, and Dirac notation)—which are the lingua franca of QIS and QC. Those multiple representations allow the readers to develop a broader and deeper understanding of the fundamental concepts and their applications. In addition, the book provides examples of recent experimental demonstrations of quantum teleportation and the applications of quantum computational chemistry. The last chapter connects to the growing commercial world of QC and QIS and provides recommendations for further study.
Alice Flarend and Bob Hilborn
- Published in print:
- 2022
- Published Online:
- June 2022
- ISBN:
- 9780192857972
- eISBN:
- 9780191948763
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780192857972.003.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
We meet our hosts, Alice and Bob, and an undergraduate student, Cardy. Alice and Bob tell Cardy why QC is “the next big thing.” They give a brief introduction to quantum information science (QIS) and ...
More
We meet our hosts, Alice and Bob, and an undergraduate student, Cardy. Alice and Bob tell Cardy why QC is “the next big thing.” They give a brief introduction to quantum information science (QIS) and its relation to quantum computing (QC). They also provide an overview of the rest of the book and how the book should be used to come to grips with quantum ideas that allow QCs to do things unimaginable for traditional computers. Alice and Bob emphasize that with perseverance everyone can understand the fundamentals of QC and how quantum physics enables entirely new ways of thinking about computational algorithms. They explain the book’s overarching narrative: quantum states, quantum entanglement, and quantum measurements provide the essential resources for QC and QIS.Less
We meet our hosts, Alice and Bob, and an undergraduate student, Cardy. Alice and Bob tell Cardy why QC is “the next big thing.” They give a brief introduction to quantum information science (QIS) and its relation to quantum computing (QC). They also provide an overview of the rest of the book and how the book should be used to come to grips with quantum ideas that allow QCs to do things unimaginable for traditional computers. Alice and Bob emphasize that with perseverance everyone can understand the fundamentals of QC and how quantum physics enables entirely new ways of thinking about computational algorithms. They explain the book’s overarching narrative: quantum states, quantum entanglement, and quantum measurements provide the essential resources for QC and QIS.