Limitations of quantum coset states for graph isomorphism

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

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

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 algorithmsquantum computationgraph isomorphismhidden subgroup problem

Mathematics Subject Classification ID

Quantum computation (81P68) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Quantum measurement theory, state operations, state preparations (81P15) 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 (13)

Quantum Fourier transform over symmetric groups -- improved result ⋮ Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm ⋮ Practical post-quantum signature schemes from isomorphism problems of trilinear forms ⋮ Quantum game players can have advantage without discord ⋮ General linear group action on tensors: a candidate for post-quantum cryptography ⋮ On the Complexity of the Hidden Subgroup Problem ⋮ Computational indistinguishability between quantum states and its cryptographic application ⋮ Algebraic Methods in Quantum Informatics ⋮ Quantum algorithm design: techniques and applications ⋮ Permutation groups, minimal degrees and quantum computing. ⋮ FJQuantum. A quantum object oriented language ⋮ Leveraging the hardness of dihedral coset problem for quantum cryptography ⋮ Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts

This page was built for publication: Limitations of quantum coset states for graph isomorphism