Quantum Algorithms

Key Quantum Algorithms

• Deutsch Algorithm

  The first quantum algorithm, designed to determine if a function is constant or balanced with a single query. It demonstrates the principle of quantum parallelism, but does not provide exponential speedup for practical problems.

• Deutsch–Jozsa Algorithm

  Generalizes Deutsch’s algorithm to functions with multiple inputs. It can determine if a function is constant or balanced with just one evaluation, while a classical computer may need exponentially many. This provides an exponential speedup for this specific problem.

• Grover’s Algorithm

  A quantum search algorithm that finds a marked item in an unsorted database of N items in about √N steps, compared to N/2 on average for classical search. This provides a quadratic speedup, useful for search and optimization problems.

• Shor’s Algorithm

  Efficiently factors large integers and computes discrete logarithms. Shor’s algorithm runs in polynomial time, while the best-known classical algorithms are superpolynomial. This exponential speedup threatens classical cryptography based on factoring.

• Quantum Phase Estimation

  Estimates the eigenvalues of a unitary operator. It is a core subroutine in many quantum algorithms, including Shor’s algorithm and quantum simulations. It provides exponential speedup for certain problems in physics and chemistry.

• Quantum Approximate Optimization Algorithm (QAOA)

  A hybrid quantum-classical algorithm for solving combinatorial optimization problems. QAOA leverages quantum superposition and entanglement to explore solutions, and may provide speedup for certain hard optimization tasks, though the extent of quantum advantage is still under research.

• Variational Quantum Eigensolver (VQE)

  Used to find the ground state energy of molecules and materials. VQE is a hybrid algorithm that uses quantum circuits and classical optimization, and is promising for near-term quantum devices. It can outperform classical methods for some quantum chemistry problems.