Phase diagram for the Grover algorithm with static imperfections

A. A. Pomeransky; O. V. Zhirov; D. L. Shepelyansky

doi:10.1140/epjd/e2004-00113-4

EPJ

a
b
c
d
e
ap
st
h
plus
ds
pv
ti
qt
am
n

2023 Impact factor 1.5

Atomic, Molecular, Optical and Plasma Physics

Eur. Phys. J. D 31, 131-135 (2004)
https://doi.org/10.1140/epjd/e2004-00113-4

Phase diagram for the Grover algorithm with static imperfections

A. A. Pomeransky¹, O. V. Zhirov² and D. L. Shepelyansky¹^a

¹ Laboratoire de Physique Théorique, UMR 5152 du CNRS, Université P. Sabatier, 31062 Toulouse Cedex 4, France
² Budker Institute of Nuclear Physics, 630090 Novosibirsk, Russia

Corresponding author: ^a dima@irsamc.ups-tlse.fr

Received: 3 May 2004
Revised: 1 July 2004
Published online: 31 August 2004

Abstract

We study effects of static inter-qubit interactions on the stability of the Grover quantum search algorithm. Our numerical and analytical results show existence of regular and chaotic phases depending on the imperfection strength ε. The critical border $\varepsilon_c$ between two phases drops polynomially with the number of qubits n_q as $\varepsilon_c \sim n_q^{-3/2}$ . In the regular phase $(\varepsilon < \varepsilon_c)$ the algorithm remains robust against imperfections showing the efficiency gain $\varepsilon_c / \varepsilon$ for $\varepsilon \gtrsim 2^{-n_q/2}$ . In the chaotic phase $(\varepsilon > \varepsilon_c)$ the algorithm is completely destroyed.