A quantum algorithm is a sequence of operations that can be performed only on a quantum computer. Such algorithms exploit properties inherent to quantum systems, such as entanglement, superposition and interferences.
These features allow quantum algorithms to outperform the state-of-the-art classical algorithms for solving certain problems. The best-known quantum algorithms are Shor’s algorithm for factoring integers into prime numbers and Grover’s algorithm for searching in an unstructured database.
Quantum algorithms can be built using different approaches, called models of quantum computation. These models are like different ‘languages’ or ‘tools’ to solve problems using the laws of quantum physics. The most common ones are the gate-based model , quantum annealing, and Measurement-based quantum computing (MBQC). Even though these models work differently, they can often solve the same problems.
Frequently Asked Questions About Quantum Algorithm
- What makes a quantum algorithm really quantum? This is a very interesting and complicated question that is still at the heart of quantum information theory. Resource theories allow us to better understand the role of quantum resources such as coherence, magic or entanglement.
- What is the output of a quantum algorithm? The output of a quantum algorithm is obtained by measuring the quantum system. A classical post-processing is usually performed on the measurement outcome.
- Do all classical algorithms admit a more efficient equivalent quantum algorithm? Many classical algorithms do not admit a more efficient equivalent quantum algorithm, e.g., sorting algorithms. For many classes of problem, this question is tackled by computational complexity theory.
