Beyond Worst-Case Branching: Quantum Tree Search via Amplitude Amplification
In this work, we investigate quantum tree search via amplitude amplification. Amplitude amplification generalizes Grover's algorithm by replacing the Hadamard initialization with an arbitrary unitary $A$, with Grover's algorithm recovered as the special case of uniform initialization. We demonstrate the construction of a dynamic search tree of depth $m$ with query complexity $\sqrt{\left(b_{avg}\right)^m}$ where $b_{avg}$ denotes the average branching factor, improving upon the commonly assumed $\sqrt{\left(b_{max}\right)^m}$, where $b_{max}$ is the maximum branching factor. We further…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.28452
curl -X POST /api/v1/records/arxiv/2606.28452/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.28452/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'