# Quantum Fourier Transform using Dynamic Circuits

Elisa Bäumer<EMAIL_ADDRESS>IBM Quantum, IBM Research – Zurich, 8803
Rüschlikon, Switzerland  Vinay Tripathi  Department of Physics & Astronomy,
and Center for Quantum Information Science & Technology, University of
Southern California, Los Angeles, California 90089, USA  Alireza Seif  IBM
Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA
Daniel Lidar  Departments of Electrical & Computer Engineering, Chemistry,
Physics & Astronomy, and Center for Quantum Information Science & Technology,
University of Southern California, Los Angeles, California 90089, USA  Derek
S. Wang  IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY
10598, USA

###### Abstract

In dynamic quantum circuits, classical information from mid-circuit
measurements is fed forward during circuit execution. This emerging capability
of quantum computers confers numerous advantages that can enable more
efficient and powerful protocols by drastically reducing the resource
requirements for certain core algorithmic primitives. In particular, in the
case of the $n$-qubit quantum Fourier transform followed immediately by
measurement, the scaling of resource requirements is reduced from $O(n^{2})$
two-qubit gates in an all-to-all connectivity in the standard unitary
formulation to $O(n)$ mid-circuit measurements in its dynamic counterpart
without any connectivity constraints. Here, we demonstrate the advantage of
dynamic quantum circuits for the quantum Fourier transform on IBM’s
superconducting quantum hardware with certified process fidelities of $>50\%$
on up to $16$ qubits and $>1\%$ on up to $37$ qubits, exceeding previous
reports across all quantum computing platforms. These results are enabled by
our contribution of an efficient method for certifying the process fidelity,
as well as of a dynamical decoupling protocol for error suppression during
mid-circuit measurements and feed-forward within a dynamic quantum circuit
that we call “feed-forward-compensated dynamical decoupling” (FC-DD). Our
results demonstrate the advantages of leveraging dynamic circuits in
optimizing the compilation of quantum algorithms.

Quantum computations have the potential to be more powerful than classical
calculations for certain applications [1]. However, especially for
calculations that do not utilize quantum effects, such as the addition of two
bits, classical computations are likely to be faster and more reliable.
Exploiting these trade-offs has resulted in the development of dynamic quantum
circuits, namely quantum circuits that collect classical information from mid-
circuit measurements, classically process the results, and feed-forward
operations within a single shot of the circuit. A flagship application of
dynamic circuits is active quantum error correction, a likely requirement of
large-scale quantum computations [2, 3]. Other applications of dynamic
circuits include the generation of long-range entanglement in shallow quantum
circuits used, e.g., for measurement-based quantum computations [4, 5], state
preparation [6, 7] or the observation of phase transitions [8, 9, 10, 11, 10,
12], resulting in experimental studies that have demonstrated advantages with
dynamic circuits for comparatively simple state preparations or gate
teleportation [13, 14, 15, 16, 17, 18, 19, 20].

These studies typically do not explore a crucial capability of dynamic
circuits: the semi-classical fan-out gate, which operates on many qubits at
the same time after conditioning on the same classical output. Importantly, as
the mid-circuit-measured qubits collapse to a classical state, the semi-
classical fan-out gate can replace conditioned gates applied at the end of an
algorithm just before the measurement of the conditioned qubit. It is then
straightforward to see that the outcomes should be the same using the
principle of deferred measurement, which states that any measurement can be
postponed to the end of a quantum algorithm without affecting the algorithm’s
outcome [1]. Although the requirement that the measurement must immediately
follow the semi-classical fan-out gate limits some applications, there do
exist useful subroutines to which this idea can be applied. One such example
is the quantum Fourier transform followed immediately by a measurement [21],
or “QFT + measurement” (QFT+M), a subroutine used in both Shor’s algorithm
[22] and in quantum phase estimation [23], as well as in emerging applications
[24, 25].

Here, we experimentally demonstrate the QFT+M subroutine using dynamic
circuits with certified process fidelities on up to 40 qubits using error
suppression via dynamical decoupling (DD). The performance of the dynamic
circuits-based implementation far exceeds that of its unitary implementation
in this work and others on any quantum computing platform to date. To realize
this comparison, we contribute an efficient method of certifying the process
fidelity, as well as a DD protocol for mid-circuit measurements and feed-
forward within a dynamic circuit. This demonstration of the advantage of
dynamic circuits for a core quantum algorithmic primitive promises broader
potential for compiling larger-scale quantum algorithms with dynamic circuits.

Figure 1: The quantum Fourier transform with measurements implemented using
(a) a unitary circuit and (b) a dynamic circuit, with
$R_{k}=\begin{pmatrix}&1&0\\\ &0&\mathrm{e}^{2\pi i/2^{k}}\end{pmatrix}$.
Figure 2: Demonstration of the advantage of the dynamic circuit implementation
of QFT+M versus the unitary version. (a) Process fidelity
$\mathcal{F}_{\mathrm{proc}}$ of QFT+M with and without DD on ibm_kyiv. All
curves include readout mitigation on the final readouts via the mthree method
[26]. Shading corresponds to error bars bootstrapped over shots and input
bitstrings. (b) DD scheme applied to each qubit (except the one with readout)
following the Hadamard gate (H) throughout the readout with length
$\tau_{\mathrm{readout}}=1244$ ns and feed-forward with time
$\tau_{\mathrm{FF}}=653$ ns. No pulses can be applied during the feed-forward
time, so we insert an X2 sequence with uniform spacing on either end, cutting
into the readout time by $\tau_{\mathrm{FF}}$. In the remaining
$\tau:=\tau_{\mathrm{readout}}-\tau_{\mathrm{FF}}=591$ ns idle period, we
insert a uniformly spaced XY4 sequence. (c) To visualize the difference in
QFT+M with the unitary vs. dynamic implementation, we first prepare a periodic
state over 10 qubits, $\sum_{k=0}^{N/4-1}\ket{3+4k}$ for $N=2^{10}=1024$,
where we expect the probability of each state $\ket{3+4k}$ to be $1/256$ with
variations largely due to shot noise. After applying QFT, we expect 4 peaks
with probability 1/4 each and observe stronger agreement for the
implementation with dynamic circuits.

Theory.— As shown in Fig. 1(a), the traditional unitary QFT+M circuit requires
$O(n^{2})$ two-qubit gates with all-to-all connectivity between $n$ qubits.
Transpiling to device architectures with limited connectivity requires larger
gate counts to mediate SWAPs [27, 28] that can be traded off for increased
depth [29], although these increased resources can then be compensated with
approximate compilation [30, 31]. Note that the controlled phase gates $R_{k}$
are symmetric, therefore allowing the upper or lower qubits to play the role
of control or target qubits interchangeably. According to the principle of
deferred measurement, quantum gates commute with measurements when the qubit
being measured is the control qubit. This can be applied to replace
conditional quantum operations with classically controlled operations [1]. The
result is the corresponding dynamic circuit for QFT+M as shown in Fig. 1(b).
Crucially, this formulation does not have qubit connectivity requirements and
the number of mid-circuit measurements with feed-forward scales only as
$O(n)$.

To quantify the performance of QFT+M, we present an efficient method for
certifying the process fidelity for a noisy unitary followed by a projective
measurement. While there have been proposals for benchmarking the success
probability of such a process [32], these measures are based on normalizing
the classical fidelity and therefore do not define a proper quantum fidelity
measure. In Appendix A, we derive a general expression for the process
fidelity of a quantum channel $\mathcal{V}=\Pi\circ\mathcal{U}$ comprising a
unitary operation $\mathcal{U}$ followed by a measurement $\Pi$. This leads to
the following expression for the fidelity of its noisy realization
$\tilde{\mathcal{V}}=\Pi\circ\tilde{\mathcal{U}}$, e.g., the noisy QFT+M:

$\displaystyle\mathcal{F}_{\mathrm{proc}}(\mathcal{V},\tilde{\mathcal{V}})$
$\displaystyle=\left[\frac{1}{2^{n}}\sum_{k=1}^{2^{n}}\sqrt{\text{Pr}\left(k|\tilde{\mathcal{QFT}}(\sigma_{k}^{\ast})\right)}\right]^{2},$
(1)

where $\tilde{\mathcal{QFT}}$ describes the noisy QFT,
$\sigma_{k}^{\ast}:=QFT^{\dagger}\ket{k}\\!\\!\bra{k}QFT$ the noise-free
inverse-QFT applied to the computational basis state $\ket{k}$ (binary
representation of $k$), and $\text{Pr}(x|\rho)$ the probability of measuring
the output $x$ given a state $\rho$. Therefore, a practical scheme to evaluate
this expression is as follows: prepare the initial states $\sigma_{k}^{\ast}$,
apply the noisy $\tilde{\mathcal{QFT}}$, and combine the probabilities to
measure the respective outputs $k$. This resembles circuit mirroring [34, 35],
but significantly, one can prepare the initial states $\sigma_{k}^{\ast}$ with
high fidelity as $QFT^{\dagger}\ket{k}=\bigotimes_{l=1}^{n}R_{Z}(-\pi
k/2^{l},l)H^{\otimes n}\ket{0}$, where the $R_{Z}(\phi,l)$ gate with angle
$\phi$ on qubit $l$ can be implemented virtually and hence noiselessly [36].
The scheme is efficient since, despite the fact that the number of different
initial states $\sigma_{k}^{\ast}$ is $2^{n}$, we can sample $m$ different
values $\\{k_{l}\\}_{l=1..m}$, $k_{l}\in\\{1,..,2^{n}\\}$ and estimate the
process fidelity as

$\displaystyle\mathcal{F}_{\mathrm{proc}}(\mathcal{V},\tilde{\mathcal{V}})$
$\displaystyle\approx\frac{m}{m-1}\left[\frac{1}{m}\sum_{l=1}^{m}\sqrt{\text{Pr}\left(k_{l}|\tilde{\mathcal{QFT}}(\sigma_{k_{l}}^{\ast})\right)}\right]^{2}$
$\displaystyle\quad-\frac{1}{m(m-1)}\sum_{l=1}^{m}\text{Pr}\left(k_{l}|\tilde{\mathcal{QFT}}(\sigma_{k_{l}}^{\ast})\right).$
(2)

See Appendix A for details.

Results without DD.— In Fig. 2(a), we compare the process fidelity
$\mathcal{F}_{\mathrm{proc}}$ of QFT+M on one of IBM’s superconducting quantum
processors, ibm_kyiv, for the unitary and dynamic circuits shown in Fig. 1.
The experimental details can be found in Appendix B. Comparing the “‘Dynamic
(no DD)” and “‘Unitary (no DD)” curves, we see that the dynamic circuit
implementation already outperforms the unitary one. However, without error
suppression, the fidelities drop below $1\%$ for $n>9$ qubits, and the
performance difference becomes negligible. To improve performance, we next
consider the incorporation of error suppression. As the idling time scales
quadratically with $n$, we expect to see a drastic increase in
$\mathcal{F}_{\mathrm{proc}}$ when applying dynamical decoupling (DD).

Results with DD.— Dynamical decoupling [37, 38, 39], whose origins are in
early spin-echo experiments [40, 41], is a commonly used quantum error
suppression method that has been used for years on various experimental
quantum platforms [42]. In essence, DD involves applying a sequence of pulses
from a group of unitary operations that group-average the system-bath
interaction; for every such interaction, a sequence can be found for which
this average is zero [43, 44]. In particular, in the single-qubit setting,
this holds for the Pauli group, and the result is the well-known XY4 sequence.
DD has been applied to suppress decoherence [45, 46, 47, 48, 49, 50] and
crosstalk errors [51, 52, 53, 54], improve quantum volume [55] and algorithmic
fidelity [56, 57], culminating in recent algorithmic quantum speedup
demonstrations [58, 59].

A major challenge in using DD is that pulse imperfections can significantly
impact performance. Thus, a careful choice of the DD sequence is necessary.
For the unitary implementation, we use the universally robust (UR$p$) sequence
family [60], which was designed to suppress pulse axis and angle errors. It
suppresses pulse errors up to $O(\epsilon^{p/2})$ using $p$ pulses, where
$\epsilon$ is the nominal infidelity [60]. Varying $p$, and also comparing
with other sequences from the DD survey [49], we found that UR10 performed
optimally in the setting of our experiments when inserted into the idle
periods of the unitary circuit shown in Fig. 1(a). This strategy is similar to
the one used in most other recent DD experiments referenced above. However, a
different strategy is needed for our dynamic circuits because they incorporate
feed-forward; the corresponding DD scheme is illustrated in Fig. 2(b), and we
next explain its design.

