Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad
We consider classical and quantum algorithms which have a duality property: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random. This enables one to give guarantees that the algorithm will find such a...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2019-11-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2019-11-11-201/pdf/ |