Multi-self-loop Lackadaisical Quantum Walk with Partial Phase Inversion
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929593980551168 |
|---|---|
| author | de Souza, Luciano S. de Carvalho, Jonathan H. A. Santos, Henrique C. T. Ferreira, Tiago A. E. |
| author_facet | de Souza, Luciano S. de Carvalho, Jonathan H. A. Santos, Henrique C. T. Ferreira, Tiago A. E. |
| contents | The lackadaisical quantum walk, a quantum analog of the lazy random walk, is obtained by adding a weighted self-loop transition to each state. Impacts of the self-loop weight $l$ on the final success probability in finding a solution make it a key parameter for the search process. The number of self-loops can also be critical for search tasks. This article proposes the quantum search algorithm Multi-self-loop Lackadaisical Quantum Walk with Partial Phase Inversion, which can be defined as a lackadaisical quantum walk with multiple self-loops, where the target state phase is partially inverted. In the proposed algorithm, each vertex has $m$ self-loops, with weights $l' = l/m$, where $l$ is a real parameter. The phase inversion is based on Grover's algorithm and acts partially, modifying the phase of a given quantity $s < m$ of self-loops. On a hypercube structure, we analyzed the situation where $1 \leqslant m \leqslant 30$. We also propose two new weight values based on two ideal weights $l$ used in the literature. We investigated the effects of partial phase inversion in the search for $1$ to $12$ marked vertices. As a result, this proposal improved the maximum success probabilities to values close to $1$ in $O (\sqrt{(n+m)\cdot N})$, where $n$ is the hypercube degree. This article contributes with a new perspective on the use of quantum interferences in constructing new quantum search algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_01121 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Multi-self-loop Lackadaisical Quantum Walk with Partial Phase Inversion de Souza, Luciano S. de Carvalho, Jonathan H. A. Santos, Henrique C. T. Ferreira, Tiago A. E. Quantum Physics The lackadaisical quantum walk, a quantum analog of the lazy random walk, is obtained by adding a weighted self-loop transition to each state. Impacts of the self-loop weight $l$ on the final success probability in finding a solution make it a key parameter for the search process. The number of self-loops can also be critical for search tasks. This article proposes the quantum search algorithm Multi-self-loop Lackadaisical Quantum Walk with Partial Phase Inversion, which can be defined as a lackadaisical quantum walk with multiple self-loops, where the target state phase is partially inverted. In the proposed algorithm, each vertex has $m$ self-loops, with weights $l' = l/m$, where $l$ is a real parameter. The phase inversion is based on Grover's algorithm and acts partially, modifying the phase of a given quantity $s < m$ of self-loops. On a hypercube structure, we analyzed the situation where $1 \leqslant m \leqslant 30$. We also propose two new weight values based on two ideal weights $l$ used in the literature. We investigated the effects of partial phase inversion in the search for $1$ to $12$ marked vertices. As a result, this proposal improved the maximum success probabilities to values close to $1$ in $O (\sqrt{(n+m)\cdot N})$, where $n$ is the hypercube degree. This article contributes with a new perspective on the use of quantum interferences in constructing new quantum search algorithms. |
| title | Multi-self-loop Lackadaisical Quantum Walk with Partial Phase Inversion |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2305.01121 |