Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.23716 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911087837839360 |
|---|---|
| author | Tulsi, Avatar |
| author_facet | Tulsi, Avatar |
| contents | Quantum Phase Estimation (QPE) has potential for a scientific revolution through numerous practical applications like finding better medicines, batteries, materials, catalysts etc. Many QPE algorithms use the Hadamard test to estimate $\langle ψ|U^{k}|ψ\rangle$ for a large integer $k$ for an efficiently preparable initial state $|ψ\rangle$ and an efficiently implementable unitary operator $U$. The Hadamard test is hard to implement because it requires controlled applications of $U^{k}$. Recently, a Sequential Hadamard test (SHT) was proposed (arXiv:2506.18765) which requires controlled application of $U$ only but its total run time $T_{\rm tot}$ scales as $\mathcal{O}(k^{3}/ε^{2}r_{\rm min}^{2})$ where $r_{\rm min}$ is the minimum value of $|\langle ψ|U^{k'}|ψ\rangle|$ among all integers $k' \leq k$. Typically $r_{\rm min}$ is exponentially low and SHT becomes too slow. We present a new algorithm, the SANDWICH test to address this bottleneck. Our algorithm uses efficient preparation of the initial state $|ψ\rangle$ to efficiently implement the SPROTIS operator $R_ψ^ϕ$ where SPROTIS stands for the Selective Phase Rotation of the Initial State. It sandwiches the SPROTIS operator between $U^{a}$ and $U^{b}$ for integers $\{a,b\} \leq k$ to estimate $\langle ψ|U^{k}|ψ\rangle$. The total run time $T_{\rm tot}$ is $\mathcal{O}(k^{2}\ln k/ ε^{2} s_{\rm min}^{6})$. Here $s_{\rm min}$ is the minimum value of $|\langle ψ|U^{\hat{k}}|ψ\rangle$ among all integers $\hat{k}$ which are values of the nodes of a random binary sum tree whose root node value is $k$ and leaf nodes' values are $1$ or $0$. It can be reasonably expected that $s_{\rm min} \not\ll 1$ in typical cases because there is wide freedom in choosing the random binary sum tree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_23716 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sandwich test for Quantum Phase Estimation Tulsi, Avatar Quantum Physics Quantum Phase Estimation (QPE) has potential for a scientific revolution through numerous practical applications like finding better medicines, batteries, materials, catalysts etc. Many QPE algorithms use the Hadamard test to estimate $\langle ψ|U^{k}|ψ\rangle$ for a large integer $k$ for an efficiently preparable initial state $|ψ\rangle$ and an efficiently implementable unitary operator $U$. The Hadamard test is hard to implement because it requires controlled applications of $U^{k}$. Recently, a Sequential Hadamard test (SHT) was proposed (arXiv:2506.18765) which requires controlled application of $U$ only but its total run time $T_{\rm tot}$ scales as $\mathcal{O}(k^{3}/ε^{2}r_{\rm min}^{2})$ where $r_{\rm min}$ is the minimum value of $|\langle ψ|U^{k'}|ψ\rangle|$ among all integers $k' \leq k$. Typically $r_{\rm min}$ is exponentially low and SHT becomes too slow. We present a new algorithm, the SANDWICH test to address this bottleneck. Our algorithm uses efficient preparation of the initial state $|ψ\rangle$ to efficiently implement the SPROTIS operator $R_ψ^ϕ$ where SPROTIS stands for the Selective Phase Rotation of the Initial State. It sandwiches the SPROTIS operator between $U^{a}$ and $U^{b}$ for integers $\{a,b\} \leq k$ to estimate $\langle ψ|U^{k}|ψ\rangle$. The total run time $T_{\rm tot}$ is $\mathcal{O}(k^{2}\ln k/ ε^{2} s_{\rm min}^{6})$. Here $s_{\rm min}$ is the minimum value of $|\langle ψ|U^{\hat{k}}|ψ\rangle$ among all integers $\hat{k}$ which are values of the nodes of a random binary sum tree whose root node value is $k$ and leaf nodes' values are $1$ or $0$. It can be reasonably expected that $s_{\rm min} \not\ll 1$ in typical cases because there is wide freedom in choosing the random binary sum tree. |
| title | Sandwich test for Quantum Phase Estimation |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2507.23716 |