On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism

DOI10.1137/080724101zbMath1219.68104OpenAlexW1966401204MaRDI QIDQ3068637

Alexander Russell, Moore, Cristopher, Piotr Śniady

Publication date: 17 January 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080724101

zbMATH Keywords

symmetric grouprepresentation theoryquantum algorithmquantum computinggraph isomorphism

Mathematics Subject Classification ID

Representations of finite symmetric groups (20C30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Quantum computation vs. firewalls ⋮ The independence of reduced subgroup-state