Improved Quantum Query Upper Bounds Based on Classical Decision Trees
Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up....
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2025-06-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2025-06-23-1777/pdf/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|