Like classical computers, quantum computers depend on algorithms to perform calculations. However, quantum algorithms differ from their classical counterparts in that they can make use of the unique properties of quantum mechanics such as superposition, entanglement, and interference to perform operations. This can lead to novel ways to solve a particular problem, sometimes leading to significant speed-ups over classical computers. Creating quantum algorithms requires a solid understanding of both quantum mechanics and quantum computing, as well as facility with a quantum programming language such as Q#, or a quantum circuit simulator such as Qiskit. Quantum algorithm development is a complex and rapidly evolving field and developing useful algorithms is an active area of research.
One of the most famous quantum algorithms is Shor’s algorithm, developed by Peter Shor in 1994 to efficiently factor large numbers. The key to Shor’s algorithm’s is a quantum computing step that uses Quantum Phase Estimation and the Quantum Fourier Transform to find a mathematical pattern that can be used to solve the problem. Quantum computers can perform this step much faster than classical computers, enabling a potentially large speed-up. (It is important to note that Shor’s algorithm is a theoretical demonstration of the power of quantum computing. While it has been successfully implemented on small-scale quantum computers, factoring large numbers requires a fault-tolerant, large-scale quantum computer, which is still under development.)
Other examples of commonly used quantum algorithms include:
- Quantum amplitude amplification: This is a technique used in quantum algorithms to intensify the amplitudes of the marked states in a quantum superposition, while decreasing the amplitudes of unmarked states.
- Quantum Fourier Transform (QFT): The QFT is a quantum analogue of the classical discrete Fourier transform, which is used to transform a classical signal from its original time domain to a frequency domain. The QFT works by applying a sequence of quantum gates, called the QFT circuit, which consists of a sequence of Hadamard and controlled phase gates. This algorithm is a fundamental component of many other quantum algorithms, including Shor’s and quantum phase estimation.
- Draper adder: An adder is a quantum circuit that uses quantum gates to perform addition of two numbers on a quantum computer. The Draper adder is based on the Quantum Fourier Transform and works by applying a sequence of controlled phase gates and single-qubit gates to input qubits, followed by the inverse QFT. The controlled phase gates encode the sum of the two input numbers, while the single-qubit gates are used to correct the carry bits.
- Beauregard adder: The Beauregard adder has a different structure than the Draper adder and can be more efficient in certain cases. It can be parallelized to compute multiple additions in parallel, and it is more fault tolerant than the Draper adder.
Quantum oracles
In classical computing, we often discuss “closed box” versus “open box” testing. In “open box” testing, the implementation of a function is visible to the tester, thus they can verify specific runtime or memory expectations for the algorithm. However, in “closed box” testing the tester doesn’t have access to the details of the function implementation, only to the “box” that takes an input and produces the corresponding output. This means the tester can observe only the functionality and expected behavior of the function, but not the implementation.
Closed box testing is a good analogy for how oracles work in computing. Formally, a classical oracle is a function that when provided an input produces a deterministic output. In other words, the same input always results in the same output. In quantum computing, an oracle is a closed box that is designed to implement a specific quantum computation. An oracle takes a quantum state as input, performs a quantum algorithm or computation on it, and returns the resulting quantum state as output. The key property of a quantum oracle is that it can evaluate a function on a superposition of inputs in a single step, which is exponentially faster than classical algorithms that requires evaluating the function of each input separately.
Quantum oracles are used in many quantum algorithms, including Grover’s search algorithm and Shor’s algorithm. Grover’s search algorithm uses a quantum oracle to take a superposition of all possible inputs and marks the inputs that satisfy the search criterion. Repeating this process several times with a cleverly chosen number of repetitions allows the algorithm to identify the desired item with high probability. Shor’s algorithm uses a quantum oracle to perform modular exponentiation. The quantum oracle takes a superposition of all possible inputs and applies a function that maps each input to its modular exponentiation. By applying Quantum Fourier Transform on the resulting superposition, the algorithm can find the period of the function, which is used to factor the integer. Other examples of quantum oracles include the Deutsch-Jozsa algorithm, which determines whether a closed box function is constant or balanced, and Simon’s algorithm, which finds a hidden period in a closed box function. These algorithms demonstrate the power of quantum oracles to perform computations more efficiently than is possible using classical algorithms.