First, we note that current experimental constraints prevent the application
of DD pulses immediately after the measurement pulse during the feed-forward
operation with length $\tau_{\text{FF}}=653$ ns, which is the time required to
logically process mid-circuit measurements and feed-forward a quantum
operation. Therefore, to maximize the suppression of noise during this feed-
forward time with two uniformly spaced X pulses (the X2 sequence) [40, 41], we
apply an X pulse at the beginning and the end of the feed-forward time.
Because these pulses must be uniformly spaced, we do not insert any pulses for
$\tau_{\text{FF}}$ into the preceding readout time
$\tau_{\text{readout}}=1244$ ns, which consists of a measurement pulse of
$781$ ns followed by a delay of $463$ ns. In the remaining time of the readout
pulse $\tau:=\tau_{\text{readout}}-\tau_{\text{FF}}=591$ ns, the uniformly
spaced XY4 [61] sequence was inserted. We call this sequence feed-forward-
compensated DD (FC-DD).

When comparing the “no DD” curves with the “Dynamic (with FC-DD)” and “Unitary
(with DD)” curves, the fidelities for both the unitary and dynamic circuit
implementations drastically increase with the inclusion of DD. Most notably,
the fidelities observed for the dynamic circuit implementation with FC-DD are
larger than those reported on any platform thus far [62, 32, 63, 64, 65]. In
particular, we obtain fidelities $>1\%$ for up to 37 qubits, as compared to up
to 11 qubits with unitary circuits. The performance of the unitary circuits is
comparable to the demonstrations of QFT in recent benchmarking works [32, 63]
on IBM’s quantum hardware. To visualize the improvement of QFT+M with dynamic
circuits, we prepare a simple periodic state
$\sum_{k=0}^{2^{n}/4-1}|3+4k\rangle$ on $n=10$ qubits in Fig. 2(c) and compare
the ideal, unitary, and dynamic circuit implementation of QFT+M applied to
that state. While the implementation with dynamic circuits yields a sharply
peaked distribution that resembles that of the ideal case, the unitary
circuits result in a flatter distribution characterized by broad peaks. This
difference is expected given that the fidelities with DD are $6\%$ for unitary
circuits and $88\%$ for dynamic circuits with 10 qubits; see Fig. 2(a).

A different performance metric for the dynamic circuit implementation with FC-
DD—the “average result fidelity” with plurality vote—is reported in Appendix
C, and we similarly find that the present implementation outperforms the
previous ones.

Conclusion and Outlook.— In this work, we demonstrate the advantage of dynamic
quantum circuits, particularly for QFT+M, on IBM’s superconducting quantum
hardware. As first described in Ref. [21], by leveraging the capability of
dynamic circuits to perform mid-circuit measurements and feed-forward
operations, a reduction in scaling of the required resources can be achieved
from $O(n^{2})$ two-qubit gates to $O(n)$ mid-circuit measurements with no
connectivity constraints. Our experiments show
$\mathcal{F}_{\mathrm{proc}}>50\%$ on up to $16$ qubits and $>1\%$ on up to
$37$ qubits, setting new benchmarks across quantum computing platforms. This
advancement is enabled by our efficient certification of the process fidelity
and a context-aware DD protocol for dynamic circuits.

We emphasize that the fidelities are significantly improved in the presence of
a tailored DD sequence—FC-DD—that leverages the fact that the qubits are not
coupled and, therefore, suffer little crosstalk noise. Although this
assumption may not hold in some applications, we stress that useful cases do
exist, e.g., when implementing dynamic circuits with ancilla qubits or using
multiple registers such as in Shor’s algorithm. Moreover, future generations
of superconducting devices with tunable couplers [66] may suffer drastically
less nearest-neighbor crosstalk, suggesting even stronger potential for
advantage with dynamic circuits in such devices.

Looking ahead, the successful application of dynamic circuits to the QFT+M
subroutine suggests broader potential for optimizing and enabling quantum
algorithms. Additionally, refining error suppression techniques and developing
error mitigation methods for mid-circuit measurement and feed-forward
operations in dynamic circuits, such as adapting measurement-based
probabilistic error cancellation [67], will be crucial for unlocking their
full potential.

###### Acknowledgements.

We thank Diego Ristè, Maika Takita, Edward H. Chen, Oles Shtanko, Luke Govia,
Jay Gambetta, Emily Pritchett, and Sarah Sheldon for valuable discussions and
support. The research of VT and DL was supported by the ARO MURI grant
W911NF-22-S-0007. AS was sponsored by the Army Research Office under Grant
Number W911NF-21-1-0002. The views and conclusions contained in this document
are those of the authors and should not be interpreted as representing the
official policies, either expressed or implied, of the Army Research Office or
the U.S. Government. The U.S. Government is authorized to reproduce and
distribute reprints for Government purposes notwithstanding any copyright
notation herein.

## References

  * Nielsen and Chuang [2011] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, 2011).
  * Shor [1997a] P. W. Shor, Fault-tolerant quantum computation (1997a), arXiv:quant-ph/9605011 [quant-ph] .
  * Terhal [2015] B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015).
  * Jozsa [2005] R. Jozsa, An introduction to measurement based quantum computation, arXiv:0508124 (2005).
  * Raussendorf  _et al._ [2003] R. Raussendorf, D. E. Browne, and H. J. Briegel, Measurement-based quantum computation on cluster states, Phys. Rev. A 68, 022312 (2003).
  * Buhrman  _et al._ [2023] H. Buhrman, M. Folkertsma, B. Loff, and N. M. P. Neumann, State preparation by shallow circuits using feed forward (2023), arXiv:2307.14840 [quant-ph] .
  * Malz  _et al._ [2024] D. Malz, G. Styliaris, Z.-Y. Wei, and J. I. Cirac, Preparation of matrix product states with log-depth quantum circuits, Phys. Rev. Lett. 132, 040404 (2024).
  * Raussendorf  _et al._ [2005] R. Raussendorf, S. Bravyi, and J. Harrington, Long-range quantum entanglement in noisy cluster states, Phys. Rev. A 71, 062313 (2005).
  * Piroli  _et al._ [2021] L. Piroli, G. Styliaris, and J. I. Cirac, Quantum circuits assisted by local operations and classical communication: Transformations and phases of matter, Phys. Rev. Lett. 127, 220503 (2021).
  * Lu  _et al._ [2022] T.-C. Lu, L. A. Lessa, I. H. Kim, and T. H. Hsieh, Measurement as a shortcut to long-range entangled quantum matter, PRX Quantum 3, 040337 (2022).
  * Tantivasadakarn  _et al._ [2021] N. Tantivasadakarn, R. Thorngren, A. Vishwanath, and R. Verresen, Long-range entanglement from measuring symmetry-protected topological phases, arXiv:2112.01519 (2021).
  * Tantivasadakarn  _et al._ [2023] N. Tantivasadakarn, A. Vishwanath, and R. Verresen, Hierarchy of topological order from finite-depth unitaries, measurement, and feedforward, PRX Quantum 4, 020339 (2023).
  * Córcoles  _et al._ [2021] A. D. Córcoles, M. Takita, K. Inoue, S. Lekuch, Z. K. Minev, J. M. Chow, and J. M. Gambetta, Exploiting dynamic quantum circuits in a quantum algorithm with superconducting qubits, Phys. Rev. Lett. 127, 100501 (2021).
  * Foss-Feig  _et al._ [2023] M. Foss-Feig, A. Tikku, T.-C. Lu, K. Mayer, M. Iqbal, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, A. Hankin, N. Hewitt, C. V. Horst, M. Matheny, T. Mengle, B. Neyenhuis, H. Dreyer, D. Hayes, T. H. Hsieh, and I. H. Kim, Experimental demonstration of the advantage of adaptive quantum circuits, arXiv:2302.03029 (2023).
  * Iqbal  _et al._ [2023] M. Iqbal, N. Tantivasadakarn, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, A. Hankin, N. Hewitt, C. V. Horst, M. Matheny, T. Mengle, B. Neyenhuis, A. Vishwanath, M. Foss-Feig, R. Verresen, and H. Dreyer, Topological order from measurements and feed-forward on a trapped ion quantum computer, arXiv:2302.01917 (2023).
  * Moses  _et al._ [2023] S. Moses, C. Baldwin, M. Allman, R. Ancona, L. Ascarrunz, C. Barnes, J. Bartolotta, B. Bjork, P. Blanchard, M. Bohn, _et al._ , A race-track trapped-ion quantum processor, Phys. Rev. X 13, 041052 (2023).
  * Smith  _et al._ [2023] K. C. Smith, E. Crane, N. Wiebe, and S. Girvin, Deterministic constant-depth preparation of the aklt state on a quantum processor using fusion measurements, PRX Quantum 4, 020315 (2023).
  * Cao  _et al._ [2023] S. Cao, B. Wu, F. Chen, M. Gong, Y. Wu, Y. Ye, C. Zha, H. Qian, C. Ying, S. Guo, Q. Zhu, H.-L. Huang, Y. Zhao, S. Li, S. Wang, J. Yu, D. Fan, D. Wu, H. Su, H. Deng, H. Rong, Y. Li, K. Zhang, T.-H. Chung, F. Liang, J. Lin, Y. Xu, L. Sun, C. Guo, N. Li, Y.-H. Huo, C.-Z. Peng, C.-Y. Lu, X. Yuan, X. Zhu, and J.-W. Pan, Generation of genuine entanglement up to 51 superconducting qubits, Nature 619, 738 (2023).
  * Bäumer  _et al._ [2023] E. Bäumer, V. Tripathi, D. S. Wang, P. Rall, E. H. Chen, S. Majumder, A. Seif, and Z. K. Minev, Efficient long-range entanglement using dynamic circuits (2023), arXiv:2308.13065 [quant-ph] .
  * Chen  _et al._ [2023a] E. H. Chen, G.-Y. Zhu, R. Verresen, A. Seif, E. Bäumer, D. Layden, N. Tantivasadakarn, G. Zhu, S. Sheldon, A. Vishwanath, S. Trebst, and A. Kandala, Realizing the nishimori transition across the error threshold for constant-depth quantum circuits (2023a), arXiv:2309.02863 [quant-ph] .
  * Griffiths and Niu [1996] R. B. Griffiths and C.-S. Niu, Semiclassical fourier transform for quantum computation, Physical Review Letters 76, 3228–3231 (1996).
  * Shor [1997b] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26, 1484 (1997b), https://doi.org/10.1137/S0097539795293172 .
  * Kitaev [1995] A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem (1995), arXiv:quant-ph/9511026 [quant-ph] .
  * Wright  _et al._ [2024] L. Wright, C. M. Keever, J. T. First, R. Johnston, J. Tillay, S. Chaney, M. Rosenkranz, and M. Lubasch, Noisy intermediate-scale quantum simulation of the one-dimensional wave equation (2024), arXiv:2402.19247 [quant-ph] .
  * Paler [2022] A. Paler, Quantum fourier addition simplified to toffoli addition, Phys. Rev. A 106, 042444 (2022).
  * Nation  _et al._ [2021] P. D. Nation, H. Kang, N. Sundaresan, and J. M. Gambetta, Scalable mitigation of measurement errors on quantum computers, PRX Quantum 2, 040326 (2021).
  * Moore  _et al._ [2003] C. Moore, D. Rockmore, and A. Russell, Generic quantum fourier transforms (2003), arXiv:quant-ph/0304064 [quant-ph] .
  * Fowler  _et al._ [2004] A. G. Fowler, S. J. Devitt, and L. C. L. Hollenberg, Implementation of shor’s algorithm on a linear nearest neighbour qubit array (2004), arXiv:quant-ph/0402196 [quant-ph] .
  * Park and Ahn [2023] B. Park and D. Ahn, Reducing cnot count in quantum fourier transform for the linear nearest-neighbor architecture, Scientific Reports 13, 8638 (2023).
  * Barenco  _et al._ [1996] A. Barenco, A. Ekert, K.-A. Suominen, and P. Törmä, Approximate quantum fourier transform and decoherence, Physical Review A 54, 139 (1996).
  * Hales and Hallgren [2000] L. Hales and S. Hallgren, An improved quantum fourier transform algorithm and applications, in  _Proceedings 41st Annual Symposium on Foundations of Computer Science_ (2000) pp. 515–525.
  * Lubinski  _et al._ [2023] T. Lubinski, S. Johri, P. Varosy, J. Coleman, L. Zhao, J. Necaise, C. H. Baldwin, K. Mayer, and T. Proctor, Application-oriented performance benchmarks for quantum computing, IEEE Transactions on Quantum Engineering 4, 1 (2023).
  * [33] See Supplemental Material at URL-will-be-inserted-by-publisher for the derivation of our process fidelity estimation, experimental details and the average result success probability.
  * Proctor  _et al._ [2022] T. Proctor, K. Rudinger, K. Young, E. Nielsen, and R. Blume-Kohout, Measuring the capabilities of quantum computers, Nature Physics 18, 75 (2022).
  * Hines and Proctor [2023] J. Hines and T. Proctor, Scalable full-stack benchmarks for quantum computers (2023), arXiv:2312.14107 [quant-ph] .
  * McKay  _et al._ [2017] D. C. McKay, C. J. Wood, S. Sheldon, J. M. Chow, and J. M. Gambetta, Efficient $z$ gates for quantum computing, Phys. Rev. A 96, 022330 (2017).
  * Viola and Lloyd [1998] L. Viola and S. Lloyd, Dynamical suppression of decoherence in two-state quantum systems, Phys. Rev. A 58, 2733 (1998).
  * Khodjasteh and Lidar [2005] K. Khodjasteh and D. A. Lidar, Fault-tolerant quantum dynamical decoupling, Physical Review Letters 95, 180501 (2005).
  * Uhrig [2007] G. S. Uhrig, Keeping a quantum bit alive by optimized $\pi$-pulse sequences, Phys. Rev. Lett. 98, 100504 (2007).
  * Carr and Purcell [1954] H. Y. Carr and E. M. Purcell, Effects of diffusion on free precession in nuclear magnetic resonance experiments, Phys. Rev. 94, 630 (1954).
  * Meiboom and Gill [1958] S. Meiboom and D. Gill, Modified Spin‐Echo Method for Measuring Nuclear Relaxation Times, Review of Scientific Instruments 29, 688 (1958), https://pubs.aip.org/aip/rsi/article-pdf/29/8/688/19287064/688_1_online.pdf .
  * Suter and Álvarez [2016] D. Suter and G. A. Álvarez, Colloquium: Protecting quantum information against environmental noise, Rev. Mod. Phys. 88, 041001 (2016).
  * Zanardi [1999] P. Zanardi, Symmetrizing evolutions, Physics Letters A 258, 77 (1999).
  * Viola  _et al._ [1999] L. Viola, E. Knill, and S. Lloyd, Dynamical decoupling of open quantum systems, Physical Review Letters 82, 2417 (1999).
  * Pokharel  _et al._ [2018] B. Pokharel, N. Anand, B. Fortman, and D. A. Lidar, Demonstration of fidelity improvement using dynamical decoupling with superconducting qubits, Phys. Rev. Lett. 121, 220502 (2018).
  * Shirizly  _et al._ [2024] L. Shirizly, G. Misguich, and H. Landa, Dissipative dynamics of graph-state stabilizers with superconducting qubits, Phys. Rev. Lett. 132, 010601 (2024).
  * Souza [2021] A. M. Souza, Process tomography of robust dynamical decoupling with superconducting qubits, Quantum Information Processing 20, 237 (2021).
  * Gautam  _et al._ [2021] A. Gautam, Arvind, and K. Dorai, Protection of noisy multipartite entangled states of superconducting qubits via universally robust dynamical decoupling schemes (2021), arXiv:2112.05821 [quant-ph] .
  * Ezzell  _et al._ [2023] N. Ezzell, B. Pokharel, L. Tewala, G. Quiroz, and D. A. Lidar, Dynamical decoupling for superconducting qubits: A performance survey, Physical Review Applied 20, 064027 (2023).
  * Tong  _et al._ [2024] C. Tong, H. Zhang, and B. Pokharel, Empirical learning of dynamical decoupling on quantum processors (2024), arXiv:2403.02294 [quant-ph] .
  * Tripathi  _et al._ [2022] V. Tripathi, H. Chen, M. Khezri, K.-W. Yip, E. Levenson-Falk, and D. A. Lidar, Suppression of crosstalk in superconducting qubits using dynamical decoupling, Phys. Rev. Appl. 18, 024068 (2022).
  * Zhou  _et al._ [2023] Z. Zhou, R. Sitler, Y. Oda, K. Schultz, and G. Quiroz, Quantum crosstalk robust quantum control, Phys. Rev. Lett. 131, 210802 (2023).
  * Seif  _et al._ [2024] A. Seif, H. Liao, V. Tripathi, K. Krsulich, M. Malekakhlagh, M. Amico, P. Jurcevic, and A. Javadi-Abhari, Suppressing correlated noise in quantum computers via context-aware compiling (2024), arXiv:2403.06852 .
  * Evert  _et al._ [2024] B. Evert, Z. G. Izquierdo, J. Sud, H.-Y. Hu, S. Grabbe, E. G. Rieffel, M. J. Reagor, and Z. Wang, Syncopated dynamical decoupling for suppressing crosstalk in quantum circuits (2024), arXiv:2403.07836 [quant-ph] .
  * Jurcevic  _et al._ [2021] P. Jurcevic, A. Javadi-Abhari, L. S. Bishop, I. Lauer, D. F. Bogorin, M. Brink, L. Capelluto, O. Günlük, T. Itoko, N. Kanazawa, A. Kandala, G. A. Keefe, K. Krsulich, W. Landers, E. P. Lewandowski, D. T. McClure, G. Nannicini, A. Narasgond, H. M. Nayfeh, E. Pritchett, M. B. Rothwell, S. Srinivasan, N. Sundaresan, C. Wang, K. X. Wei, C. J. Wood, J.-B. Yau, E. J. Zhang, O. E. Dial, J. M. Chow, and J. M. Gambetta, Demonstration of quantum volume 64 on a superconducting quantum computing system, Quantum Sci. Technol. 6, 025020 (2021).
  * rav [2022] _2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_ (2022).
  * Pokharel and Lidar [2024] B. Pokharel and D. A. Lidar, Better-than-classical grover search via quantum error detection and suppression, npj Quantum Information 10, 23 (2024).
  * Pokharel and Lidar [2023] B. Pokharel and D. A. Lidar, Demonstration of algorithmic quantum speedup, Physical Review Letters 130, 210602 (2023).
  * Singkanipa  _et al._ [2024] P. Singkanipa, V. Kasatkin, Z. Zhou, G. Quiroz, and D. A. Lidar, Demonstration of algorithmic quantum speedup for an abelian hidden subgroup problem (2024), arXiv:2401.07934 [quant-ph] .
  * Genov  _et al._ [2017] G. T. Genov, D. Schraft, N. V. Vitanov, and T. Halfmann, Arbitrarily accurate pulse sequences for robust dynamical decoupling, Phys. Rev. Lett. 118, 133202 (2017).
  * Maudsley [1986] A. Maudsley, Modified carr-purcell-meiboom-gill sequence for nmr fourier imaging applications, Journal of Magnetic Resonance (1969) 69, 488 (1986).
  * Weinstein  _et al._ [2001] Y. S. Weinstein, M. A. Pravia, E. M. Fortunato, S. Lloyd, and D. G. Cory, Implementation of the quantum fourier transform, Phys. Rev. Lett. 86, 1889 (2001).
  * Amico  _et al._ [2023] M. Amico, H. Zhang, P. Jurcevic, L. S. Bishop, P. Nation, A. Wack, and D. C. McKay, Defining standard strategies for quantum benchmarks (2023), arXiv:2303.02108 [quant-ph] .
  * Vorobyov  _et al._ [2021] V. Vorobyov, S. Zaiser, N. Abt, J. Meinel, D. Dasari, P. Neumann, and J. Wrachtrup, Quantum fourier transform for nanoscale quantum sensing, npj Quantum Information 7, 124 (2021).
  * Pfeffer [2023] P. Pfeffer, Multidimensional quantum fourier transformation (2023), arXiv:2301.13835 [quant-ph] .
  * Stehlik  _et al._ [2021] J. Stehlik, D. M. Zajac, D. L. Underwood, T. Phung, J. Blair, S. Carnevale, D. Klaus, G. A. Keefe, A. Carniol, M. Kumph, M. Steffen, and O. E. Dial, Tunable coupling architecture for fixed-frequency transmon superconducting qubits, Phys. Rev. Lett. 127, 080505 (2021).
  * Gupta  _et al._ [2023] R. S. Gupta, E. van den Berg, M. Takita, K. Temme, and A. Kandala, Probabilistic error cancellation for measurement-based quantum circuits (2023), arXiv:2310.07825 [quant-ph] .
  * Chen  _et al._ [2023b] J.-S. Chen, E. Nielsen, M. Ebert, V. Inlek, K. Wright, V. Chaplin, A. Maksymov, E. Páez, A. Poudel, P. Maunz, and J. Gamble, Benchmarking a trapped-ion quantum computer with 29 algorithmic qubits (2023b), arXiv:2308.05071 [quant-ph] .

