Hypercube quantum search: exact computation of the probability of success in polynomial time
Open Access
- 15 March 2023
- journal article
- research article
- Published by Springer Nature in Quantum Information Processing
- Vol. 22 (3) , 1-46
Abstract
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.Keywords
All Related Versions
Funding Information
- Université de Bretagne Occidentale
This publication has 6 references indexed in Scilit:
- Shuffling matrices, Kronecker product and Discrete Fourier TransformDiscrete Applied Mathematics, 2017
- Quantum walks: a comprehensive reviewQuantum Information Processing, 2012
- Quantum random-walk search algorithmPhysical Review A, 2003
- Quantum Walks on the Hypercube2002
- Quantum walks on graphs2001
- A fast quantum mechanical algorithm for database search1996