Quantum Algorithms

Knowing the underpinnings of randomized benchmarking addressed in the last part, we first begin with the standard protocol. Standard RB is used to assess the error rate over gates of Clifford group with an assumption that these gates have the same error rate. After that, another improvement of the technique will be introduced, namely Interleaved Randomized Benchmarking. The upgraded version was proposed not to investigate the Clifford group as a whole, but restricted to one single kind of Clifford gate of our choice. ...

As you can see in the cover figure, quantum computing is just at the onset of its journey. There are tons of work to do before we can move to the next stage of quantum computing, quantum supremacy. Two pivotal constraints to the realization of any useful quantum processor are decoherence and the high error rate of quantum operators, or quantum gates experimentally. It’s been suggested that the probability of error per unitary gate should be less than $10^{-2}$ (better $10^{-4}$) for the outcome to be reliable. ...

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. ...