Introduction Any technology that functions at the quantum level must face the issues of measurement and control. We have good reasons to believe that quantum physics enables communication and computation tasks that are either impossible or intractable in a classical world [NC00]. The security of widely used classical cryptographic systems relies upon the difficulty of certain computational tasks, such as breaking large semi-prime numbers into their two prime factors in the case of RSA encryption. By contrast, quantum cryptography can be absolutely secure, and is already a commercial reality. At the same time, the prospect of a quantum computer vastly faster than any classical computer at certain tasks is driving an international research programme to implement quantum information processing. Shor's factoring algorithm would enable a quantum computer to find factors exponentially faster than any known algorithm for classical computers, making classical encryption insecure. In this chapter, we investigate how issues of measurement and control arise in this most challenging quantum technology of all, quantum computation. The subjects of information theory and computational theory at first sight appear to belong to mathematics rather than physics. For example, communication was thought to have been captured by Shannon's abstract theory of information [SW49, Sha49]. However, physics must impact on such fundamental concepts once we acknowledge the fact that information requires a physical medium to support it.
Introduction Any technology that functions at the quantum level must face the issues of measurement and control. We have good reasons to believe that quantum physics enables communication and computation tasks that are either impossible or intractable in a classical world [NC00]. The security of widely used classical cryptographic systems relies upon the difficulty of certain computational tasks, such as breaking large semi-prime numbers into their two prime factors in the case of RSA encryption. By contrast, quantum cryptography can be absolutely secure, and is already a commercial reality. At the same time, the prospect of a quantum computer vastly faster than any classical computer at certain tasks is driving an international research programme to implement quantum information processing. Shor's factoring algorithm would enable a quantum computer to find factors exponentially faster than any known algorithm for classical computers, making classical encryption insecure. In this chapter, we investigate how issues of measurement and control arise in this most challenging quantum technology of all, quantum computation. The subjects of information theory and computational theory at first sight appear to belong to mathematics rather than physics. For example, communication was thought to have been captured by Shannon's abstract theory of information [SW49, Sha49]. However, physics must impact on such fundamental concepts once we acknowledge the fact that information requires a physical medium to support it.
Introduction In an ordinary computer, information is stored in a collection of tiny circuits each of which is designed to have two stable and easily distinguishable configurations: each represents a bit . In our study of quantum cryptography, we have seen how it can be useful to express information not in ordinary bits but in qubits . Whereas a bit can have only two values, say 0 and 1, a qubit can be in any quantum superposition of ∣0〉 and ∣1〉. Moreover, a qubit can be entangled with other qubits. Thus one might wonder whether a quantum computer, in which the basic elements for storing and processing information are qubits, can outperform an ordinary (classical) computer in certain ways. This question was addressed by researchers starting in the 1980s. In terms of practical consequences, perhaps the most dramatic answer has been given by Peter Shor in his 1994 factoring algorithm for a quantum computer, an algorithm that is exponentially faster than any known classical algorithm. As we have seen in Chapter 1, the difficulty of factoring a product of two large primes is the basis of the security of the RSA cryptosystem. So if one could build a large enough quantum computer – and there is no reason in principle why this could not be done – the RSA system would be rendered ineffective. In this chapter we present the basics of quantum computation and then focus on Shor's factoring algorithm.
Summary form only given. Quantum mechanics offers the information scientist a new rich resource, which is only recently being tapped to allow for secure communication in the form of quantum cryptography, and for tremendous parallelism in quantum information processing and computing. I will describe developments and prospects for each. Quantum cryptography has already advanced beyond the research laboratory to become a realizable technology with proven secret key distribution for encryption. Quantum computing, although at an earlier stage of development has been recognized as a major new development in physics, enables us (if a quantum computer is realizable) to attack problems previously thought to be too complex for normal computation in a reasonable time. Examples of quantum algorithms involving this kind of advantage are Shor's for fast factorization (in itself a threat to secure communication) and Grover's for database searching. I will discuss the ways quantum mechanics allow such a speed-up, stressing how quantum entanglement is the key resource being exploited, and how quantum gates, networks, and the processors may be implemented in a realistically noisy environment. Simple demonstrators have already been built, and I will discuss prospects for future realization of large-scale processors.
“All information is physical”, the slogan advocated over many years by Rolf Landauer of IBM, has recently led to some remarkable changes in the way we view communications, computing and cryptography. By employing quantum physics, several objectives that were thought impossible in a classical world have now proven to be possible. Quantum communications links, for example, become impossible to eavesdrop without detection. Quantum computers (were they to be realized) could turn some algorithms that are labelled “difficult” for a classical machine, no matter how powerful, into ones that become “simple”. The details of what constitutes “difficult” and what “easy” are the subject of mathematical complexity theory, but an example here will illustrate the point and the impact that quantum information processors will have on all of us. The security of many forms of encryption is predicated on the difficulty of factoring large numbers. Finding the factors of a 1024-digit number would take longer than the age of the universe on a computer designed according to the laws of classical physics, and yet can be done in the blink of an eye on a quantum computer were it to have a comparable clock speed. But only if we can build one, and that's the challenge! No one has yet realized a quantum register of the necessary size, or quantum gates with the prerequisite accuracy. Yet it is worth the chase, as a quantum computer with a modest-sized register could out-perform any classical machine.
Nowadays quantum information science is in a state of theoretic completeness; much is invested to research quality physical solution for quantum computer and applications, so the field is led by physicists and information science and technology professionals. This field proved its potential and many (including us) believe it is in the right direction to go. In this paper we'll try to present and analyze the philosophy and nature of quantum information science and discuss hot topics around them. Although there is plenty of space for discussion around this field, we will concentrate on some important issues, such as quantum communication, algorithms and cryptography. Communication promises to be one of the directions where huge breakthroughs will be observed (entanglement as communication), algorithms have already shown exponential advantage (Shor's factoring) over classical counterparts and different paradigm of information processing. Cryptography seems to utilize general achievements in quantum information science and make encryption protocols very secure. Quantum computation can be understood as a generalization of classical computation: The possible states of a quantum computer are superpositions of bit strings, where the tensor factor is called a quantum bit or qubit. To evaluate the computational complexity of an algorithm, either classical or quantum, it is necessary to specify a set of elementary operations, the number of which used during the computation quantities the complexity. If we allow arbitrary permutations classically, or arbitrary unitary transformations quantum mechanically, any state can be reached from any other state in a single step. The general kind of quantum computer should be programmed to perform distinctively quantum operations such as generating two bits in a superposition state. An appropriate measurement on the final superposed state of the computer produces a probabilistic behavior of the output, and because of this quantum parallelization does not reduce the average time required for parallelizable computation completion. The development of quantum computing science and technology as well as quantum computers as thinking machines is very dependent on different achievements of modern research in fundamental and applied physics as well as novel mathematical methods and tools.
This dissertation analyzes the impact of quantum computing on the security of classical cryptographic systems, with a focus on the vulnerability of the RSA algorithm. RSA cryptography is based on the difficulty of factoring large prime numbers, a task considered computationally very difficulty for classical computers. However, with quantum computing, especially through Shor’s algorithm—this barrier can be overcome. Shor’s algorithm allows factorization in polynomial time, which would completely compromise the security of RSA.The dissertation presents the theoretical foundations of both cryptography and quantum computing, explaining key concepts such as qubits, superposition, entanglement, and quantum parallelism. It details the operation of Shor’s algorithm, from identifying the period of the modular exponential function to applying the Quantum Fourier Transform (QFT) and phase estimation to obtain the prime factors of a composite number.In addition to the theoretical component, the work includes practical implementations of the algorithm in both classical and simulated quantum environments, using IBM’s Qiskit library. Finally, it discusses post-quantum cryptography as a secure alternative in light of technological advancements, highlighting methods based on lattices, codes, hash functions, and multivariate systems.The conclusion emphasizes the urgency of adopting cryptographic systems resistant to quantum computing, as ongoing advances increasingly make the breaking of RSA a realistic threat. Post-quantum cryptography is mentioned as a necessary response to the challenge posed by quantum computing.In conclusion, although current quantum computers do not yet have sufficient power to break RSA in practice, technological progress is steadily bringing that scenario closer. Therefore, it is essential to develop and adopt quantum-resistant cryptographic systems to ensure information security in the coming decades.
The paper is intended to be a survey of all the important aspects and results that have shaped the field of quantum computation and quantum information. The reader is first familiarized with those features and principles of quantum mechanics providing a more efficient and secure information processing. Their applications to the general theory of information, cryptography, algorithms, computational complexity and error-correction are then discussed. Prospects for building a practical quantum computer are also analyzed.