In this article, we propose a new strategy to exploit Grover's algorithm for unstructured search problems. We first show that running Grover's routine with a reduced number of iterations but allowing several trials presents a complexity advantage while keeping the same success probability. Then, by a theoretical analysis of the performance, we provide a generic procedure to parameterize the number of iterations $k$ within one shot of Grover's algorithm and the maximum number of trials $T$ , given a targeted success $p$ and the size of the database $N$ . At the end, we highlight that this new approach permits to reduce the computational time by at least 10% for $p \geq 0.999$ independently of the size of the database.In this article, we propose a new strategy to exploit Grover's algorithm for unstructured search problems. We first show that running Grover's routine with a reduced number of iterations but allowing several trials presents a complexity advantage while keeping the same success probability. Then, by a theoretical analysis of the performance, we provide a generic procedure to parameterize the number of iterations$k$within one shot of Grover's algorithm and the maximum number of trials$T$, given a targeted success$p$and the size of the database$N$. At the end, we highlight that this new approach permits to reduce the computational time by at least 10% for$p \geq 0.999$independently of the size of the database.

IEEE Transactions on Quantum EngineeringJan 1, 20254 citations

A SURVEY OF GROVER'S ALGORITHM AND ITS MODIFICATIONS FOR EFFICIENT UNSTRUCTURED SEARCH

Iram Fatima,Syed Khaldoon Khurshid,Fareed Ud Din Mehmood Jafri,Sanam Shoukat,Haroon Bashir

Mar 31, 20260 citations

Time Complexity of the Oracle Phase in Grover’s Algorithm

Ying Liu

Since Grover’s algorithm was first introduced, it has become a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The original application was the unstructured search problems with the time complexity of O(). In Grover’s algorithm, the key is Oracle and Amplitude Amplification. In this paper, our purpose is to show through examples that, in general, the time complexity of the Oracle Phase is O(N), not O(1). As a result, the time complexity of Grover’s algorithm is O(N), not O(). As a secondary purpose, we also attempt to restore the time complexity of Grover’s algorithm to its original form, O(), by introducing an O(1) parallel algorithm for unstructured search without repeated items, which will work for most cases. In the worst-case scenarios where the number of repeated items is O(N), the time complexity of the Oracle Phase is still O(N) even after additional preprocessing.Since Grover’s algorithm was first introduced, it has become a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The original application was the unstructured search problems with the time complexity of O(). In Grover’s algorithm, the key is Oracle and Amplitude Amplification. In this paper, our purpose is to show through examples that, in general, the time complexity of the Oracle Phase is O(N), not O(1). As a result, the time complexity of Grover’s algorithm is O(N), not O(). As a secondary purpose, we also attempt to restore the time complexity of Grover’s algorithm to its original form, O(), by introducing an O(1) parallel algorithm for unstructured search without repeated items, which will work for most cases. In the worst-case scenarios where the number of repeated items is O(N), the time complexity of the Oracle Phase is still O(N) even after additional preprocessing.

American Journal of Computational MathematicsJan 1, 20242 citations

Grover’s Search Algorithm

Mika Hirvensalo

Springer eBooksJan 1, 20010 citations

Grover’s Search Algorithm

Taylor & Francis eBooksMar 11, 20081 citation

基于改进Grover算法的ECC扫描式攻击

Yuchen He, Yulong Fu, Zeyang Zhang +2 more

Scan-based attacks represent a category of side-channel attacks that pose potential risks to elliptic curve cryptosystems. A critical computational element in such attacks is the unstructured search of the scan data. The Grover algorithm, a quantum algorithm for the unstructured search, achieves quadratic speedup over classical methods, making it a promising tool for enhancing scan-based attacks in the quantum context. In this paper, we propose two methods to improve the Grover algorithm used in the ECC scan-based attack. These methods reduce the depth of the quantum circuit by over 85% compared with the Grover-Long algorithm, thus improving the feasibility of the Grover algorithm in scan-based attacks in the noisy intermediate-scale quantum (NISQ) era.Scan-based attacks represent a category of side-channel attacks that pose potential risks to elliptic curve cryptosystems. A critical computational element in such attacks is the unstructured search of the scan data. The Grover algorithm, a quantum algorithm for the unstructured search, achieves quadratic speedup over classical methods, making it a promising tool for enhancing scan-based attacks in the quantum context. In this paper, we propose two methods to improve the Grover algorithm used in the ECC scan-based attack. These methods reduce the depth of the quantum circuit by over 85% compared with the Grover-Long algorithm, thus improving the feasibility of the Grover algorithm in scan-based attacks in the noisy intermediate-scale quantum (NISQ) era.

Zhongguo kexue. Wulixue Lixue TianwenxueNov 1, 20240 citations

k

within one shot of Grover's algorithm and the maximum number of trials

T

, given a targeted success

p

and the size of the database

N

. At the end, we highlight that this new approach permits to reduce the computational time by at least 10% for

p \geq 0.999

independently of the size of the database.