On the Quantum Query Complexity of Detecting Triangles in Graphs
| dc.creator | Szegedy, Mario | |
| dc.date | 2003-10-16 | |
| dc.date | 2003-11-06 | |
| dc.date.accessioned | 2026-07-07T06:08:07Z | |
| dc.date.available | 2026-07-07T06:08:07Z | |
| dc.description | We show that in the quantum query model the complexity of detecting a triangle in an undirected graph on $n$ nodes can be done using $O(n^{1+{3\over 7}}\log^{2}n)$ quantum queries. The same complexity bound applies for outputting the triangle if there is any. This improves upon the earlier bound of $O(n^{1+{1\over 2}})$. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0310107 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0310107 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/91519 | |
| dc.subject | Quantum Physics | |
| dc.title | On the Quantum Query Complexity of Detecting Triangles in Graphs | |
| dc.type | text |