betaFeedback

WorksPhysics and Astronomy

Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis

Abstract

The hidden subgroup problem (HSP) unifies many of the best-known quantum speed-ups. For abelian groups it is solved efficiently by weak Fourier sampling, but for non-abelian groups, which include the cases relevant to graph isomorphism and lattice-based cryptography, the right measurement basis is crucial and often unknown. We experimentally study the HSP over the qq-hedral groups Zq⋉Zp\mathbb{Z}_q \ltimes \mathbb{Z}_p, which interpolate between the dihedral and affine groups and mark a boundary between instances that are efficiently solvable and those that are only information-theoretically solvable. On the IonQ Forte trapped-ion quantum computer, with p≤7p \le 7, we implement weak Fourier sampling, strong Fourier sampling in an adapted basis, strong Fourier sampling of adjacent pairs, and forgetful abelian sampling. We demonstrate that the theoretical predictions of Moore, Rockmore, Russell and Schulman survive on a noisy device: weak sampling reveals nothing about the hidden subgroup, the adapted basis succeeds for large qq, adjacent pairs succeed for small qq, and forgetful sampling saturates below unit success. For p=7p=7, q=6q=6, the hardware exceeds the success probability of an exhaustively optimised classical algorithm for up to three oracle queries.

Introduction

Possibly the most famous future application of quantum computers is efficiently factoring numbers using Shor’s Algorithm [2], which could in principle break the RSA cryptography [3] that secures much of the world’s internet traffic. Factoring can be classically reduced to period finding [2], and while no polynomial-time classical algorithm for factoring is known, a quantum computer can find periods efficiently using the quantum Fourier transform. Period finding is one instance of the abelian Hidden Subgroup Problem (HSP) [4], which can be solved efficiently on a quantum computer for any finite abelian group, whereas classical algorithms typically require exponentially many queries.

Many interesting problems can similarly be reduced to the non-abelian HSP, including graph isomorphism (symmetric group) [5, 6] and the unique shortest vector problem (dihedral group) [7], which is closely related to the problems underpinning lattice-based post-quantum cryptography. However, unlike the abelian case, no general efficient quantum algorithm is known for the non-abelian HSP. Despite this, some instances are efficiently solvable using carefully tailored quantum algorithms [1, 8, 9, 10, 11, 12, 13, 14].

In this work we demonstrate the first experimental implementation of solving a non-abelian HSP on a quantum device. We explore the particularly interesting q-hedral family of non-abelian groups which delineate a boundary of efficiently solvable problems and those only solveable in an information theoretical sense. This family was first studied in this context by Moore, Rockmore, Russell and Schulman (MRRS) [1, 15], and our work can be viewed as an experimental demonstration that their theoretical results survive on a noisy quantum device.

MRRS distinguish between fully reconstructible HSP over group GG, which can be solved using quantum circuits of size polynomial in log⁡∣G∣\log|G| followed by polynomial-time classical post-processing, and information-theoretically reconstructible problems that are solvable with polynomial sized quantum circuits but the classical post-processing may be arbitrary. HSP over the dihedral group (DpD_p) is information-theoretically reconstructible as O(log⁡p)O(\log p) quantum queries provide enough information to determine the hidden subgroup, but the best known classical decoding algorithm takes time exponential in log⁡p\log p [16].1 In this work we evaluate how carefully choosing the measurement basis is crucial to ensuring both full and information-theoretic reconstructibility.

The qq-hedral groups interpolate between the dihedral group (q=2q = 2) and the affine group (q=p−1q = p - 1) for each prime pp. The main results of MRRS are that the qq-hedral HSP is fully reconstructible when q=p/polylog⁡pq = p/\operatorname{polylog} p, using strong Fourier sampling in an adapted basis, and information-theoretically reconstructible for all qq, using strong Fourier sampling of adjacent pairs. They also show that forgetful abelian sampling [16], which discards the non-abelian structure of the group, does not suffice.

In this work we implement each of these measurement strategies end-to-end on the IonQ Forte trapped-ion quantum computer for p∈{3,5,7}p \in\{3,5,7\} and a range of qq spanning the dihedral and affine extremes. Our contributions are as follows.

  1. We introduce a small modification to the adjacent-pairs measurement, replacing HH with HTH_T, which removes an ambiguity between bb and −b-b present in the original scheme.

  1. We construct hardware-efficient circuits for each

component: numerically synthesised QFTpQFT_p circuits, an oracle implemented by Fourier conjugation, and a Walsh-series synthesis of the diagonal gates required by the exponent encoding, each using substantially fewer two-qubit gates than standard compiler synthesis.

  1. We observe the signatures predicted by theory: weak Fourier sampling carries no information about the hidden subgroup; adapted-basis sampling succeeds with probability (p−1)q/p2(p-1)q/p^2; adjacent-pairs sampling succeeds for small qq, where the adapted basis fails; and forgetful abelian sampling plateaus at success probability (p+q−1)/(pq)(p+q-1)/(pq) because it cannot distinguish bb within an orbit.

  1. We compare against an exhaustively optimised, derandomised classical birthday algorithm and find that for p=7p=7, q=6q=6 the noisy hardware achieves a higher success probability than the optimal classical strategy for up to three queries.

At these sizes, the comparison concerns query complexity rather than computational speed-up. As in previous demonstrations of the abelian HSP [18], a third party must act as “compiler”, since the secret bb is compiled into the oracle circuit; knowledge of bb is used only to construct the oracle, never in decoding, and the oracle is treated as a black box when counting queries. In addition, circuit elements acting only on registers that are discarded (the final QFTp†QFT_p^\dagger and permutation in the oracle, and the controlled uncomputation in the non-abelian QFT) are omitted, as detailed in Appendix § 1.1.1. To our knowledge, this is nonetheless the first experimental demonstration of strong Fourier sampling and of an end-to-end non-abelian hidden subgroup algorithm.

The remainder of this paper is organised as follows. Section II reviews the qq-hedral HSP and derives the measurement statistics of each sampling method. Section III presents the experimental results, and Section IV discusses their implications. Appendix § 1.1.1 describes our circuit constructions and error mitigation.

q-Hedral Hidden Subgroup Problem

When solving the Hidden Subgroup Problem we first prepare a register with a uniform superposition over all of the elements of the group GG. In our case we are considering the qq-hedral group G=Zq⋉ZpG=\mathbb{Z}_q\ltimes\mathbb{Z}_p for a given prime pp and divisor qq of p−1p-1. The group is composed of elements (x,αt)(x,\alpha^t) with x∈Zpx\in\mathbb{Z}_p, t∈Zqt\in\mathbb{Z}_q, ord⁡α=q\operatorname{ord}\alpha=q and the group action is given by (x,αt)(x′,αt′)=(x+αtx′,αt+t′)(x,\alpha^t)(x',\alpha^{t'})=(x+\alpha^t x',\alpha^{t+t'}). Therefore, we begin by preparing the initial state:

1qp∑x=0p−1∑t=0q−1∣x⟩∣αt⟩(1)\frac{1}{\sqrt{qp}}\sum_{x=0}^{p-1}\sum_{t=0}^{q-1}|x\rangle|\alpha^t\rangle \tag*{(1)}

We then act with an oracle invariant under the action of our hidden subgroup Hb={(1−αt)b,αt) ∀t∈Zq}H_b=\{(1-\alpha^t)b,\alpha^t)\ \forall t\in\mathbb{Z}_q\}. In our instance the oracle we choose is:

fb(x,t)=π(x+αtb)(2)f_b(x,t)=\pi(x+\alpha^t b) \tag*{(2)}

where we choose a public α\alpha such that ord⁡α=q\operatorname{ord}\alpha=q, and π\pi is some random secret permutation. Our aim is to learn the secret value of bb. After acting with our oracle we have the following state:

1qp∑x=0p−1∑t=0q−1∣x⟩∣αt⟩∣fb(x,αt)⟩(3)\frac{1}{\sqrt{qp}}\sum_{x=0}^{p-1}\sum_{t=0}^{q-1}|x\rangle|\alpha^t\rangle|f_b(x,\alpha^t)\rangle \tag*{(3)}

