dorsal/arxiv
View SchemaOn the Quantum Query Complexity of Detecting Triangles in Graphs
| Authors | Mario Szegedy |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0310107 |
| URL | https://arxiv.org/abs/quant-ph/0310107 |
Abstract
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}})$.
{
"annotation_id": "aa388b75-aa2d-4f4b-9b96-b0282974cab6",
"date_created": "2026-03-02T18:02:03.351000Z",
"date_modified": "2026-03-02T18:02:03.351000Z",
"file_hash": "5fa8da3b66c6236df67e5c921015481b3142103529bc07c39d5757874ff09df0",
"private": false,
"record": {
"abstract": "We show that in the quantum query model the complexity of detecting a\ntriangle in an undirected graph on $n$ nodes can be done using $O(n^{1+{3\\over\n7}}\\log^{2}n)$ quantum queries. The same complexity bound applies for\noutputting the triangle if there is any. This improves upon the earlier bound\nof $O(n^{1+{1\\over 2}})$.",
"arxiv_id": "quant-ph/0310107",
"authors": [
"Mario Szegedy"
],
"categories": [
"quant-ph"
],
"title": "On the Quantum Query Complexity of Detecting Triangles in Graphs",
"url": "https://arxiv.org/abs/quant-ph/0310107"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "57ca6235-8278-4f58-91e1-725c186a30ff",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}