More quantum algorithms
The Bernstein-Vazirani algorithm is an interesting algorithm to study. Though, its impact on any real-world problem is limited. However, one of its basic principles applies to nearly every quantum algorithm out there:
In a quantum algorithm, quantum gates are used to influence the state of the qubits in such a way that the probability of measuring a correct solution increases.
And of course, there are other algorithms that could help solve problems in the different areas where we expect applications of quantum computing.
Grover's algorithm for search
One of them is Grover's algorithm for search. It can be used to speed up search problems. For this, let's refresh our knowledge about search algorithms.
-
A
\(1\)
-
B
\(\frac{n}{2}\)
-
C
\(n\)
Exactly! The correct item will be found by checking half of all items on average.
Not quite! The correct item will be found by checking half of all items on average.
-
A
\(1\)
-
B
\(\frac{n}{2}\)
-
C
\(n\)
Exactly! In the worst case we will need to check all \(n\) items to find out if an item is or is not in the list.
Not quite! In the worst case we will need to check all \(n\) items to find out if an item is or is not in the list.
With Grover's algorithm problems like this can be solved in \(\sqrt{n}\) checks! That provides a quadratical speedup over the best classical solution! While this is not an exponential speedup, it still can be very useful in a lot of situation where input size is large.
The best part with Grover's algorithm is, that its not only about searching for something in a list, but for everything search is involved. Finding the best seating order for your birthday party so your grumpy uncle and your aunt are not sitting at the same table? Grover's algorithm is here to help! Searching for the solution to a combinatorial optimisation problem? Grover's algorithm is here to help!
Grover's algorithm can not only be used to speed up search, but the trick involved here can also be applied to speed up multiple other algorithms.
Shor's algorithm for prime factorization
Another one is Shor's algorithm for prime factorization.
Given some integer \(n\), prime factorization is the problem of finding prime numbers so we can write \(n\) as a product of these prime numbers. This is a problem, believed to be computationally really hard for classical computers to do (though, this is not proven)! A classical computer will require sub-expontential but super-polynomial runtime. The fact that prime factorization is believed to be hard to do is actually the basis for a lot of cryptographic protocols we use, for example in internet communication.
However, on a quantum computer, we can actually make it in polynomial time!
There is another version of Shor's algorithm for calculating discrete logarithms.
Variational quantum algorithms
Variational quantum algorithms describe algorithms that combine parametrized quantum circuits with classical computing. In a parametrized quantum circuit the gates (e.g. rotations around a specific axis of the bloch sphere) are determined by external parameters (in the picture denoted as p1, p2,...). Those parameters are initialized randomly. Then the circuit is executed and the measurement statistics are evaluated and optimized classically to a certain objective (i.e. to minimize a given mathematical function).
Variational quantum algorithms are the leading approach to utilize near-term quantum computers. Algorithms like quantum approximate optimization algorithms (QAOA) are used to provide approximate solution for combinatorial optimization problems such as the Max-Cut problem.
The website quantumalgorithmzoo.org collects quantum
algorithms with a known speed-up over their classical counterparts.
At IQM Academy, we are also providing hands-on learning experiences with quantum
algorithms such as QAOA or Grover. Check out the other IQM Academy modules.