Summary: Quantum Computing Algorithms

Here are the key takeaways:

• The two quantum algorithms discussed in this chapter illustrate that the use of superposition and entanglement may make quantum computing more effective than classical computing by providing a method to have the analysis work on all possible states at once. This does not mean that the calculation is done repetitively on each possible state, but rather the superposition of states interacts with quantum gates in a way that results in a single measurement having a high probability of containing an answer. As usual, that probability is given by the square of the coefficient of the state. Because there is a small but nonzero probability of a wrong answer—due to the probabilistic nature of measurements on superposition states—we may need to run an algorithm several times. But with a clever quantum algorithm, the process can be less computationally intensive than the corresponding classical algorithm. Almost all quantum algorithms make use of entanglement to allow measurements on one part of the system’s state to give information about another part of that state.

• The Deutsch algorithm analyzes whether a function is constant (always returns the same output regardless of input) or balanced (output depends on input). This tableTable_11_1 shows the four possible outcomes for single-qubit inputs. A classical algorithm would need to evaluate the function twice to determine whether it is constant or balanced. The Deutsch algorithm can determine the type of function with only a single evaluation of the function.