3
$\begingroup$

I am new to the concept of HSP. Previously, I saw how to solve hidden subgroup problem over $\mathbb{Z}_2^n$, which was Simon's algorithm. Over there the first step was to apply $H^{\otimes n}$, which was indeed the Fourier transform over $\mathbb{Z}_2^n$.

Now for any general finite abelian group, the course notes I have been following and in many other materials, the starting step is given as to form equal superposition over all the basis vectors i.e.,

$$\frac{1}{\sqrt{|G|}}\sum_{g\in G} | g,0\rangle$$

Here $G$ is the finite abelian group. The pair of register contains $|0,0\rangle$ at the beginning where the first register $|0\rangle$ means log$(|G|)$ qubits(Why?).

In case of Hadamard in Simon's algorithm it was easy to see this step, but in this case can anyone show me how do we get here? We have to apply Fourier transform I know, but the whole steps I am not getting.

$\endgroup$
5
  • 1
    $\begingroup$ For an Abelian group $G$ there are $|G|$ characters, therefore we can map each character to an integer $g$, thus in binary we need log(|G|) many bits to represent these integers. $\endgroup$
    – Sam Palmer
    Mar 26, 2021 at 13:59
  • $\begingroup$ @SamPalmer Do you know how this equal superposition comes? $\endgroup$ Mar 26, 2021 at 14:19
  • 1
    $\begingroup$ Are you asking how to prepare the uniform superposition over all elements of $G$, or are you asking why we prepare such a uniform superposition? For most groups we could just treat the first register as a bit string/integer and do a bunch of Hadamards; we would need to keep track of a mapping between bit strings/integers and elements of $G$. $\endgroup$ Mar 27, 2021 at 13:09
  • $\begingroup$ @MarkS"Are you asking how to prepare the uniform superposition over all elements of G"-This. So, this is just Hadamard over $\mathbb{Z}_2^n$? Does in case of any finite abelian group this holds? $\endgroup$ Mar 27, 2021 at 14:48
  • 1
    $\begingroup$ Yes, even for nonabelian groups. As you have some bijection between such bit strings and $g\in G$. $\endgroup$ Mar 27, 2021 at 15:33

1 Answer 1

2
$\begingroup$

With the Hidden Subgroup Problem, abelian or otherwise, we have a function $f$ from elements of $g\in G$ to an arbitrary set $X$, that is constant on cosets of $H\le G$ and is distinct on different cosets of $H$.

Conventionally and at a high level of abstraction, this function $f$ is described with an oracle that maps elements of $g\in G$ to elements $x\in X$. Elements $g\in G$ are described just as elements of $G$ (while elements $x\in X$ are often called colors as there may or may not be an ordering among elements of $X$).

However it can be convenient to think of $g$ as integers or bit-strings $\mathbb{Z}^n_2$, with $n=\log_2 \vert G\vert$. But then we will need to envision a bijection mapping $g$ (as abstract group elements) to/from integers/bit-strings in $\mathbb{Z}^n_2$ (as more concrete states of qubits on which we work).

One of the first steps in HSP algorithms is to prepare a first input register into the uniform superposition over all elements of $G$; later we evaluate our oracle $f$ on the second output register representing elements of $X$.

Hence once we can conceptualize the inputs $g$ as integers/bit-strings, this can be accomplished in a straightforward manner, by performing Hadamard transforms on the input qubits.

This works for nonabelian groups too. For example in the symmetric group $S_n$, elements $g\in S_n$ may be permutations $\pi$. So a first step would be to find a good bijection between integers in $[n!]$ and elements of $S_n$, that enables evaluation of an oracle $f$ into the second register. I believe (although I've not studied it too much) that there are many efficiently-evaluated bijections between integers in $[n!]$ and permutations $\pi\in S_n$.

$\endgroup$
3
  • $\begingroup$ every finite group cannot have a bijection from $\mathbb{Z}_2^n$ right? Take $\mathbb{Z}_10$ for example. How do we define equal superposition on such group? $\endgroup$ Mar 28, 2021 at 5:47
  • $\begingroup$ Take $\mathbb{Z}_{10}$ $\endgroup$ Mar 28, 2021 at 5:53
  • $\begingroup$ Well, at least there's a bijection between elements of $G$ and integers in $[\vert G\vert]$. You might likely have to pad up to a power of $2$ to determine the number of qubits, and do some other, easier processing to get rid of the unwanted numbers between $\vert G\vert$ and $2^n$. In your $\mathbb{Z}_{10}$ example you could, for example, repeat using $4$ qubits to prepare all integers in $[16]$, calculating in another register whether the qubits represent an integer $\ge 10$, and post-select on this register, to get a uniform superposition over all $10$ elements. $\endgroup$ Mar 28, 2021 at 14:30

Your Answer

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