Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing
- Publisher:
- Springer
- Publication Type:
- Journal Article
- Citation:
- Algorithmica: an international journal in computer science, 2017, 77, (2), pp. 459-486
- Issue Date:
- 2017-02-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Lee2017_Article_ImprovedQuantumQueryAlgorithms.pdf | 737.87 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is O(n9 / 7). This improves the previous best algorithm of Belovs (Proceedings of 44th symposium on theory of computing conference, pp 77–84, 2012) making O(n35 / 27) queries. For the problem of determining if an operation ∘ : S× S→ S is associative, we give an algorithm making O(| S| 10 / 7) queries, the first improvement to the trivial O(| S| 3 / 2) application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm.
Please use this identifier to cite or link to this item: