{'fraction_non_alphanumeric': 0.03263127877133662, 'fraction_numerical': 0.0068711723089040075, 'mean_word_length': 4.619381915299504, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Spectral analysis for noise diagnostics and filter-based digital error mitigation

We investigate the effects of noise on parameterised quantum circuits using spectral analysis and classical signal processing tools. For different noise models, we quantify the additional, higher frequency modes in the output signal caused by device errors. We show that filtering these noise-induced modes effectively mitigates device errors. When combined with existing methods, this yields an improved reconstruction of the noiseless variational landscape. Moreover, we describe the classical and quantum resource requirements for these techniques and test their effectiveness for application motivated circuits on quantum hardware.


I. INTRODUCTION
Characterisation and verification of quantum computations becomes increasingly important as quantum hardware scale and facilitate noisy intermediate scale quantum (NISQ) applications for larger problem sizes. In most cases, there is a trade-off between the amount of information obtained about the errors and resource requirements of the protocols that acquire it [1].
For larger circuits, process tomography quickly becomes prohibitively expensive, so one must resort to holistic benchmarks [11][12][13]. Typically these produce a single metric to characterise the performance of a quantum device at running application-motivated circuits of specified sizes [14]. However, the question of how to quantify the effect of noise for given circuit structures remains. Tools that allow to gain this additional information to an extent that can inform strategies for noise suppression at the circuit level will be needed to push NISQ applications towards reaching regimes where computational quantum advantage may be possible [15].
Near-term (variational) algorithms typically involve circuits with a set of variable gate parameters, but otherwise a fixed structure. Although variational methods grant partial resilience to noise [16,17], accumulation of errors still impacts their ability to generate expectation values that are competitive with classical methods [18]. Furthermore, noise can also impact the trainability of variational algorithms through the presence of barren plateaus in the optimisation landscape for increasing problem sizes [19].
Error mitigation methods aim to reduce the approximation error in the noisy estimation of expectation values and are generally designed for near-term applications. While they typically require a sampling overhead that scales exponentially (with depth) [20,21], error mitigation can be achieved in regimes beyond classical simulability [15,22,23].
Some of the techniques involve boosting errors and extrapolation to zero noise levels [24,25], using quasiprobabilities to decompose noisy gates [24,26], machine learning approaches [27,28] and combining methods [29,30]. However, in regimes with low quantum volume [12], the general performance of different error mitigation methods can exhibit a great deal of variability on physical hardware [31]. Combining noise suppression at circuit and gate level with error mitigation and knowledge of the specific circuit or application may be a way to circumvent this [15].
In this work we investigate the effects of noise on parameterised quantum circuits with a fixed circuit structure by means of signal processing methods. We employ harmonic analysis at the level of quantum channels, along with decompositions of unitaries into linear combinations of Clifford operations. This allows us to relate expectation values of parameterised circuits to trigonometric polynomials. Previous works also highlighted this relationship for specific applications [32][33][34][35][36][37][38], and our contribution expands and generalises the connection along several directions. We characterise both the frequency support, in terms of lattice structures generated by parameters of the circuit, and the coefficients in terms of process modes that are derived through channel decompositions into Clifford paths. These observations allow us to treat noisy expected values as output signals that carry information about how errors affect the specified circuit.
We analyse the effects of noise in the frequency domain by taking (fast) Fourier transforms with respect to the variational parameters. In particular, for real hardware implementations the presence of frequencies outside the support of the noiseless input signal indicates not only the gate dependent errors (due to calibration or control imprecision) but also how these build up through the circuit. Therefore, these additional modes also pick up information about the correlated errors induced by the circuit structure. Furthermore, we explore the effect of common noise models: for instance, incoherent noise leads to contractions of Fourier coefficients.
Crucially, for a target set of parametrised circuits and observables the harmonic analysis infers the support of the frequency spectrum. This additional information certifies that the presence of modes outside this support is attributed to noise alone, a connection that allows us to design new error mitigation methods that target these isolated noise components. These spectral filtering techniques can be shown to work exactly (below a fixed noise threshold) for certain classes of classically simulable circuits. We also demonstrate their effectiveness for practically relevant circuit structures used for quantum chemistry and combinatorial optimisation problems, by combining them with complementary error mitigation methods targeting decoherence, and demonstrate improved estimators for expectation values over the whole variational landscape. The output of a measurement operator on noisy parameterised quantum circuit is sampled at different parameter levels; the discrete samples are transformed (e.g. with FFT) to deduce the frequency spectrum of the noisy landscape; the spectral information is then used to characterise and benchmark the machine or to reduce the noise to give a mitigated cost function landscape.

II. EXPECTATION VALUES OF PARAMETERISED STATES AS TRIGONOMETRIC POLYNOMIALS
Several authors have observed the simple relation between expectation values of observables with respect to parameterised circuits and trigonometric functions, or finite Fourier series [32][33][34][35][36][37][38]. In particular Schuld et al. [32] give a general analysis that is used to explore the expressivity of ansätze for data-encoding. The particular circuit involved repeated applications of the same parameterised unitary of the form V := V 0 U (θ)V 1 U (θ)...U (θ)V m with one-parameter unitaries U (θ) generated by a Hermitian operator H acting on the Hilbert space corresponding to n qubits.
We extend these results to generalised circuits with m independent parameters. Our approach is conceptually different, as we decompose the target unitary operation into a linear combination of operations that separates the dependency on the parametrisation from the specific circuit structures involved. This is related to sum-over-Clifford paths approaches to classical simulation of circuits [39,40]. This channel-based perspective is particularly well-suited to analyse the effects of noise.
We consider unitaries that are parameterised by a set of angles θ = [θ 1 , ..., θ m ] so that they take the general form where each of the one-parameter unitaries are generated by hermitian operators U (θ j ) = e iθj Hj . An m-variate trigonometric polynomial with degree at most d has the form where k = (k 1 , ..., k m ) and k i ∈ Z, θ i ∈ [0, 2π] and k · θ = m i=1 k i θ i . Furthermore, for real functions f it holds that c −k = c * k . We will denote by T m,d the set of all such real trigonometric functions on m variables with degree at most d; k is called a path.

A. Illustrative example: Pauli gadgets
Consider first a single-qubit parameterised Z rotation gate Z(θ j ) = e −iθj Z/2 . We denote the corresponding unitary channel by Z(θ j )(·) := Z(θ j )(·)Z(θ j ) † . Recall that the set of Clifford unitaries on n qubits forms a group generated by the single and two-qubit gates {H, S, CNOT}. Z(θ) j decomposes as a linear combination of Clifford unitary channels given by Z(θ j )(ρ) = p I (θ j )ρ + p Z (θ j )ZρZ † + p S (θ j )SρS † , where each coefficient p I , p Z , p Z ∈ T 1,1 and is defined in Appendix A. Alternatively, we can write with C 0 , C ±1 linear combinations of Clifford channels defined in Appendix A and independent of the parameter θ j . Following our previous work [41], we call these channels Clifford process modes. The above directly implies that the corresponding expectation values satisfy tr(OZ(θ j )(ρ 0 )) ∈ T 1,1 for any observable O and initial state ρ 0 . This generalises to circuits U (θ) as in Eq. (2) with independent parameters where each unitary U (θ j ) has a circuit implementation using a single parameterised onequbit Z(θ j ) gate. For example, this occurs when each of the one-parameter unitaries U j (θ j ) = e −iPj θj /2 are Pauli gadgets with P j an n-qubit Pauli operator. Then, by linearity and since the m parameters are independent, it follows that given ρ(θ) := U (θ)ρ 0 U (θ) † the expectation value of any observable tr(Oρ(θ)) ∈ T m,1 is a multivariate trigonometric polynomial in θ with degree at most 1.

B. Process mode decomposition with Clifford paths
In general situations, it may be that the circuit implementing U (θ j ) consists of several Z-rotations by (noninteger) real-valued multiples of the independent parameter. In such a case the resulting expected values with respect to θ will be described by generalised m-variate trigonometric polynomials [42] of the form where k = (k 1 , ..., k m ) with k i ∈ Z d and ω k = ((ω k ) 1 , ...., (ω k ) m ) is a real vector of frequencies.
Here, m labels the number of independent parameters θ i and each k i is an index counter of the frequencies corresponding to θ i . The maximal number of (distinct) frequencies in a parameter is labelled by d. Note that generally this may take a different value for each parameter, but we use the maximal value for simiplicity of exposition. In order to determine the allowed values for the frequency vector ω k and represent the corresponding coefficients c k in terms of operations derived from the circuit structure we decompose the target unitary channel U(θ) into a linear combination of operations separating the parameter dependency.
can be expressed in terms of what we call a process mode decomposition with Clifford paths where each U kj is an operation derived from the circuit U j (θ j ) by replacing each parametrised Z-rotation with one of its constituent Clifford process modes, per Eq. (4).
The length of each vector k j will be given by the number of parametrised gates in the circuit, with entries taking values {0, ±1} corresponding to all particular replacements. Note that the U kj need not be completely positive trace preserving maps. The circuit implementation of U j (θ j ) may also be given in terms of other multi-qubit parametrised gates, or in terms of the Hamiltonians generating it. In these cases, the process modes are constructed by generalising Eq. (4), which we describe in Appendix A in more detail. However, the frequency spectrum will be independent of any particular description of U (θ).

C. Frequency spectrum for parametrised circuits
The decomposition in Sec. II B directly gives the trigonometric polynomial form taken by expectation values; to emphasise their dependency on the measured observable, we employ the notation c k (O) for the coefficients.
A full proof of this result may be found in Appendix C as well as its relationship to previous work that described the frequencies (ω k ) j in terms of eigenvalue differences.
As an illustrative example, suppose that U i (θ i ) is given in circuit form where the only θ i -dependent gates are Z(a 1 θ i ), ..., Z(a ri θ i ) with fixed a 1 , ..., a ri ∈ R. Then, the allowed frequencies are (ω k ) j = a · k j for k j ∈ {0, ±1} ×ri with a = (a 1 , ..., a ri ) and furthermore −||a|| 1 ≤ (ω k ) j ≤ ||a|| 1 2 . Note that generally, the frequencies are not uniquely defined by a given path k. It may be the case that two different paths give ω k = ω k , in which case the corresponding coefficient in the Fourier transform will be c k + c k . Therefore in the Fourier-transform frequency spectra S the two paths will have indistinguishable contributions.
This analysis involving process modes with Clifford paths may be more suitable than the expressions in Eq. 1 to determine the allowed frequencies and coefficients in the expectation value in the following situations: when one does not have direct access to the eigenvalues; when the parameterised unitary is given as a quantum circuit, or when the eigenvalues have higher multiplicities where it provides a more compact form for the coefficients. Our focus is ultimately on analysing and mitigating the effects of quantum noise on expectation values of observables viewed as trigonometric polynomials, where such a quantum channel perspective is more suitable.

III. ERROR DIAGNOSTICS FROM FOURIER SPECTRA
A. Fourier spectra of quantum channels In the previous section we showed how a quantum channel approach can be used to derive the Fourier spectra of 1 The 2 m -dim Walsh-Hadamard transform matrix can be defined as [Hm] ij := 1 2 m/2 (−1) i·j where the i · j indicates the bitwise dot product between the binary representations of the indices. 2 For clarity of exposition we assumed U (θ) as in Eq.(2), however the result on the allowed frequency spectrum holds in the most general sense, where differently parametrised gates may be interlaced throughout the circuits e.g U (θ) = parameterised unitary circuits, via a process mode decomposition with Clifford paths. We now drop the unitary requirement, and discuss Fourier spectra of general quantum channels that may represent noisy implementations. The previous decomposition of unitary operations into process modes can also be seen as a consequence of the following general result.

Lemma 3 ([43]
). Any linear map χ on n qubits can be expressed as a linear combination of Clifford unitary channels C i and Pauli reset channels 3 S j for q i , q i ∈ R. Trace preservation is equivalent to i q i + j q j = 1, and the S j terms are only required for nonunital channels 4 . The decomposition is not unique.
In general, the Fourier spectrum of an expectation value evaluated on a parameterised state produced by a noisy channel will differ from that of a noiseless one in two distinct ways: the Fourier coefficients might be different, and the frequency support might vary.
Theorem 4. Writingρ(θ) = χ(ρ(θ)) for the noisy implementation of the target state ρ(θ), and allowing the noise channel χ to depend on θ, we have where q (θ) := j q j (θ) P j |O|P j for some |P j eigenstates of Pauli operators in the decomposition of Pauli reset channels.
See Appendix D for the proof and additional details.
Recall that in the noiseless case, a discrete set of frequencies suffices, corresponding to the points of the lattice Λ ⊂ R m . In the noisy case, the expectation value O ρ(θ) is still a function of θ, but it may no longer have a discrete Fourier series. Therefore we define the noisy frequency spectrum asS where F denotes the Fourier transform, computed as The difference between S andS depends on the specific noise parameters q j (θ), and different channels have distinct effects on the spectra. In the following section we illustrate this for several noise models based on varying physical assumptions.

B. Effect of decoherent channels
Consider a noisy implementation where each unitary gate operation is followed by a noise channel that is independent of the parameters It is clear that for any fixed observableS ⊆ S, in other words the range of frequencies remains the same. However the magnitude of the Fourier coefficients might be different. Stronger assertions are possible if we specialise to particular cases. For example, if each noisy gate V i is affected by a (global) depolarising channel with parameter p, then one finds that the noisy Fourier coefficientsc k are homogeneously contracted This can be seen as a special case of the following result.
Lemma 5 (Pauli channel). LetŨ be as in Eq. (13) and suppose eachṼ i is a Clifford unitary followed by a Pauli channel 5 , and each U i is a Pauli gadget; then, for any Pauli observable O, the coefficients are contracted for all paths so that |c k (O)| ≤ |c k (O)|.
For general observables O and non-Clifford V i , some modes that were previously zero due to cancellation of paths might find themselves with a non-zero value under a Pauli noise model.
In Appendix F, we provide a comprehensive analysis of noise channels and their effect on Fourier coefficients, summarised in Table I. Importantly, the effect of coherent, non-unital and parameter-dependent channels is detectable from the Fourier spectrum as additional modes. Parameter-dependent channel in particular may lead to modes with frequencies outside the theoretical spectrum S.

C. Shot noise
Overall the analysis in previous sections confirms that noise is capable of expanding the frequency spectrum. With knowledge of the exact, noiseless spectrum, one thus has a direct way of quantifying the impact of noise on a quantum variational landscape. In practical terms, an implementation of error diagnosis from Fourier data would involve performing a discrete Fourier transform (DFT) by sampling parameter values. Since the number of points determines the resolution at which the frequencies in the noisy spectrum can be determined, the grid should be fine enough to be able to resolve frequencies beyond S. In Appendix E we discuss possible approaches to optimising the number of calls to the quantum computer.
These sampling requirements are in turn different to those needed to resolve the individual points of the landscape with sufficient accuracy. We consider this requirement in the next section.
Typically, for DFT the sampled points θ i are equally spaced on a grid Θ = 2π d Z ×m d , where d = 2N + 1 for N the largest frequency resolvable. For each sampled point, the corresponding circuit U (θ i ) is repeated n s times to construct sample mean estimatorsx i for the expectation value x i . From the central limit theorem, the standard deviation due to a finite number of shots scales as 1/ √ n s and using properties of the DFT a similar scaling occurs in estimating the Fourier coefficients under shot noise.
Lemma 6 (Shot noise). Given a number of shots n s , each Fourier coefficient is normally distributed around the noiseless mean with standard deviation and similarly for the imaginary part.
Two observations can be made on this result: first, the standard deviation of each Fourier coefficient due to shot noise is independent on the coefficient's frequency vector k, and second, the dependence on d m means that increasing the resolution in the frequency spectrum or the number of parameters varied reduces the shot noise in the Fourier coefficients with a scaling of 1/O( √ d m ).

Power spectra
If a frequency spectrum is known to be included into S, one can quantify the extra noise-induced modes from an experimentally measured spectrumS using the signal power (or energy).

Definition 7 (Quality measures).
The power in the extra modes due to noise is given by while the signal power will be given by The total power P := P N + P S is proportional, via Parseval's theorem, to the power of the real-space signal i |x i | 2 . One can also define the observed signal-tonoise ratio (SNR) as SN R := P S /P N . Distinguishing noise from the signal will depend on the knowledge of the spectrum S, as well as the size of the experimentally measured spectrumS. To maximise the distinction, it is beneficial to identify S as small as possible, which might be possible for specific circuit structures. In Section IV B we show how the noiseless spectrum can be refined for the case of QAOA. However, for general circuits one is confined to the results of Theorem 2.

Average fidelity and purity
A quantity of practical relevance for benchmarking that can be extracted from the Fourier representation is the average fidelity over all sampled parameter values F θ , equal to F[F ] 0 . Let us represent the Fourier coefficients over all Pauli operators in the vectorised notation c, where [ c] k,i = c k (P i ). Therefore one can show that Lemma 8 (Average fidelity). The average fidelity of the output state over all sampled parameters is proportional to the inner product of the vectors of Fourier coefficients: where F (ρ(θ), ρ(θ)) is the fidelity between the target state ρ and the noisy implementationρ.
From this it is clear that the Fourier modes in c that fall outside the support of c do not contribute to the average fidelity. In other words, additional modes such as those produced by parameter-dependent errors are not captured by this averaged measure, but nonetheless will affect fidelity of individual circuits.
Of course, in a practical setting it is unrealistic to measure all Pauli observables, while direct fidelity estimation [44] requires at worst Ω(2 n ) measurements, for many classes of states resource requirements are reduced, and one could also further employ estimation of multiple observables using classical shadows to reduce the computational burden [45].
Similarly, the average purity can be related to the norm of the noisy Fourier coefficient vector: Lemma 9 (Average purity). The average purity of the output stateρ(θ) over all sampled parameters is propor-tional to the squared norm of the vector of Fourier coefficients The relation between purity and spectral power is therefore that the average power over all Pauli operators is proportional to the average purity of the state over all sampled parameters. As a corollary, coherent noise channels in the preparation circuit preserve purity of the final state and therefore the norm of c.
Furthermore, since coherent errors preserve purity of the state, it must be that under coherent noise channels the norm of c is preserved. Vice versa, decoherent channels will decrease purity, and therefore lead to a contraction in the components of c, consistent with the analysis presented in Sec. F.

Simple circuit
In the following we apply spectral noise evaluation to example circuits run on real quantum devices. The first circuit examined is a two-qubit circuit, consisting of two parameterised R y rotations, and the measurement operator is the parity operator ZZ. The parameterisation is the canonical one, therefore the noiseless expectation value is f (θ 1 , θ 2 ) = cos(θ 1 ) cos(θ 2 ), which corresponds to 4 nonzero Fourier coefficients with maximum absolute frequency 1. Therefore, to study the presence of higher frequency modes we sample up to a maximum absolute frequency of 2, giving a 5x5 grid. The experiment was run on a superconducting device (ibmq lima).
To assess the effect of noise on the frequency spectrum, after state preparation and prior to measurement we introduce a series of identity gates, composed of two successive CNOT gates. These would cause an increase in noise by extending the depth and therefore computation time, increasing decoherence, and by being noisy themselves. Furthermore, we note that error mitigation via extrapolation for digitised computations [46] involves introducing such fiducial gates to artificially boost noise levels, and so the analysis here may also be used to test noise assumptions involved in deriving fitting functions.
In Figure 2 we show the total power in noise modes, defined above as modes not present in the noiseless spectrum. The latter is further divided in noise on the expected noiseless spectrum S ('on support') and noise outside of it ('off support' ), which in this case consists of modes having any components with frequency higher than 1. The error bars correspond to one standard deviation as evaluated by a bootstrapping variance estimation method [47]. The results reveal that, as expected, increasing the number of identity gates has a progressive detrimental effect on the quality of the output. Most of the noise appears to come from on-support modes, while off-support extra modes remain minor, however they also appear to increase progressively with depth. Based on the previous discussion, the decay in signal power is to be interpreted as likely being caused by decoherence, while the increase in additional modes, both on-and off-support, signals the increased effect of more complex noise channels.

UCC circuit
Next, we evaluate the spectrum of a more complex 2-qubit circuit inspired by the unitary coupled cluster (UCC) approach to VQE [48], consisting of two Pauli gadgets with P 1 = XY and P 2 = Y X. The measurement operator is ZI, which yields the expectation value f (θ 1 , θ 2 ) = cos(θ 1 ) cos(θ 2 ) − sin(θ 1 ) sin(θ 2 ), giving 2 Fourier coefficients. This time, the experiment is run on four superconducting devices provided by IBM, as well as the ion trap computer Quantinuum H1-1, powered by Honeywell. The sampling grid is identical to the previous experiment. The results are shown in Figure 3.
Overall, the devices with the worst performance are ibmq santiago and ibmq lima, while the best performing on the task are HQ1 and ibmq lagos. This might be ascribed to their greater number of qubits (10 and 7), giving a larger parameter space for the compiler to optimise noise, as well as to higher quantum volume in the case of H1-1 (which, at the time of writing, holds the world record for this measure [49]). On the other hand, the other machines have all a lower number of qubits (5). Interestingly, for the most accurate devices the majority of the noise modes fall outside the exact support, hinting that these devices might benefit the most from spectral analysis and noise mitigation. Therefore we see that in principle spectral methods could be valuable in benchmarking quantum devices by providing multiple figures of merit, and separating different physical noise effects. However, we stress that the experiments presented here are extremely limited in both system size, circuit depth and number of measurement operators sampled. The results cannot be considered as anything beyond a rough assessment of the performance of the different machines in this particular task, and are meant to serve as a proof-of-principle rather than a meaningful comparison.

IV. ERROR MITIGATION BASED ON SPECTRAL INFORMATION
In Appendix I we prove that below a noise threshold, a signal can be perfectly recovered by rounding its Fourier coefficients for a class of quantum circuits. These contain parametrised gates with independent parameters and unparameterised gates that are Clifford but otherwise unknown. However, this theorem does not extend to general circuits, where typically one has both unparameterised non-Clifford gates and dependent parameters. While the result applies to circuits of practical interest such as the unitary coupled clustered ansatz [50,51], the classical complexity of the fast Fourier transform scales exponentially in the number of parameters thus limiting the theorem's use to circuits containing few non-Clifford gates. On the other hand, circuits with a number of non-Clifford gates scaling logarithmically in the number of qubits can be efficiently simulated [52].
However, given knowledge of the frequency spectrum for a circuit family, we design application-specific error mitigation strategies that allow to approximately reconstruct the signal. In Appendix I we outline two such strategies inspired by well-known classical spectral filtering methods, namely thresholding and filtering. Both aim to recover the clean signal by isolating the most significant components from a noisy spectrum. Thresholding assumes that the noise modes are small in magnitude, and therefore sets a lower bound to the coefficient's absolute value, while filtering uses knowledge of the noiseless spectrum to remove all frequencies that must be induced by noise.
In the next sections we combine these strategies with a decoherence-mitigating method and demonstrate their usefulness in a realistic scenario.

A. Spectral denoising with near-Clifford circuits
A general feature of incoherent quantum noise is the scaling of signal coefficients, as explained in Section III A. Denoising techniques based on frequency filtering or thresholding do not change the value of the significant coefficients, and therefore would not reduce the effect of decoherent processes on their own. This can be viewed as an indication that Fourier methods should be complemented with other noise mitigation techniques designed to reduce decoherence effects. Here, we explore a combination of Fourier methods with Clifford Data Regression (CDR) [28], which has shown promise as a practical mitigation method for expectation values. CDR has features that make it natural to integrate with Fourier methods, as it relies on learning noise based on the entanglement structure of the circuit, independently from the angles of rotation. The combination thus leads to a more efficient use of samples.
Denote byf (θ) the noisy expectation value of a given observable O with respect to the parameterised circuit U (θ) acting on input state ρ 0 and by f # (θ) its restriction to the frequency spectrum ω ∈ S for the input circuit as determined using the techniques illustrated in Appendix I. In practice, when implementing these protcols on a quantum device, one deals with sample mean estimators of the noisy expectation valuef which, along with implementing a discrete Fourier transforms gives an estimator for f # that includes shot noise as discussed in Sec. III C. After filtering noise-induced modes, the second step would be to reduce the effect of incoherent noise by determining the noise scaling A ω that give the error-mitigated estimatorŝ c ω := A ωcω of the exact Fourier coefficients c ω . To this aim, there are several strategies one can employ. In our experiments we have explored the following strategies The simplest approach is to first apply CDR, as it was introduced in [28], in order to learn scaling factors A and A that minimise wheref C and f C denote respectively the noisy and the classically simulated expectation value of the observable O with respect to state Cρ 0 C † . C is a near-Clifford circuit derived from the target parameterised circuit U (θ) where all but a fixed number of D non-Clifford gates are replaced with Clifford operations. Once A and A have been found, we filter out noise-induced modes using the methods in Sec. III A and I 3 to give an error-mitigated estimator.
for the target expectation value f (θ). To further reduce quantum compute resources, we include (part of) the circuit evaluations required for the Fourier transform into the training set C. Alternatively, one may implement CDR by training the model on spectrally filtered data. There is the limitation that the training data must now be in a form conducive to Fourier mitigation, and thus a minimum of non-Clifford gates must be present. This issue is exacerbated whenever, for a given parameter θ, multiple θ-dependent gates occur in the synthesised target circuit, as they cannot be replaced by independent Clifford gates in the training phase. Lastly, a more involved strategy rests on the observation that not all coefficients corresponding to ω = 0 are scaled by the same amount under the action of real hardware noise. This behaviour may be seen in the raw Fourier spectrum obtained on IBMQ devices (Figures 4 and 5) but also in the analysis of different noise models in Sec. III. Using a similar training set as in the second approach above, one then would seek to learn a vector A = (A ω ) of parameters that minimise where θ C corresponds to the near-Clifford circuit C, with each (θ i ) C parameter chosen so that the corresponding θ i parameterised gates are Clifford. This suffers from analogous problems in constructing the training set.
In our experiments all three methods were attempted, however we found that more involved methods did not amount to a significant improvement in the mitigation results, while significantly increasing the computational burden. Therefore, we limit our analysis to the simplest method.

B. Experiments
To demonstrate the applicability of noise filtering methods, we give proof-of-principle implementations on current quantum hardware for circuit structures used in near-term algorithms.
The magnitude threshold for determining the most significant Fourier coefficients is calculated as for some tunable constant B. Assuming the majority of coefficients in the sampled frequency spectrum are due to noise (which in principle requires the resolved spectrum to be double the size of the noiseless one), and further that these are small and of similar magnitude, this allows us to select only the outliers and hence recover the signal coefficients. The CDR is performed with a simple linear model as in Equation 21. The training set C is generated by substituting for each target circuit the closest Clifford to every non-Clifford gate, except for D randomly chosen gates.
As noted before, spectral noise filtering is expected to yield a landscape that has more similar features to the noiseless one, while a scaling technique like CDR is necessary to reduce the error in the magnitudes. Therefore, we focus on two quantities of interest that capture these two different scenarios.
For each noise mitigation experiment we report the similarity measure between the mitigated vector C # and the noiseless vector C obtained from a unitary simulator (Qiskit Aer's statevector simulator [53]). The simplest measure of similarity between vectors of data points is the Euclidean distance ||C # − C||, which has a practical interpretation as the root mean squared error between the data points. Furthermore, it is invariant (up to a constant) under the Fourier transform, due to Parseval's theorem, and therefore may be easily calculated from the spectrum. We then choose to consider the additional measure of cosine similarity This quantity is robust to global scaling of any one of the two vectors. The quantity can therefore be visualised as a scale-invariant measure of error: indeed, if both vectors are unit-normalised, cosine similarity is monotonically related to Euclidean distance: The experiments are performed on IBMQ superconducting devices.

UCCSD
We begin by analysing a UCCSD circuit for the H2 molecule under the STO-3g basis set, which requires four qubits under Jordan-Wigner representation. The circuit has two parameters corresponding to 'singles' excitations, each appearing on two Pauli gadgets, and one parameter governing 'doubles' excitations, composed of eight further gadgets. The circuit has a total CNOT depth of 52 and no depth-reduction compilation passes were applied. We choose to focus on the two singles parameters for spectral noise mitigation. Since they each control two single-qubit rotation gates, the noiseless support has a maximum frequency of 2, therefore we sample on a 7x7 grid giving a maximum frequency resolution of 3.
In the target circuit, the Pauli gadgets implementing the doubles excitations are chosen independently and set to fixed angles normally distributed around π/4 with standard deviation 0.1. By randomising the fixed parameters instead of setting them to the optimum we aim to illustrate an improved profile of the noisy energy landscape for general parameter values, allowing to evaluate the mitigation method in a realistic setting where the optimal parameters are not known. For CDR we set D = 2 and for thresholding constant we find that B = 3 is sufficient.
The results are shown in Table II. Both cosine similarity and Euclidean distance are consistently improved by the combination of spectral noise mitigation and CDR compared to no mitigation and CDR alone. The improvement due to spectral techniques is especially notable for cosine similarity, while the decrease in Euclidean distance is more modest. This reflects the fact that Euclidean distance is highly dependent on relative scaling between the vectors, which is what CDR targets by construction.

QAOA
We then consider a quantum approximate optimization algorithm (QAOA) circuit [54] for the MaxCut problem on random 3-regular triangle-free graphs of various sizes, with V and E denoting the vertices and edges. The circuits involve repeated layers labelled by p, whereas each layer alternates between a unitary generated by the cost Hamiltonian H C = (i,j)∈E Z i Z j and a mixing Hamiltonian H D = i∈V X i , with the initial state an equal superposition over the computational basis. The p = 1 layer circuit on n qubits produces the parametrised state e −iβH D e −iγH C |+ ⊗n . The benefits of this class of QAOA problems for benchmarking noise mitigation algorithms are twofold: first, the scaling in depth with system size is favourable compared to UCC, as long as the number of layers is kept small. Second, since the Hamiltonian is diagonal in the Z basis the cost function value can be calculated from the single shots without adding additional rotation gates. We compare the same noise mitigation techniques as UCC, on an 8-qubit QAOA circuit with p = 1, 2 on both the 16-qubit ibmq guadalupe and the 27-qubit ibmq sydney quantum computers. We also run a 16-qubit p = 1 experiment on ibmq guadalupe as an example of a larger system. As target function we measure the expectation value of the Hamiltonian.
All experiments are run on two parameters. In the p = 2 experiments we choose to focus on the parameters in the last layer, in which case we set both parameters of the first layer to π/4. By using a lightcone argument one can then show that in all experiments that the frequencies will be limited to 2 for the mixing parameter β, and 5 for the problem parameter γ, which follows from the problem graphs being all 3-regular and triangle-free. Therefore, we sample on a 13x13 grid to ensure a resolution of 6 in frequency space.
Training CDR on this system presents with the additional complication that setting all parameters to give Clifford gates leads to an expectation value of zero. Therefore, in order to obtain training data of sufficient magnitudes the CDR parameter D is increased from 2 to 10, and the data is post-selected to only train on the largest magnitude datapoints. Due to the higher noise level we find that increasing the thresholding constant to B = 10 is more appropriate.
The results are shown in Table III. The performance of noise mitigation techniques is seen as highly dependent on the depth of the circuit. Circuits with p = 1 show consistent improvements with noise mitigation and especially following spectral filtering. Interestingly, thresholding appears to be the most effective filtering method, which can be justified by the noiseless signal being sparse and much higher than the noise level, as shown in Figure 4. Increasing the system size to 16 qubits does not seem to affect the noise mitigation capability.
On the other hand, circuits with p = 2 generally see little improvement in either measures of quality. This is due to the fitting subroutine in CDR failing to find an appropriate scaling factor due to Clifford data being extremely noisy. As a related effect, hardware noise causes the experimental signal to be considerably different from the noiseless one as can be seen in Figure 5. Overall this is a reminder that excessive noise can be an insormountable obstacle for any kind of error mitigation, whether classic or frequency-based.

V. DISCUSSION
We investigated the quantum noise-induced effects on the Fourier spectrum of parameterised quantum circuits, both in real hardware and through theoretical analysis of common noise models. This led us to design methods for digital error mitigation based on filtering noise-induced modes or thresholding most-significant coefficients. For specific circuit classes, in Appendix I show that if the noise is below a certain threshold one may perfectly reconstruct the landscape from noisy circuit evaluations. While these circuits do not exhibit quantum advantage, they illustrate that denoising in the frequency domain may recover error-free estimates of expected values from hardware data without performing any classical simulation. However, these methods, among others derived from them, can be employed for more general circuits. In particular we show how to combine denoising in Fourier space with existing error mitigation based on learning from Clifford circuits. The latter targets incoherent noise, while the former reduces the effect of gate-dependent, correlated errors, including coherent contributions. We implement these methods in different quantum hardware using application-specific circuits employed in QAOA and VQE applications. The compound effect of the Fourierbased error mitigation strategies reduces not only the magnitude of errors but also the noise-induced distortion in the energy landscape.  The most glaring disadvantage of Fourier methods is the large sampling overhead required. We discuss the resource requirements, as well as possible ways to reduce it, in Appendix E. There we discuss also how to approach the problem of incomplete or nonuniform sampling, which might also help ameliorate the resource requirement and make the methods more flexible.
While here we only explored combining spectral methods with CDR, one may adapt our approach for other techniques such as zero noise extrapolation [24,25] and probabilistic error cancellation [24,26], which similarly address decoherence effects. More recent work [28] that improves the efficiency of CDR could also be employed to reduce the total number of training circuits required. Furthermore, investigating the effect of noise on the Fourier coefficients might also give new insight into the extent to which hardware noise satisfies some of the in-built assumptions of error mitigation protocols. For example, digital versions of zero noise extrapolation involve increasing the noise level by introducing additional gates [46]. Fourier methods could then be useful to determine appropriate type of such gate folding to validate the different fitting functions used in the extrapolation.
Beyond this, our theoretical contributions may also be of independent interest in building data-encoding models for quantum machine learning and investigating computational complexity of classical optimisation in variational quantum algorithms. Recent work [55] shows that the classical optimisation step for variational quantum algorithms is NP-hard. Essentially this relies on the NP-hardness of finding extremal points of specific classes of trigonometric polynomials and constructing corresponding circuits. Since our work explores this connection between trigonometric polynomials and circuit structures, it may also be useful to investigate worst-case or even average-case hardness in the optimisation step for more restricted classes of ansätze.
A major conceptual contribution of this work is reframing the study of quantum landscapes in the familiar terms of spectral analysis. As such, the theory developed here may be a fruitful approach to the recently coined quantum landscape theory [56]. Spectral analysis of the landscape can be employed to make statements about its global characteristics; for example, the presence or absence of barren plateaus and narrow gorges [57]. Furthermore, within this framework noise channels can be included naturally, making it amenable to study phenomena such as noise-induced barren plateaus [58] and alterations of the quantum training landscape [59].
Our work also opens up new directions to explore the vast range of signal processing techniques for the purpose of quantifying and reducing quantum noise. We tackled these topics from the perspective of digitised quantum computations, however similar analysis may be applied at the level of pulse sequences. In fact, the latter connects with experimental techniques used in the tuning and calibration of individual gates such as noise spectroscopy [60][61][62].
In this work, we focused on parameterised circuits typically used in NISQ applications. The parameter domain and the gates employed by such circuits make it natural to employ U (1) Fourier transforms. However, one can also consider families of circuits with structures that are embeddings of different groups, in which case one might look at Fourier transforms with respect to finite abelian (or even non-abelian) groups. For example, randomised benchmarking involves randomly sampling gates in the Clifford group to form sequences of increasing depth, making it suitable to use discrete spectral methods to analyse the effect of gate dependent errors [63]. Moreover, many algorithms such as phase estimation involve repeated applications of similar circuit structures, so a noise analysis in the Fourier domain may also prove to be fruitful. Overall the work presented here introduces a flexible framework that might extend to numerous other methods of noise characterisation and mitigation, but also to the analysis of (variational) quantum algorithms.

VI. ACKNOWLEDGEMENTS
The authors would like to thank Steven Herbert, Nathan Fitzpatrick and David Muñoz Ramo for useful feedback and discussions. We thank Dan Mills and Steven Herbert for helpful comments on the final draft of this manuscript. EF and IR acknowledge the support of the UK government department for Business, Energy and Industrial Strategy through the UK national quantum technologies programme. EF acknowledges the support of an industrial CASE (iCASE) studentship, funded by the UK Engineering and Physical Sciences Research Council (grant EP/T517665/1), in collaboration with the university of Strathclyde, the National Physical Laboratory, and Cambridge Quantum Computing. Code and data used in this project is available at https://github.com/e-font/fourier-noise.

Appendix B: Trigonometric form of expectation values
First consider the following Lemma: Lemma 11 (Transformation of Pauli operators by Z-rotations). Given a conjugate Z-rotation channel Z † θ acting on qubit k, the result of its application onto a Pauli operator P is where P is another Pauli operator and σ (k) denotes the k-th single-qubit Pauli composing the operator P .
Proof. Let us focus on a single-qubit Pauli operator σ i . Equation A1 described the result of applying the conjugate Z channel onto this operator. It is easy to show that Z(σ i ) = S † (σ i ) = σ i if i = 0, 3, and that Z(σ i ) = −σ i for i = 1, 2, S † (σ 1 ) = −σ 2 , S † (σ 2 ) = σ 1 . Therefore, we get the following cases: where we labelled σ i as the unsigned Pauli operator one gets after applying the S † channel. As the Z-rotation channel only acts on a single qubit, we can in general write the action on any Pauli operator in the same form, with the outcome depending on the single-qubit Pauli that the rotation acts upon. Therefore, the result follows.
This can be used to prove the following result:

Lemma 12 (Trigonometric form of expectation values). Consider a parameterised quantum unitary of the form
and the state resulting from applying the corresponding channel to a fixed initial state: ρ(θ) = U(θ)(ρ 0 ). Now suppose each of the one-parameter unitaries is generated by Pauli operators U (θ j ) = e −iPj θj /2 , and in addition the unparameterised unitaries V i are Clifford and the input state ρ 0 is a stabiliser state. Then the Fourier coefficients of the trigonometric polynomial tr(ρ(θ)P ) where P is a Pauli operator are where k ∈ {−1, 0, 1} m . Furthermore, the expansion of tr(ρ(θ)P ) in terms of trigonometric functions becomes particularly simple: Proof. It is most direct to prove first that the expectation value tr(ρ(θ)P ) is in the given trigonometric form. To do this, first consider that every parameterised operator U (θ j ) = e −iPj θj /2 is a Pauli gadget, and as such it can be decomposed into one single-qubit parameterised Z-rotation and Clifford gates, which can be absorbed into the fixed gates. Therefore, the circuit consists entirely of fixed Clifford gates V and parameterised single-qubit Z-rotations: Now consider the channel form of the unitary as it appears in the calculation of the expectation value tr(P U(θ)(ρ 0 )), which in the Heisenberg picture becomes tr(U † (θ)(P )ρ 0 ). Every step of the calculation of the expectation value then consists in the successive application of either a conjugate Z-rotation channel or a Clifford channel. Clifford channels by definition normalise the Pauli group and hence turn a Pauli operator into another Pauli operator. On the other hand according to Lemma 11 Z-rotation channels may, depending on the operator, produce a linear combination of operators with trigonometric coefficients. Therefore, at the end of the procedure, one is left with a sum of Pauli operators where φ 0 (θ) = 1, φ 1 (θ) = cos θ and φ −1 (θ) = sin θ. As a final step, the expectation value of this operator is taken with respect to the stabiliser ρ 0 state, which for each term yields either 0 or ±1. One is therefore left with a function of the wanted form.
To express the trigonometric function as a Fourier series, each trigonometric monomial can be expanded in complex exponentials, giving where the coefficients are c k ∈ {±1/2 ||k||1 , ±i1/2 ||k||1 , 0}, where ||k|| 1 = i |k i |. As the function is real, where z · j = n i=1 z i j i and with inverse Therefore, the action of the unitary can be decomposed into a series that involves replacing the action of each phase gadget Z j (θ) = e ia j Z j 1 ⊗...⊗Z jn θ by a Clifford process modes decomposition This is similar to the decomposition in the example from Sec II A and the exact form of each superoperators C j k for k ∈ {−1, 0, 1} may be found in Appendix A. Therefore, where a · k = r i=1 a ji k i with r the rank of the vector (a 0 , ..., a 2 n −1 ) and {j 1 , ..., j r } = {j : a j = 0}. Each vector k has entries in {−1, 0, 1} and labels a particular Clifford path decomposition.
The decomposition of U in the form of Equation C6, under certain circumstances, may in fact naively overcount the number of frequencies ω k := −2a · k. Interestingly, this comes from the fact that phase gadgets commute and particular compositions of process modes of the type C j k give a null channel, so the corresponding term in Equation C6 vanishes. For example, C j1 −1 • C j2 0 • C j1⊕j2 0 = 0 with more details in the Appendix A. This means there are certain 'selection'-type of rules for the vectors k, so the summation in Equation C6 ranges only over a subset of the full lattice of points Z ×r 3 . In particular, they will take the form k i = (−1) j i ·z −(−1) j i ·z 2 for i ∈ {1, 2, ..., r} for some binary vectors z, z of length n and with corresponding frequencies ω k = λ z − λ z .
In the above analysis, we considered the sequence of phase gadgets as it is, and we were not a priori synthesising the unitary into a circuit containing a minimal number of single qubit Z-rotations. This is also one of the reasons we had to employ 'selection' rules for the k vectors as in some sense we had redundancies in our description. Instead, if we were to start from a given optimised circuit and applied the Clifford decomposition directly to the parameterised gates in said circuit, then we would not come across the situation where a large number of channel terms are in fact zero. This highlights two aspects. Firstly, that there may be a connection between circuit synthesis and the fact that particular compositions of the process modes considered give a zero channel. Secondly, while employing a decomposition as in Equation C6 recovers the previously known result that frequencies correspond to differences between any two eigenvalues of the generator, our present approach also offers a route to determine those frequencies when the unitary is described in circuit form.
Appendix D: Proof of Theorem 4 Theorem 13. Writingρ(θ) = U(θ)(ρ 0 ) for the noisy implementation of the target state ρ(θ) we have where now the set of frequenciesω k are no longer necessarily indexed with a discrete subset of an integer lattice bounded by 1.
Proof. One may formally writeŨ(θ) = E • U(θ), where the noise channel E may itself be dependent on the angles θ.
One may then employ decompositions as in Lemma 3 for E so that only the quasiprobability distribution carries an angle dependency, namely Therefore the noisy expected values take the form where we have used that the adjoint Pauli reset channel is S † j (O) = I P j |O|P j for some eigenstate |P j of a Pauli operator. Following the analysis in the previous section, tr[ρ(θ)C † i (O)] = k∈Λ c k (C † i (O))e iω k ·θ where we explicitly add the dependency of the coefficients c k on the observable. This implies that The second summation can be absorbed into the ω k = 0 term giving the intended result. Let us denote by S the (maximal) frequency support for the Fourier decomposition of the unitary channel U(θ). For any given observable, the frequency spectrum of O ρ(θ) will be included in S, but may contain fewer modes. As we have seen in the previous section, for each independent parameter θ i the frequency spectrum is included in a finite lattice S i := {ω ki = −2a i · k i : k i ∈ Z ×ri 3 } over Z 3 with real basis vectors −2a i which can be determined from the circuit description of U i (θ i ). On the other hand, there's no a priori constraint for q i , q i to have discrete spectra since the noise channel may not present periodicity in the angles.

Appendix E: Resource requirements and nonuniform sampling
As mentioned in the text, sampling overhead is the largest obstacle to a pratical implementation of spectral analysis methods. One-dimensional DFT up to a frequency of N would require sampling d = 2N + 1 points, itself a linear scaling. However, the scaling in the dimension is unfavourable as it is exponential, practically limiting the applicability of the method to small sets of parameters. In a practical setting the runtime is also affected by the requirement of high shot counts to reduce shot noise. In itself, however, the method could still be useful even in these conditions. A variational circuit with several parameters could be broken down into sets of parameters which then could be mitigated for noise individually. Furthermore, one might expect that different parameterised gates would be affected differently by noise based on factors such as their order and the noise characteristics of the qubits they act on. For example the effect of the first gates in the circuit would be diluted by successive noise channels. Therefore, one might choose to focus on the most noisy gates in order to maximise the benefit of mitigation.
In addition, we remark that many variational algorithms of interest do not feature many individual parameters, but rather a few parameters that govern larger sets of correlated gates. In that case, the sampling points would be much reduced, even when accounting for the larger set of frequencies that need to be sampled. For example, while the spectrum of M uncorrelated single-qubit rotations would have size 3 M , correlating the angles into a single parameter would require sampling a number of points linear in M .
Finally, the use of advanced signal extraction techniques might enable these methods to work with much reduced sets of data. There exists an array of techniques that allow for the retrieval of the most significant Fourier coefficients from a signal, using a subexponential amount of samples [65][66][67][68]. In the case of sparse signals, techniques such as the sparse fast Fourier transform (sFFT) actually allow for complete reconstruction with sampling much below the Nyquist rate [69]. Therefore, if the quantum signal consists of a few large Fourier coefficients or, even better, if it is indeed sparse, these techniques could allow to circumvent the exponential sampling requirements in the case of many parameters. Interestingly, they would also apply an implicit thresholding by selecting only the most significant coefficients, and therefore is expected to provide some denoising effects.

Non-integer and non-equidistant samples or frequency spectra
In some cases, it might be desirable to get an estimate of the signal at non-integer frequencies, or spectra that are not equidistant. This might be relevant in case, for example, the error channel is suspected to depend in a nontrivial way on a parameter, leading to frequencies that are non-integer multiples of the parameter's frequency. This problem is known as non-uniform DFT or NUDFT and various approaches have been developed that implement an efficient version (NUFFT), based on interpolation [70][71][72] or low-rank approximations [73]. The discrete Fourier transform can also be implemented on incomplete data or nonuniform sampled data, while returning frequency data on a uniform support, known as type II NUDFT [73]. Fast algorithms exist also in this scenario, which similarly use approximations and therefore come at the cost of reduced accuracy [72,73], however might be sufficient as a rough error estimation technique. There exist scenarios where a large amount of nonuniform data points are generated as a byproduct, for example in the optimisation of a variational algorithm. Using nonuniform estimation, it might be possible to implement spectral noise evaluation at no additional sampling cost. Finally, we note the connection between the spectral analysis of quantum algorithms and signal processing in NMR. The latter similarly features a costly sampling procedure that generates multidimensional data, which then needs to be processed into its spectral components. Techniques such as nonuniform sampling [74] and maximum entropy reconstruction [75] have been devised to minimise the sampling and therefore the running time, while reconstructing the image with accuracy. One can therefore envisage directly utilising similar techniques for quantum algorithm.
Therefore, the noisy Fourier coefficientsc k are homogeneously contracted.
Then, using Equation D4 the result follows. Consider a single Pauli noise channel N p := (1 − p)I + pP, which appears within a quantum process For this we have the following Proof. First we consider the case of p = 1, that is, a Pauli error P that occurs within the quantum process Assume that each U i (θ i ) = e −iPiθi/2 where P i are Pauli operators themselves, and that the unparameterised unitaries are Clifford as well. Then since Pauli operators either commute or anti-commute then propagating a Pauli error P through the circuit will change a subset of θ i → −θ i . In terms of the individual Clifford paths V 0 • C 1 k1 • ... • C m km • V m labelled by vector k = (k 1 , ..., k m ) ∈ Z ×m 3 , the effect of a Pauli error within the circuit will result in a "noisy" path where P • V 0 • C 1 k m • V m labelled by vector k for which k i = −k i on the fixed (path-independent) subset of i ∈ {1, ..., m}. What happens is that since the lattice S contains both ω and −ω then this means that the spectrum of frequencies for noisyŨ will, just like those for U, also be included in S. However, some new modes that were previously zero due to cancellation of paths might find themselves with a small non-zero value under noise for specific target observables. Going back to the case where O is a Pauli operator, we have P (O) = ±O. Now, c k is equal to c k or its conjugate. To see this, consider any one of the components, say k j . For the case of k j = ±1, one has where C j r = 1 4 (U(0) − U(π)) and C j i = 1 8 (U(0) − 2U(π/2) + U(π)) are two real channels. Therefore, k i → −k i is equivalent to conjugating the coefficient, and by induction, it is so for any k as long as the number of affected nontrivial indices is odd. It follows that |c k (P (O))| = |c k (O)|. Therefore by the triangle inequality the noisy coefficients will obey |c k (O)| ≤ |c k (O)|.
Thus we see that a contraction of the Fourier coefficients is a feature of Pauli channels, and this result extends the previous one on global depolarising channels.
The case of general Vs, as well as noise channels that are linear combinations of different Pauli channels, and multiple Pauli channels, follow analogously from these considerations. Furthermore, state preparation and measurement (SPAM) errors can also be modelled by Pauli noise channels.
A special case of the above for which more can be said is the aligned Pauli error, which is when a channel is followed by a Pauli channel which is identical to its generator. Proof. Take the operator U (θ j ) = e −iPj θj /2 = C (j) If this channel is followed by a Pauli channel which is identical to its generator, the overall channel is P j U (θ j ) = U (θ j + π) = C (j) −1 , and therefore for a Pauli noise channel we get Seen from the spectrum's perspective, there will be a contraction of some coefficients without extra modes.
Lemma 17 (Non-unital channel). For non-unital channels, the Fourier coefficients will be modified and new modes might be present that only include a subset of the parameters following the channel.
Proof. As explained in Section III A, Clifford channels are not sufficient to represent arbitrary non-unital channels such as amplitude damping. One must also include Pauli reset channels, which trace out a qubit and initialise it with a specific eigenstate of a Pauli operator. Therefore, from the Clifford path point of view such channels will include additional paths that are independent of the initial state, and only depend on gates following the channel where N N U is the non-unital channel, while N U is the unital part and σ is the state which the channel resets to. The latter two need not be physical, however they still allow a description in terms of Clifford paths.
Finally, we explore what happens if the noise channels now depend on some of the parameters.
Lemma 18 (Parameter-dependent and correlated channels). For channels which depend on some parameters, we can haveS ⊂ S.
This is in contrast with all other types of noise explored previously.
Proof. For simplicity, consider a single noise channel that depends on a single parameter elsewhere in the circuit. Due to causality, the noise channel must follow the unitary with that parameter For noise channels and unitaries acting on a subset of the qubits, it is not guaranteed that the measurement operator falls into both light cones. Let us analyse the two distinct cases. In case it does, there may be Clifford paths which depend on both channels, and therefore the range of frequencies will be increased to include the additional ones from the noise channel. Denoting by ω the frequencies in the clean spectrum S, and byω k the frequencies fromÑ (θ k ), the new spectrum will beS = {ω +ω k }. In case it does not, the two channels will not interact, and therefore the frequencies are not added together, and the new spectrum will beS = S ∪ {ω k }. In either case we haveS ⊂ S.

Appendix G: Shot noise
Lemma 19 (Shot noise). Given a number of shots n s , each Fourier coefficient is normally distributed around the noiseless mean with standard deviation and similarly for the imaginary part. Note that the distributions at different k's are not independent.
Proof. First let us review the DFT convention we use in this paper. Given an m-dimensional signal {x i }, its DFT is defined as x j e −iθ j ·ω k (G2) with this convention Parseval's theorem is ||x|| 2 = d m ||F[x]|| 2 . For simplicity we assume that both the samples and the frequencies are considered on regular lattices, and we set θ i = 2πi/d and ω k = k. In the quantum case, the signal is corrupted by sampling noise, which follows a binomial distribution. For a sufficient number of samples n s , one can show that the signal is approximately Gaussian distributed around the expectation value x i , with a variance √ ns . Therefore, we can write the signal as a noiseless signal plus a Gaussian noisẽ Since the DFT is a linear operation, Let us focus on the noise signal. This is equivalent to a Gaussian signal with standard deviation 1/ √ n s scaled by a function of x: G σs( The Fourier transform of the noise can therefore be written as a convolution Now the following lemma can be proven: Lemma 20. The Fourier transform of a 1D normally distributed signal of size d with standard deviation σ is normally distributed with standard deviation σ/ √ 2d For an m-dim normal distributed signal of over a grid of volume d m , the same holds with a standard deviation of σ/ √ 2d m . Proof. Focus on the real part of F[G σ ] k (the result for the imaginary part follows by symmetry) First first notice that F[G σ ] k = 0. Now consider the variance Since each x m is independently distributed, x j x j is only nonzero when j = j All other moments are zero as the higher moments of a normal distribution are zero. Therefore, the distribution is normal with mean 0 and standard deviation σ √ 2d . A similar argument leads to the result for higher dimensions. Finally, it remains to be shown that the convolution of a normally distributed signal and an arbitrary signal is still normally distributed. We can show Lemma 21. Take an arbitrary deterministic signal {y k }. Then [G σ * y] k is a normally distributed signal with mean 0 and standard deviation σ||y|| 2 . Note that this time, the distributions at different k's are no longer necessarily independent.
Proof. By definition of the convolution, Now we have [G σ * Y ] k = 0 as the normal distribution has zero mean. For the variance we can use a similar argument as before As before, all the higher moments vanish, implying a normal distribution. To see that the distributions are no longer independent in general, consider the two-point correlation Therefore the correlation between the distributions at k, k depends on the autocorrelation characteristics of the coefficients y k .
Combining the results of these two lemmas, one deduces that each Fourier coefficient F[x] k is normally distributed around the noiseless mean F[x] k with standard deviation where in the second equality we used Parseval's identity. The imaginary part is identically and independently distributed because of symmetry.
Proof. As a reminder, we use the vectorised notation c for the Fourier coefficients over all Paulis: [ c] k,i = c k (P i ). Consider the following expression for the fidelity between a pure state and an arbitrary state [44] F where the summation is over some informationally complete set of observables, which we can take to be the normalised Pauli observables: χ i = P i / √ 2 n . Now consider the fidelity between a state produced by a noisy parameterised quantum circuitρ(θ) and its exact counterpart ρ(θ).
In the Fourier picture, the coefficients of the fidelity as a function of θ are given by a convolution between the Fourier coefficients of the expectation values of the Pauli observables where the discrete convolution is defined as: Therefore, the set of Fourier coefficients over all Pauli observables determines the fidelity as a function of the parameters. If we define the average fidelity over all sampled parameters: we see that it is equivalent to F[F ] 0 . Hence: As a remark, for the average fidelity defined as above to correspond to the average over all possible parameters F (ρ(θ),ρ(θ))d m θ a sufficient condition is for the sampling rate to be twice the maximum frequency of the signal, via Nyquist-Shannon sampling theorem.
We also have a corresponding lemma for the purity: Lemma 23 (Average purity). The average purity of the output state over all parameters is proportional to the squared norm of the vector of Fourier coefficients: Proof. In Section II A we saw that the noiseless cost function, when expressed as a trigonometric polynomial, has coefficients c k ∈ {0, ±1} with support Λ as defined in Theorem 2. We also saw in Section III A that noise channels introduce a perturbation in these coefficients, such that under noise they becomec k with potentially different support Λ. Therefore, given perfect access to the noisy cost function, as long as |c k − c k | ≤ 1 2 ∀k ∈ Λ, a thresholding algorithm can perfectly reconstruct the noiseless trigonometric coefficients by S(c k ) = round(c k ) if k ∈ Λ; 0 otherwise.
Conversely, if noise is larger than the threshold, then it is not guaranteed that the outcome will be the correct noiseless landscape. This is a consequence of the fact that parameterised quantum circuits are universal approximators, as proven in [32]. Therefore a landscape produced by a highly noisy state could be corrected to one produced by another, incorrect, circuit.
In Figure 6 we show a practical example of reconstructing such a landscape. The landscape is sampled at different numbers of shots and therefore different levels of noise, showing the existence of a well-defined noise threshold for perfect reconstruction.

Filters for noise-induced frequency modes
In line with classical signal processing, some of the simplest filters that can be applied are band-pass filters, that allow particular frequencies while eliminating the others. These can be designed based on knowledge of the theoretical frequency spectrum, which in the most general case is given by Theorem 2. In general, given an observed functionf of quantum expectation values on a support spanned by a basis {ψ k } (which may be the Fourier basis or any other basis of choice) indexed by a latticeΛ, as well as a known exact support indexed by a lattice Λ ⊂Λ, the denoised function is given by In other words, such a filter cuts off all frequencies beyond those expected to be output by the circuit. Such a method would be especially helpful to mitigate correlated noise that can give rise to high-frequency modes. However, it would most likely not be helpful for other non-correlated noise channels, as well as being more resource-intensive by requiring the resolution of a larger set of frequencies.
For specific circuits, it is possible to deduce additional characteristics that the noiseless spectrum should have, allowing for an improved noise mitigation. For example, take the case where the measurement operator is local, i.e. acts on only a subset of qubits. Then it is clear that its expectation value can only depend on the parameters in its backwards light-cone. For a more involved example, assume the input state ρ 0 is known, and the parameters of interest are those of the first r unitaries, which are Pauli gadgets U i (θ i ) = e −iPiθi/2 , i = 1, 2, · · · , r. Further, suppose that all P i 's commute, such that the ordering of the Pauli gadgets does not matter. All the subsequent gates, as well as the measurement operator, are arbitrary. Then, if [ρ 0 , P i ] = 0 for all i ≤ r, it follows that f must contain terms where either all parameters θ 1 , · · · , θ r appear, or none of them do. This is because a parameterised Pauli gadget that does not commute with its input state gives an output state that is a non-constant function of that parameter. A similar reasoning can be applied on the measurement operator and by extension to the expectation value. These conditions apply in many situations of practical interests, thereby affording a more refined error mitigation than general circuits.

Thresholding
The previous filtering methods relied on specific knowledge of the circuits. It is desirable to devise mitigation methods that would apply in general, and therefore would need to be agnostic to the circuit structure. One such method is based on isolating the most significant coefficients. In classical signal processing, this is known as thresholding, and was first studied in Ref. [76]. As a basic review of the method, thresholding applies a non-linear transform to the coefficients of some basis Reconstructing the landscape of a classically simulable circuit as run on Quantinuum H1-1 system, at different numbers of shots. Left is raw landscape, right is after rounding of the trigonometric coefficients. Colour indicates the height. Perfect reconstruction is obtained for all experiments except the 1-shot one, the exact (noiseless) landscape corresponds to the last three diagrams in the right column.
There exist two common choices for the transform S, known as 'hard' and 'soft' thresholding. Hard thresholding has S H T (x) = x if |x| > T 0 if |x| ≤ T , while soft thresholding has S S T (x) = max(1 − T /|x|, 0)x [77].
In [76] it was proven that, given an N -sparse signal perturbed by additive Gaussian noise with mean 0 and standard deviation σ, the optimal threshold is T = σ √ 2 log N , however in practice it is observed that T = O(σ) is sufficient for both hard and soft thresholding [78].
Thresholding methods rely on the basic assumption that the noiseless signal is sparse, or approximately sparse, in the basis of interest. As this in general is not the case for quantum algorithms, we only claim that thresholding be useful on a heuristic level. Another assumption that might not hold is that of additive Gaussian white noise. In the Fourier basis, this is only true for shot noise, however quantum noise will not generally obey these requirements. At the same time, from an experimental point of view, it does make at least practical sense to assume Gaussian noise to reflect the lack of knowledge of these noise processes. To this end, estimates of σ could be derived from a combination of the predicted sources of error, including known decoherence and measurement error rates.