### What's Up

### Most Read Articles

#### Welcome to Einstein Relatively Easy!

This web site is aimed at the general reader who is keen to discover Einstein's theories of special and general relativity, and who may also like to tackle the essential underlying mathematics.

Einstein's Relativity is too beautiful and too engaging to be restricted to the professionals!

Have fun!

*"I have no special talents*

* I am only passionately curious" *

Albert Einstein

If you like this content, you can help maintaining this website with a small tip on my tipeee page

## Qubit

- Details
- Category: Dictionary
- Hits: 115

What is a **qubit**? Just as a classical bit has a state – either 0 or 1 – a qubit also has a state.

Two possible states for a qubit are the states |0> and |1>, which as you might guess correspond to the states 0 and 1 for a classical bit. Notation like ‘|>’ is called the ** Dirac notation**, and it’s the standard notation for states in quantum mechanics.

The difference between bits and qubits is that a qubit can be in a state other than |0> or|1>.

It is also possible to form linear combinations of states, often called superpositions: **|ψ> = α|0> + β|1>** with the numbers α and β being complex numbers.

Put another way, the state of a qubit is a vector in a two-dimensional complex vector space. The special states |0> and |1> are known as computational basis states, and form an orthonormal basis for this vector space.

Another difference is that the value of the bit can be determined at any time: computers do this all the time when they retrieve the contents of their memory, to check whether it is in state 0 or 1. On the contrary, **we cannot examine a qubit to determine its quantum state**, that is, the values of α and β. Instead, quantum mechanics tells us that we can only acquire much more restricted information about the quantum state. When we measure a qubit we get either the result 0, with **probability|α| ^{2}**, or the result 1, with

**probability|β|**, with |α|

^{2}^{2}+|β|

^{2}= 1, since the probabilities must sum to one.

## The Deutsch-Jozsa algorithm

- Details
- Category: Quantum Mechanics
- Hits: 432

Quantum parallelism is a fundamental feature of many quantum algorithms. Heuristically, quantum parallelism allows quantum computers to evaluate a function f(x) for many different values of x simultaneously. |

The Deutsch-Jozsa algorithm - published by David Deutsch and Richard Jozsa in 1992 - is one of the first quantum algorithms with nice speedup over its classical counterpart, and it represents a good example of quantum parallelism.

##### Constant and balanced functions

In most typical cases where functions are involved, we are mostly interested in finding the result of a function. But in some cases though, the function evaluations are not important, but the characteristics or the **properties** of the functions are. In this area, quantum algorithms can be helpful.

In general, the functions we consider are noted as *f*(*x*) where *f* is the function that operates on an input variable called *x*. The evaluation of a function for a specific input is also called the *result* and sometimes noted as *y*, where *y* = *f*(*x*).

Let's start with a very simple function f which takes a single bit (a boolean value) as its input, and it produces a single bit as well. The function thus only operates on either '0' and '1' and its result is either '0' or '1'

Let f :{0, 1}→{0, 1}.

The combination of 2 input options and 2 output options leads to 4 possible cases for this function, which we will name f1, f2, f3 and f4:

f1: f(0) = 0 and f(1) = 0

f2: f(0) = 0 and f(1) = 1

f3: f(0) = 1 and f(1) = 0

f4: f(1) = 1 and f(1) = 1

##### The Deutsch problem

This being said, the question that we ask ourselves is very simple: does f(0) =f(1)?

This is often stated in a much more pedantic way for whatever reasons: “Is f constant or balanced?

- by **constant**, we mean f(0) = f(1),

- by **balanced** we mean f(0) != f(1).

This is to say in much more words ;-)

From those defintions, it appears that *f*1 and *f*4 are constant functions, and *f*2 and *f*3 are balanced functions.

We can state the **Deutsch problem** in an even more pedantic way, as follows:

Determine the value of the parity of f(0) ⊕ f(1) where ⊕ denotes addition modulo two.

Show that if *f* is **constant** then the parity is zero, and if *f* is **balanced** then the parity is one.

In the Deutsch algorithm, one of the four functions is provided, but we don’t know what function it is. We know it is *f*1, *f*2, *f*3 or *f*4 but that’s all we know.

We are now asked to find out if this function is constant or balanced. Keep in mind that our task is **not** to find out if the provided function is *f*1, *f*2, *f*3 or *f*4 .

Now we get to the intersting part, solving the problem.

##### Solving the problem

First, we can ask ourselves **how many classical queries** does it take to solve this problem?

That’s a pretty easy exercise. It’s** two**. It must be two since the values of f(0) and f(1) are completely independent of each other.

We have to ask what both values are, then compare to see if they’re the same ordifferent.

For example, suppose we measure *f*(0) and the result is `1`

. From the table above, it seems that in this case, our function is either *f*3 (which is balanced) or *f*4 (which is constant). Hence, we don’t have enough information.

In case the result of measuring *f*(0) is `0`

, the table above shows that the function is either *f*1 (which is constant) or *f*4 (which is balanced). Again, this proves that measuring *f*(0) is not enough to conclude whether the function is constant or balanced. It can be either.

If the number of input bits is increased to *n*, to verify a function is balanced, we query *f* for **2 ^{n-1} +1** in the worst case. We have a problem with query complexity that can grow

**exponentially**in the worst case

### Login Form

### Breadcrumbs

### Quotes

### RSS Feed

### Who is online

We have 22 guests and no members online