# Non-locality and Entanglement Detection with Mermin polynomials for Grover's algorithm and Quantum Fourier Transform

Henri de Boutray, Hamza Jaffali, Frédéric Holweck, Alain Giorgetti, Pierre-Alain Masson

► To cite this version:

Henri de Boutray, Hamza Jaffali, Frédéric Holweck, Alain Giorgetti, Pierre-Alain Masson. Non-locality and Entanglement Detection with Mermin polynomials for Grover's algorithm and Quantum Fourier Transform. Colloquium of the CNRS GDR N° 3322 on Quantum Engineering, Foundations & Applications Ingénierie Quantique, des aspects Fondamentaux aux Applications, Dec 2020, Online (Electronic Conference), France. hal-03221845

HAL Id: hal-03221845

https://hal.science/hal-03221845

Submitted on 10 May 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# NON-LOCALITY AND ENTANGLEMENT DETECTION WITH MERMIN POLYNOMIALS FOR GROVER'S ALGORITHM AND QUANTUM FOURIER TRANSFORM

Henri de Boutray, Hamza Jaffali, Frédéric Holweck, Alain Giorgetti & Pierre-Alain Masson

Institut FEMTO-ST, Université Bourgogne Franche-Comté, CNRS, Besançon, France
Laboratoire Interdisciplinaire Carnot de Bourgogne, CNRS, Besançon, France

## Grover's quantum algorithm

<figure><img src="image_2.png" /></figure>

* Search of an item $|\mathbf{x}_0\rangle$ in a list, based on an oracle

* Complexity: $O(\sqrt{2^n})$ (against $O(2^n)$ for classical search algorithms)

## Quantum Fourier Transform

<figure><img src="image_3.png" /></figure>

Generally performed on
periodic states defined by:
$|\varphi^{l,r}\rangle = \frac{1}{\sqrt{A}} \sum_{i=0}^{A-1} |l+ir\rangle$

* Quantum analogue of the discrete Fourier transform

* Complexity: $O(n^2)$ (against $O(n2^n)$)

## Mermin's polynomials

$$
\left\{
\begin{array}{l}
M_1 = a_1 \\
\forall n \ge 2, M_n = \frac{1}{2} M_{n-1} \otimes (a_n + a'_n) + \frac{1}{2} M'_{n-1} \otimes (a_n - a'_n) \\
(a_i) \text{ and } (a'_i) \text{ are one-qubit observables with eigenvalues in } \{-1, 1\}
\end{array}
\right.
$$

$\langle\varphi|M_n|\varphi\rangle > 1$ implies that $|\varphi\rangle$ is non-local.

Example:

With $(a_1, a_2, a'_1, a'_2) = (Z, X, (Z+X)/\sqrt{2}, (Z-X)/\sqrt{2})$,
$M_2$ corresponds to the operator used for Bell inequalities.

## Grover's algorithm evaluation

**Proposition ([JH19]):**

* The states in Grover's algorithm are $|\varphi_k\rangle = \alpha_k |\mathbf{x}_0\rangle + \beta_k |+\rangle^{\otimes n}$, with $(\alpha_0, \beta_0) = (0, 1)$ and $(\alpha_{k_{opt}}, \beta_{k_{opt}}) \approx (1, 0)$.

* For $k$ close to $k_{opt}/2$, $|\varphi_k\rangle$ comes close to a state $|\varphi_{ent}\rangle = (|\mathbf{x}_0\rangle + |+\rangle^{\otimes n})/K$ maximizing $\langle\varphi|M_n|\varphi\rangle$.

Evaluation method: find $M_n$ such that $\langle\varphi_{ent}|M_n|\varphi_{ent}\rangle$ is maximal.

Computing $\langle\varphi_k|M_n|\varphi_k\rangle$ for every $k$ with this $M_n$ **positively** answers the following question:

"Is Grover's algorithm using entanglement to achieve quantum speedup?".

<figure><img src="image_4.png" /></figure>

## QFT evaluation

$q: |\varphi\rangle \mapsto \max_{M_n} \langle\varphi|M_n|\varphi\rangle$ is a measure of entanglement.

Evaluation method: for each state $|\varphi_k\rangle$, find $\tilde{M}_n$ such that $\langle\varphi_k|\tilde{M}_n|\varphi_k\rangle$ is maximal.

The corresponding experimental approximation $\tilde{q}$ of $q$ allows us to distinguish between three types of QFT runs in our experiments with $n = 4$:

<figure><img src="image_5.png" /></figure>

Separable states (here for $(l, r) = (8, 5)$).
One can also check some key points such as the fact that entanglement evaluation doesn't change during LOCC operations ($H$ gates in this case).

## References

[dJH+20] H. de Boutray, H. Jaffali, F. Holweck, A. Giorgetti, and P.-A. Masson. Non-locality and Entanglement Detection with Mermin polynomials for Grover's algorithm and Quantum Fourier Transform. *Submitted in September 2020*, previous version at arXiv:2001.05192.

[JH19] H. Jaffali and F. Holweck. Quantum Entanglement involved in Grover's and Shor's algorithms: The four-qubit case. *Quantum Information Processing*, 18(5):133, May 2019.