Search Results

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.

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.

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.

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.

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.

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.