We then measure the register containing the output of the oracle getting measurement result cc. As the oracle is invariant under the action of the subgroup HbH_b we are now restricted to a superposition over the coset CHbCH_b. Therefore, our post-measurement state is given by:

1q∑t=0q−1∣π−1(c)−αtb⟩∣αt⟩(4)\frac{1}{\sqrt{q}}\sum_{t=0}^{q-1}|\pi^{-1}(c)-\alpha^t b\rangle|\alpha^t\rangle \tag*{(4)}

The next step is to perform the QFT over the full group GG. As the group is non-abelian the form of this QFT is more complex than usual. As defined by [8] the QFT of this coset state is given by:

∑ρ∈G~1qdρp∑i,j∑t=0q−1ρ((π−1(c)−αtb,αt))i,j∣ρ,i,j⟩(5)\sum_{\rho\in\widetilde{G}}\frac{1}{q}\sqrt{\frac{d_\rho}{p}}\sum_{i,j}\sum_{t=0}^{q-1}\rho((\pi^{-1}(c)-\alpha^t b,\alpha^t))_{i,j}|\rho,i,j\rangle \tag*{(5)}

where G~\widetilde{G} is the set of irreducible representations of GG. In our instance GG has qq one-dimensional irreps given by:

σl((x,t))=ωqlt(6)\sigma_l((x,t))=\omega_q^{lt} \tag*{(6)}

for l∈Zql\in\mathbb{Z}_q and (p−1)/q(p-1)/q distinct qq-dimensional irreps given by:

