On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism

DOI10.1137/080724101MaRDI QIDQ3068637zbMATH OpenOpenAlexFDO

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

Recommendations

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

Cited in

(4)

• Quantum computation vs. firewalls
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• A graph isomorphism algorithm using signatures computed via quantum walk search model
• The independence of reduced subgroup-state

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)