Quantum Algorithms: Promise and Perspective

SHELBY KIMMEL
Middlebury College

Much of the excitement surrounding quantum computers is driven by the possibility of using quantum algorithms to solve problems that are intractable using standard, or “classical,” computers. Several prominent examples of quantum speed-ups have been discovered, in particular with applications to cryptography and chemistry. Despite these exciting applications, quantum computers are not a magic bullet for computation; with some problems quantum algorithms give no or only a small advantage. However, because quantum computers are so difficult to simulate and analyze, for many problems and algorithms researchers simply do not know how quantum algorithms will perform. As larger quantum devices and computers come online, it will be possible to test quantum algorithms on them—and discover new problems where quantum computers give an advantage.

EXAMPLES OF QUANTUM ALGORITHMS

Perhaps the most famous quantum algorithm is for factoring (Shor 1994). There is a quantum factoring algorithm whose run time scales roughly like the number of digits in the integer, whereas the best classical algorithm requires nearly exponential time. The assumption that factoring is difficult is critical for the functioning of current cryptosystems, the systems that allow for much of e-commerce. In these cryptosystems, a user encodes information (like a credit card in order to purchase something online), and the only known way that “eavesdroppers” can decode the information is by factoring a very large number. As long as there are no fast methods for factoring, this strategy is good for keeping information private. However, once large quantum computers are developed, they will easily break these codes.

A second well-known application of quantum computers is modeling chemical and physical interactions. Quantum mechanics is often very difficult to simulate using a regular computer because the amount of space needed to keep track of the quantum system scales exponentially in the number of particles. This fact has made it challenging for scientists and engineers to understand the workings of many important systems and interactions, from high-temperature superconductors to photosynthesis. A quantum computer by its very nature can simulate these many-body quantum systems (Buluta and Nori 2009; Kassal et al. 2011). For example, one of the hopes of quantum computers is that they will improve and speed up the development of drugs and industrial chemistry processes by allowing testing of chemical synthesis and performance in silico.

While quantum algorithms have impressive performance for problems like factoring and quantum simulation, there are many problems where quantum computers provably do not have a large advantage over regular computers. The best-known example is the parity problem, which involves determining whether a string of 0s and 1s has an even or odd number of 1s. The best possible quantum algorithm for parity has the same scaling as the best possible classical algorithm (Beals et al. 2001).

Another example of a problem with only a modest quantum speed-up is search. While a classical computer can search through the elements of a list to find a certain item in time that scales like the number of items in the list, a quantum algorithm can do this in time that scales like the square root of the number of elements (Boyer et al. 1998; Grover 1996). While this is certainly an improvement, it is not the kind of speed-up that would likely warrant the huge investment required to make quantum computers a reality.

WHY QUANTUM COMPUTERS ARE USEFUL FOR SOME PROBLEMS AND NOT OTHERS

To get perspective on the potential of quantum algorithms, it is important to understand why they have such an advantage for some types of problems and little to no advantage for others. There are three properties of quantum mechanics that are different from standard computation and that are required for quantum speedups: superposition, interference, and entanglement. I focus on the first two; while entanglement is necessary for a quantum speed-up (Josza and Linden 2003), it is often implied by the presence of superposition and interference.

Superposition allows quantum systems to be in multiple states at the same time. The most famous example of this is Schrödinger’s cat, which is put in a situation in which it is both alive and dead at the same time. While superposition sounds incredibly powerful, as it seems to imply unlimited parallel computation, there is a catch. A quantum computer can be in a superposition of many states, but when a user tries to get an answer from it, the system collapses to one of

the states at random. Thus superposition on its own is essentially as powerful as probabilistic computation, where a state of the system is chosen at random.

For superposition to be advantageous to quantum algorithms, it needs to be combined with interference. Whereas in probabilistic computation each state of the computer would be associated with a positive probability, in quantum computing each state of the system can be associated with a complex “probability” or weight. The advantage of having states with complex weighting is that the combination of a positive and a negative weight results in cancellation. In probabilistic computation, where all the weightings are positive, cancellation is not possible.

Therefore, a successful quantum algorithm involves creating a large superposition of carefully weighted states, such that when the states interfere with each other those that don’t correspond to solutions cancel out, and those that give the correct solution are reinforced. Certain problems have a structure that allows cancellation to happen quickly, while others require time to amass a proper distribution of weightings. The more structure a problem has, the more likely it is to admit a large speed-up. Parity and search don’t have a lot of structure, because flipping a single bit of the input for either problem can change the value of the outcome. Problems like factoring or simulating chemistry are not so sensitive to small changes in the input and instead extract larger-scale structures.

THE FUTURE OF QUANTUM ALGORITHMS

Quantum computers behave in ways that cannot be simulated easily or efficiently with classical computers. While this fact is why quantum computation is exciting, it also hampers the development of quantum algorithms. There are whole classes of quantum algorithms that seem promising, but without being able to simulate their behavior on large problems of interest or analyze them by hand, it is not possible to know how they will perform in practice.

Quantum algorithm designers have developed a toolkit of paradigms. For only some of these approaches and only certain problems has it been possible to analyze their performance. The development of small-scale quantum computers in the coming years will create exciting opportunities to test these algorithms and search for new paradigms.

With the transition from a field that has been purely theoretical to a field that is also “computational” much work needs to be done. Quantum programming languages have just begun to be developed, and for many existing algorithms there is not an easy way to go from the theoretical description to a programming language description. Furthermore, even when an algorithm is described by a quantum programming language, there remain many challenges in converting instructions to quantum machine code, as different physical quantum computers tend to have different sets of basic operations.

CONCLUSION

Quantum computers are not all-powerful; they do not provide significant speed-ups for all problems. But for problems with appropriate structure, quantum properties like superposition and interference enable significantly better performance than is possible with standard computers. While these applications are exciting, current understanding of quantum algorithms is truly quite limited. As physical quantum computers are developed and quantum algorithms are tested on them, an unprecedented new tool will be available for the development and exploration of quantum algorithms.

REFERENCES

Beals R, Buhrman H, Cleve R, Mosca M, De Wolf R. 2001. Quantum lower bounds by polynomials. Journal of the ACM 48(4):778–797.

Boyer M, Brassard G, Høyer P, Tapp A. 1998. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics 46(4–5):493–505.

Buluta I, Nori F. 2009. Quantum simulators. Science 326(5949):108–111.

Grover LK. 1996. A fast quantum mechanical algorithm for database search. Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 212–219. ACM.

Jozsa R, Linden N. 2003. On the role of entanglement in quantum-computational speed-up. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 459(2036):2011–2032.

Kassal I, Whitfield JD, Perdomo-Ortiz A, Yung MH, Aspuru-Guzik A. 2011. Simulating chemistry using quantum computers. Annual Review of Physical Chemistry 62:185–207.

Shor PW. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE.