Efficient Implementation of a Quantum Search Algorithm for Arbitrary N
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909637685542912 |
|---|---|
| author | Shukla, Alok Vedula, Prakash |
| author_facet | Shukla, Alok Vedula, Prakash |
| contents | This paper presents an enhancement to Grover's search algorithm for instances where the number of items (or the size of the search problem) $N$ is not a power of 2. By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases. For special cases (i.e., when $N$ is of the form such that it is slightly greater than an integer power of 2), the reduction in the number of oracle calls (and Grover's iterations) asymptotically approaches 29.33\%. This improvement is significant compared to the traditional Grover's algorithm, which handles such cases by rounding $N$ up to the nearest power of 2. The key to this improvement is our algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, which requires gate complexity and circuit depth of only $ O (\log_2 (N)) $, without using any ancilla qubits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13785 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Implementation of a Quantum Search Algorithm for Arbitrary N Shukla, Alok Vedula, Prakash Quantum Physics 81P68, 81P15, 81P45 This paper presents an enhancement to Grover's search algorithm for instances where the number of items (or the size of the search problem) $N$ is not a power of 2. By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases. For special cases (i.e., when $N$ is of the form such that it is slightly greater than an integer power of 2), the reduction in the number of oracle calls (and Grover's iterations) asymptotically approaches 29.33\%. This improvement is significant compared to the traditional Grover's algorithm, which handles such cases by rounding $N$ up to the nearest power of 2. The key to this improvement is our algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, which requires gate complexity and circuit depth of only $ O (\log_2 (N)) $, without using any ancilla qubits. |
| title | Efficient Implementation of a Quantum Search Algorithm for Arbitrary N |
| topic | Quantum Physics 81P68, 81P15, 81P45 |
| url | https://arxiv.org/abs/2406.13785 |