QC — Quantum Algorithm with an example

Image for post
Image for post
Photo by Sensei Minimal

In Part 5 & 6, we look into the details of both single and 2-qubit quantum gates — the building blocks for quantum algorithms. Let’s get ready to build a quantum program. In this example, we will demonstrate ways to build a quantum program, in particular how quantum parallelism and interference work. The interference plays a key role in creating a pattern of measurements to calculate the final results.

Deutsch-Jozsa Algorithm

Deutsch-Jozsa algorithm is one of the first quantum algorithms with nice speedup over its classical counterpart. Consider this as my “hello world” in quantum computing but don’t expect it as a single line program.

Consider a function f that takes 0 or 1 as input and outputs either 0 or 1.

Image for post
Image for post

Our functions in mind are either balanced or constant. A function f is called balanced if it outputs 0 half the time and 1 the other half. It is a constant function if its output is a constant (1 or 0) regardless of input. Here is an example with a single-bit input.

Image for post
Image for post

Our task is given a function, determine it is constant or balanced. The problem is simple but involves a few cool quantum concepts. But before we develop the maths, let’s conceptualize a possible solution.

For classical computing, we can query the function twice and aggregate the result with some if-then-else statements.

Image for post
Image for post

If the number of input bits is increased to n, to verify a function is balanced, we query f for

Image for post
Image for post

Nice. We have a problem with query complexity that can grow exponentially in the worst case. Let’s expand n to 2 qubits. We can use Hadamard gates to prepare a superposition representing all 4 possible bit combinations. We assume that we have an Oracle function (a super smart or a super slick quantum circuit). It uses the quantum parallelism concept to compute all values of f(x) from the superposition in polynomial time, instead of growing exponentially with the number of bases. Let’s not bother on how this oracle function is implemented for now. It deserves some separate discussion at the end of the article.

By creating a superposition, we allow an Oracle function to work on all possible configurations all at once.

Image for post
Image for post

The key idea is the Oracle function will output values that after applying interference (a transformation), we will measure 0 for all constant functions or 1 for balanced functions.

Image for post
Image for post

Single bit input

Let’s lay down a big picture before detailing it. For simplicity, our function f will take 0 or 1 only (a single-bit input). Below is the quantum circuit. Step ① and ② prepares the superposition, step ③ is the oracle and step ④ is the interference.

Image for post
Image for post
Modified from source

To realize what is happening exactly, let’s do some math. The corresponding math corresponding to each step above is:

Image for post
Image for post
Modified from source

① applies a Pauli X-gate to the second qubit which converts it from |0⟩ to |1⟩.

② applies a Hadamard gate to each of the qubits and put them into a superposition

Image for post
Image for post

Now, our first qubit is in a superposition representing both possible input |0⟩ and|1⟩ for the Oracle function. ③ applies an oracle function

Image for post
Image for post

For f(x) = 0, the second qubit is simply y. (For simplicity, we will drop 1/√2 from the equation for now.)

Image for post
Image for post

For f(x) = 1, we flip the sign.

Image for post
Image for post

By examining both outputs, we can generalize the equation as:

Image for post
Image for post

Replacing |x⟩ with |0⟩ +|1⟩, we get

Image for post
Image for post

Here is the result after applying the Oracle function.

Image for post
Image for post

We can go through all possible combination of f and compute the superposition of the first qubit for each scenario.

Image for post
Image for post

We find that for the same function type, the values differ by a sign only. i.e. by a global phase with the Δγ equals π.

Image for post
Image for post

Superpositions different by a constant global phase are indistinguishable in the real word. They always have the same probability of measurements regardless of how they measure. This does not change as long as no operations or the same operations are applied to both.

Image for post
Image for post

This is excellent news! Within the same function type, they will always measure the same way. So our focus is applying a transformation so different groups end with different measurements. ④ applies the Hadamard gate and a constant function will be measured as |0⟩ and a balanced function as |1⟩.

