Quantum Fourier Sampling is Guaranteed to Fail to Compute Automorphism Groups of Easy Graphs

Abstract

The quantum hidden subgroup approach is an actively studied approach to solve combinatorial problems in quantum complexity theory. With the success of the Shor's algorithm, it was hoped that similar approach may be useful to solve the other combinatorial problems. One such problem is the graph isomorphism problem which has survived decades of efforts using the hidden subgroup approach. This paper provides a systematic approach to create arbitrarily large classes of classically efficiently solvable graph automorphism problems or easy graph automorphism problems for which hidden subgroup approach is guaranteed to always fail irrespective of the size of the graphs no matter how many copies of coset states are used. As the graph isomorphism problem is believed to be at least as hard as the graph automorphism problem, the result of this paper entails that the hidden subgroup approach is also guaranteed to always fail for the arbitrarily large classes of graph isomorphism problems. Combining these two results, it is argued that the hidden subgroup approach is essentially a dead end and alternative quantum algorithmic approach needs to be investigated for the graph isomorphism and automorphism problems.

arXiv comment54 pages

References in corpus (7)

• Graph Isomorphism in Quasipolynomial Time
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
• The quantum query complexity of the hidden subgroup problem is polynomial
• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups
• On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
• Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)
• Automorphism groups of graphs