Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.00567 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915042355576832 |
|---|---|
| author | Rotello, Caleb |
| author_facet | Rotello, Caleb |
| contents | Quantum amplitude amplification and estimation have shown quadratic speedups to unstructured search and estimation tasks. We show that a coherent combination of these quantum algorithms also provides a quadratic speedup to calculating the expectation value of a random-exist quantified oracle. In this problem, Nature makes a decision randomly, i.e. chooses a bitstring according to some probability distribution, and a player has a chance to react by finding a complementary bitstring such that an black-box oracle evaluates to $1$ (or True). Our task is to approximate the probability that the player has a valid reaction to Nature's initial decision. We compare the quantum algorithm to the average-case performance of Monte-Carlo integration over brute-force search, which is, under reasonable assumptions, the best performing classical algorithm. We find the performance separation depends on some problem parameters, and show a regime where the canonical quadratic speedup exists. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_00567 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum algorithm for approximating the expected value of a random-exist quantified oracle Rotello, Caleb Quantum Physics Data Structures and Algorithms Quantum amplitude amplification and estimation have shown quadratic speedups to unstructured search and estimation tasks. We show that a coherent combination of these quantum algorithms also provides a quadratic speedup to calculating the expectation value of a random-exist quantified oracle. In this problem, Nature makes a decision randomly, i.e. chooses a bitstring according to some probability distribution, and a player has a chance to react by finding a complementary bitstring such that an black-box oracle evaluates to $1$ (or True). Our task is to approximate the probability that the player has a valid reaction to Nature's initial decision. We compare the quantum algorithm to the average-case performance of Monte-Carlo integration over brute-force search, which is, under reasonable assumptions, the best performing classical algorithm. We find the performance separation depends on some problem parameters, and show a regime where the canonical quadratic speedup exists. |
| title | Quantum algorithm for approximating the expected value of a random-exist quantified oracle |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.00567 |