User:Jaydavidmartin/Quantum computing
From Wikipedia, the free encyclopedia
Quantum computing is the use of quantum-mechanical phenomena such as superposition and entanglement to perform computation. Computers that perform quantum computation are known as a quantum computers.[1]: I-5 Quantum computers are believed to be able to solve certain computational problems, such as the integer factorization that underlies RSA encryption, significantly faster than classical computers. The study of quantum computing is a subfield of quantum information science.
The field of quantum computing began in the early 1980s, when physicist Paul Benioff proposed a quantum mechanical model of the Turing machine.[2] Richard Feynman and Yuri Manin later suggested that a quantum computer had the potential to simulate things that a classical computer could not.[3][4] In 1994, Peter Shor developed a quantum algorithm for factoring integers that had the potential to decrypt RSA-encrypted communications.[5] Despite ongoing experimental progress since the late 1990s, most researchers believe that "fault-tolerant quantum computing [is] still a rather distant dream".[6] On 23 October 2019, Google AI, in partnership with the U.S. National Aeronautics and Space Administration (NASA), published a paper in which they claimed to have achieved quantum supremacy.[7] While some have disputed this claim, it is still a significant milestone in the history of quantum computing.[8]
Quantum computing is modeled by quantum circuits. Quantum circuits are based on the quantum bit, or "qubit", which is somewhat analogous to the bit in classical computation. Qubits can be in a 1 or 0 quantum state (much like the 0 and 1 states of classical bits), or they can be in a superposition of the 1 and 0 states. However, when qubits are measured the result is always either a 0 or a 1. The probabilities of these two outcomes depend on the quantum state that they were in immediately prior to the measurement. Computation is performed by manipulating qubits with quantum logic gates, which are somewhat analogous to classical logic gates.
There are currently two main approaches to physically implementing quantum computers: analog and digital (both of which make use of qubits[1]: 2–13 ). Analog approaches are further divided into quantum simulation, quantum annealing, and adiabatic quantum computation. Digital quantum computers use quantum logic gates to do computation.
Any computational problem that can be solved by a classical computer can also, in principle, be solved by a quantum computer. Conversely, quantum computers obey the Church–Turing thesis; that is, any computational problem that can be solved by a quantum computer can also be solved by a classical computer. While this means that quantum computers provide no additional power over classical computers in terms of computability, they do in theory provide additional power when it comes to the time complexity of solving certain problems. Notably, quantum computers are believed to be able to quickly solve certain problems that no classical computer could solve in any feasible amount of time—a feat known as "quantum supremacy". The study of the computational complexity of problems with respect to quantum computers is known as quantum complexity theory.