A Quantum Observable for the Graph Isomorphism Problem

Simple item page
dc.creatorEttinger, Mark
dc.creatorHoyer, Peter
dc.date1999-01-13
dc.date.accessioned2026-07-07T06:16:02Z
dc.date.available2026-07-07T06:16:02Z
dc.descriptionSuppose 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.
dc.description5 pages, no figures
dc.identifierhttps://arxiv.org/abs/quant-ph/9901029
dc.identifierhttp://arxiv.org/abs/quant-ph/9901029
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/93941
dc.subjectQuantum Physics
dc.titleA Quantum Observable for the Graph Isomorphism Problem
dc.typetext

Files

Collections

arXiv