Image for post
Image for post

Multiple-bit input

Let’s expand our solution for input with n bits (say f(1101)). We can apply n Hadamard gates to prepare the superposition.

Image for post
Image for post

And apply the Oracle function again. If you work out the case where f(x)=0 and f(x)=1, like what we did, you will end up the same equation in the last step below.

Image for post
Image for post

The second qubit above will remain the same for the rest of the circuit. So for simplicity, we just focus on the first qubit.

Image for post
Image for post

Then, we apply n Hadamard gate again. The general equation for the Hadamard gate transformation on multiple qubits is:

Image for post
Image for post

This is just a nice condensed formularization (nothing new) where <x , y> is the bitwise dot product of the binary representation of x and y. For example,

Image for post

So after applying Hadamard gates, the qubits become

Image for post
Image for post

Let see the case when y = |00000…00⟩. Now, x · y = 0.

Image for post
Image for post

It becomes:

Image for post
Image for post

When f(x) is balanced, half of the inner summation terms above will destructively cancel each other. If f(x) is a constant, all the inner summation terms will add up together and becomes

Image for post
Image for post

So for the former case, no measurement should be made for |00000…00⟩ while in the second case, all the measurements are |00000…00⟩. In short, the measurement of the superposition depends on the interference created by f(x).

Image for post
Image for post

Yes. We are done with the first “hello world”. Let’s recap the math before we see the quantum circuit.

Recap

Here is a quick recap of the whole calculation:

Image for post
Image for post
Source

Implementation

Let’s implement it. The Oracle function here represent the function:

Image for post
Image for post

Since we know the exact function we want to support, the quantum circuit can be simplified and implemented as:

Image for post
Image for post

Here are the measurements running on a real quantum computer.

Image for post
Image for post

Measurements for |000⟩ are very low. Mostly caused by gate errors and noise. So the Oracle function is a balanced function. That is exactly the type of our function belonging to.

Let’s have an oracle representing a constant function. Actually, an identical operator will do it.

Image for post
Image for post

As expected, we measure the three qubits as |000⟩.

Image for post
Image for post
Image for post
Image for post

Oracle function

Deutsch-Jozsa Algorithm and many other quantum algorithms provide a solution template for a large range of problems. By replacing the Oracle function with a domain-specific function, we can apply the same kind of solution to many problems. Unfortunately, this creates a major stumbling block when first studying quantum computing. The speedup expectation is raised too high with the illusion that we break the curse of the exponential problem forever — the solution may be hard but generally available. In our example, we present an Oracle that hardcode the knowledge of the function into the circuit. We do not query the value of f(x) directly. We map the inputs directly to the output we want. I call it slick because the solution is not generalized enough for any practical use. People want to know the magic of not query f exponentially and we only provide some toy examples. So the disappointment is well understood.

The reality is if we expect the Oracle function to handle any possible functions, query the function for at least half of the possible data seems unavoidable for the worst case. We can argue that the information is already available in superposition so we can compute them in parallel. It is not that simple and we will not elaborate it further.

The real-life problems that can beat the classical algorithms must discover a pattern that can load information into superposition efficiently or they only need a polynomial amount of information. In our toy example, we discover a pattern of the function and take advantage of it. But such hardcoded knowledge hurts its generalization. So what is the point if we do not show a real problem with a nice Oracle implementation? We will continually discover generic algorithms based on Oracle functions to learn different quantum tricks. In the process, we will learn all the methods and combine them to solve significant problems. Shor’s algorithm is one good example which is used to break RSA cryptography.

Quantum computing is not the answer to everything. Scientists are focusing on the BQP problems below. We know prime factoring and many problems belong to this category. So we are looking into what other problems may belong to this group of the algorithm.

Image for post
Image for post
Source

Next

We will look into a few more Oracle based algorithms to get familiar with quantum algorithms before we get into Shor’s algorithm.

Written by

Deep Learning

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store