Quantum algorithms for graph connectivity and formula evaluation
We give a new upper bound on the quantum query complexity of deciding $st$-connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of gr...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2017-08-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2017-08-17-26/pdf/ |