On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism

DOI10.1137/080724101zbMATH Open1219.68104OpenAlexW1966401204MaRDI QIDQ3068637FDOQ3068637

Alexander Russell, Cristopher Moore, 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

quantum algorithmgraph isomorphismquantum computingrepresentation theorysymmetric group

Mathematics Subject Classification ID

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

Cited In (4)

• Quantum computation vs. firewalls
• Limitations of quantum coset states for graph isomorphism
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• The independence of reduced subgroup-state

Recommendations

• A classical approach to the graph isomorphism problem using quantum walks 👍 👎
• Automata, Languages and Programming 👍 👎
• Quantum Query Complexity of Some Graph Problems 👍 👎
• SOFSEM 2004: Theory and Practice of Computer Science 👍 👎
• Limitations of quantum coset states for graph isomorphism 👍 👎
• Quantum and non-signalling graph isomorphisms 👍 👎
• A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems 👍 👎
• Quantum time complexity and algorithms for pattern matching on labeled graphs 👍 👎
• Quantum Query Complexity of Subgraph Isomorphism and Homomorphism 👍 👎

This page was built for publication: On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068637)