##  Appendix A Fidelity estimation

###  A.1 Process fidelity of a noisy unitary followed by a measurement

Consider a projective measurement in the $Z$-basis described by
$\Pi(\rho)=\sum_{k}\Pi_{k}(\rho)=\sum_{k}\pi_{k}\rho\pi_{k}$ (where
$\pi_{k}=\ket{k}\\!\\!\bra{k}$ and $\\{\pi_{k}\\}$ are a complete set of
orthogonal projectors), an ideal unitary map $\mathcal{U}(\rho)=U\rho
U^{\dagger}$, and its noisy implementation $\tilde{\mathcal{U}}$. Let the
ideal map be $\mathcal{V}=\Pi\circ\mathcal{U}$ and its noisy version be
$\tilde{\mathcal{V}}=\Pi\circ\tilde{\mathcal{U}}$. We can always formally
decompose the noisy unitary map as
$\tilde{\mathcal{U}}=\Lambda_{U}\circ\mathcal{U}$ where $\Lambda_{U}$ is a
$U$-dependent noise channel that captures all the noise acting during the
noisy implementation of the ideal unitary.

Writing $e_{ij}\equiv\ket{i}\\!\\!\bra{j}$, and noting that

$\displaystyle\Pi(A)$
$\displaystyle=\sum_{k}\pi_{k}A\pi_{k}=\sum_{k}\bra{k}A\ket{k}\pi_{k}$ (3a)
$\displaystyle=\sum_{k}\operatorname{Tr}(\pi_{k}A)\pi_{k}=\sum_{k}\langle\pi_{k},A\rangle\pi_{k},$
(3b)

