dorsal/arxiv
View SchemaA Quantum Observable for the Graph Isomorphism Problem
| Authors | Mark Ettinger, Peter Hoyer |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9901029 |
| URL | https://arxiv.org/abs/quant-ph/9901029 |
Abstract
Suppose we are given two graphs on $n$ vertices. We define an observable in the Hilbert space $\Co[(S_n \wr S_2)^m]$ which returns the answer ``yes'' with certainty if the graphs are isomorphic and ``no'' with probability at least $1-n!/2^m$ if the graphs are not isomorphic. We do not know if this observable is efficiently implementable.
{
"annotation_id": "279ab860-7af4-4dc4-a695-e2ec0a6cfe79",
"date_created": "2026-03-02T18:02:44.836000Z",
"date_modified": "2026-03-02T18:02:44.836000Z",
"file_hash": "87b0e3e63d1ab915f37bef95da4640d290fdd238b93c79ee7a9e22f583d86445",
"private": false,
"record": {
"abstract": "Suppose we are given two graphs on $n$ vertices. We define an observable in\nthe Hilbert space $\\Co[(S_n \\wr S_2)^m]$ which returns the answer ``yes\u0027\u0027 with\ncertainty if the graphs are isomorphic and ``no\u0027\u0027 with probability at least\n$1-n!/2^m$ if the graphs are not isomorphic. We do not know if this observable\nis efficiently implementable.",
"arxiv_id": "quant-ph/9901029",
"authors": [
"Mark Ettinger",
"Peter Hoyer"
],
"categories": [
"quant-ph"
],
"title": "A Quantum Observable for the Graph Isomorphism Problem",
"url": "https://arxiv.org/abs/quant-ph/9901029"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "2d213086-66de-4c8d-a818-61226509a166",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}