Q-Intro: Inversion about the Mean
How to perform reflection about mean quantumly?
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.
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
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
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
After performing multiplication, we get matrix A as shown below
For complex vectors, it is often useful to take the conjugate transpose of v, denoted (v†) as shown below
In Bra-ket notation, as an example we can write A as shown below
similarly, The conjugate transpose (also called Hermitian conjugate) of a ket is the corresponding bra as shown below
from the fig outer2 as mentioned above we can write the outer product in terms of bra-ket notation as shown below
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|
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
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!
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
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.
references:
some other references: qiskit textbook, cirq tutorials, IITM course by (@Prabha M, Anil Prabhakar), Qubit by Qubit(The Coding School) course, Textbook by Isaac Chuang and Michael Nielsen, Textbook by Noson S, Textbook by Phillip Kaye, Wikipedia, stack exchange and open source materials.
