In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
Abstract: Computers have significantly changed the human life, the existing computers are evolved on Turing machine model. Scientific advancements and requirements of human life are progressing rapidly and the existing computers and computational models are unable to meet the actual requirements due to their constraints. Many researchers have studied on computational models for improving its efficiency; quantum computational model has shown promising results. This paper discusses various topics related to quantum computation and quantum computers. Keywords: Quantum Computers, Classical Computers.
Quantum computing represents a revolutionary leap in computational power, leveraging the principles of quantum mechanics to process information in fundamentally new ways. Unlike classical computers, which use bits to represent data as 0s or 1s, quantum computers use quantum bits or qubits, enabling the phenomena of superposition and entanglement to perform complex calculations more efficiently (Nielsen & Chuang, 2010). This article explores the basic principles of quantum computing, the different models and algorithms that have been developed, and the current state of quantum hardware. The power of quantum computing lies in its ability to solve certain types of problems exponentially faster than classical computers. For instance, Shor's algorithm can factorize large integers in polynomial time, posing a significant threat to classical encryption methods (Shor, 1997). Similarly, Grover's algorithm provides a quadratic speedup for unstructured search problems, showcasing the potential for dramatic improvements in database search capabilities (Grover, 1996). These algorithms exemplify how quantum computing can revolutionize fields that rely on complex computations. Quantum hardware, however, is still in its nascent stage, with significant challenges to be overcome. Current quantum computers, such as those developed by IBM and Google, have demonstrated quantum supremacy but are limited by issues of qubit coherence and error rates (Arute et al., 2019). Quantum error correction and the development of more stable qubit technologies are critical areas of ongoing research (Preskill, 2018). Despite these challenges, recent advancements in quantum hardware and algorithms continue to drive the field forward, promising transformative impacts on industries such as cryptography, drug discovery, and artificial intelligence. As quantum computing continues to advance, it holds the promise of solving problems that are currently intractable for classical computers, paving the way for unprecedented technological and scientific advancements (Shor, 1997; Grover, 1996). This article provides a comprehensive overview of the current landscape of quantum computing, discussing its foundational principles, key algorithms, hardware challenges, and potential applications. By understanding these aspects, we can better appreciate the profound implications of quantum computing for the future of technology and science.
The rapid evolution of computers in the half century since their invention has resulted in dramatically smaller and faster computers. However, from a computational point of view, all these computers look alike; for example, they are built out of simple logic gates. A fundamental thesis of computer science---the modern form of the Church--Turing thesis---asserts that this is inevitable in a deep sense. Any computer can be simulated with at most a polynomial factor slowdown by a probabilistic Turing machine. Quantum computation poses the first credible challenge to this thesis. It goes back to a suggestion by Feynman [4], who pointed out that there appears to be no efficient way of simulating a quantum mechanical system on a computer, and suggested that, perhaps, a computer based on quantum physical principles might be able to carry out the simulation efficiently. Two formal models for quantum computers---the quantum Turing machine [2] and quantum computational networks [3]---were defined by Deutsch. The first three papers in this issue describe efficient quantum algorithms for computational tasks that we do not know how to solve classically. In "Quantum Complexity Theory," Bernstein and Vazirani give the first formal evidence that quantum computers violate the modern form of the Church--Turing thesis. They show that a certain problem---the recursive Fourier sampling problem---can be solved in polynomial time on a quantum Turing machine, but relative to an oracle, requires superpolynomial time on a classical probabilistic Turing machine. Simon, in the paper "On the Power of Quantum Computation" introduces a fundamental projection technique and uses it to design an efficient quantum algorithm to determine whether a certain type of function is 2-1 or 1-1. He further shows that, relative to an oracle, this problem requires exponential time on a classical probabilistic Turing machine. In the paper "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," Shor gives remarkable polynomial time quantum algorithms for two of the most famous problems in computer science: factoring and discrete log. Since the computational hardness of these problems is the basis of several famous cryptosystems, Shor's paper very dramatically underlines the power of quantum computers. To understand the computational power of quantum computers, it is helpful to consider a quantum mechanical system of n particles, each of which can be in one of two states, labeled
∣0⟩ and
∣1⟩. If this were a classical system, then its instantaneous state could be described by n bits. However, in quantum physics, the system is allowed to be in a linear superposition of configurations, and indeed the instantaneous state of the system is described by a unit vector in the 2n dimensional vector space, whose basis vectors correspond to all the2n classical configurations. Therefore, to describe the instantaneous state of the system, we must specify 2n complex numbers. Nature must update 2n complex numbers at each instant to evolve the system in time. This is an extraordinary amount of effort, since even for n = 200, 2n is larger than estimates of the number of elementary particles in the visible universe. Nonetheless, there are limits to the power of quantum computers. In "Strengths and Weaknesses of Quantum Computing," Bennett, Bernstein, Brassard, and Vazirani show that, relative to a random oracle, with probability 1, the class NP cannot be solved on a quantum Turing machine in time o(2n/2). This bound is tight, since recent work of Grover [5] has shown how to accept any language in NP in time O(2n/2) on a quantum Turing machine. Quantum computers are necessarily time reversible. Indeed, Bennett's work [1] on reversible computation inspired early work on quantum computation that preceded Feynman's paper [4]. The reversibility requirement makes it quite complex to implement even basic computational primitives such as looping or composition. In "Quantum Complexity Theory," Bernstein and Vazirani show how to implement quantum programming primitives and give a construction for an efficient universal quantum Turing machine. The structure of the universal quantum Turing machine is quite simple: it consists of a deterministic Turing machine with a single "quantum coin flip." In "Quantum Computability," Adleman, DeMarrais, and Huang greatly simplify this further by showing that a very simple type of coin flip is sufficient---a rotation by an angle
θ such that
sinθ=3/5. Making quantum computers robust against noise and decoherence is an important and challenging problem. In "Stabilization of Quantum Computations by Symmetrization," Barenco, Berthiaume, Deutsch, Ekert, Jozsa, and Macchiavello show how to use the quantum watchdog effect to stabilize a quantum computation against noise. Their method is based on running several copies of the quantum computer in parallel and projecting its state into the symmetric subspace at frequent intervals. They show that the quantum watchdog effect results in the suppression of errors that lie outside the symmetric subspace. Quantum computation touches upon the foundations of both computer science and quantum physics. It is not unlikely that the issues raised by quantum computation will stimulate further research into the foundations of quantum physics. I wish to express my gratitude to several people who made this special section possible. Oded Goldreich acted as editor for two of the papers in the issue and dealt with them with his characteristic efficiency and judgment. The editorial staff at SIAM, most notably Lisa Dougherty, Beth Gallagher, Deidre Wunderlich, and Sam Young, were extremely helpful, patient, and resourceful. Finally, I would like to thank a number of referees whose careful and timely reviews were critical to putting together this issue. Umesh Vazirani
Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.
Quantum technologies' processing capacity is built on quantum mechanics foundations, including superposition, the no-cloning theorem, and quantum entanglement. Quantum computing seeks to understand and embrace quantum effects, as well as techniques to improve and sustain them in order to achieve old computational goals in novel ways. It accomplishes this by utilising quintessentially quantum phenomena. We can't get equivalent findings using traditional computation because these processes don't have a classical analogue. There have been significant claims that quantum computers can surpass the Turing limit, however these assertions have been debunked. The Church-Turing thesis, which states that all realisable physical and dynamical systems cannot be more powerful than classical models of computation, has been the subject of numerous intensive attempts. However, quantum computing technologies' experimental insights have already been proved, and various studies are currently underway. In this article, the authors look at the most current quantum computation results and claims.