Behind phase Oracles

 


Quantum algorithms such as Deutsch, Bernstein-Vazirani, Simon and Grove rely on Oracles. A particular class of Oracles, the phase Oracles, allows to selectively switch phases of the input state, thus helping these algorithms to distinguish states by their phases. In this blog I will explore a bit more this class of Oracles

Firstly. lets revisit the superposition state for a single qubit $|0\rangle$ after applying the Hadamard gate:

                $ H\otimes|0\rangle = \frac {1} {\sqrt{2}} ( |0\rangle + |1\rangle ) = |+\rangle $

To recap, this is a state of maximum uncertainty when measured in the computational basis. In simple terms, it represents a state where, when measured, has equal probability of being 0 or 1.

As mentioned before, the trick to make the information conveyed by a state more useful is to include a local phase to it. This can be achieved by adding a new qubit in the superposition state $|-\rangle = \frac {1} {\sqrt{2}} ( |0\rangle - |1\rangle )$. The addition of the new qubit results in the following new state:

               $ |+\rangle |-\rangle  = \frac {1} {2} ( |0\rangle{\color{red}+ |1\rangle })\otimes ( |0\rangle - |1\rangle  ) $

There are two special characteristics of this new state!

First, the new state has now a local phase (introduced by the minus on the second qubit: $|-\rangle $!

Second, note that, by flipping the signal of ${\color{red}+ |1\rangle }$ in the first qubit state we move the first qubit state, from the state $\pm |+\rangle$ to the state $\pm |-\rangle $!

This is exactly the tricky implemented by algorithms like Deutsch and Bernstein-Vazirani !

Let's break it down...

Expanding to terms the state we have:

                $ |+\rangle |-\rangle  = \frac {1} {2} ( |00\rangle - |01\rangle {\color{red}+ |10\rangle }- |11\rangle  ) $

Note again the basis state highlighted in red above. To manipulate the first qubit on our output, we need to be able to change the signal of the state $|10\rangle$.

So, how the states can be manipulated in a way to change the phase of the state $|10\rangle$ ?

So far we only prepared the state so that it contains a negative phase. Now the Oracle function gets into the picture. In our example, the Oracle is built using the function "sum mod 2" applied to the second qubit and f(x), where f(x) is a function we need to define. As long as f(x) outputs binary, any function can be used and will help on the trick to change the states' phase.

Why that works ?

First, consider the "sum mod 2" operation, also known as XOR, which is represented by the table below:

                        2nd qubit    f(x)       2nd qubit "sum mod 2" f(x)

                            0                0                                                0

                            0                1                                                1

                            1                0                                                1

                            1                1                                                0

Now let's apply the function f(x) to each of the basis states using the "sum mod 2", and using as parameter for the function f(x) the value of the first qubit of each basis state. In the example below, the values in ${\color{blue}blue}$ ilustrate, for the basis $|10\rangle$, which of the two qubits is used as input for the function:

            $ |\psi_{out}\rangle = \frac {1} {2} ( |00\rangle \oplus f(0) - |01\rangle \oplus f(0) {\color{red}+ |}{\color{blue}1}{\color{red}0\rangle \oplus f(}{\color{blue}1}{\color{red}) }- |11\rangle \oplus f(1)  ) $ 

Observing the table above and $ |\psi_{out}\rangle$, the only way to flip the signal of $|10\rangle $ is to force the basis state $|11\rangle $ to turn into $|10\rangle $ and to maintain the signal of the states where the first qubit is 0 (otherwise, the double flip will turn the local phase into a global phase). This can be achieved if we define f(1)=1 and f(0)=0. Note that with this configuration of f(x) both basis states $|1\_ \rangle$ will flip signs, ending with the following state:

            $ |\psi_{out}\rangle = \frac {1} {2} ( |00\rangle  - |01\rangle  + |11\rangle  {\color{red}- |10\rangle }  ) $

Factoring these states gives:

             $ |\psi_{out}\rangle = \frac {1} {2} ( |0\rangle{\color{red}- |1\rangle })\otimes ( |0\rangle - |1\rangle  ) $

and we have the flip on the first qubit, caused by the function implemented in the phase Oracle.

So, a quick recap...

  • using the state $|-\rangle$ introduces a handy local phase to the initial state
  • the function f(x) must be linked to the first qubit (ie. must use the first qubit as input) so that phase flips are applied to the right pairs of states
  • ultimately, information is represented by the states $|+\rangle$ and $|-\rangle$ on the first qubit. Once we apply a Hadamard and measure it, it will render either the value 0 or 1
  • the same concept can be easily extended for when $|x\rangle$ is composed of many qubits

Comments

Post a Comment

Popular posts from this blog

The simplest quantum binary classifier

Image
How the simplest quantum binary classifier looks like? While searching in internet for the smallest quantum classifier I came across the article from Maria Schuld “Building the world’s smallest quantum classifier” (1) and, based on the circuit proposed there, I thought an even smaller classifier could be built. Here I show a simple variational circuit that can be applied to a 2-feature dataset for binary classification. Though the example is questionable for practical purposes, it gives interesting insights on how to apply quantum computing to machine learning. The circuit is composed of two parts: the embedding, which transforms the classical data into quantum states, and the ansatz, which is parametrized, and the parameters are optimized using a particle swarm optimization algorithm (2). The circuit and the findings follow. First, we need a dataset! Instead of searching for real datasets which must be cleaned, normalized, etc… I’ve created one. The dataset contains 60 samples, each s...
Read more

IBM Qiskit Exam: my four weeks preparation

Image
After dedicating approximately a month to preparing for the IBM Certified Associate Developer - Quantum Computation using Qiskit v0.2X, and successfully passing the exam (making 3 errors out of 60 questions), I am sharing my experience in this blog. First of all, let me be very clear: I cannot and will not share exam questions due to the exam policies. Nevertheless, what I can and will share is how I organized myself, the materials I used, and the preparation tests I undertook along the last month. First of all, let me provide some context regarding my prior knowledge before the preparation. I have acquired previous knowledge in quantum computing through my attendance at two quantum computing courses, participation in two IBMQ challenges, reading of books, articles, and papers on quantum computing and quantum machine learning (some of which I have shared in my previous blogs). While this prior knowledge is advantageous for preparation, it's important to emphasize that the test spec...
Read more

A View on the Deutsch Algorithm

Image
  The Deutsch Algorithm is an excellent example of the application of quantum parallelism using superposition of states. The problem which is solved by the algorithm is the following: Given an unknown function f(x): {0:1} -> {0,1}, by using the minimum amount of queries to this function, determine if the function is constant (it always returns 0 or always returns 1) or balanced (on half of the inputs it returns 0 and the other half, 1). In the classical case, we need to query the function twice, one for x=0 and a second for x=1. In case of the quantum algorithm, a single query can define if the function is balanced or constant. There are many articles explaining how the algorithm works. Here I've taken a different approach: After a brief recap of the algorithm, the analysis of the algorithm follows by opening each state and showing how the problem definition and the function we want to classify contributes to the algorithm output.  On its simplest form, the algorithm utiliz...
Read more