MilestoneTheory & algorithmsConfirmed

Researchers show a standard quantum method fails for graph isomorphism

Jan 12, 2005

Cristopher Moore, Alexander Russell and Leonard Schulman show that strong Fourier sampling, the approach behind Shor's algorithm, cannot efficiently solve the hidden subgroup problem on the symmetric group, the case linked to telling whether two networks have the same shape.

Why it matters

It helps explain why no fast quantum algorithm for graph isomorphism is known: the technique that cracked factoring does not carry over directly.

Cristopher Moore · Alexander Russell · Leonard J. Schulman

See it on the timeline

Related

• Kuperberg finds a faster quantum attack on the dihedral hidden subgroup problem (Feb 14, 2003)
• Kitaev extends Shor's results with a method for measuring eigenvalues (Nov 20, 1995)
• Peter Shor shows a quantum computer could factor large numbers quickly (Nov 1994)