The way in which computers store data has been relatively unchanged since the 1950s and 1960s. While the earliest computers used decimal ‘bits’, binary bits became the norm due to the easier and more efficient manufacturing process. These bits are stored as either a 1 or a 0, on or off. These bits can be combined into 8-digit binary numbers, called bytes. With 1 byte, a computer can represent most standard characters, and with 4 bytes, a computer can represent almost every symbol and character from every relatively popular script. While this is truly remarkable, certain modern use-cases require more than the standard bit to achieve their full potential. Quantum computers are an excellent solution to this problem, but quantum computing and quantum algorithm design are still underdeveloped, yet a highly researched area of study.
Quantum computers are based on the idea of using qubits instead of bits. Rather than storing a single 1 or 0, qubits store a quantum wave function that represents a probability of collapsing to either 1 or 0. When a qubit is observed, this wave function is not returned, but rather the collapsed state is observed. This reflects the idea of quantum superposition, that a qubit is in all of its possible states according to its wave function until it is observed, at which point the act of observation forces it into a singular state. A common thought experiment used to explain this is Schrodinger’s cat, which describes a cat in a box with poison released by random chance as being both dead and alive until the box is opened. While this idea may seem unintuitive at first, it unleashes a whole new realm of possibilities for computing. 1 qubit represents 2 bits of information, 10 qubits represent 1024 bits of information, and 1000 qubits represent 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376 bits of information. This is an incredible improvement but hinges on the ability of quantum algorithm designers to create algorithms that can still function despite the uncertainty in quantum observations.
Quantum algorithm design is an active area of research with incredible potential. The most apparent applications of quantum algorithms are in solving NP (non-polynomial) problems in P (polynomial) time. In computer science, the ‘speed’ of an algorithm is denoted with O(n) notation. O(n^x) denotes polynomial time, where x is the degree of the polynomial. O(x^n), however, denotes exponential time. For small values of n, this makes little difference, but for a large enough n, a polynomial algorithm will be dramatically more efficient than an exponential algorithm. It has also been shown that if one non-polynomial problem can be solved in polynomial time, all other non-polynomial problems can be solved in polynomial time. While this seems like an incredible achievement that will certainly benefit society, concepts such as encryption are based on the idea of certain problems being unsolvable in polynomial time. The most common type of encryption algorithm used today, RSA encryption, depends on factoring large numbers into their prime factors and is currently a non-polynomial problem. This is ideal because nothing but the most powerful supercomputers can break encryption in this way. With quantum computing, however, many NP problems can be solved in polynomial time. In regards to encryption, a quantum algorithm called Shor’s algorithm can factor numbers in polynomial time, meaning that if an organization was able to produce a quantum computer with a sufficient number of qubits, encryption would be broken. The struggle, however, lies in the difficulty of creating qubits without interference and in designing algorithms that account for the inherent error that occurs from observing a non-deterministic probability function. As such, the quest for quantum computing algorithms and devices to run them on is an extremely fruitful endeavor with incredible consequences for the future of humanity.
Further reading: