What is quantum computing?
Quantum computing is essentially harnessing and exploiting the amazing laws of quantum mechanics to process information. A traditional computer uses long strings of “bits,” which encode either a zero or a one. A quantum computer, on the other hand, uses quantum bits, or qubits. What’s the difference? Well a qubit is a quantum system that encodes the zero and the one into two distinguishable quantum states. But, because qubits behave quantumly, we can capitalize on the phenomena of “superposition” and “entanglement.”
Entanglement
Entanglement is a term used in quantum theory to describe the way that particles of energy/matter can become correlated to predictably interact with each other regardless of how far apart they are.
Particles, such as photons, electrons, or qubits that have interacted with each other retain a type of connection and can be entangled with each other in pairs, in the process known as correlation. Knowing the spin state of one entangled particle – whether the direction of the spin is up or down – allows one to know that the spin of its mate is in the opposite direction. Even more amazing is the knowledge that, due to the phenomenon of superposition, the measured particle has no single spin direction before being measured, but is simultaneously in both a spin-up and spin-down state. The spin state of the particle being measured is decided at the time of measurement and communicated to the correlated particle, which simultaneously assumes the opposite spin direction to that of the measured particle. Quantum entanglement allows qubits that are separated by incredible distances to interact with each other immediately, in a communication that is not limited to the speed of light. No matter how great the distance between the correlated particles, they will remain entangled as long as they are isolated.
Entanglement is a real phenomenon (Einstein called it “spooky action at a distance”), which has been demonstrated repeatedly through experimentation. The mechanism behind it cannot, as yet, be fully explained by any theory. One proposed theory suggests that all particles on earth were once compacted tightly together and, as a consequence, maintain a connectedness. Much current research is focusing on how to harness the potential of entanglement in developing systems for quantum cryptography and quantum computing.
In 1997, Nicholas Gisin and colleagues at the University of Geneva used entangled photons to enable simple – but instantaneous – communication over a distance of seven miles.
Qubit
A qubit is a quantum bit , the counterpart in quantum computing to the binary digit or bit of classical computing. Just as a bit is the basic unit of information in a classical computer, a qubit is the basic unit of information in a quantum computer .
In a quantum computer, a number of elemental particles such as electrons or photons can be used (in practice, success has also been achieved with ions), with either their charge or polarization acting as a representation of 0 and/or 1. Each of these particles is known as a qubit; the nature and behavior of these particles (as expressed in quantum theory ) form the basis of quantum computing. The two most relevant aspects of quantum physics are the principles of superposition and entanglement .
Quantum gates
We need to figure out which part goes in evolutions and operations and which goes into computation (eg, the universal section)
A quantum gate or quantum logic gate is a rudimentary quantum circuit operating on a small number of qubits. They are the analogues for quantum computers to classical logic gates for conventional digital computers. Quantum logic gates are reversible, unlike many classical logic gates. Some universal classical logic gates, such as the Toffoli gate, provide reversibility and can be directly mapped onto quantum logic gates. Quantum logic gates are represented by unitary matrices.
The most common quantum gates operate on spaces of one or two qubits. This means that as matrices, quantum gates can be described by 2 x 2 or 4 x 4 matrices with orthonormal rows.
Remark. The investigation of quantum logic gates is unrelated to quantum logic, which is a foundational formalism for quantum mechanics based on a modification of some of the rules of propositional logic.
Shor’s algorithm
Shor’s algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm which runs on a quantum computer) for integer factorization discovered in 1994. Informally it solves the following problem: Given an integer N, find its prime factors.
On a quantum computer, to factor an integer N, Shor’s algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input). Specifically it takes time O((log N)3), demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is thus in the complexity class BQP. This is exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time — about O(e(log N)1/3 (log log N)2/3). The efficiency lies in the efficiency of the quantum Fourier transform, and modular exponentiation by squarings.
Given a quantum computer with a sufficient number of qubits, Shor’s algorithm can be used to break the widely used public-key cryptography scheme known as RSA. RSA is based on the assumption that factoring large numbers is computationally infeasible. So far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor in polynomial time. However, Shor’s algorithm shows that factoring is efficient on a quantum computer, so an appropriately large quantum computer can break RSA. It was also a powerful motivator for the design and construction of quantum computers and for the study of new quantum computer algorithms. It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptograph
On a quantum computer, to factor an integer N, Shor’s algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input). Specifically it takes time O((log N)3), demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is thus in the complexity class BQP. This is exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time — about O(e(log N)1/3 (log log N)2/3). The efficiency lies in the efficiency of the quantum Fourier transform, and modular exponentiation by squarings.
Given a quantum computer with a sufficient number of qubits, Shor’s algorithm can be used to break the widely used public-key cryptography scheme known as RSA. RSA is based on the assumption that factoring large numbers is computationally infeasible. So far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor in polynomial time. However, Shor’s algorithm shows that factoring is efficient on a quantum computer, so an appropriately large quantum computer can break RSA. It was also a powerful motivator for the design and construction of quantum computers and for the study of new quantum computer algorithms. It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptograph
