1
$\begingroup$

In general or in specific examples, how is the group used in an instance of the hidden subgroup problem embedded into a complex Hilbert space in order to apply the quantum fourier transform needed to solve the problem efficiently?

In quantum computing we imagine qubits as unit vectors in a complex Hilbert space $\mathbb{C}^{2^n}$ where $n$ is the number of bits in the system.

I've thought about this myself and come up with the idea that we can decompose a group into a product of cyclic groups, which can then be embedded as "rings" around the unit n-sphere in $\mathbb{C}^{2^n}$, where each cyclic group gets its own ring about a plane, but im not sure if this is the "usual" way this is done.

$\endgroup$
4
  • $\begingroup$ If there is a nexus of your Question with the subject of cryptography, it would improve your post to include a sketch of that context. Perhaps you have in mind (for finite abelian groups) the use of Schor's algorithm for factoring with quantum computers? Cf. here. $\endgroup$
    – hardmath
    Jun 8, 2023 at 16:05
  • $\begingroup$ Or, is it about the details of how Schor's algorithm works (when you view it as an operation within the complex Hilbert space)? $\endgroup$
    – poncho
    Jun 8, 2023 at 16:30
  • $\begingroup$ @hardmath I'm studying the hidden subgroup problem in general, but i guess a particular example that would be enlightening would be how we can apply QFT to efficiently solve the discrete log problem? $\endgroup$
    – kipawaa
    Jun 9, 2023 at 1:27
  • $\begingroup$ Note also that sister site Theoretical Computer Science has a fair number of posts concerning the hidden subgroup problem and its applications to complexity. $\endgroup$
    – hardmath
    Jun 9, 2023 at 13:39

1 Answer 1

1
$\begingroup$

The task of embedding a group in a vector space is the realm of (group) "Representation theory". Roughly speaking, you want to produce maps

$$\rho: G\to \mathsf{End}(V)$$ that behave well with respect to the group operations, i.e. $$\rho(\mathsf{id}_G) = \mathsf{id}_V, \rho(gg') = \rho(g)\rho(g'), \rho(g^{-1}) = \rho(g)^{-1}.$$

Here, $\mathsf{End}(V)$ is the group of endomorphisms of $V$, or equivalently for $\dim V = n$ it is $k^{n\times n}$, viewed as a group of matrices.

Representation theory then allows one to decompose a representation into a direct sum of "easy" representations (these are typically called "semi-simple" iirc). For abelian groups these semi-simple representations are all one-dimensional. From the right perspective they are "cyclic groups". The study of these types of representations typically goes by the name of "character theory", and roughly corresponds to your idea.

For non-abelian groups things get more complex. The general group-theoretic Fourier transform all of this theory implies (see here) breaks down. Namely, one cannot always break a representation down into its "cyclic components".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.