Q-Intro: Inversion about the Mean

In this introduction article, we discuss and try to understand about projection, outer product and how to achieve the Inversion about the mean using Unitary Gates.

Let’s explore inversion about mean with the following example:

Consider a sequence of integers: 53, 38, 17, 23, 79.

The average of this numbers is a = 42

The average is the number such that the sum of the lengths of the lines above the average is the same as the sum of the lengths of the lines below.

fig 1: sample sequence

Suppose we wanted to change the sequence so that each element of the original sequence above the average would be the same distance from the average but below. Furthermore, each element of the original sequence below the average would be the same distance from the average but above.

In other words, we are trying to inverting each element around the average.

For example, the first number, 53 is

a - 53 = 42 - 53 =-11 units away from the average.

We must add a = 42 to -11 and get a + (a - 53) = 31.

The second element of the original sequence, 38, is

a - 38 = 42 - 38 = 4 units below the average.

We must add a = 42 to 4 and get a + (a - 38) = 46

The third element of the original sequence, 17, is

a - 17 = 42 - 17 = 25 units below the average.

We must add a = 42 to 25 and get a + (a - 17) = 67

The fourth element of the original sequence, 23, is

a - 23 = 42 - 23 = 19 units below the average.

We must add a = 42 to 19 and get a + (a - 23) = 61

The fifth element of the original sequence, 79, is

a - 79 = 42 - 79 = -37 units below the average.

We must add a = 42 to -37 and get a + (a - 23) = 5

fig2: inversion about the mean

In general, we shall change each element to v

The above sequence(as shown in fig 1) becomes 31, 46, 67, 61, and 5 as shown in fig 2. Notice that the average of this sequence remains 42.

what we have seen is invert around the mean, the below points become above points and above points become below points.

Let us write this in terms of matrices. Rather than writing the numbers as a sequence,

consider a vector V as shown below

and consider the matrix A(all-1’s) divided by no. of elements as shown below

where 5 is the number of elements and let’s see what happens when perform the operation A * V as shown below

after performing the multiplication with 5×5 by 5×1 gives us 5×1 as shown below

53 + 38 + 17 + 23 + 79 = 210 and 210/5 = 42 the resultant as shown in the below fig.

It is easy to see that A is a matrix that finds the average of a sequence/Vector V.

In terms of matrices, the formula v’ = -v + 2a becomes V’ = -V + 2AV = (- I + 2A)V.

Let’s calculate -I + 2A as shown below

after performing the matrix addition, the result is as shown below

And, as expected, (-I + 2A)V = V’ ,

in our case,

after performing multiplication the resultant is as shown below

after simplifying

which gives us

Let us generalize, rather than dealing with five numbers, let us deal with 2^n numbers. Given n qubits, there are 2^n possible states. A state is a 2^n vector. Consider the following 2^n-by-2^n matrix:

and -I+2A can be as shown below

we can identify that A² = A

Multiplying a state by −I + 2A will invert amplitudes about the mean. which we have observed above with an example

We must show that −I + 2A is a unitary matrix.

First, observe that the ad joint of −I + 2A is itself. Then, using the properties of matrix multiplication and realizing that matrices act very much like polynomials,

we have (−I + 2A) * (−I + 2A) = +I − 2A − 2A + 4 A² = I − 4A + 4A²

from A² = A we can write as

I − 4A + 4A = I

Note: In linear algebra and functional analysis, a projection is a linear transformation P from a vector space to itself such that P² = P. That is, whenever P is applied twice to any vector, it gives the same result as if it were applied once (i.e. P is idempotent).

A projection on a vector space V is a linear operator P: V → V such that P² = P

Projection matrix:

In the finite-dimensional case, a square matrix P is called a projection matrix if it is equal to its square, i.e. P² = P

A square matrix P is called an orthogonal projection matrix if P²= P = P*

Outer Product:

In linear algebra, the outer product of two vectors is a matrix. If the two vectors have dimensions n and m, then their outer product is an n × m matrix.

Given two vectors of size m × 1 and n × 1 as shown below

outer1

their outer product, denoted u ⊗ v , is defined as the m × n matrix A obtained by multiplying each element of u by each element of v as shown below

outer2

After performing multiplication, we get matrix A as shown below

outer3

For complex vectors, it is often useful to take the conjugate transpose of v, denoted (v†) as shown below

outer4

In Bra-ket notation, as an example we can write A as shown below

braket 1

similarly, The conjugate transpose (also called Hermitian conjugate) of a ket is the corresponding bra as shown below

braket 2

from the fig outer2 as mentioned above we can write the outer product in terms of bra-ket notation as shown below

braket 3

From the below fig braket 4, we can observe that the outer product is similar to the matrix A as mentioned in fig outer3 (above) we can replace matrix A with |u⟩⟨v|

braket 4

Coming back to our original discussion Inversion about the mean

in the expression -I+2A, here A is an all-1's matrix with a division number of elements.

the matrix to be all-1’s it shall have “u = v” or in other wards |u⟩⟨u|

let see the equivalent notation in quantum case:

The operator Us = 2|s⟩⟨s| -I is a reflection through |s⟩

How to write this operator in our known quantum gates?

Let’s explore little deep about -I + 2A, specially A

we know A is all-1's matrix divide by number of elements or qubits

we write this as follows : A= J/N where J is a all-1's matrix(commonly used in physics) and N = 2^n.

then let’s define |ψ⟩ as shown below

and the complex conjugate as shown below

the outer product of these bra ket as shown below

the result is all-1’s matrix as we expected so we can achieve the matrix J using the states |0⟩ and|1⟩

then finally A= J/N, here N = 2 for the example we consider, following is the way we achieve J/2

ket plus state as shown below

bra plus state as shown below

the outer product of plus state as shown below, we gives us J/2 as expected

in case of N qubits J/N can be achieved as shown below

Let’s further simplify, with so far we achieved as shown below

we validate, the above expression can be written as shown below in the following

by solving what HIH means as shown below

After multiplying the first two matrices from right to left as shown below

after performing the multiplication the result is an Identity matrix as shown below

from this result we can observe that HIH = I, replacing what we observed result as shown below

In case of n qubits as shown below

which rises to the following circuit as shown below, -I + 2A inversion about the mean

inversion about the mean

Let’s further understanding which gate is equivalent to 2|0⟩⟨0|-I

simplifying gives the expression is equivalent to Pauli Z matrix

what is the result of H(2|0⟩⟨0|-I)H?

2|0⟩⟨0|-I = pauli -z = Z gate

We see, what exactly HZH do!

HZH

from right to left solving as shown below

which gives as follows

further simplifying

and the result of the HZH gives us X as shown below

HZH = 𝜎𝑥 which means HZH performs the action of bit flip as we expected.

by performing the same in circuit composer we see as below. apply superposition to the circuit

H gate with input as default |0⟩

when add Z gate which gives as HZ as shown below

and finally when we add H gate again to collapse the superposition and draw the measurement as shown below

in the case of multi qubit as shown below

it performs bit flip, |0⟩ to |1⟩ and |1⟩ to |0⟩, it is performing the projection as we discussed.

--

--

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