Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
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_ | 1866909645359022080 |
|---|---|
| author | Singkanipa, P. Kasatkin, V. Zhou, Z. Quiroz, G. Lidar, D. A. |
| author_facet | Singkanipa, P. Kasatkin, V. Zhou, Z. Quiroz, G. Lidar, D. A. |
| contents | Simon's problem is to find a hidden period (a bitstring) encoded into an unknown 2-to-1 function. It is one of the earliest problems for which an exponential quantum speedup was proven for ideal, noiseless quantum computers, albeit in the oracle model. Here, using two different 127-qubit IBM Quantum superconducting processors, we demonstrate an algorithmic quantum speedup for a variant of Simon's problem where the hidden period has a restricted Hamming weight $w$. For sufficiently small values of $w$ and for circuits involving up to 58 qubits, we demonstrate an exponential speedup, albeit of a lower quality than the speedup predicted for the noiseless algorithm. The speedup exponent and the range of $w$ values for which an exponential speedup exists are significantly enhanced when the computation is protected by dynamical decoupling. Further enhancement is achieved with measurement error mitigation. This constitutes a demonstration of a bona fide quantum advantage for an Abelian hidden subgroup problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_07934 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem Singkanipa, P. Kasatkin, V. Zhou, Z. Quiroz, G. Lidar, D. A. Quantum Physics Simon's problem is to find a hidden period (a bitstring) encoded into an unknown 2-to-1 function. It is one of the earliest problems for which an exponential quantum speedup was proven for ideal, noiseless quantum computers, albeit in the oracle model. Here, using two different 127-qubit IBM Quantum superconducting processors, we demonstrate an algorithmic quantum speedup for a variant of Simon's problem where the hidden period has a restricted Hamming weight $w$. For sufficiently small values of $w$ and for circuits involving up to 58 qubits, we demonstrate an exponential speedup, albeit of a lower quality than the speedup predicted for the noiseless algorithm. The speedup exponent and the range of $w$ values for which an exponential speedup exists are significantly enhanced when the computation is protected by dynamical decoupling. Further enhancement is achieved with measurement error mitigation. This constitutes a demonstration of a bona fide quantum advantage for an Abelian hidden subgroup problem. |
| title | Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2401.07934 |