2
$\begingroup$

I'm trying to use Grover operator in Qiskit (more precisely to perform Amplitude Amplification) but I'm facing some problems. I'm experimenting the Quantum Amplitude Amplification in order to amplify some states of an arbitrary quantum input states providing more than one solutions (sometimes more than half of the total states). In particular, I'm struggling with the right number of iterations that I have to provide in order to get the best results.

I have seen that Qiskit already provides a method to compute this optimal number, but in my case it doesn't work as expected. Indeed, I have as input state a quantum circuit of 5 qubits and as solutions the following states: '11111' and '11110'. Following the theory and the Qiskit's method, the optimal number of iterations is 3 but providing this number I obtain the opposite result that I expect.

enter image description here

Indeed, I see that the procedure amplifies all the states except the last two that correspond to my solutions. However, with 1 iteration the procedure amplifies the correct states. The problem is that it seems not possible to estimate the correct number of iterations to get the correct results when I choose a custom circuit as StatePreparation.

I also provide the example code that I'm using to generate the solution.

enter image description here

Hope someone can help me,

Thank you.

$\endgroup$
2
  • 1
    $\begingroup$ "Following the theory and the Qiskit's method, the optimal number of iterations is 3" what formula did you use exactly here, and how did you use it? $\endgroup$
    – glS
    Commented Jun 13, 2023 at 5:57
  • $\begingroup$ I use the Qiskit method optimal_num_iterations (qiskit.org/documentation/stubs/…) passing as argument the number of solutions (2) and the number of qubits (5), as described in the Qiskit Grover tutorial. Probably this method is used when the StatePreparation is a uniform superposition, but if this is the case, how can I calculate the number of iterations for a custom StatePreparation? $\endgroup$
    – Tommaso
    Commented Jun 13, 2023 at 7:56

1 Answer 1

0
$\begingroup$

Taking the problem generally, we have an operator $O$ defined such that $O|k\rangle = (-1)^{f(k)}|k\rangle$ for all computational basis states $|k\rangle$ where $f(k) \in \{0, 1\}$ for all $k$, and a unitary state preparation $U$ and its inverse. Defining $G = U(2|0\rangle\langle0| - I)U^{\dagger}O$, we want to know the value $q$ such that the probability that $G^q U|0\rangle$ will be measured on the computational basis as a -1 eigenvector of $O$ is maximized.

$|\psi\rangle = U|0\rangle$ can be written in the form $\cos(\theta) |\psi_b\rangle + \sin(\theta)|\psi_g\rangle$ where $0 \leq \theta \leq \pi/2$ for two $|\psi_b\rangle$ and $|\psi_g\rangle$ that are unit eigenvectors of $O$ corresponding to 1 and -1 eigenvalues respectively. Treating this geometrically as just a unit vector on a 2D real plane, applying $O$ will reflect the vector across $|\psi_b\rangle$, and applying $2|\psi\rangle\langle\psi| - I$ will reflect the new vector across $|\psi\rangle$. Applying them in order will result in $\cos(3\theta)|\psi_b\rangle + \sin(3 \theta)|\psi_g\rangle$, and then $G^q |\psi\rangle = \cos((2q + 1)\theta)|\psi_b\rangle + \sin((2q + 1)\theta)|\psi_g\rangle$. Since the probability of measuring a good state is best if $(2q + 1)\theta = \frac{\pi}{2}$, we get what can be rounded to the nearest integer as the number of iterations, independent of any more details of $U$, $O$, and $|\psi\rangle$ other than $\theta$.

Qiskit's built-in optimal_num_iterations (source https://qiskit.org/documentation/_modules/qiskit/algorithms/amplitude_amplifiers/grover.html#Grover.optimal_num_iterations) calculates $a = \sin(\theta)$ ("amplitude") as $\sqrt{s/2^n}$ where $s$ is the number of solutions and $n$ the number of qubits, and then solves for $q = \frac{\pi}{4\theta} - \frac{1}{2} = \frac{\pi}{4 \sin^{-1}(a)} - \frac{1}{2} = \frac{\cos^{-1}(a)}{2\sin^{-1}(a)}$. The amplitude of $|\psi_g\rangle$ is guaranteed as $\sqrt{s/2^n}$ only in the uniform superposition case, so this built-in function won't work if the state preparation is different.

In the more general case, you'll need to know the value of $\theta$ beforehand, or have a procedure classically or quantum to derive it, to know the number of iterations to do. The value of $\theta$ can be worked out in general using a separate quantum phase estimation circuit to measure the period of $G$ applied to $|\psi\rangle$ with a number of additional qubits corresponding to the desired level of precision: in very small cases, this will take sufficient effort so as to invalidate the potential advantage, but asymptotically the phase estimation circuit will remain only about as large as the Grover circuit run afterwards armed with knowledge of $\theta$.

$\endgroup$

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.