where $\langle A,B\rangle=\operatorname{Tr}(A^{\dagger}B)=\langle
B,A\rangle^{*}$ is the Hilbert-Schmidt inner product and $A,B$ are arbitrary
operators, the corresponding Choi states are given by

$\displaystyle\rho_{\tilde{\mathcal{V}}}$
$\displaystyle\equiv(\mathbb{I}\otimes\tilde{\mathcal{V}})(\ket{\phi}\\!\\!\bra{\phi})=\frac{1}{d}\sum_{i,j=1}^{d}e_{ij}\otimes\Pi[\tilde{\mathcal{U}}(e_{ij})]$
(4a)
$\displaystyle=\frac{1}{d}\sum_{k=1}^{d}\sum_{i,j=1}^{d}\operatorname{Tr}[\pi_{k}\tilde{\mathcal{U}}(e_{ij})]e_{ij}\otimes\pi_{k}$
(4b) $\displaystyle=\frac{1}{d}\sum_{k}\tilde{\sigma_{k}}\otimes\pi_{k},$ (4c)

with

$\displaystyle\tilde{\sigma_{k}}$
$\displaystyle\equiv\sum_{i,j}\langle\pi_{k},\tilde{\mathcal{U}}(e_{ij})\rangle
e_{ij}=\sum_{i,j}\langle\tilde{\mathcal{U}}^{\dagger}(\pi_{k}),e_{ij}\rangle
e_{ij}$ (5a) $\displaystyle=\sum_{i,j}\langle
e_{ij},\tilde{\mathcal{U}}^{\dagger}(\pi_{k})\rangle^{*}e_{ij}=[\tilde{\mathcal{U}}^{\dagger}(\pi_{k})]^{*}=\tilde{\mathcal{U}}^{T}(\pi_{k}),$
(5b)

where we used $\langle A,\Phi(B)\rangle=\langle\Phi^{\dagger}(A),B\rangle$ and
$[\Phi(\pi_{k})]^{\dagger}=[\sum_{\alpha}K_{\alpha}\pi_{k}K_{\alpha}^{\dagger}]^{\dagger}=\Phi(\pi_{k})$
for any CP map $\Phi$ with Kraus operators $\\{K_{\alpha}\\}$.

Similarly, after dropping the tilde everywhere:

$\rho_{\mathcal{V}}\equiv(\mathbb{I}\otimes\mathcal{V})(\ket{\phi}\\!\\!\bra{\phi})=\frac{1}{d}\sum_{k}\sigma_{k}\otimes\pi_{k}.$
(6)

Note that if $U$ is unitary then so is $U^{T}$ [since transposing
$U^{\dagger}U=I$ implies $U^{T}U^{*}=I$]. Thus

$\sigma_{k}=\mathcal{U}^{T}(\pi_{k})$ (7)

is a pure state. Moreover, the $\\{\sigma_{k}\\}$ also form a (rotated)
complete set of orthogonal projectors:
$\sigma_{k}\sigma_{l}=\delta_{kl}\sigma_{k}$. Therefore

$\rho_{\mathcal{V}}^{2}=\frac{1}{d^{2}}\sum_{k,l}\sigma_{k}\sigma_{l}\otimes\pi_{k}\pi_{l}=\frac{1}{d}\rho_{\mathcal{V}},$
(8)

so that $\sqrt{\rho_{\mathcal{V}}}=\sqrt{d}\rho_{\mathcal{V}}$ is the unique
positive semi-definite square-root of $\rho_{\mathcal{V}}$.