ρl((x,t))j,k={ωplαjxk=j+t(modq)0else(7)\rho_l((x,t))_{j,k}= \begin{cases} \omega_p^{l\alpha^j x} & k=j+t\pmod q\\ 0 & \text{else} \end{cases} \tag*{(7)}

for l∈Zp∗/Zql\in\mathbb{Z}_p^*/\mathbb{Z}_q. Therefore, we can rewrite (5) as:

1q1p∑t=0q−1∑l=0p−1q−1ωqlt∣σl,0,0⟩+1pq∑t=0q−1∑l=0p−1q−1∑j=0q−1ωpgl+1αjx∣ρl,j,j+t⟩(8)\frac{1}{q}\sqrt{\frac{1}{p}}\sum_{t=0}^{q-1}\sum_{l=0}^{\frac{p-1}{q}-1}\omega_q^{lt}|\sigma_l,0,0\rangle+ \sqrt{\frac{1}{pq}}\sum_{t=0}^{q-1}\sum_{l=0}^{\frac{p-1}{q}-1}\sum_{j=0}^{q-1}\omega_p^{g^{l+1}\alpha^j x}|\rho_l,j,j+t\rangle \tag*{(8)}

where gg is a primitive root modulo pp and x=π−1(c)−αtbx=\pi^{-1}(c)-\alpha^t b. It is clear that α=gp−1q\alpha=g^{\frac{p-1}{q}} as αq=gp−1=1(modp)\alpha^q=g^{p-1}=1\pmod p. Every l∈Zp−1ql\in\mathbb{Z}_{\frac{p-1}{q}} and j∈Zqj\in\mathbb{Z}_q gives a unique k=gl+1αjk=g^{l+1}\alpha^j mod pp with k∈Zp∗k\in\mathbb{Z}_p^*, and hence we can perform the unique relabeling of the (p−1)q(p-1)q basis states ∣ρl,j,j+t⟩|\rho_l,j,j+t\rangle as ∣gl+1αj,αt⟩|g^{l+1}\alpha^j,\alpha^t\rangle. Therefore, we have:

1q1p∑t=0q−1∑l=0q−1ωqlt∣σl,0,0⟩+1pq∑t=0q−1∑l=0p−1q−1∑j=0q−1ωpgl+1αjx∣gl+1αj,αt⟩(9)\frac{1}{q}\sqrt{\frac{1}{p}\sum_{t=0}^{q-1}\sum_{l=0}^{q-1}\omega_q^{lt}|\sigma_l,0,0\rangle}+\sqrt{\frac{1}{pq}\sum_{t=0}^{q-1}\sum_{l=0}^{\frac{p-1}{q}-1}\sum_{j=0}^{q-1}\omega_p^{g^{l+1}\alpha^j x}|g^{l+1}\alpha^j,\alpha^t\rangle} \tag*{(9)}

as gl+1αjg^{l+1}\alpha^j generates every k∈Zp∗k\in\mathbb{Z}_p^* exactly once when we sum over l∈Zp−1ql\in\mathbb{Z}_{\frac{p-1}{q}} and j∈Zqj\in\mathbb{Z}_q, and hence we can replace the summations with one over k∈Zp∗k\in\mathbb{Z}_p^*:

1q1p∑t=0q−1∑l=0q−1ωqlt∣σl,0,0⟩+1pq∑t=0q−1∑k=1p−1ωpkx∣k⟩∣αt⟩(10)\frac{1}{q}\sqrt{\frac{1}{p}\sum_{t=0}^{q-1}\sum_{l=0}^{q-1}\omega_q^{lt}|\sigma_l,0,0\rangle}+\sqrt{\frac{1}{pq}\sum_{t=0}^{q-1}\sum_{k=1}^{p-1}\omega_p^{kx}|k\rangle|\alpha^t\rangle} \tag*{(10)}

Now we can perform a unique relabeling of the first term from ∣σl,0,0⟩|\sigma_l,0,0\rangle to ∣0⟩∣l⟩|0\rangle|l\rangle giving:

1q1p∑t=0q−1∑l=0q−1ωqlt∣0⟩∣l⟩+1pq∑t=0q−1∑k=1p−1ωpk(π−1(c)−αtb)∣k⟩∣αt⟩(11)\frac{1}{q}\sqrt{\frac{1}{p}\sum_{t=0}^{q-1}\sum_{l=0}^{q-1}\omega_q^{lt}|0\rangle|l\rangle}+\sqrt{\frac{1}{pq}\sum_{t=0}^{q-1}\sum_{k=1}^{p-1}\omega_p^{k(\pi^{-1}(c)-\alpha^t b)}|k\rangle|\alpha^t\rangle} \tag*{(11)}

where we have substituted back in our expression for xx. By taking the summation over tt in the first term we have:

1p∣0⟩∣0⟩+1pq∑t=0q−1∑k=1p−1ωpk(π−1(c)−αtb)∣k⟩∣αt⟩(12)\sqrt{\frac{1}{p}}|0\rangle|0\rangle+\sqrt{\frac{1}{pq}\sum_{t=0}^{q-1}\sum_{k=1}^{p-1}\omega_p^{k(\pi^{-1}(c)-\alpha^t b)}|k\rangle|\alpha^t\rangle} \tag*{(12)}

We have now made a choice of basis that ensures the state after applying QFT has the same tensor product structure as before.

After applying the Quantum Fourier Transform the next step of the standard Hidden Subgroup Problem algorithm is to measure the state. This measurement reveals an irrep label that the coset state transforms under. For abelian groups we can stop here as the distribution of irrep labels unique identifies the subgroup of the abelian group. However, for non-abelian groups such as ours many subgroups can share the same irrep label. Indeed measuring just the irrep label is categorised in the literature as “weak fourier sampling” and is known to be sufficient to identify normal subgroups but insufficient for any non-normal subgroups. Therefore, the standard approach to solving HSP for non-abelian groups is to employ the “strong fourier sampling” method. Here we still measure the irrep label, but do not simply discard the remaining state. Instead by employing a careful choice of measurement basis we are able to extract information about the hidden subgroup. This approach is not always successful and has been demonstrated to be insufficient for the symmetric group [19].

The optimal choice of measurement basis for “strong fourier sampling” is not easily derived for a general non-abelian group. However, for the q-hedral group we consider there has been extensive research into different methods for performing “strong fourier sampling”. In this work we demonstrate practical implementations of a range of sampling methods and compare their performance on an existing quantum device. To our knowledge this is the first experimental implementation of “strong fourier sampling” and the first experimental demonstration of end-to-end non-abelian HSP. Below we will discuss each of the sampling techniques we will demonstrate.

Strong sampling in adapted basis

After measuring the irrep label k≠0k\ne0 (with probability 1−1p1-\frac{1}{p}) we have the following post-measurement state:

1q∑t=0q−1ωpk(π−1(c)−αtb)∣αt⟩(13)\sqrt{\frac{1}{q}\sum_{t=0}^{q-1}\omega_p^{k(\pi^{-1}(c)-\alpha^t b)}|\alpha^t\rangle} \tag*{(13)}

If we simply perform abelian QFTpQFT_p on the remaining register to get:

1qp∑t=0q−1∑l=0p−1ωpkπ−1(c)−αtbk+αtl∣l⟩(14)\sqrt{\frac{1}{qp}\sum_{t=0}^{q-1}\sum_{l=0}^{p-1}\omega_p^{k\pi^{-1}(c)-\alpha^t b k+\alpha^t l}|l\rangle} \tag*{(14)}

We then measure the register which gives ll with probability:

1qp∣∑t=0q−1ωpαt(l−kb)∣2(15)\frac{1}{qp}\left|\sum_{t=0}^{q-1}\omega_p^{\alpha^t(l-kb)}\right|^2 \tag*{(15)}

Therefore, the outcome l=kb(modp)l=kb\pmod p occurs with probability qp\frac{q}{p}. Hence, as we know kk we are able to solve the Hidden Subgroup Problem by finding bb with probability (1−1p)qp(1-\frac{1}{p})\frac{q}{p}. Therefore, in the regime where q=p/polylog⁡(p)q=p/\operatorname{polylog}(p) the Hidden Subgroup Problem on Zq⋊Zp\mathbb{Z}_q\rtimes\mathbb{Z}_p is fully reconstructible (solvable with O(polylog⁡(p))O(\operatorname{polylog}(p)) quantum samples by a quantum circuit of size O(polylog⁡(p))O(\operatorname{polylog}(p))). However, in the regime of small qq this approach breaks down. For example, for constant qq we would require Ω(p)\Omega(p) samples to determine bb using a mode based decoder which is less efficient than the O(p)O(\sqrt{p}) classical collision approach. Therefore, in this regime we use a different method of strong sampling described below.

Strong sampling of adjacent pairs

To implement this sampling technique on existing quantum devices we use a different encoding of the group to the previous method. Instead of storing αt\alpha^t in the second register, we will simply store the exponent tt. The only impact of this is upon the quantum circuit for applying the oracle and the state preparation technique. In this encoding the post-measurement state we obtain with probability 1−1p1-\frac{1}{p} is:

1q∑t=0q−1ωpk(π−1(c)−αtb)∣t⟩(16)\sqrt{\frac{1}{q}}\sum_{t=0}^{q-1}\omega_p^{k(\pi^{-1}(c)-\alpha^t b)}|t\rangle \tag*{(16)}

We proceed by applying HTHT to the qubit storing the least significant bit of tt, which gives the following state:

ωpkπ−1(c)1q∑t=0q/2−1ωp−α2tbk∣2t⟩∣+⟩+eiπ4ωp−α2t+1bk∣2t⟩∣−⟩(17)\omega_p^{k\pi^{-1}(c)}\sqrt{\frac{1}{q}}\sum_{t=0}^{q/2-1}\omega_p^{-\alpha^{2t}bk}|2t\rangle|+\rangle+e^{i\frac{\pi}{4}}\omega_p^{-\alpha^{2t+1}bk}|2t\rangle|-\rangle \tag*{(17)}
ωpkπ−1(c)2q∑t=0q/2−1eiπ8ωp−12(1+α)α2tbkcos⁡(πp(1−α)α2tbk+π8)∣2t⟩∣0⟩−ieiπ8ωp−12(1+α)α2tbksin⁡(πp(1−α)α2tbk+π8)∣2t⟩∣1⟩(18)\omega_p^{k\pi^{-1}(c)}\sqrt{\frac{2}{q}}\sum_{t=0}^{q/2-1}e^{i\frac{\pi}{8}}\omega_p^{-\frac{1}{2}(1+\alpha)\alpha^{2t}bk}\cos\left(\frac{\pi}{p}(1-\alpha)\alpha^{2t}bk+\frac{\pi}{8}\right)|2t\rangle|0\rangle-ie^{i\frac{\pi}{8}}\omega_p^{-\frac{1}{2}(1+\alpha)\alpha^{2t}bk}\sin\left(\frac{\pi}{p}(1-\alpha)\alpha^{2t}bk+\frac{\pi}{8}\right)|2t\rangle|1\rangle \tag*{(18)}

for even qq. Therefore, upon measuring all the qubits we have that the expectation value of the least significant bit varies as sin⁡(mπpb+π8)2\sin\left(\frac{m\pi}{p}b+\frac{\pi}{8}\right)^2 in m=(1−α)α2tk mod pm=(1-\alpha)\alpha^{2t}k\bmod p. The original MRRS paper instead applied just HH leading to a sin⁡(mπpb)2\sin\left(\frac{m\pi}{p}b\right)^2 signal. They state that the total variation distance of this signal between any two distinct bb is bounded below by a constant, so in theory we can distinguish between pp different bb with only O(log⁡p)O(\log p) samples for all qq. However, under their signal it is impossible to distinguish bb from p−bp-b as:

sin⁡(mπp(p−b))2=sin⁡(mπpb)2(19)\sin\left(\frac{m\pi}{p}(p-b)\right)^2=\sin\left(\frac{m\pi}{p}b\right)^2 \tag*{(19)}

The total-variation bound of [1] therefore holds only for pairs b′≠±bb'\ne\pm b. Our slight modification of applying HTHT alleviates this and ensures that the Hidden Subgroup Problem on Zq⋊Zp\mathbb{Z}_q\rtimes\mathbb{Z}_p is information-theoretic reconstructible for all qq. However, there is no known O(polylog⁡p)O(\operatorname{polylog} p) classical decoder, so it is not shown to be fully reconstructible for all qq.

We can however decode the signal in O(plog⁡p)O(p\log p) time using FFT and hence demonstrate an oracle query advantage over a purely classical approach.

Forgetful Abelian Method

As discussed in MRRS it is sometimes possible to solve HSP for a non-abelian group by erasing its non-abelian structure and performing an abelian Fourier transform instead. In our case this would correspond to treating the group instead as the direct product Zq×Zp\mathbb{Z}_q\times\mathbb{Z}_p with the corresponding abelian Fourier transform given by QFTp⊗QFTqQFT_p\otimes QFT_q. We can view this in within our existing framework as a choice of basis for strong Fourier sampling with the exponent encoding described in the previous section.

Starting from the post-measurement state for any kk (including k=0k=0):

1q∑t=0q−1ωpk(π−1(c)−αtb)∣t⟩(20)\sqrt{\frac{1}{q}}\sum_{t=0}^{q-1}\omega_p^{k(\pi^{-1}(c)-\alpha^t b)}|t\rangle \tag*{(20)}

we apply QFTqQFT_q to get:

1q∑l,t=0q−1ωpk(π−1(c)−αtb)ωqlt∣l⟩(21)\frac{1}{q}\sum_{l,t=0}^{q-1}\omega_p^{k(\pi^{-1}(c)-\alpha^t b)}\omega_q^{lt}|l\rangle \tag*{(21)}

Therefore, the probability of measuring irrep labels kk and ll is given by:

Pb(k,l)=1pq2∣∑t=0q−1ωp−αtbkωqlt∣2(22)P_b(k,l)=\frac{1}{pq^2}\left|\sum_{t=0}^{q-1}\omega_p^{-\alpha^t bk}\omega_q^{lt}\right|^2 \tag*{(22)}

Taking b′=αmbb'=\alpha^m b for m∈Zqm\in\mathbb{Z}_q gives:

Pb′(k,l)=1pq2∣∑t=0q−1ωp−αt+mbkωqlt∣2(23)P_{b'}(k,l)=\frac{1}{pq^2}\left|\sum_{t=0}^{q-1}\omega_p^{-\alpha^{t+m}bk}\omega_q^{lt}\right|^2 \tag*{(23)}
=1pq2∣∑t′=0q−1ωp−αt′bkωql(t′−m)∣2(24)=\frac{1}{pq^2}\left|\sum_{t'=0}^{q-1}\omega_p^{-\alpha^{t'}bk}\omega_q^{l(t'-m)}\right|^2 \tag*{(24)}
=1pq2∣ωq−lm∑t′=0q−1ωp−αt′bkωqlt′∣2(25)=\frac{1}{pq^2}\left|\omega_q^{-lm}\sum_{t'=0}^{q-1}\omega_p^{-\alpha^{t'}bk}\omega_q^{lt'}\right|^2 \tag*{(25)}
=Pb(k,l)(26)=P_b(k,l) \tag*{(26)}

Therefore, this forgetful abelian sampling method cannot distinguish bb from q−1q-1 other bb for b≠0b\ne0. A decoder can therefore only identify the orbit of bb, as the average number of elements in a orbit is pqp+q−1\frac{pq}{p+q-1} the success probability is capped at p+q−1pq\frac{p+q-1}{pq} regardless of the number of samples collected. This is evidence that not only is the choice of strong Fourier sampling basis important for efficient decoding, but also effects the information theoretic reconstruction of the subgroup.

Results

We demonstrate the theoretical predictions of Section II by running the quantum circuits described in Appendix A (Figure 7 and Figure 8) on the IonQ Forte quantum device [20]. We restrict to primes p=3,5,7p=3,5,7 as larger primes required larger circuits and subsequently too much hardware noise to observe a clear signal.

Figure 7. Adapted-basis circuit for p=7p=7 in the field encoding. Controlled phases θm=2π2m/p\theta_m = 2\pi2^m/p from xx and bθmb\theta_m from aa act on the computation register yy. QFTpQFT_p on xx gives kk and QFTpQFT_p on aa gives ll; shots with k=0k=0 are discarded. We omit the yy register’s final QFTp†QFT_p^\dagger and π\pi as yy is discarded.

Figure 8. Exponent-encoding circuit. Θ\Theta applies the controlled phases from xx on the computation register yy as in Fig. 7, and DbD_b applies the bb-dependent phases from tt (Fig. 9). The measurement MM on tt sets the sampling method: HTHT on t0t_0 for adjacent pairs, HH for the original MRRS scheme, FqF_q for forgetful abelian sampling and no gate for weak Fourier sampling.

Figure 1. Weak Fourier sampling for p=7p = 7 with (a) q=2q = 2 and (b) q=6q = 6, from the raw hardware data of the forgetful circuits (2,048 shots per secret; 95% Wilson intervals). The irrep distribution is the same for every bb, so weak Fourier sampling reveals nothing about the hidden subgroup. “Invalid” counts outcomes outside the group encoding.

Experimental Details All data were taken on the IonQ Forte trapped-ion computer between 9 and 12 October 2026. We ran 62 circuits (every p≤7p \le7, qq and secret bb shown in the figures) at 2,048 shots each, plus gate-folded (fold =3= 3) copies of 13 circuits, for 75 jobs and 153,600 shots in total. Circuits were compiled offline to Forte’s native gates (GPi, GPi2 and arbitrary-angle ZZ) and submitted as native gate lists, so no further compilation removed the folded gates. Every job used IonQ’s debiasing, which runs a job as 32 variants of 64 shots over different qubit assignments and combines their counts. We refer to these debiased counts, without further mitigation, as “raw”.

First, in Fig. 1 we demonstrate that weak fourier sampling provides no information about the hidden subgroup parameterised by bb. This draws a direct contrast with the abelian hidden subgroup problem where the irrep label revealed by weak fourier sampling uniquely determines the hidden subgroup. We draw our weak Fourier samples from the forgetful abelian circuits. On the k=0k = 0 branch, FqF_q on the second register completes the non-abelian QFT on the one-dimensional irreps, so the measured ll is the label of σl\sigma_l; on the k≠0k \ne0 branch the irrep is fixed by kk alone, and weak sampling discards the second register anyway. For k≠0k \ne0 the irrep is ρc\rho_c with c=(log⁡gk−1) mod p−1c = (\log_g k - 1) \bmod p-1 where gg is the primitive root with α=g(p−1)/q\alpha= g^{(p-1)/q}, and for k=0k = 0 it is σl\sigma_l. For our subgroups HbH_b only l=0l = 0 occurs, as seen in Eq. (12).

Figure 2 demonstrates that, unlike weak fourier sampling, strong fourier sampling in an adapted basis gives bb with high probability. Figure 3 shows that the success probability due to strong fourier sampling in the adapted basis follows the theoretical prediction of (p−1)q/p2(p-1)q/p^2. Further, it shows that for fixed qq we have decaying success probability with increasing pp, and hence we require a different sampling method for small qq.

Figure 2. Strong Fourier sampling in the adapted basis for p=7p = 7, q=6q = 6 with (a) b=0b = 0, (b) b=1b = 1 and (c) b=5b = 5 (2,048 shots per circuit; 95% Wilson intervals for raw data and bootstrap intervals for ZNE). Conditioned on k≠0k \ne0, the candidate lk−1 mod pl k^{-1} \bmod p peaks at the hidden bb with ideal height q/pq/p.

Figure 3. Success probability of adapted-basis sampling for b=1b = 1, (a) against qq for p=7p = 7 and (b) against pp for q=2q = 2 (2,048 shots each; 95% bootstrap intervals). The hardware follows the prediction (p−1)q/p2(p-1)q/p^2, and for fixed qq it decays as pp increases.

Strong sampling via adjacent pairs is demonstrated by Figure 4 and demonstrates a high probability of success even for small qq. Figure 4 also confirms the theoretical prediction that the original protocol of MRRS for adjacent pairs fails to distinguish bb from −b-b. The theory predicts that we only need O(log⁡p)O(\log p) samples to distinguish bb. Unfortunately, we cannot confirm this prediction with our small sample of three different pp.

Figure 4. Strong Fourier sampling of adjacent pairs for p=7p=7, q=2q=2 with b=1,3,6b=1,3,6, applying (a)–(c) HTHT and (d)–(f) HH to the least significant bit t0t_0 of tt (2,048 shots per circuit, 95% bootstrap intervals). The Fourier coefficient at b′b' is the real part of e−iπ/4(−1)tωp−mb′e^{-i\pi/4}(-1)^t\omega_p^{-mb'} for HTHT, and of (−1)tωp−mb′(-1)^t\omega_p^{-mb'} for HH, with m=(1−α)kmod⁡pm=(1-\alpha)k\mathbin{\operatorname{mod}}p, summed over the shots with k≠0k\ne0 and divided by the total number of shots. With HTHT the signal peaks only at bb, whereas HH cannot distinguish bb from −b-b.

The final example of sampling we consider is forgetful abelian sampling. Here the theory predicts that we will be able to distinguish the orbit of bb but not which bb we have within the orbit. Figure 5 demonstrates that this holds as we can successfully distinguish b=1b=1 from b=3b=3 but not from b=2b=2 as {1,2,4}\{1,2,4\} share an orbit.

Figure 5. Joint probability of (k,l)(k,l) under forgetful abelian sampling for p=7p=7, q=3q=3 with (a) b=1b=1, (b) b=2b=2 and (c) b=3b=3, from raw hardware data (2,048 shots each). As b=1b=1 and b=2b=2 share the orbit {1,2,4}\{1,2,4\} they cannot be distinguished, whereas b=3b=3 can.

In Figure 6 we compare the performance of each of the considered sampling techniques. To accomplish this we perform bootstrap sampling of the measured bitstrings (including those with k=0k=0) and plot the probability of decoding a uniformly random bb successfully against the number of bootstrap samples taken (which is equivalent to the total oracle queries consumed). We do not use zero noise extrapolation for these plots as that would require additional queries. We include the recovery by random guess as a comparison that highlights the poor performance of weak fourier sampling. For a fair comparison we also include the optimum classical baseline of recovery probability against query count.

Figure 6. Probability of recovering bb against total oracle queries for p=7p=7 with q=2q=2 (top) and q=6q=6 (bottom), using (a,d) the adapted basis, (b,e) adjacent pairs and (c,f) forgetful abelian sampling. Each of 20,000 trials draws bb uniformly and resamples shots from that circuit’s 2,048-shot histogram, one shot per query; bands are pointwise 95% percentile intervals over 1,000 multinomial resamples of the histograms, so they include the hardware sampling error but not device drift, and maximum likelihood uses the ideal outcome probabilities. We compare the raw hardware data with noiseless simulation, a random guess and the optimal classical algorithm. Forgetful abelian sampling plateaus at (p+q−1)/(pq)(p+q-1)/(pq).

The standard classical approach to the HSP is the birthday algorithm [21, 22]. This proceeds by querying random elements until two return the same label, placing both elements in the same coset of HH which determines the secret via:

b=(x′−x)(αt−αt′)−1(modp)(27)b=(x'-x)(\alpha^t-\alpha^{t'})^{-1}\pmod p \tag*{(27)}

where fb(x,t)=fb(x′,t′)f_b(x,t)=f_b(x',t'). This requires O(p)O(\sqrt{p}) queries to succeed and is optimal up to a constant [22, 23]. However, choosing random elements to query is inefficient as some elements can never collide (e.g. if t=t′t=t') and some different pairs test the same bb. Therefore, we have chosen to use a derandomised version of the birthday algorithm [22] as our classical comparison. In this derandomised version we have chosen the sequence of queries which ensures the maximum probability of successfully decoding bb for every query budget. We found this sequence via an exhaustive search and hence ensure this is the classical algorithm which uses the fewest possible queries.

Despite the classical algorithm having the optimal success probability for all query counts, Figure 6 shows that with up to 3 queries the real noisy quantum hardware gives a higher success probability for p=7p=7 and q=6q=6. Further, the noiseless simulation of quantum hardware exceeds 90% success probability at fewer queries than the classical case.

Figure 6 provides a useful comparison between the relative performance of the different sampling methods at two extremes: q=2q=2 (dihedral) and q=6q=6 (affine). We see that as expected the adapted basis outperforms the adjacent pairs method for large qq but loses out to it for small qq. It is also interesting to consider the behavior of the forgetful abelian sampling. We decode bb from the forgetful abelian signal using a maximum likelihood estimator. We see that the probability of successfully decoding bb via forgetful abelian sampling reaches a plateau before reaching 1. This corresponds to the theoretical prediction that forgetful abelian sampling cannot distinguish bb within the same orbit, and as expected the success probability is capped at p+q−1pq\frac{p+q-1}{pq} in both figures. We can also see that the performance of the adjacent pairs sampling method is largely independent of qq as predicted by the theory, unlike the adapted basis method which is heavily dependent on qq.

Figure 6 also highlights the relative performance of our chosen decoders. For the adjacent-pairs method, FFT decoding performs similarly to maximum likelihood decoding for both q=2q=2 and q=6q=6. For the adapted-basis method, the mode decoder matches the maximum likelihood decoder at q=6q=6, but significantly underperforms at q=2q=2. This suggests that, for small qq, the mode decoder does not exploit all the information available in the adapted-basis measurement outcomes.

Discussion

Importantly we have shown that the choice of measurement basis matters practically as well as asymptotically. Figure 6 demonstrates that even at only p=7p=7 choosing the weak Fourier or forgetful abelian methods prevents the success probability reaching 1 irregardless of the number of samples taken. Even more starkly Figure 4 shows that a single gate can make the difference between being information-theoretic reconstructible and not. This highlights that choosing the correct measurement basis is crucial to ensure the problem is information-theoretic reconstructible as predicted by [1].

Figure 6 demonstrates that a system known to be fully reconstructible can outperform an optimized classical algorithm in recovery probability for low query counts despite the presence of hardware noise. This is despite the classical baseline having access to a perfect oracle, whereas every quantum query is subject to hardware noise. In noiseless simulation the separation extends further, with the quantum algorithm exceeding 90% success at fewer queries than the classical algorithm.

In this work we have restricted ourselves to considering the q-hedral group, however, there are many other non-abelian groups which present interesting targets for near term quantum experiments. For many of these groups single-register measurements are provably insufficient, and the optimal measurement is entangled across several coset states [6, 9, 24], therefore a two-copy entangled measurement, or a single combination step of Kuperberg’s sieve [17], would be a natural next experiment. Whilst the dihedral group is included within the q-hedral groups we solve in this work it has more efficient solutions than the more general methods we have presented here. One recent algorithm [25] shows particularly strong promise for NISQ devices due to its constant circuit depth.

Data and code availability

The experimental count histograms, quantum circuits, and analysis code supporting this work are available at [26]. The repository includes the circuit-generation and compilation code, classical-baseline enumeration, decoding and uncertainty-analysis routines, and scripts used to generate the figures.

Acknowledgements

I thank Frank Verstraete for supporting the proposal to FormationQ for access to IonQ hardware and for encouraging me to publish this work independently. I thank Subhayan Roy Moulik for helpfully suggesting optimising the compilation of the quantum Fourier transform circuits. I am grateful to FormationQ and IonQ for providing access to the IonQ Forte trapped-ion quantum computer.

Author contributions The author conceived and designed the study, carried out the experiments and analysis, and wrote the manuscript. The code used for circuit generation and compilation, classical-baseline enumeration, decoding, uncertainty analysis and figure generation was written with the assistance of Claude Opus 5.5. Claude was also used to generate the circuit diagrams in the Appendix and to review the manuscript before submission. The author checked and validated all code and results, and takes full responsibility for the content of this paper.

References

Quantum Circuit

Initial State

In order to prepare the uniform superposition over pp computation basis states required by (1) we use the Shukla-Vedula algorithm [27] which uses O(log⁡2(p))O(\log_2(p)) qubits and O(log⁡2(p))O(\log_2(p)) gates and we denote with UpU_p.

To prepare the state 1q∑t=0q−1∣αt⟩\frac{1}{\sqrt{q}}\sum_{t=0}^{q-1}|\alpha^t\rangle we employ the Gleinig-Hoefler algorithm [28] via the open source PyEn- code library [29]. However, for large qq the state stops being sparse and this algorithm produces more 2 qubit gates than Qiskit’s in-built dense state preparation technique [30], so we synthesise both and use whichever is cheaper. We denote this preparation technique with VqV_q.

Oracle

To implement the action of the oracle we use fourier conjugation. First, we prepare the computation register yy into a uniform superposition over pp basis states using the Shukla-Vedula algorithm (UpU_p):

∣x⟩∣αt⟩∣0⟩→∣x⟩∣αt⟩∣+p⟩(28)|x\rangle|\alpha^t\rangle|0\rangle\to|x\rangle|\alpha^t\rangle|+_p\rangle \tag*{(28)}

Then we act with ⌈log⁡p⌉2\lceil\log p\rceil^2 controlled-phase gates with phase 2i+jp\frac{2^{i+j}}{p} from the ii-th qubit of the first register on the jj-th qubit of the computation register:

∣x⟩∣αt⟩∣+p⟩→∣x⟩∣αt⟩1p∑y=0p−1ωpyx∣y⟩(29)|x\rangle|\alpha^t\rangle|+_p\rangle\to|x\rangle|\alpha^t\rangle\frac{1}{\sqrt{p}}\sum_{y=0}^{p-1}\omega_p^{yx}|y\rangle \tag*{(29)}

where

ωpyx=∏i,j=0n−1e2πi2i+jxiyjp(30)\omega_p^{yx}=\prod_{i,j=0}^{n-1}e^{2\pi i\frac{2^{i+j}x_i y_j}{p}} \tag*{(30)}

where x=∑i2ixix=\sum_i2^i x_i, y=∑i2iyiy=\sum_i2^i y_i. Similarly, we act with ⌈log⁡p⌉2\lceil\log p\rceil^2 controlled-phase gates with phase 2i+jpb\frac{2^{i+j}}{p}b from the ii-th qubit of the second register on the jj-th qubit of the computation register to give overall transformation:

∣x⟩∣αt⟩∣+p⟩→∣x⟩∣αt⟩1p∑y=0p−1ωpy(x+αtb)∣y⟩(31)|x\rangle|\alpha^t\rangle|+_p\rangle\to|x\rangle|\alpha^t\rangle\frac{1}{\sqrt{p}}\sum_{y=0}^{p-1}\omega_p^{y(x+\alpha^t b)}|y\rangle \tag*{(31)}

Next, we act with QFTp†QFT_p^\dagger upon the computation register which gives:

∣x⟩∣αt⟩∣+p⟩→∣x⟩∣αt⟩1p∑x′,y=0p−1ωpy(x+αtb−x′)∣x′⟩(32)|x\rangle|\alpha^t\rangle|+_p\rangle\to|x\rangle|\alpha^t\rangle\frac{1}{p}\sum_{x',y=0}^{p-1}\omega_p^{y(x+\alpha^t b-x')}|x'\rangle \tag*{(32)}
→∣x⟩∣αt⟩∣x+αtb⟩(33)\to|x\rangle|\alpha^t\rangle|x+\alpha^t b\rangle \tag*{(33)}

Finally, we apply a random secret permutation π\pi to the computational basis elements of the computation register. Thus we have completed our application of the oracle:

∣x⟩∣αt⟩∣0⟩→∣x⟩∣αt⟩∣π(x+αtb)⟩(34)|x\rangle|\alpha^t\rangle|0\rangle\to|x\rangle|\alpha^t\rangle|\pi(x+\alpha^t b)\rangle \tag*{(34)}

As we never use the outcome of the measurement on the computation register in our algorithm we are free to instead discard the register. This would produce the coset state:

1qp∑c=0p−1∑t,t′=0q−1∣π−1(c)−αtb⟩⟨π−1(c)−αt′b∣⊗∣αt⟩⟨αt′∣(35)\frac{1}{qp}\sum_{c=0}^{p-1}\sum_{t,t'=0}^{q-1}|\pi^{-1}(c)-\alpha^t b\rangle\langle\pi^{-1}(c)-\alpha^{t'}b|\otimes|\alpha^t\rangle\langle\alpha^{t'}| \tag*{(35)}

Under this assumption we are free to apply any unitary we wish to the discarded register before we discard it, and hence we do not actually need to implement the QFTpQFT_p or permutation π\pi as physical circuits provided we discard the measurement outcome obtained from the computation register.

Non-Abelian QFT

Once we have applied the oracle we must perform QFTQFT over the non-abelian q-hedral group. By inspecting (12) it is clear how to perform the non-abelian QFT as a quantum circuit. First, one must apply the abelian QFTpQFT_p on the first register (QFTp⊗IqQFT_p \otimes I_q) giving state:

1pq∑k=0p−1∑t=0q−1ωpk(π−1(c)−αtb)∣k⟩∣αt⟩(36)\frac{1}{\sqrt{pq}}\sum_{k=0}^{p-1}\sum_{t=0}^{q-1}\omega_p^{k(\pi^{-1}(c)-\alpha^t b)}|k\rangle|\alpha^t\rangle \tag*{(36)}

This can be rewritten as:

1pq∑t=0q−1∣0⟩∣αt⟩+1pq∑k=1p−1∑t=0q−1ωpk(π−1(c)−αtb)∣k⟩∣αt⟩(37)\frac{1}{\sqrt{pq}}\sum_{t=0}^{q-1}|0\rangle|\alpha^t\rangle+\frac{1}{\sqrt{pq}}\sum_{k=1}^{p-1}\sum_{t=0}^{q-1}\omega_p^{k(\pi^{-1}(c)-\alpha^t b)}|k\rangle|\alpha^t\rangle \tag*{(37)}

Therefore, if we uncompute 1q∑t=0q−1∣αt⟩\frac{1}{\sqrt{q}}\sum_{t=0}^{q-1}|\alpha^t\rangle controlled upon the first register being in state ∣0⟩|0\rangle then we apply the full non-abelian QFT giving state:

1p∣0⟩∣0⟩+1pq∑k=1p−1∑t=0q−1ωpk(π−1(c)−αtb)∣k⟩∣αt⟩(38)\frac{1}{\sqrt{p}}|0\rangle|0\rangle+\frac{1}{\sqrt{pq}}\sum_{k=1}^{p-1}\sum_{t=0}^{q-1}\omega_p^{k(\pi^{-1}(c)-\alpha^t b)}|k\rangle|\alpha^t\rangle \tag*{(38)}

This uncomputation is simply the inverse of the state preparation circuit (Vq†V_q^\dagger) we used to prepare 1q∑t=0q−1∣αt⟩\frac{1}{\sqrt{q}}\sum_{t=0}^{q-1}|\alpha^t\rangle. As we discard the results of the second register if the first register is measured to be k=0k=0, we do not actually need to perform this uncomputation step, and hence we do not actually demonstrate non-abelian QFT, but rather abelian QFT with post-selection. The full adapted-basis circuit, combining the state preparation, oracle and QFT described above, is shown in Figure 7.

Quantum Fourier Transform

The quantum Fourier transform over Zp\mathbb{Z}_p is a unitary on span⁡{∣j⟩}j<p\operatorname{span}\{|j\rangle\}_{j<p} acting as

QFTp∣j⟩=1p∑k=0p−1ωpjk∣k⟩∀ j∈Zp(39)QFT_p|j\rangle=\frac{1}{\sqrt{p}}\sum_{k=0}^{p-1}\omega_p^{jk}|k\rangle\qquad\forall\ j\in\mathbb{Z}_p \tag*{(39)}

realised on n=⌈log⁡2p⌉n=\lceil\log_2p\rceil qubits. Its action on the remaining 2n−p2^n-p dimensions is unconstrained.

There exist many asymptotically efficient methods for implementing QFTpQFT_p for generic pp [4, 31, 32, 33, 34]. However, for small pp it is possible to find more hardware efficient implementations through numerical synthesis, in the manner of approximate quantum compiling [35, 36, 37, 38]. In this work we use an ansatz with alternating layers of arbitrary single-qubit gates and a round-robin of 2-qubit RzzR_{zz} gates. Every QFTpQFT_p in our circuits is directly followed by a full ZZ basis measurement, so the phase of each output is irrelevant. Hence, for a given ansatz V(Θ)V(\Theta) we use BFGS to maximise F(Θ)\mathcal{F}(\Theta):

TransformQubitsOursQiskit
QFT3QFT_{3}223
QFT5QFT_{5}3819
QFT6QFT_{6}3719
QFT7QFT_{7}31019

Table 1. Two-qubit (RZZR_{ZZ}) gate counts for QFTdQFT_d on n=⌈log⁡2d⌉n = \lceil\log_{2} d \rceil qubits, comparing our numerically synthesised circuits with Qiskit’s quantum Shannon decomposition of QFTd⊕I2n−dQFT_d \oplus I_{2^n-d}.

F(Θ)=max⁡{φ}∣1p∑k<p⟨k∣V(Θ)QFTp†∣k⟩e−iφk∣(40)\mathcal{F}(\Theta) = \max_{\{\varphi\}} \left| \frac{1}{p} \sum_{k<p} \langle k|V(\Theta)QFT_p^\dagger|k\rangle e^{-i\varphi_k} \right| \tag*{(40)}
=1p∑k<p∣⟨k∣V(Θ)QFTp†∣k⟩∣(41)= \frac{1}{p}\sum_{k<p}\left|\langle k|V(\Theta)QFT_p^\dagger|k\rangle\right| \tag*{(41)}

The solution is then further refined using Gauss–Newton. We increment the depth of the ansatz until we achieve a machine precision approximation. Using this method we are able to attain far lower 2-qubit gate counts than that obtained by a standard Qiskit method of quantum Shannon decomposition of the embedded unitary QFTp⊕I2n−pQFT_p\oplus I_{2^n-p} as shown in Table I.

Exponent encoding

In Sections IIB and IIC we use an exponent encoding of our group rather than the above consider field encoding, with the full circuit shown in Figure 8. This greatly simplifies the state preparation of our circuit which can now use the Shukla-Vedula algorithm [27] for both registers, which we denote UpU_p and UqU_q, to produce:

1qp∑x=0p−1∑t=0q−1∣x⟩∣t⟩(42)\frac{1}{\sqrt{qp}}\sum_{x=0}^{p-1}\sum_{t=0}^{q-1}|x\rangle|t\rangle \tag*{(42)}
qqQubits (t+yt+y)OursQiskit
21+31+333
32+32+3615
63+33+31939

Table 2. Two-qubit (RZZR_{ZZ}) gate counts for the oracle diagonal DbD_b at p=7p=7, comparing our Walsh-series synthesis with one Qiskit diagonal gate per qubit of yy. Counts are the same for every bb.

However, it does increase the complexity of applying the oracle as we can no longer use n2n^2 controlled-phase gates to apply the contribution from the second register. Instead we act with nn different nqn_q-qubit diagonal gates, which we collectively denote DbD_b, acting on ∣t⟩|t\rangle and the ii-th qubit of the ∣y⟩|y\rangle register (nq=⌈log⁡q⌉+1n_q=\lceil\log q\rceil+1):

∑yi=01∑t=0q−1e2πi2iyiαtbp∣t⟩⟨t∣⊗∣yi⟩⟨yi∣(43)\sum_{y_i=0}^{1}\sum_{t=0}^{q-1}e^{2\pi i\frac{2^{i}y_i\alpha^t b}{p}}|t\rangle\langle t|\otimes|y_i\rangle\langle y_i| \tag*{(43)}

We synthesize these gates using techniques introduced by [39]. We first rewrite f(t)=2π2iαtbpf(t)=2\pi\frac{2^{i}\alpha^t b}{p} as a Walsh-Fourier series given by f(t)=∑s=02nq−1f^(s)(−1)∑jsjtjf(t)=\sum_{s=0}^{2^{n_q}-1}\hat{f}(s)(-1)^{\sum_j s_jt_j}. This reduces (A16) to:

∑yi=01∑t=0q−1∏s=02nq−1eiyif^(s)(−1)∑jsjtj∣t⟩⟨t∣⊗∣yi⟩⟨yi∣(44)\sum_{y_i=0}^{1}\sum_{t=0}^{q-1}\prod_{s=0}^{2^{n_q}-1}e^{iy_i\hat{f}(s)(-1)^{\sum_j s_jt_j}}|t\rangle\langle t|\otimes|y_i\rangle\langle y_i| \tag*{(44)}

We define the Walsh operator WsW_s as:

Ws=⨂j=1nq(Zj)sj=(Z1)s1⊗(Z2)s2⊗⋯⊗(Znq)snq(45)W_s=\bigotimes_{j=1}^{n_q}(Z_j)^{s_j}=(Z_1)^{s_1}\otimes(Z_2)^{s_2}\otimes\cdots\otimes(Z_{n_q})^{s_{n_q}} \tag*{(45)}

Hence we can further reduce (A16) to:

∑yi=01∑t=0q−1∏s=02nq−1eif^(s)1−Zyi2Ws∣t⟩⟨t∣⊗∣yi⟩⟨yi∣(46)\sum_{y_i=0}^{1}\sum_{t=0}^{q-1}\prod_{s=0}^{2^{n_q}-1}e^{i\hat{f}(s)\frac{1-Z_{y_i}}{2}W_s}|t\rangle\langle t|\otimes|y_i\rangle\langle y_i| \tag*{(46)}

We implement this gate by acting with CNOTs upon the register tt such that every parity ⨁jtjsj\bigoplus_j t_j^{s_j} occurs at least once on some qubit. When that parity is stored we can then perform e−if^(s)2ZyiWse^{-i\frac{\hat{f}(s)}{2}Z_{y_i}W_s} with a single RZZR_{ZZ} between the parity qubit and the ii-th qubit of ∣y⟩|y\rangle and eif^(s)2Wse^{i\frac{\hat{f}(s)}{2}W_s} with a single RZR_Z gate just on the parity qubit.

As f(t)f(t) is only restricted on t∈Zqt\in\mathbb{Z}_q we need only have qq non-zero f^(s)\hat{f}(s). Therefore, we do not need to implement WsW_s for every possible parity. Hence, we exhaustively search all the different methods of iterating through qq parities to find the shortest CNOT sequence that we can use to implement this gate. Figure 9 shows an example of our implementation of DbD_b for p=7p=7, q=6q=6.

Figure 9. Walsh-series implementation of DbD_b for p=7p=7, q=6q=6. A CNOT walk stores each required parity of tt on a single qubit, which is then coupled to each qubit of yy with an RZZR_{ZZ} gate.

This methodology results in fewer 2-qubit gates for DbD_b than using the standard Qiskit synthesis for diagonal gates [40] as highlighted in Table II.

Zero-noise extrapolation

Zero-noise extrapolation (ZNE) [41, 42] runs a circuit at several deliberately amplified noise levels and extrapolates the measured quantities back to zero noise. We perform digital zero-noise extrapolation through unitary folding [43] and exponential extrapolation [44]. We deliberately increase the noise in our circuit by replacing every RZZ(θ)R_{ZZ}(\theta) gate by RZZ(θ)RZZ(θ)−1RZZ(θ)R_{ZZ}(\theta)R_{ZZ}(\theta)^{-1}R_{ZZ}(\theta) as shown in Figure 10. We chose to just scale the noise due to our 2-qubit gates as they are the dominant contribution to error in our circuits. We assign the folded circuit a noise scale of λ=3\lambda=3 and the original circuit λ=1\lambda=1. Assuming the noise drives the state towards the maximally mixed state, so that the signal decays exponentially with λ\lambda, we model the expectation values as

Figure 10. Gate folding for zero-noise extrapolation. Each ZZ(θ)ZZ(\theta) is replaced by ZZ(θ)ZZ(θ)−1ZZ(θ)ZZ(\theta)ZZ(\theta)^{-1}ZZ(\theta) with ZZ(θ)−1=X1ZZ(θ)X1ZZ(\theta)^{-1}=X_1ZZ(\theta)X_1 which triples the two-qubit gate count. Single-qubit gates are not folded, and circuits are submitted as native gates so the folds are not compiled away.

⟨Oλ⟩−Tr⁡[O]d=gλ(⟨O0⟩−Tr⁡[O]d)(47)\langle O_\lambda\rangle-\frac{\operatorname{Tr}[O]}{d}=g^\lambda\left(\langle O_0\rangle-\frac{\operatorname{Tr}[O]}{d}\right) \tag*{(47)}

where dd is the Hilbert-space dimension, so that Tr⁡[O]/d\operatorname{Tr}[O]/d is the expectation value of OO in the maximally mixed state. Hence, we can derive:

⟨O0⟩=Tr⁡[O]d+⟨O1⟩−Tr⁡[O]dg(48)\langle O_0\rangle=\frac{\operatorname{Tr}[O]}{d}+\frac{\langle O_1\rangle-\frac{\operatorname{Tr}[O]}{d}}{g} \tag*{(48)}

We fit a single gg per circuit by least squares across all outcomes.

To derive error bars for our ZNE values we perform bootstrap resampling from the measured count histograms. For each replicate we resample both the λ=1\lambda=1 and λ=3\lambda=3 histograms, refit gg and recompute the ZNE value. We perform 1000 replicates and record the 2.5th and 97.5th percentiles for the ZNE value.

References

  1. [1]C. Moore, D. Rockmore, A. Russell, and L. J. Schulman. The power of strong fourier sampling: Quantum algorithms for affine groups and hidden shifts, SIAM Journal on Computing 37, 938 (2007).DOI
  2. [2]P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review 41, 303 (1999).
  3. [3]R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21, 120 (1978).
  4. [4]A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem, arXiv preprint quant-ph/9511026 (1995).
  5. [5]R. Beals, Quantum computation of fourier transforms over symmetric groups, in Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (1997) pp. 48–53.DOI
  6. [6]S. Hallgren, C. Moore, M. Röetteler, A. Russell, and P. Sen, Limitations of quantum coset states for graph isomorphism, J. ACM 57, 10.1145/1857914.1857918 (2010).
  7. [7]O. Regev, Quantum computation and lattice problems, SIAM Journal on Computing 33, 738 (2004).
  8. [8]S. Hallgren, A. Russell, and A. Ta-Shma, Normal subgroup reconstruction and quantum computation using group representations, in Proceedings of the thirty-second annual ACM symposium on Theory of computing (2000) pp. 627–635.DOI
  9. [9]D. Bacon, A. M. Childs, and W. van Dam, From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups, in 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) (IEEE, 2005) pp. 469–478.DOI
  10. [10]M. Grigni, L. Schulman, M. Vazirani, and U. Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, in Proceedings of the thirty-third annual ACM symposium on Theory of computing (2001) pp. 68–74.
  11. [11]G. Ivanyos, F. Magniez, and M. Santha, Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem, in Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures (2001) pp. 263–270.
  12. [12]K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen, Hidden translation and translating coset in quantum computing, SIAM Journal on Computing 43, 1 (2014).
  13. [13]M. E. S. Morales, The hidden subgroup problem in semidirect products and quasi-hamiltonian groups, arXiv preprint arXiv:2608.05321 (2026).arxiv.org/abs/2608.05321
  14. [14]Y. Inui and F. Le Gall, Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups, Quantum Information and Computation 7, 559–570 (2007).DOI
  15. [15]C. Moore, D. Rockmore, A. Russell, and L. Schulman, The hidden subgroup problem in affine groups: Basis selection in fourier sampling, arXiv preprint quant-ph/0211124 (2002).DOI
  16. [16]M. Ettinger and P. Høyer, On quantum algorithms for noncommutative hidden subgroups, in Annual Symposium on Theoretical Aspects of Computer Science (Springer, 1999) pp. 478–487.
  17. [17]G. Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, SIAM Journal on Computing 35, 170 (2005).arxiv.org/abs/quant-ph/0302112
  18. [18]P. Singhkanipa, V. Kasatkin, Z. Zhou, G. Quiroz, and D. A. Lidar, Demonstration of algorithmic quantum speedup for an abelian hidden subgroup problem, Physical Review X 15, 021082 (2025).
  19. [19]C. Moore, A. Russell, and L. J. Schulman, The symmetric group defies strong fourier sampling, SIAM Journal on Computing 37, 1842 (2008).
  20. [20]J.-S. Chen, E. Nielsen, M. Ebert, V. Inlek, K. Wright, V. Chaplin, A. Maksymov, E. Páez, A. Poudel, P. Maunz, et al., Benchmarking a trapped-ion quantum computer with 30 qubits, Quantum 8, 1516 (2024).DOI
  21. [21]D. R. Simon, On the power of quantum computation, SIAM journal on computing 26, 1474 (1997).
  22. [22]A. Nayak, Deterministic algorithms for the hidden subgroup problem, Quantum Information and Computation 22, 755–769 (2022).DOI
  23. [23]A. M. Childs, Lecture notes on quantum algorithms, University of Maryland, accessed October 2026.
  24. [24]M. Ettinger, P. Høyer, and E. Knill, The quantum query complexity of the hidden subgroup problem is polynomial, Information Processing Letters 91, 43 (2004).DOI
  25. [25]G. Lee, J. A. Gross, M. Fukami, and Z. Jiang, Learning t-conjugated stabilizers: The multiple-squares dihedral stateshp, arXiv preprint arXiv:2510.07872 (2025).arxiv.org/abs/2510.07872
  26. [26]O. O’Brien, Code and data for: Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer (2026).DOI
  27. [27]A. Shukla and P. Vedula, An efficient quantum algorithm for preparation of uniform quantum superposition states, Quantum Information Processing 23, 38 (2024).DOI
  28. [28]N. Gleinig and T. Hoefler, An efficient algorithm for sparse quantum state preparation, in Proceedings of the 58th Annual ACM/IEEE Design Automation Conference, DAC ’21 (IEEE Press, 2022) p. 433–438.DOI
  29. [29]K. Suresh and S. Suresh, Pyencode: an open-source library for structured quantum state preparation, Quantum Science and Technology 11, 045032 (2026).arxiv.org/abs/2603.28259
  30. [30]R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, Quantum circuits for isometries, Physical Review A 93, 032318 (2016).DOI
  31. [31]L. Hales and S. Hallgren, An improved quantum fourier transform algorithm and applications, in Proceedings 41st Annual Symposium on Foundations of Computer Science (IEEE, 2000) pp. 515–525.
  32. [32]L. R. Hales, The quantum Fourier transform and extensions of the abelian hidden subgroup problem (University of California, Berkeley, 2002).DOI
  33. [33]M. Mosca and C. Zalka, Exact quantum fourier transforms and discrete logarithm algorithms, International Journal of Quantum Information 2, 91 (2004).DOI
  34. [34]N.-H. Kuo and R. Wong, A quantum blustein’s algorithm for arbitrary-size quantum fourier transform, Physica Scripta 101, 385104 (2026).DOI
  35. [35]S. Khatri, R. LaRose, A. Poremba, L. Cincio, A. T. Sornborger, and P. J. Coles, Quantum-assisted quantum compiling, Quantum 3, 140 (2019).DOI
  36. [36]L. Madden and M. Simonetto, Best approximate quantum compiling problems, ACM Transactions on Quantum Computing 3, 10.1145/3505181 (2022).arxiv.org/abs/2106.05649
  37. [37]P. Rakyta and Z. Zimborás, Approaching the theoretical limit in quantum gate decomposition, Quantum 6, 710 (2022).DOI
  38. [38]N. A. Nemkov, E. O. Kiktenko, I. A. Luchnikov, and A. K. Fedorov, Efficient variational synthesis of quantum circuits with coherent multi-start optimization, Quantum 7, 993 (2023).DOI
  39. [39]J. Welch, D. Greenbaum, S. Mostame, and A. Aspuru-Guzik, Efficient quantum circuits for diagonal unitaries without ancillas, New Journal of Physics 16, 033040 (2014).
  40. [40]V. V. Shende, S. S. Bullock, and I. L. Markov, Synthesis of quantum logic circuits, in Proceedings of the 2005 Asia and South Pacific Design Automation Conference (2005) pp. 272–275.
  41. [41]Y. Li and S. C. Benjamin, Efficient variational quantum simulator incorporating active error minimization, Physical Review X 7, 021050 (2017).DOI
  42. [42]K. Temme, S. Bravyi, and J. M. Gambetta, Error mitigation for short-depth quantum circuits, Physical review letters 119, 180509 (2017).DOI
  43. [43]T. Giurgica-Tiron, Y. Hindy, R. LaRose, A. Mari, and W. J. Zeng, Digital zero noise extrapolation for quantum error mitigation, in 2020 IEEE international conference on quantum computing and engineering (QCE) (IEEE, 2020) pp. 306–316.
  44. [44]S. Endo, S. C. Benjamin, and Y. Li, Practical quantum error mitigation for near-future applications, Physical Review X 8, 031027 (2018).DOI

Paper details

vlnc:W_fp8gsc67
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Claude Opus 5.5

View statement
Looking for related papers…
Contents