On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
DOI10.1137/080724101zbMATH Open1219.68104OpenAlexW1966401204MaRDI QIDQ3068637FDOQ3068637
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
Recommendations
- Quantum Query Complexity of Some Graph Problems
- Automata, Languages and Programming
- Limitations of quantum coset states for graph isomorphism
- Limitations of quantum coset states for graph isomorphism
- 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
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 (5)
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)
