Motivation
The Hidden Subgroup Problem is especially important in the theory of quantum computing for the following reasons.
- Shor's quantum algorithm for factoring and discrete logarithm (as well as several of its extensions) relies on the ability of quantum computers to solve the HSP for finite Abelian groups.
- The existence of efficient quantum algorithms for HSPs for certain non-Abelian groups would imply efficient quantum algorithms for two major problems: the graph isomorphism problem and certain shortest vector problems (SVPs) in lattices. More precisely, an efficient quantum algorithm for the HSP for the symmetric group would give a quantum algorithm for the graph isomorphism. An efficient quantum algorithm for the HSP for the dihedral group would give a quantum algorithm for the poly(n) unique SVP.
Read more about this topic: Hidden Subgroup Problem
Famous quotes containing the word motivation:
“Self-determination has to mean that the leader is your individual gut, and heart, and mind or we’re talking about power, again, and its rather well-known impurities. Who is really going to care whether you live or die and who is going to know the most intimate motivation for your laughter and your tears is the only person to be trusted to speak for you and to decide what you will or will not do.”
—June Jordan (b. 1939)