Limitations of quantum coset states for graph isomorphism

DOI10.1145/1132516.1132603zbMath1301.68130arXivquant-ph/0511148MaRDI QIDQ5891930

Moore, Cristopher, Alexander Russell, Martin Roetteler, Pranab Sen, Sean Hallgren

Publication date: 25 November 2014

Published in: Journal of the ACM, Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0511148

zbMATH Keywords

quantum algorithms; quantum computation; graph isomorphism; hidden subgroup problem

Mathematics Subject Classification ID

81P68: Quantum computation

05C25: Graphs and abstract algebra (groups, rings, fields, etc.)

81P15: Quantum measurement theory, state operations, state preparations

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

68Q12: Quantum algorithms and complexity in the theory of computing