Quantum computing is the exploitation of collective properties of quantum states, such as superposition and entanglement, to perform computation. The devices that perform quantum computations are known as quantum computers.: I-5 They are believed to be able to solve certain computational problems, such as integer factorization (which underlies RSA encryption), substantially faster than classical computers. The study of quantum computing is a subfield of quantum information science. Expansion is expected in the next few years as the field shifts toward real-world use in pharmaceutical, data security and other applications.
There are several types of quantum computers (also known as quantum computing systems), including the quantum circuit model, quantum Turing machine, adiabatic quantum computer, one-way quantum computer, and various quantum cellular automata. The most widely used model is the quantum circuit, based on the quantum bit, or "qubit", which is somewhat analogous to the bit in classical computation. A qubit can be in a 1 or 0 quantum state, or a superposition of the 1 and 0 states. When it is measured, however, it is always 0 or 1; the probability of either outcome depends on the qubit's quantum state immediately before measurement.
Any computational problem that can be solved by a classical computer can also be solved by a quantum computer. Conversely, any problem that can be solved by a quantum computer can also be solved by a classical computer, at least in principle given enough time. In other words, quantum computers obey the Church–Turing thesis. This means that while quantum computers provide no additional advantages over classical computers in terms of computability, quantum algorithms for certain problems have significantly lower time complexities than corresponding known classical algorithms. 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 for quantum computers is known as quantum complexity theory.
Quantum circuit
The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers
Definition
The prevailing model of quantum computation describes the computation in terms of a network of quantum logic gates.[14] This model can be thought of as an abstract linear-algebraic generalization of a classical circuit. Since this circuit model obeys quantum mechanics, a quantum computer capable of efficiently running these circuits is believed to be physically realizable.
A memory consisting of {\textstyle n} bits of information has {\textstyle 2^{n}} possible states. A vector representing all memory states thus has {\textstyle 2^{n}} entries (one for each state). This vector is viewed as a probability vector and represents the fact that the memory is to be found in a particular state.
In the classical view, one entry would have a value of 1 (i.e. a 100% probability of being in this state) and all other entries would be zero. In quantum mechanics, probability vectors are generalized to density operators. This is the technically rigorous mathematical foundation for quantum logic gates, but the intermediate quantum state vector formalism is usually introduced first because it is conceptually simpler. This article focuses on the quantum state vector formalism for simplicity.
We begin by considering a simple memory consisting of only one bit. This memory may be found in one of two states: the zero state or the one state. We may represent the state of this memory using Dirac notation so that
{\displaystyle |0\rangle :={\begin{pmatrix}1\\0\end{pmatrix}};\quad |1\rangle :={\begin{pmatrix}0\\1\end{pmatrix}}}
A quantum memory may then be found in any quantum superposition {\textstyle |\psi \rangle } of the two classical states {\textstyle |0\rangle } and {\textstyle |1\rangle }:
{\displaystyle |\psi \rangle :=\alpha \,|0\rangle +\beta \,|1\rangle ={\begin{pmatrix}\alpha \\\beta \end{pmatrix}};\quad |\alpha |^{2}+|\beta |^{2}=1.}
In general, the coefficients {\textstyle \alpha } and {\textstyle \beta } are complex numbers. In this scenario, one qubit of information is said to be encoded into the quantum memory. The state {\textstyle |\psi \rangle } is not itself a probability vector but can be connected with a probability vector via a measurement operation. If the quantum memory is measured to determine whether the state is {\textstyle |0\rangle } or {\textstyle |1\rangle } (this is known as a computational basis measurement), the zero state would be observed with probability {\textstyle |\alpha |^{2}} and the one state with probability {\textstyle |\beta |^{2}}. The numbers {\textstyle \alpha } and {\textstyle \beta } are called quantum amplitudes.
The state of this one-qubit quantum memory can be manipulated by applying quantum logic gates, analogous to how classical memory can be manipulated with classical logic gates. One important gate for both classical and quantum computation is the NOT gate, which can be represented by a matrix
{\displaystyle X:={\begin{pmatrix}0&1\\1&0\end{pmatrix}}.}
Mathematically, the application of such a logic gate to a quantum state vector is modelled with matrix multiplication. Thus {\textstyle X|0\rangle =|1\rangle } and {\textstyle X|1\rangle =|0\rangle }.
The mathematics of single-qubit gates can be extended to operate on multi-qubit quantum memories in two important ways. One way is simply to select a qubit and apply that gate to the target qubit whilst leaving the remainder of the memory unaffected. Another way is to apply the gate to its target only if another part of the memory is in the desired state. These two choices can be illustrated using another example. The possible states of a two-qubit quantum memory are
{\displaystyle |00\rangle :={\begin{pmatrix}1\\0\\0\\0\end{pmatrix}};\quad |01\rangle :={\begin{pmatrix}0\\1\\0\\0\end{pmatrix}};\quad |10\rangle :={\begin{pmatrix}0\\0\\1\\0\end{pmatrix}};\quad |11\rangle :={\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}.}
The CNOT gate can then be represented using the following matrix:
{\displaystyle \operatorname {CNOT} :={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}}.}
As a mathematical consequence of this definition, {\textstyle \operatorname {CNOT} |00\rangle =|00\rangle }, {\textstyle \operatorname {CNOT} |01\rangle =|01\rangle }, {\textstyle \operatorname {CNOT} |10\rangle =|11\rangle }, and {\textstyle \operatorname {CNOT} |11\rangle =|10\rangle }. In other words, the CNOT applies a NOT gate ({\textstyle X} from before) to the second qubit if and only if the first qubit is in the state {\textstyle |1\rangle }. If the first qubit is {\textstyle |0\rangle }, nothing is done to either qubit.
In summary, a quantum computation can be described as a network of quantum logic gates and measurements. However, any measurement can be deferred to the end of quantum computation, though this deferment may come at a computational cost, so most quantum circuits depict a network consisting only of quantum logic gates and no measurements.
Any quantum computation (which is, in the above formalism, any unitary matrix over {\displaystyle n} qubits) can be represented as a network of quantum logic gates from a fairly small family of gates. A choice of gate family that enables this construction is known as a universal gate set since a computer that can run such circuits is a universal quantum computer. One common such set includes all single-qubit gates as well as the CNOT gate from above. This means any quantum computation can be performed by executing a sequence of single-qubit gates together with CNOT gates. Though this gate set is infinite, it can be replaced with a finite gate set by appealing to the Solovay-Kitaev theorem.
Quantum algorithms
Progress in finding quantum algorithms typically focuses on this quantum circuit model, though exceptions like the quantum adiabatic algorithm exist. Quantum algorithms can be roughly categorized by the type of speedup achieved over corresponding classical algorithms.
Quantum algorithms that offer more than a polynomial speedup over the best known classical algorithm include Shor's algorithm for factoring and the related quantum algorithms for computing discrete logarithms, solving Pell's equation, and more generally solving the hidden subgroup problem for abelian finite groups. These algorithms depend on the primitive of the quantum Fourier transform. No mathematical proof has been found that shows that an equally fast classical algorithm cannot be discovered, although this is considered unlikely. Certain oracle problems like Simon's problem and the Bernstein–Vazirani problem do give provable speedups, though this is in the quantum query model, which is a restricted model where lower bounds are much easier to prove, and doesn't necessarily translate to speedups for practical problems.
Other problems, including the simulation of quantum physical processes from chemistry and solid-state physics, the approximation of certain Jones polynomials, and the quantum algorithm for linear systems of equations have quantum algorithms appearing to give super-polynomial speedups and are BQP-complete. Because these problems are BQP-complete, an equally fast classical algorithm for them would imply that no quantum algorithm gives a super-polynomial speedup, which is believed to be unlikely.
Some quantum algorithms, like Grover's algorithm and amplitude amplification, give polynomial speedups over corresponding classical algorithms. Though these algorithms give comparably modest quadratic speed up, they are widely applicable and thus give speedups for a wide range of problems. Many examples of provable quantum speedups for query problems are related to Grover's algorithm, including Brassard, Høyer, and Tapp's algorithm for finding collisions in two-to-one functions, which uses Grover's algorithm, and Farhi, Goldstone, and Gutmann's algorithm for evaluating NAND trees, which is a variant of the search problem.
Potential applications
Cryptography:
A notable application of quantum computation is for attacks on cryptographic systems that are currently in use. Integer factorization, which underpins the security of public-key cryptographic systems, is believed to be computationally infeasible with an ordinary computer for large integers if they are the product of a few prime numbers (e.g., products of two 300-digit primes). By comparison, a quantum computer could efficiently solve this problem using Shor's algorithm to find its factors. This ability would allow a quantum computer to break many of the cryptographic systems in use today, in the sense that there would be a polynomial-time (in the number of digits of the integer) algorithm for solving the problem. In particular, most of the popular public-key cyphers are based on the difficulty of factoring integers or the discrete logarithm problem, both of which can be solved by Shor's algorithm. In particular, the RSA, Diffie–Hellman, and elliptic curve Diffie–Hellman algorithms could be broken. These are used to protect secure Web pages, encrypted email, and many other types of data. Breaking these would have significant ramifications for electronic privacy and security.
Identifying cryptographic systems that may be secure against quantum algorithms is an actively researched topic under the field of post-quantum cryptography. Some public-key algorithms are based on problems other than the integer factorization and discrete logarithm problems to which Shor's algorithm applies, like the McEliece cryptosystem based on a problem in coding theory. Lattice-based cryptosystems are also not known to be broken by quantum computers, and finding a polynomial-time algorithm for solving the dihedral hidden subgroup problem, which would break many lattice-based cryptosystems, is a well-studied open problem. It has been proven that applying Grover's algorithm to break asymmetric (secret key) algorithm by brute force requires time equal to roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case, meaning that symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search (see Key size).
Quantum cryptography could potentially fulfil some of the functions of public-key cryptography. Quantum-based cryptographic systems could, therefore, be more secure than traditional systems against quantum hacking.
Search problems:
The most well-known example of a problem admitting a polynomial quantum speedup is unstructured search, finding a marked item out of a list of {\displaystyle n} items in a database. This can be solved by Grover's algorithm using {\displaystyle O({\sqrt {n}})} queries to the database, quadratically fewer than the {\displaystyle \Omega (n)} queries required for classical algorithms. In this case, the advantage is not only provable but also optimal: it has been shown that Grover's algorithm gives the maximal possible probability of finding the desired element for any number of oracle lookups.
Problems that can be addressed with Grover's algorithm have the following properties:
There is no searchable structure in the collection of possible answers,
The number of possible answers to check is the same as the number of inputs to the algorithm, and
There exists a boolean function that evaluates each input and determines whether it is the correct answer
For problems with all these properties, the running time of Grover's algorithm on a quantum computer scales as the square root of the number of inputs (or elements in the database), as opposed to the linear scaling of classical algorithms. A general class of problems to which Grover's algorithm can be applied is the Boolean satisfiability problem, where the database through which the algorithm iterates is that of all possible answers. An example and (possible) application of this is a password cracker that attempts to guess a password. Symmetric cyphers such as Triple-DES and AES are particularly vulnerable to this kind of attack. this application of quantum computing is a major interest of government agencies.
Simulation of quantum systems
Since chemistry and nanotechnology rely on understanding quantum systems, and such systems are impossible to simulate efficiently classically, many believe quantum simulation will be one of the most important applications of quantum computing. Quantum simulation could also be used to simulate the behaviour of atoms and particles at unusual conditions such as the reactions inside a collider. Quantum simulations might be used to predict future paths of particles and protons under superposition in the double-slit experiment.[citation needed] About 2% of the annual global energy output is used for nitrogen fixation to produce ammonia for the Haber process in the agricultural fertilizer industry while naturally occurring organisms also produce ammonia. Quantum simulations might be used to understand this process of increasing production.
Quantum annealing and adiabatic optimization
Quantum annealing or Adiabatic quantum computation relies on the adiabatic theorem to undertake calculations. A system is placed in the ground state for a simple Hamiltonian, which is slowly evolved to a more complicated Hamiltonian whose ground state represents the solution to the problem in question. The adiabatic theorem states that if the evolution is slow enough the system will stay in its ground state at all times through the process.
Machine learning
Since quantum computers can produce outputs that classical computers cannot produce efficiently, and since quantum computation is fundamentally linear algebraic, some express hope in developing quantum algorithms that can speed up machine learning tasks. For example, the quantum algorithm for linear systems of equations, or "HHL Algorithm", named after its discoverers Harrow, Hassidim, and Lloyd, is believed to provide speedup over classical counterparts. Some research groups have recently explored the use of quantum annealing hardware for training Boltzmann machines and deep neural networks.
Computational biology
In the field of computational biology, computing has played a big role in solving many biological problems. One of the well-known examples would be in computational genomics and how computing has drastically reduced the time to sequence a human genome. Given how computational biology is using generic data modelling and storage, its applications to computational biology are expected to arise as well.
Quantum supremacy
John Preskill has introduced the term quantum supremacy to refer to the hypothetical speedup advantage that a quantum computer would have over a classical computer in a certain field. Google announced in 2017 that is expected to achieve quantum supremacy by the end of the year though that did not happen. IBM said in 2018 that the best classical computers will be beaten on some practical task within about five years and views the quantum supremacy test only as a potential future benchmark. Although sceptics like Gil Kalai doubt that quantum supremacy will ever be achieved, in October 2019, a Sycamore processor created in conjunction with Google AI Quantum was reported to have achieved quantum supremacy, with calculations more than 3,000,000 times as fast as those of Summit, generally considered the world's fastest computer. In December 2020, a group at USTC implemented a type of Boson sampling on 76 photons with a photonic quantum computer Jiuzhang to demonstrate quantum supremacy. The authors claim that a classical contemporary supercomputer would require a computational time of 600 million years to generate the number of samples their quantum processor can generate in 20 seconds. Bill Unruh doubted the practicality of quantum computers in a paper published back in 1994. Paul Davies argued that a 400-qubit computer would even come into conflict with the cosmological information bound implied by the holographic principle.
THE SECOND PART OF QUANTUM COMPUTING WILL BE UPLOADED ON NEXT SCHEDULE
FOLLOW US ON INSTAGRAM, FACEBOOK AND PINTEREST
DISCLAIMER
The information is provided by Tecquisition for general informational and educational purposes only and is not a substitute for professional legal advice. If you have any feedback, comments, requests for technical support or other inquiries, please mail us at tecqusition@gmail.com.
Comments