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 -hedral groups , 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 , 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 , adjacent pairs succeed for small , and forgetful sampling saturates below unit success. For , , 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 , which can be solved using quantum circuits of size polynomial in 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 () is information-theoretically reconstructible as quantum queries provide enough information to determine the hidden subgroup, but the best known classical decoding algorithm takes time exponential in [16].1 In this work we evaluate how carefully choosing the measurement basis is crucial to ensuring both full and information-theoretic reconstructibility.
The -hedral groups interpolate between the dihedral group () and the affine group () for each prime . The main results of MRRS are that the -hedral HSP is fully reconstructible when , using strong Fourier sampling in an adapted basis, and information-theoretically reconstructible for all , 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 and a range of spanning the dihedral and affine extremes. Our contributions are as follows.
We introduce a small modification to the adjacent-pairs measurement, replacing with , which removes an ambiguity between and present in the original scheme.
We construct hardware-efficient circuits for each
component: numerically synthesised 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.
We observe the signatures predicted by theory: weak Fourier sampling carries no information about the hidden subgroup; adapted-basis sampling succeeds with probability ; adjacent-pairs sampling succeeds for small , where the adapted basis fails; and forgetful abelian sampling plateaus at success probability because it cannot distinguish within an orbit.
We compare against an exhaustively optimised, derandomised classical birthday algorithm and find that for , 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 is compiled into the oracle circuit; knowledge of 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 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 -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 . In our case we are considering the -hedral group for a given prime and divisor of . The group is composed of elements with , , and the group action is given by . Therefore, we begin by preparing the initial state:
We then act with an oracle invariant under the action of our hidden subgroup . In our instance the oracle we choose is:
where we choose a public such that , and is some random secret permutation. Our aim is to learn the secret value of . After acting with our oracle we have the following state:
We then measure the register containing the output of the oracle getting measurement result . As the oracle is invariant under the action of the subgroup we are now restricted to a superposition over the coset . Therefore, our post-measurement state is given by:
The next step is to perform the QFT over the full group . 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:
where is the set of irreducible representations of . In our instance has one-dimensional irreps given by:
for and distinct -dimensional irreps given by:
for . Therefore, we can rewrite (5) as:
where is a primitive root modulo and . It is clear that as . Every and gives a unique mod with , and hence we can perform the unique relabeling of the basis states as . Therefore, we have:
as generates every exactly once when we sum over and , and hence we can replace the summations with one over :
Now we can perform a unique relabeling of the first term from to giving:
where we have substituted back in our expression for . By taking the summation over in the first term we have:
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 (with probability ) we have the following post-measurement state:
If we simply perform abelian on the remaining register to get:
We then measure the register which gives with probability:
Therefore, the outcome occurs with probability . Hence, as we know we are able to solve the Hidden Subgroup Problem by finding with probability . Therefore, in the regime where the Hidden Subgroup Problem on is fully reconstructible (solvable with quantum samples by a quantum circuit of size ). However, in the regime of small this approach breaks down. For example, for constant we would require samples to determine using a mode based decoder which is less efficient than the 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 in the second register, we will simply store the exponent . 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 is:
We proceed by applying to the qubit storing the least significant bit of , which gives the following state:
for even . Therefore, upon measuring all the qubits we have that the expectation value of the least significant bit varies as in . The original MRRS paper instead applied just leading to a signal. They state that the total variation distance of this signal between any two distinct is bounded below by a constant, so in theory we can distinguish between different with only samples for all . However, under their signal it is impossible to distinguish from as:
The total-variation bound of [1] therefore holds only for pairs . Our slight modification of applying alleviates this and ensures that the Hidden Subgroup Problem on is information-theoretic reconstructible for all . However, there is no known classical decoder, so it is not shown to be fully reconstructible for all .
We can however decode the signal in 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 with the corresponding abelian Fourier transform given by . 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 (including ):
we apply to get:
Therefore, the probability of measuring irrep labels and is given by:
Taking for gives:
Therefore, this forgetful abelian sampling method cannot distinguish from other for . A decoder can therefore only identify the orbit of , as the average number of elements in a orbit is the success probability is capped at 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 as larger primes required larger circuits and subsequently too much hardware noise to observe a clear signal.
Figure 7. Adapted-basis circuit for in the field encoding. Controlled phases from and from act on the computation register . on gives and on gives ; shots with are discarded. We omit the register’s final and as is discarded.
Figure 8. Exponent-encoding circuit. applies the controlled phases from on the computation register as in Fig. 7, and applies the -dependent phases from (Fig. 9). The measurement on sets the sampling method: on for adjacent pairs, for the original MRRS scheme, for forgetful abelian sampling and no gate for weak Fourier sampling.
Figure 1. Weak Fourier sampling for with (a) and (b) , 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 , 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 , and secret shown in the figures) at 2,048 shots each, plus gate-folded (fold ) 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 . 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 branch, on the second register completes the non-abelian QFT on the one-dimensional irreps, so the measured is the label of ; on the branch the irrep is fixed by alone, and weak sampling discards the second register anyway. For the irrep is with where is the primitive root with , and for it is . For our subgroups only occurs, as seen in Eq. (12).
Figure 2 demonstrates that, unlike weak fourier sampling, strong fourier sampling in an adapted basis gives with high probability. Figure 3 shows that the success probability due to strong fourier sampling in the adapted basis follows the theoretical prediction of . Further, it shows that for fixed we have decaying success probability with increasing , and hence we require a different sampling method for small .
Figure 2. Strong Fourier sampling in the adapted basis for , with (a) , (b) and (c) (2,048 shots per circuit; 95% Wilson intervals for raw data and bootstrap intervals for ZNE). Conditioned on , the candidate peaks at the hidden with ideal height .
Figure 3. Success probability of adapted-basis sampling for , (a) against for and (b) against for (2,048 shots each; 95% bootstrap intervals). The hardware follows the prediction , and for fixed it decays as increases.
Strong sampling via adjacent pairs is demonstrated by Figure 4 and demonstrates a high probability of success even for small . Figure 4 also confirms the theoretical prediction that the original protocol of MRRS for adjacent pairs fails to distinguish from . The theory predicts that we only need samples to distinguish . Unfortunately, we cannot confirm this prediction with our small sample of three different .
Figure 4. Strong Fourier sampling of adjacent pairs for , with , applying (a)–(c) and (d)–(f) to the least significant bit of (2,048 shots per circuit, 95% bootstrap intervals). The Fourier coefficient at is the real part of for , and of for , with , summed over the shots with and divided by the total number of shots. With the signal peaks only at , whereas cannot distinguish from .
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 but not which we have within the orbit. Figure 5 demonstrates that this holds as we can successfully distinguish from but not from as share an orbit.
Figure 5. Joint probability of under forgetful abelian sampling for , with (a) , (b) and (c) , from raw hardware data (2,048 shots each). As and share the orbit they cannot be distinguished, whereas 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 ) and plot the probability of decoding a uniformly random 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 against total oracle queries for with (top) and (bottom), using (a,d) the adapted basis, (b,e) adjacent pairs and (c,f) forgetful abelian sampling. Each of 20,000 trials draws 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 .
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 which determines the secret via:
where . This requires 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 ) and some different pairs test the same . 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 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 and . 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: (dihedral) and (affine). We see that as expected the adapted basis outperforms the adjacent pairs method for large but loses out to it for small . It is also interesting to consider the behavior of the forgetful abelian sampling. We decode from the forgetful abelian signal using a maximum likelihood estimator. We see that the probability of successfully decoding via forgetful abelian sampling reaches a plateau before reaching 1. This corresponds to the theoretical prediction that forgetful abelian sampling cannot distinguish within the same orbit, and as expected the success probability is capped at in both figures. We can also see that the performance of the adjacent pairs sampling method is largely independent of as predicted by the theory, unlike the adapted basis method which is heavily dependent on .
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 and . For the adapted-basis method, the mode decoder matches the maximum likelihood decoder at , but significantly underperforms at . This suggests that, for small , 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 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 computation basis states required by (1) we use the Shukla-Vedula algorithm [27] which uses qubits and gates and we denote with .
To prepare the state we employ the Gleinig-Hoefler algorithm [28] via the open source PyEn- code library [29]. However, for large 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 .
Oracle
To implement the action of the oracle we use fourier conjugation. First, we prepare the computation register into a uniform superposition over basis states using the Shukla-Vedula algorithm ():
Then we act with controlled-phase gates with phase from the -th qubit of the first register on the -th qubit of the computation register:
where
where , . Similarly, we act with controlled-phase gates with phase from the -th qubit of the second register on the -th qubit of the computation register to give overall transformation:
Next, we act with upon the computation register which gives:
Finally, we apply a random secret permutation to the computational basis elements of the computation register. Thus we have completed our application of the oracle:
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:
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 or permutation 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 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 on the first register () giving state:
This can be rewritten as:
Therefore, if we uncompute controlled upon the first register being in state then we apply the full non-abelian QFT giving state:
This uncomputation is simply the inverse of the state preparation circuit () we used to prepare . As we discard the results of the second register if the first register is measured to be , 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 is a unitary on acting as
realised on qubits. Its action on the remaining dimensions is unconstrained.
There exist many asymptotically efficient methods for implementing for generic [4, 31, 32, 33, 34]. However, for small 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 gates. Every in our circuits is directly followed by a full basis measurement, so the phase of each output is irrelevant. Hence, for a given ansatz we use BFGS to maximise :
| Transform | Qubits | Ours | Qiskit |
| 2 | 2 | 3 | |
| 3 | 8 | 19 | |
| 3 | 7 | 19 | |
| 3 | 10 | 19 |
Table 1. Two-qubit () gate counts for on qubits, comparing our numerically synthesised circuits with Qiskit’s quantum Shannon decomposition of .
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 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 and , to produce:
| Qubits () | Ours | Qiskit | |
| 2 | 3 | 3 | |
| 3 | 6 | 15 | |
| 6 | 19 | 39 |
Table 2. Two-qubit () gate counts for the oracle diagonal at , comparing our Walsh-series synthesis with one Qiskit diagonal gate per qubit of . Counts are the same for every .
However, it does increase the complexity of applying the oracle as we can no longer use controlled-phase gates to apply the contribution from the second register. Instead we act with different -qubit diagonal gates, which we collectively denote , acting on and the -th qubit of the register ():
We synthesize these gates using techniques introduced by [39]. We first rewrite as a Walsh-Fourier series given by . This reduces (A16) to:
We define the Walsh operator as:
Hence we can further reduce (A16) to:
We implement this gate by acting with CNOTs upon the register such that every parity occurs at least once on some qubit. When that parity is stored we can then perform with a single between the parity qubit and the -th qubit of and with a single gate just on the parity qubit.
As is only restricted on we need only have non-zero . Therefore, we do not need to implement for every possible parity. Hence, we exhaustively search all the different methods of iterating through parities to find the shortest CNOT sequence that we can use to implement this gate. Figure 9 shows an example of our implementation of for , .
Figure 9. Walsh-series implementation of for , . A CNOT walk stores each required parity of on a single qubit, which is then coupled to each qubit of with an gate.
This methodology results in fewer 2-qubit gates for 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 gate by 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 and the original circuit . Assuming the noise drives the state towards the maximally mixed state, so that the signal decays exponentially with , we model the expectation values as
Figure 10. Gate folding for zero-noise extrapolation. Each is replaced by with 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.
where is the Hilbert-space dimension, so that is the expectation value of in the maximally mixed state. Hence, we can derive:
We fit a single 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 and histograms, refit and recompute the ZNE value. We perform 1000 replicates and record the 2.5th and 97.5th percentiles for the ZNE value.
References
- [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]P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review 41, 303 (1999).
- [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]A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem, arXiv preprint quant-ph/9511026 (1995).
- [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]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]O. Regev, Quantum computation and lattice problems, SIAM Journal on Computing 33, 738 (2004).
- [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]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]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]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]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]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]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]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]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]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]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]C. Moore, A. Russell, and L. J. Schulman, The symmetric group defies strong fourier sampling, SIAM Journal on Computing 37, 1842 (2008).
- [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]D. R. Simon, On the power of quantum computation, SIAM journal on computing 26, 1474 (1997).
- [22]A. Nayak, Deterministic algorithms for the hidden subgroup problem, Quantum Information and Computation 22, 755–769 (2022).DOI
- [23]A. M. Childs, Lecture notes on quantum algorithms, University of Maryland, accessed October 2026.
- [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]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]O. O’Brien, Code and data for: Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer (2026).DOI
- [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]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]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]R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, Quantum circuits for isometries, Physical Review A 93, 032318 (2016).DOI
- [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]L. R. Hales, The quantum Fourier transform and extensions of the abelian hidden subgroup problem (University of California, Berkeley, 2002).DOI
- [33]M. Mosca and C. Zalka, Exact quantum fourier transforms and discrete logarithm algorithms, International Journal of Quantum Information 2, 91 (2004).DOI
- [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]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]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]P. Rakyta and Z. Zimborás, Approaching the theoretical limit in quantum gate decomposition, Quantum 6, 710 (2022).DOI
- [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]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]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]Y. Li and S. C. Benjamin, Efficient variational quantum simulator incorporating active error minimization, Physical Review X 7, 021050 (2017).DOI
- [42]K. Temme, S. Bravyi, and J. M. Gambetta, Error mitigation for short-depth quantum circuits, Physical review letters 119, 180509 (2017).DOI
- [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]S. Endo, S. C. Benjamin, and Y. Li, Practical quantum error mitigation for near-future applications, Physical Review X 8, 031027 (2018).DOI









