One-Query Quantum Algorithms for the Index-$q$ Hidden Subgroup Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910269809098752 |
|---|---|
| author | Te'eni, Amit Oz, Yaron Cohen, Eliahu |
| author_facet | Te'eni, Amit Oz, Yaron Cohen, Eliahu |
| contents | The quantum Fourier transform (QFT) is central to many quantum algorithms, yet its necessity is not always well understood. We re-examine its role in canonical query problems. The Deutsch-Jozsa algorithm requires neither a QFT nor a domain group structure. In contrast, the Bernstein-Vazirani problem is an instance of the hidden subgroup problem (HSP), where the hidden subgroup has either index $1$ or $2$, and the Bernstein-Vazirani algorithm exploits this promise to solve the problem with a single query. Motivated by these insights, we introduce the index-$q$ HSP: determine whether a hidden subgroup $H \le G$ has index $1$ or $q$, and, when possible, identify $H$. We present a single-query algorithm that always distinguishes index $1$ from $q$, for any choice of abelian structure on the oracle's codomain. Moreover, with suitable pre- and post-oracle unitaries (inverse-QFT/QFT over $G$), the same query exactly identifies $H$ under explicit minimal conditions: $G/H$ is cyclic of order $q$, and the output alphabet is equipped, up to affine relabeling, with a compatible $ \mathbb{Z} / q \mathbb{Z} $ structure. These conditions hold automatically for $q \in \left\{ 2,3 \right\} $, giving unconditional single-query identification in these cases. In contrast, the Shor-Kitaev sampling approach cannot guarantee exact recovery from a single sample. Our results sharpen the landscape of one-query quantum solvability for abelian HSPs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_10538 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | One-Query Quantum Algorithms for the Index-$q$ Hidden Subgroup Problem Te'eni, Amit Oz, Yaron Cohen, Eliahu Quantum Physics The quantum Fourier transform (QFT) is central to many quantum algorithms, yet its necessity is not always well understood. We re-examine its role in canonical query problems. The Deutsch-Jozsa algorithm requires neither a QFT nor a domain group structure. In contrast, the Bernstein-Vazirani problem is an instance of the hidden subgroup problem (HSP), where the hidden subgroup has either index $1$ or $2$, and the Bernstein-Vazirani algorithm exploits this promise to solve the problem with a single query. Motivated by these insights, we introduce the index-$q$ HSP: determine whether a hidden subgroup $H \le G$ has index $1$ or $q$, and, when possible, identify $H$. We present a single-query algorithm that always distinguishes index $1$ from $q$, for any choice of abelian structure on the oracle's codomain. Moreover, with suitable pre- and post-oracle unitaries (inverse-QFT/QFT over $G$), the same query exactly identifies $H$ under explicit minimal conditions: $G/H$ is cyclic of order $q$, and the output alphabet is equipped, up to affine relabeling, with a compatible $ \mathbb{Z} / q \mathbb{Z} $ structure. These conditions hold automatically for $q \in \left\{ 2,3 \right\} $, giving unconditional single-query identification in these cases. In contrast, the Shor-Kitaev sampling approach cannot guarantee exact recovery from a single sample. Our results sharpen the landscape of one-query quantum solvability for abelian HSPs. |
| title | One-Query Quantum Algorithms for the Index-$q$ Hidden Subgroup Problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2510.10538 |