Moreover, the results above mean that we can describe $\sigma_{k}$ and
$\tilde{\sigma_{k}}$ as the ideal and noisy transposed unitaries
$\mathcal{U}^{T}$ and $\tilde{\mathcal{U}}^{T}$, respectively, applied to the
computational state $\ket{k}$.

The process fidelity of two channels $\mathcal{V}$, $\tilde{\mathcal{V}}$ is
given by the state fidelity of their Choi states, i.e., the Uhlmann fidelity
$\mathcal{F}(\rho_{\mathcal{V}},\rho_{\tilde{\mathcal{V}}})=\|\sqrt{\rho_{\mathcal{V}}}\sqrt{\rho_{\tilde{\mathcal{V}}}}\|^{2}_{1}$
($\|\cdot\|_{1}$ is the trace norm), which we can simplify as follows:

$\displaystyle\mathcal{F}(\rho_{\mathcal{V}},\rho_{\tilde{\mathcal{V}}})$
$\displaystyle=\left[\operatorname{Tr}\sqrt{\sqrt{\rho_{\mathcal{V}}}\rho_{\tilde{\mathcal{V}}}\sqrt{\rho_{\mathcal{V}}}}\right]^{2}$
(9a)
$\displaystyle=\left[\operatorname{Tr}\sqrt{d\rho_{\mathcal{V}}\rho_{\tilde{\mathcal{V}}}\rho_{\mathcal{V}}}\right]^{2}$
(9b)
$\displaystyle=\frac{1}{d^{2}}\left[\operatorname{Tr}\sqrt{\sum_{k}\sigma_{k}\tilde{\sigma_{k}}\sigma_{k}\otimes\pi_{k}}\right]^{2}$
(9c)
$\displaystyle=\frac{1}{d^{2}}\left[\operatorname{Tr}\sqrt{\sum_{k}\operatorname{Tr}(\sigma_{k}\tilde{\sigma_{k}})\sigma_{k}\otimes\pi_{k}}\right]^{2}$
(9d)
$\displaystyle=\frac{1}{d^{2}}\left[\operatorname{Tr}\sum_{k}\sqrt{\operatorname{Tr}(\sigma_{k}\tilde{\sigma_{k}}})\sigma_{k}\otimes\pi_{k}\right]^{2}$
(9e)

where in Eq. 9d we used the fact that $\sigma_{k}$ is pure, and in the last
equality we used

$\displaystyle\left[\sum_{k}\sqrt{\operatorname{Tr}(\sigma_{k}\tilde{\sigma_{k}})}\sigma_{k}\otimes\pi_{k}\right]^{2}$
$\displaystyle\qquad=\sum_{k,l}\sqrt{\operatorname{Tr}(\sigma_{k}\tilde{\sigma_{k}})}\sqrt{\operatorname{Tr}(\sigma_{l}\tilde{\sigma_{l}})}\sigma_{k}\sigma_{l}\otimes\pi_{k}\pi_{l}$
(10a)
$\displaystyle\qquad=\sum_{k}\operatorname{Tr}(\sigma_{k}\tilde{\sigma_{k}})\sigma_{k}\otimes\pi_{k},$
(10b)

to determine the square root. As
$\operatorname{Tr}(\sigma_{k}\otimes\pi_{k})=1$ $\forall k$, the fidelity
simplifies to

$\mathcal{F}_{\mathrm{proc}}(\mathcal{V},\tilde{\mathcal{V}})=\left[\frac{1}{d}\sum_{k=1}^{d}\sqrt{\operatorname{Tr}(\sigma_{k}\tilde{\sigma_{k}})}\right]^{2}.$
(11)

This can be related to the classical case, where the fidelity between two
random variables $X$ and $Y$ with respective probability distributions
$p=(p_{1},\ldots,p_{n})$ and $q=(q_{1},\ldots,q_{n})$ is given by
$F(X,Y)=\left(\sum_{i}{\sqrt{p_{i}q_{i}}}\right)^{2}$.

Now, note that

$\displaystyle\operatorname{Tr}(\sigma_{k}\tilde{\sigma_{k}})$
$\displaystyle=\langle\sigma_{k}^{\dagger},\tilde{\sigma_{k}}\rangle=\langle\sigma_{k}^{\dagger},\tilde{\mathcal{U}}^{T}(\pi_{k})\rangle$
(12a)
$\displaystyle=\langle\tilde{\mathcal{U}}^{*}(\sigma_{k}^{\dagger}),\pi_{k}\rangle=(\langle\tilde{\mathcal{U}}^{*}(\sigma_{k}^{\dagger}),\pi_{k}\rangle)^{*}$
(12b)
$\displaystyle=\langle\pi_{k},\tilde{\mathcal{U}}^{*}(\sigma_{k}^{\dagger})\rangle=\langle\pi_{k},\tilde{\mathcal{U}}^{*}(\sigma_{k})\rangle,$
(12c)

where in the second line we used the fact that
$\operatorname{Tr}(\sigma_{k}\tilde{\sigma_{k}})$ must be non-negative (hence
real) since $\mathcal{F}_{\mathrm{proc}}(\mathcal{V},\tilde{\mathcal{V}})\geq
0$, and in the last equality we used the fact that $\sigma_{k}$ is a quantum
state.

Next, writing the CP map $\tilde{\mathcal{U}}$ in terms of its Kraus operators
$\\{K_{\alpha}\\}$, we have

$\displaystyle[\tilde{\mathcal{U}}^{*}(\sigma_{k})]^{*}$
$\displaystyle=\sum_{\alpha}(K_{\alpha}^{*}\sigma_{k}K_{\alpha}^{T})^{*}=\sum_{\alpha}K_{\alpha}\sigma_{k}^{*}K_{\alpha}^{\dagger}$
(13a) $\displaystyle=\tilde{\mathcal{U}}(\sigma_{k}^{*}),$ (13b)

where $\sigma_{k}^{*}=\mathcal{U}^{\dagger}(\pi_{k})$ is the state
corresponding to the time-reversed ideal unitary $\mathcal{U}$. Since
$\tilde{\mathcal{U}}(\sigma_{k}^{*})$ is also a state, i.e., is positive-semi
definite, it is invariant under complex conjugation. Thus, inserting
$\tilde{\mathcal{U}}^{*}(\sigma_{k})=\tilde{\mathcal{U}}(\sigma_{k}^{*})$ into
the fidelity and combining Eqs. (11)-(13) finally yields

