A quantum algorithm is a computer program that has been designed with the principles of quantum mechanics in mind. By using special features of quantum systems, such as superposition and entanglement, quantum algorithms can operate in a way that is fundamentally different to and more powerful than classical computation. Superposition describes how the state of a quantum system can be thought of as a combination, or sum, of multiple other possible states. The classical example of superposition is Schrodinger's Cat, which exists as a combination of both alive and dead.
A simpler example would be a quantum coin, which is both heads and tails until you measure it. The ability to represent quantum states as sums of other states is a fundamental feature of quantum mechanics, and gives rise to other useful phenomena. The most important of these phenomena is entanglement, which refers to how information can be stored in the relationship between two quantum systems, making a combined system that contains more information than the sum of its parts.
In order to run a quantum algorithm, there are two options. One can either simulate it on a classical computer, or run it properly on a quantum computer. Simulating a quantum algorithm on a classical computer is extremely difficult, and the amount of computational power required to simulate even relatively simple quantum systems makes it impractical. It has been twenty years since the first working quantum computer was built, but to date only very small computations have been successfully performed.
Quantum states are delicate, and collapse whenever they are interacted with. In order to prevent the registers of a quantum computer from randomly fluctuating, the system must be isolated from the environment until the end of the calculation. Carefully orchestrating interactions between the registers while preventing interaction with the rest of the universe is extremely difficult, explaining the slow (but increasing!) pace of development.
Scientists, computer scientists, and mathematicians have spent a lot of time thinking about quantum computers, and have developed many applications that can be deployed once the hardware catches up. There are certain mathematical problems that we only know how to solve with quantum algorithms, and some of these problems are vital to the security of modern cryptography. In particular, cryptographic methods based on elliptic curves and homomorphic encryption are widely used, and can be broken with quantum methods. Once larger scale quantum computers become widespread, these tools will be obsolete.
With enterprise-scale quantum computing being likely within our lifetime, many researchers are looking at beefing up our current repertoire of encryption algorithms with quantum-safe alternatives. The NIST, a US-based standards authority, recently held a competition in which participants were invited to submit proposals for the first generation of post-Quantum cryptographic standards. These algorithms are designed to be used on modern hardware, but be resistant to quantum methods. Check out https://csrc.nist.gov/Projects/Post-Quantum-Cryptography to take a look at the competition, and follow a link to see their second round candidates.
While some researchers scramble to develop quantum-resistant cryptography, there are those who're building novel cryptographic protocols that are designed to run on quantum computers. These tools use the properties of quantum information to perform feats of encryption whose security is guaranteed by the known laws of physics. One commonly cited application of these methods is "quantum money," which uses quantum states as serial numbers in a way that prevents forgery.
See www.scottaaronson.com/papers/noclone-ccc.pdf for a technical overview of several proposals for this. Other applications are the design of communication protocols that can detect whether or not messages have been read in transit, even if the attacker didn't alter the contents of the message.
If you're interested in incorporating quantum-resistant cryptography into your software, or want to learn more about the future potential of quantum computation in your field, please contact us.
