Deutsch Algorithm

In the last part of the previous series, Deutsch algorithm, I introduced a manual way to construct the oracle. That oracle must be built from matrix because the oracle function is undeterminate except for the outcome. In Bernsterin-Vazirani problem, the function is, on the other hand, clearly stated: $f(\mathbf{x}) = \mathbf{s}\cdot\mathbf{x}$. So, it’s unnecessary to repeat the previous procedure; instead, we’ll build the oracle without using matrices by understanding what the function really do. ...

Here we stop by Berstein-Vazirani problem that inherents the structure of its predecessor, Deutsch-Jozsa problem, before we can get started with problems and solutions of practical meaning later. Because this problem is similar to the one stated in the last series, we’ll get straight to it. Berstein-Vazirani problem The access for a black-box function $f: \{0,1\}^n \mapsto \{0,1\}$. It’s guaranteed that $f(\mathbf{x}) = \mathbf{s}\cdot\mathbf{x}$ (mod $2$) for some secret string $\mathbf{s} \in \{0,1\}^n$. ...

Because the Deutsch algorithm is just a simple instance of the Deutsch-Jozsa algorithm where $n=2$, we’ll only discuss how to implement the general one. Let’s go. Difficulty of reconstructing gates from matrices This is the first time we encounter a so-called black-box function in an algorithm. It’s called a black box since we don’t how it calculate the output from the input, but we do know the output it returns. ...

Here we’re gonna see the most impressive quantum algorithm in terms of query complexity. The algorithm is an generalization of the original Deutsch algorithm we discussed in the last post. But I want to say that this algorithm may not be as extraordinary as you may think of it. It was created to solve a kind of problem that has zero practical meaning for the purpose of demonstrating how strong quantum computing can reach compared to classical computing. ...

I have said something like quantum computing can overpower classical computing several times before. In this series, I’m going to showing you a problem with a quantum algorithm that is exponentially faster in terms of complexity than any classical solution. In this text, we’re going to explore an essential technique and apply it to solve the simplest version of Deutsch problem. Phase kick-back One concept you may encouter numerous times in a Linear Algebra class is eigenvalues and eigenvectors. ...