2
$\begingroup$

Before I start describing the context and background to my question, I would like to say I am relatively inexperienced in quantum computing, so my terminology may be off at times. However, I found this interesting phenomenon in a program I made concerning Grover's search and I am curious as to why it works.

Background

For this, I will say that a state with $n$ qubits can be represented by a vector with $2^n$ entries corresponding to the amplitude of the state whose binary representation is the same as its position in the vector. For example, $|\psi\rangle = |00\rangle + |11\rangle$ can be represented by $\begin{bmatrix}1\\0\\0\\1\end{bmatrix}$.

So for Grover's search, there is the Grover Diffusion Operator which can be represented by $U_s=2|\psi\rangle\langle\psi| - I$ where $|\psi\rangle$ is the uniform superposition of the n-qubits of a system and $I$ is the corresponding identity matrix. There is also the oracle operator, $U_\omega$ where $U_\omega |x\rangle = (-1)^{f(x)}|x\rangle$. $f(x)$ is 1 for a valid, or our target, state $x$ and 0 otherwise. Applying these two operators on a uniform superposition state, $|s\rangle$, roughly $\sqrt N$ times should return a significantly larger relative amplitude of the desired state.

New Operator

Now after creating a program that can run essentially a quantum circuit on Google Colab. What I found is that if the Grover Diffusion Operator is changed to simply

$$U_s=|\psi\rangle\langle\psi| - I$$

then it only takes one iteration for the search to present an extremely high probability of one state, and it gets better with more Qubits. I will present an example below using mathematical methods.

Comparative Example

Take a 4 Qubit system in which the desired state is $|0000\rangle$. We will first use the original Grover Diffusion Operator, $U_s = 2|\psi\rangle\langle\psi| - I$, which we will construct its matrix form below.

For the first term, the projection of the normalized superposition state, $|\psi\rangle\langle\psi|$ gives

$$\begin{bmatrix} 0.0625 & 0.0625 & \dots & 0.0625 \\ 0.0625 & 0.0625 & \dots & 0.0625 \\ \vdots & \vdots & \ddots & \vdots\\ 0.0625 & 0.0625 & \dots & 0.0625 \\ \end{bmatrix}$$

Then, multiplying this matrix by 2 and subtracting the identity matrix gives

$$U_s = \begin{bmatrix} -0.875 & 0.125 & \dots & 0.125 \\ 0.125 & -0.875 & \dots & 0.125 \\ \vdots & \vdots & \ddots & \vdots\\ 0.125 & 0.125 & \dots & -0.875 \\ \end{bmatrix}$$

Now we take a normalized uniform superposition state $|s\rangle$ and apply the Oracle operator to it first to get

$$U_\omega |s\rangle = \begin{bmatrix} -0.25\\ 0.25\\ \vdots \\ 0.25\\ \end{bmatrix}$$

Finally, performing

$$U_s\cdot \begin{bmatrix} -0.25 \\ 0.25 \\ \vdots \\ 0.25 \\ \end{bmatrix} = \begin{bmatrix} 0.6875 \\ 0.1875 \\ \vdots \\ 0.1875 \\ \end{bmatrix} \equiv 0.6875|0000\rangle + 0.1875|0001\rangle + \dots + 0.1875|1111\rangle$$

This is the resulting state with a 43.7% probability of measuring state $|0000\rangle$ after one iteration. Repeating this twice more, corresponding to the approximate time complexity of $O(\sqrt N)$, results in a 96.1% probability according to mathematical calculations.

Now, taking the same approach but with the revised Grover Diffusion Operator, we can do this in one step. For brevity, the Grover Diffusion Operator matrix is:

$$U_s = \begin{bmatrix} -0.9375 & 0.0625 & \dots & 0.0625 \\ 0.0625 & -0.9375 & \dots & 0.0625 \\ \vdots & \vdots & \ddots & \vdots\\ 0.0625 & 0.0625 & \dots & -0.9375 \\ \end{bmatrix}$$

This time, performing

$$U_s\cdot \begin{bmatrix} -0.25 \\ 0.25 \\ \vdots \\ 0.25 \\ \end{bmatrix} = \begin{bmatrix} 0.46875 \\ -0.03125 \\ \vdots \\ -0.03125 \\ \end{bmatrix}$$

This is equivalent to the normalized state of

$$0.96825|0000\rangle - 0.06455|0001\rangle - \dots - 0.06455|1111\rangle$$ which has a probability of 93.75% of attaining the desired state mathematically.

Interestingly, the probability after one single iteration gets better and better for larger Qubit systems. For example, for a 10 Qubit system, the probability of measuring state $|0000000000\rangle$ is 99.9023437% according to the program I wrote. Also interestingly, this value seems to be $1- \frac{1}{2^N}$ where N is the number of Qubits.

Question

After this elaborate writing, I was wondering why this seems to work and whether this has been analyzed before? It seems too real to be true, and although I don't know how this applies to constructing an actual circuit, mathematically, it seems to be valid.

$\endgroup$

1 Answer 1

4
$\begingroup$

You can't just choose any operator that you want. Generally, you want to choose something that's unitary. Your new operator isn't. Instead, it's a measurement. This is still technically allowed, but is unlikely to lend itself well to repeated iteration. It may be that you suggestion works well enough on small cases, but if it works, you should be able to prove it works for arbitrary $N$, and for arbitrary search states.

The main place where your analysis falls down is that you said "This is equivalent to the normalized state of...". You cannot freely just renormalise. The lack of normalisation of your state corresponds to a probability of success (you're measuring, this is the probability of getting that outcome). So, yes, if you get the right outcome, you've got a better state, but those probabilities don't stack up well.

I should emphasise that Grover's search has been proven to be exactly optimal. Not just the scaling, but the exact number of oracle calls. It is impossible to do better.


Some clarifying maths: Let's take your proposed operator (which I'll call $U_s'$) as a realistic proposition. Your outcome is $$ U_s'U_\omega|\psi\rangle. $$ I can write this out as $$ |\Psi\rangle=-\frac{2}{\sqrt{2^N}}\left(\frac{1}{\sqrt{2^N}}|\psi\rangle-|x_0\rangle\right) $$ where $x_0$ is the term you're search for. The probability of finding the searched state when you measure is $$ |\langle x_0|\Psi\rangle|^2=\frac{4}{2^N}\left(1-\frac{1}{2^N}\right)^2. $$ Note that this vanishes exponentially in $N$.

What you've done is assume you can renormalise the state $|\Psi\rangle$ (which you can't without keeping track separately of the probability of success of the measurement. If you do that, you'll just get the above answer) $$ |\Psi'\rangle=\frac{1}{\sqrt{\frac{1}{2^{N+1}}+\left(1-\frac{1}{2^N}\right)^2}}\left(\frac{1}{\sqrt{2^N}}|\psi\rangle-|x_0\rangle\right). $$ So, yes, if you get that state, the probability of getting your search state is $$ \frac{\left(1-\frac{1}{2^N}\right)^2}{\frac{1}{2^{N+1}}+\left(1-\frac{1}{2^N}\right)^2}\approx 1-\frac{1}{2^{N+1}}. $$ but your probability of getting that state is roughly $\frac{1}{2^N}$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.