$\displaystyle\mathcal{F}_{\mathrm{proc}}(\mathcal{V},\tilde{\mathcal{V}})$
$\displaystyle=\left[\frac{1}{d}\sum_{k=1}^{d}\sqrt{\bra{k}\tilde{\mathcal{U}}(\sigma_{k}^{*})\ket{k}}\right]^{2}$
(14a)
$\displaystyle=\left[\frac{1}{d}\sum_{k=1}^{d}\sqrt{\text{Pr}\left(k|\tilde{\mathcal{U}}(\sigma_{k}^{*})\right)}\right]^{2},$
(14b)

where $\text{Pr}(x|\rho)$ refers to the probability of measuring the output
$x$ given a state $\rho$.

This has a nice operational meaning, as it means that we can determine the
fidelity of a noisy unitary that is followed by a measurement, by preparing
the time-reversed initial states $\sigma_{k}^{*}=U^{\dagger}\pi_{k}U$,
applying the noisy unitary $\tilde{\mathcal{U}}$ and combining the
probabilities to measure the respective outputs $k$. This, however, requires
the ability to prepare the initial states with a high fidelity.

Note that while this expression superficially resembles the one presented in
Ref. [32], the sum here is over the square roots of the probabilities of the
correct outputs for different input states. In contrast, in Ref. [32] the sum
is over the square roots of the fidelities of different outputs for a fixed
input state.

###  A.2 Process fidelity of the noisy QFT+M

Let us apply the above fidelity estimation to the case where the ideal unitary
operation is the quantum Fourier transform,
$\mathcal{U}(\rho)=\mathcal{QFT}(\rho)=QFT\cdot\rho\cdot QFT^{\dagger}$, and
define the quantum Fourier transform followed by measurement as
$\text{QFT+M}:=\mathcal{V}=\Pi\circ\mathcal{QFT}$, with its noisy version
$\tilde{\mathcal{V}}=\Pi\circ\Lambda\circ\mathcal{QFT}=\Pi\circ\tilde{\mathcal{QFT}}$.
We can prepare the initial states
$\sigma_{k}^{\ast}=QFT^{\dagger}\ket{k}\\!\\!\bra{k}QFT$ with high efficiency
and fidelity as

$\displaystyle QFT^{\dagger}\ket{k}$
$\displaystyle=\frac{1}{2^{n}}\sum_{j=0}^{2^{n}-1}e^{-2\pi ikj/2^{n}}\ket{j}$
(15a) $\displaystyle=\bigotimes_{l=1}^{n}R_{Z}(-\pi k/2^{l},l)H^{\otimes
n}\ket{0},$ (15b)

which means that we simply need to apply single qubit rotations to the
corresponding qubits.

As the number of different initial states $\sigma_{k}^{\ast}$ increases
exponentially, we can sample $m$ different values $\\{k_{l}\\}_{l=1..m}$,
$k_{l}\in\\{1,..,2^{n}\\}$. Note that using the square of sample average
(denoted by an overline) as an estimator for $E[\sqrt{X}]^{2}$ has an $O(1/m)$
bias. This can be seen by noting that
$E[(\bar{\sqrt{X}})^{2}]=E[(\frac{1}{m}\sum_{i}\sqrt{X_{i}})^{2}]=E[\frac{1}{m^{2}}(\sum_{i\neq
j}\sqrt{X_{i}X_{j}}+\sum_{i}X_{i}]=\frac{m-1}{m}E[\sqrt{X}]^{2}+\frac{1}{m}E[X]$.
However, we can construct an unbiased estimator of $E[\sqrt{X}]^{2}$ by using
$\frac{m}{m-1}(\bar{\sqrt{X}})^{2}-\frac{1}{m-1}\bar{X}$, and estimate process
fidelity via

$\displaystyle\mathcal{F}_{\mathrm{proc}}(\mathcal{V},\tilde{\mathcal{V}})$
$\displaystyle=\left[\frac{1}{d}\sum_{k=1}^{2^{n}}\sqrt{\text{Pr}\left(k|\tilde{\mathcal{QFT}}(QFT^{\dagger}\ket{k}\\!\\!\bra{k}QFT)\right)}\right]^{2}$
(16a)
$\displaystyle\approx\frac{m}{m-1}\left[\frac{1}{m}\sum_{l=1}^{m}\sqrt{\text{Pr}\left(k_{l}|\tilde{\mathcal{QFT}}(\sigma_{k_{l}}^{\ast})\right)}\right]^{2}$
$\displaystyle\qquad-\frac{1}{m(m-1)}\sum_{l=1}^{m}\text{Pr}\left(k_{l}|\tilde{\mathcal{QFT}}(\sigma_{k_{l}}^{\ast})\right).$
(16b)

Note that in practice, the correction of the second term is negligibly small.

##  Appendix B Experimental details

We perform all experiments on ibm_kyiv, a 127-qubit superconducting quantum
processor. The qubits chosen for our dynamic circuits experiments are
indicated in Fig. 3(a). The cumulative distribution of the device’s T1 and T2
coherence times, as well as of the different error rates are shown in Fig.
3(b)-(c), indicating also the corresponding median values of the 40 qubits
chosen for our dynamic circuit experiments. For each $n$, we sampled $m=20$
random bit strings $k$, corresponding to the initial states
$\sigma_{k}^{\ast}$, and measured 2000 shots each.

Figure 3: Experimental implementation details. In (a), we show the device
layout of ibm_kyiv, with the 40 qubits chosen for our dynamic circuits
experiments marked in black. In (b) and (c), we plot the cumulative
distribution of T1 and T2 coherence times, the single qubit gate (SX), readout
(Meas.) and two qubit entangling gate (CX) error rates of all qubits on the
device, as well as the corresponding median values of the chosen 40 qubits (CX
gates were not used in the dynamic circuit implementation).

##  Appendix C Average result success probability

Ref. [68] reported a so-called “average result fidelity” of close to $100\%$
for the QFT on up to 27 qubits. These results rely on plurality voting as a
post-processing technique, which assumes that the ideal result is a single
bitstring. For this reason, the “average result fidelity” is not a valid
fidelity measure and we describe it instead as the “average result success
probability.” Nevertheless, for the sake of comparison, we applied a plurality
vote to our results to evaluate this quantity as well. The results are shown
in Fig. 4, where we report an average success probability of $100\%$ for up to
38 qubits. The deterioration of our unitary results compared to the previous
best reported results using the above metric is due to an all-to-all
connectivity which reduces the requirement for numerous SWAP operations, a
limitation that is particularly pronounced in our superconducting systems and
negatively impacts the performance.

Figure 4: Demonstration of the advantage of the dynamic circuit implementation
of QFT+M versus the unitary version for another metric: the average result
success probability.