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!
|
Table of 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.