Hypercube quantum search: exact computation of the probability of success in polynomial time

Hugo Pillin (1, 2, 3, 4) , Gilles Burel (1, 2, 3) , Paul Baird (4, 3) , El Houssaïn Baghious (1, 2, 3) , Roland Gautier (2, 3, 1)

1 Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
2 Lab-STICC_SI3 - Equipe Security, Intelligence and Integrity of Information
3 UBO - Université de Brest
4 LMBA - Laboratoire de Mathématiques de Bretagne Atlantique

In the emerging domain of quantum algorithms, Grover’s quantum search is certainly one of the most significant. It is relatively simple, performs a useful task and more importantly, does it in an optimal way. However, due to the success of quantum walks in the field, it is logical to study quantum search variants over several kinds of walks. In this paper, we propose an in-depth study of the quantum search over a hypercube layout. First, through the analysis of elementary walk operators restricted to suitable eigenspaces, we show that the acting component of the search algorithm takes place in a small subspace of the Hilbert workspace that grows linearly with the problem size. Subsequently, we exploit this property to predict the exact evolution of the probability of success of the quantum search in polynomial time.

Mots clés: Quantum walk; Quantum algorithm; Quantum information

Domaines: Sciences de l'ingénieur [physics]; Mathématiques [math]

Hugo Pillin, Gilles Burel, Paul Baird, El Houssaïn Baghious, Roland Gautier. Hypercube quantum search: exact computation of the probability of success in polynomial time. Quantum Information Processing, 2023, 22 (3), pp.149. ⟨10.1007/s11128-023-03883-9⟩. ⟨hal-04031275⟩