{'fraction_non_alphanumeric': 0.059911043220415135, 'fraction_numerical': 0.020711654236678947, 'mean_word_length': 3.7363549313756783, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 42, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A framework for engineering quantum likelihood functions for expectation estimation

We develop a framework for characterizing and analyzing engineered likelihood functions (ELFs), which play an important role in the task of estimating the expectation values of quantum observables. These ELFs are obtained by choosing tunable parameters in a parametrized quantum circuit that minimize the expected posterior variance of an estimated parameter. We derive analytical expressions for the likelihood functions arising from certain classes of quantum circuits and use these expressions to pick optimal ELF tunable parameters. Finally, we show applications of ELFs in the Bayesian inference framework.


Introduction
Likelihood functions play a fundamental role in various quantum algorithms ranging from quantum channel parameter estimation [1], quantum metrology [2], to quantum phase estimation [3][4][5] and amplitude estimation [6]. The ability to realize likelihood functions that are otherwise infeasible with only classical resources allows one to take advantage of quantum mechanics to significantly accelerate sampling and measurement processes. The problems encountered in many of these settings [1,2,6] can be likened to the problem of finding the bias 1 2 (1 + q) of a coin, where q ∈ [−1, 1] is an unknown parameter. Instead of the likelihood function p(d|q) = 1 2 [1 + (−1) d q], d ∈ {0, 1}, that arises in attempting to classically estimate q by direct coin flipping, quantum techniques allow for realizing likelihood functions of the form p(d|q) = 1 2 [1 + (−1) d f (q)] where f (q) is a function that depends on the specifics of the quantum scheme. This opens up fundamentally new opportunities for accelerating parameter estimation 1 .
Here we focus on the task of estimating the amplitude of overlap Π between two quantum states that differ by a unitary transformation U . This task encompasses a broad variety of quantum algorithms and techniques, including the SWAP test [7] and variants for estimating general state overlaps, expectation estimation [8,9] in the special case where U is also a Hermitian operator, and phase estimation [3,4,10,11] in the special case where U = e −iHt for some Hermitian operator H and both states are identical and an eigenvector 2 of U . Though some of these works may not explicitly refer to the output distribution p(d|Π) of the measurement outcome d as a likelihood function, it can be argued that the quantum advantage of these schemes derive from the ability to realize likelihood functions that are beyond classical possibilities.
In this work, we are motivated by likelihood functions as a way of shedding light on an origin of quantum advantage that has perhaps been previously underappreciated. Our specific approach is to investigate the inferential power of not only the likelihood functions that have commonly arisen in the literature (which we call "Chebyshev likelihood functions" (CLF) in this paper), but also a broad class of tunable likelihood functions that can be generated by quantum mechanical means (namely the "quantum-generated likelihood functions"). Our results show that the quantum-generated likelihood functions allow for more effective information gain than CLFs during inference, leading to further quantum speedup than previous CLF-based schemes. In addition, we develop an alternative scheme for amplitude estimation based on quantum-generated likelihood functions that does not involve ancilla qubits. A similar scheme has also been considered recently [6] using CLFs.
This work complements the results presented in [12], where we introduced efficient schemes based on engineering likelihood functions to estimate the expectation values of quantum observables. These engineered likelihood functions (ELFs) are obtained by choosing tunable parameters in a parameterized quantum circuit that minimize the expected posterior variance of an estimated parameter. The algorithm in [12] utilizes a multi-round Bayesian updating scheme to reduce the expected posterior variance of the parameter of interest. In this paper, we present a framework for characterizing and analyzing ELFs that forms the basis for the approximate optimization methods used in [12]. While [12] considers the more realistic case of noisy ELFs, this paper concentrates on the idealized case where the ELFs are noiseless. It turns out that studying this idealized case already suffices for gaining useful insights on the behavior and properties of these ELFs.
The rest of the paper is organized as follows. In Section 2, we introduce the concept of quantumgenerated likelihood functions through the lens of amplitude estimation. We describe two schemes, called the ancilla-based and ancilla-free schemes, and derive analytical expressions for their likelihood functions as cosine polynomials and trigono-multivariate polynomial functions. In Section 3, we define our objective function, namely the expected posterior variance, and derive simplified expressions for it as we make various assumptions. In Section 4, we combine the results of Section 2 and 3 to show how the tunable parameters in the likelihood functions can be optimized to reduce the expected posterior variance. We also present some numerical results based on solving this optimization problem that demonstrate the performance of various ELFs. For a glossary of some of the definitions and notation used in this paper, see Appendix A.

.1 Formulation of problem
For positive integers n ∈ Z + , let A be an n-qubit unitary operator and P be an n-qubit Hermitian unitary operator, i.e.
A † A = I, P = P † , P 2 = I. (1) Write |A = A |0 n , where |0 n is the all-zero computational basis state on n qubits. The computational task that we consider in this paper is the estimation of the (arccosine of the) expectation value θ = arccos( A| P |A ) ∈ [0, π].
Consider the subspace S = span{|A , P |A }. Note that the assumption in Eq. (3) implies that S is a two-dimensional subspace. This allows us to define A ⊥ as the unique state in S that is orthogonal to |A , i.e.
By construction, B = {|A , A ⊥ } forms an orthonormal basis for S . Henceforth, we shall label |A and |A ⊥ as |0 = 1 0 and |1 = 0 1 respectively and refer to S as the logical space, which is to be contrasted with the physical space describing the n-qubit system. We shall extend the bar notation to certain operators on S . For example, we will denote the Pauli matrices with respect to the basis B bȳ In the basis B, P may be written as P = cos(θ)Z + sin(θ)X = cos θ sin θ sin θ − cos θ .
In constructing our estimation algorithm, we assume that we are able to perform the following primitive operations. First, we assume that we are able to prepare computational basis states |0 n and apply A to them to obtain |0 . Next, we assume that we are allowed to apply the following operations on the physical qubits: U (θ; α) for any angle α ∈ R and V (β) for any β ∈ R, as well as controlled versions of these operations, namely c-U (θ; α) = |0 0| ⊗ I + |1 1| ⊗ U (θ; α) and c-V (β) = |0 0| ⊗ I + |1 1| ⊗ V (β). Furthermore, we assume that we can apply the single-qubit Hadamard gate H = 1 √ 2 1 1 1 −1 to the physical qubits. Finally, we assume that we are allowed to perform computational basis measurements as well as measurements of the operator P (here, a measurement of P corresponds to the projection-valued measure { I+P 2 , I−P 2 }).

Schemes for expectation estimation
We now describe two different schemes for expectation estimation that we will focus on in this paper. Each of these schemes, which will use only the primitive operations that were listed in Section 2.1, depends on some tunable parameters, which we collect in a single vector x = x 1 x 2 . . . x 2L ∈ R 2L . Here, the variable L ∈ Z + represents half the number of tunable parameters in each scheme. The vector x is tunable in the sense that we will later (specifically, in Section 4) tune it to optimize some objective function. For this section, however, it would suffice to treat x as fixed. The first scheme, called the ancilla-free (AF) scheme because it does not make use of any ancilla qubits, proceeds as follows: Algorithm 1 Ancilla-free (AF) scheme 1: Start with the n-qubit state |0 2: for i = 1, . . . , L do 3: Apply the operator U (θ; x 2i−1 )

4:
Apply the operator V (x 2i ) 5: Perform a measurement corresponding to the Hermitian operator P , i.e. perform the projective measurement ( I+P 2 , I−P 2 ) with outcomes (0, 1) The second scheme, called the ancilla-based (AB) scheme because it involves the use of a single ancilla register, proceeds as follows: Algorithm 2 Ancilla-based (AB) scheme 1: Start with the input |0 in the n-qubit data register and |0 in the single-qubit ancilla register 2: Apply the Hadamard gate H to the ancilla register 3: for i = 1, . . . , L do

4:
Apply the operator c-U (θ; x 2i−1 ) = |0 0| ⊗ I + |1 1| ⊗ U (θ; x 2i−1 ), with the control being the ancilla register and the target being the data register 5: Apply the operator c-V (x 2i ) = |0 0| ⊗ I + |1 1| ⊗ V (x 2i ), with the control being the ancilla register and the target being the data register 6: Apply the Hadamard gate H to the ancilla register 7: Perform a computational-basis measurement on the ancilla register to obtain outcomes (0, 1) Circuit diagrams illustrating these schemes are given in Figure 2.1, where we have introduced the operator to describe the overall unitary operator resulting from 2L − 1 alternations of the rotations U (θ; ·) and V (·). For each of these schemes, we denote the single-bit measurement outcome by d ∈ {0, 1}.
Ancilla-free circuit: Ancilla-based circuit: Each of these schemes is associated with a likelihood function, which will play a central role in this paper. Specifically, the likelihood function associated with the scheme A, where A = AF, AB (which stand for ancilla-free and ancilla-based respectively), and tunable parameters x is defined to be the likelihood of the random variable θ (which encodes information about the expectation value A| P |A ) given the measurement outcome d. In other words, this likelihood function, denoted L A (θ; d, x) = Pr(d|θ; x), is the probability of obtaining the outcome d in scheme A given the unknown parameter θ and tunable parameters x. Since d takes only the values 0 and 1, the likelihood function can be written as for some function Λ A (θ; x). We shall call the function Λ A the bias associated with scheme A.
In the next proposition, we derive expressions for the biases Λ A (θ; x), which will be useful for the rest of this paper. For this purpose, we first extend the definition in Eq. (9) slightly so that the second argument of Q can be a vector of arbitrary nonzero length. Let α ∈ Z + be a positive integer. For θ ∈ R and an arbitrary vector z = (z 1 , . . . , z α ) ∈ R α , define where R( · ) = U (θ; · ), α odd, Next, define to be the expectation value of Q(θ; z) in the state |0 . These allow us to state the following proposition.
Proposition 1. Let θ ∈ R and x ∈ R 2L . The ancilla-free and ancilla-based biases are given by where x R denotes the reverse of x.
In the ancilla-based case, the state just before measurement is where the second line follows from a straightforward calculation. Hence, the probability of obtaining the outcome d ∈ {0, 1} when ς is measured is Comparing this with Eq. (10), we obtain

Series expansions of the ancilla-free and ancilla-based biases
In this subsection, we will derive series expansion formulas 3 for both the ancilla-free and ancilla-based biases, which will be useful in Section 4. In order to state and prove the theorems, we first present some necessary preliminary definitions and lemmas in Sections 2.3.1 and 2.3.2.

Mathematical preliminaries I: Expansion formulas
Let n, k ∈ N and u, v ∈ F 2 . The central object that we introduce here is the set Θ n ukv , which is (informally) defined as follows: . . x n ∈ F n 2 for which the string r xn . . . p x4 q x3 p x2 q x1 can be converted to p u (qp) k q v by repeatedly applying the replacement rules pp → ε and qq → ε, where r = p if n is even and r = q if n is odd.
For example, the string 101101011 ∈ Θ 9 010 since For a formal definition of Θ n ukv , see Appendix B. By convention, we take Θ n ukv = ∅ whenever k / ∈ N. The following theorem, which we prove in Appendix B, characterizes the set of k values for which Θ n ukv is nonempty.
Lemma 2. (also Theorem 17) Let n ∈ N, u, v ∈ F 2 and k ∈ N. Then, We now introduce our key lemma, which we prove in Appendix B: where R = P if n is even and R = Q if n is odd. 3 For the series expansion formulas, see Theorems 10 and 11, which this subsection will culminate in.
By virtue of Lemma 2, the sum (25) has only a finite number of nonzero terms. Keeping only the nonzero terms in the expansion gives (a n 0 + a n 1 R) . . . a 4 0 + a 4 1 P a 3 0 + a 3 1 Q a 2 0 + a 2 1 P a 1 The next important object that we introduce is Ξ, which is defined as follows: for α ∈ Z + and l ∈ N, let It is straightforward to check that Next, we use Lemma 2 to characterize the set of k values for which Ξ n l is nonempty.
In Appendix C, we strengthen both Lemmas 2 and 4 by finding the cardinalities of the sets Ξ α l and Θ n ukv . These cardinalities will be useful for bounding the space complexity of computing various sums related to Eq. (25).
A nice property that ζ y ( x) satisfies is the following multiplicative property: The functions ζ y ( x) can be used to define the notions of trigono-multilinearity and trigono-multiquadraticity.
Equivalently, the trigono-multilinear functions are those that can be written as and the trigono-multiquadratic functions are those that can be written as where ξ y1...y k , η y1...y k ∈ C. When k = 1, the above expressions simplify as follows. A unary trigono-multilinear function is of the form and a unary trigono-multiquadratic function is of the form where ξ 0 , ξ 1 , η 0 , η 1 , η 2 ∈ C. For a larger example, consider k = 4. A 4-ary trigono-multilinear function takes the form and a 4-ary trigono-multiquadratic function takes the form Trigono-multilinear and trigono-multiquadratic functions have various nice properties that are useful and of independent interest. We explore some of these properties in Appendix D.

Applying the expansion formulas to the quantum-generated biases
We will now apply the results of Sections 2.3.1 and 2.3.2 to the quantum-generated biases Λ A (θ; x). Specifically, we will use the expansion formula of Eq. (25) to expand the functions Q(θ, z), Q 00 [ z](θ) and the biases Λ A (θ; x) and show that Λ AF (θ; x) and Λ AB (θ; x) are trigono-multiquadratic and trigono-multilinear functions (of θ) respectively. For an example, we refer the reader to Appendix E, where we work out explicit expressions for the expansion formulas in the case when L = 1.
First, the expansion formula when applied to Q(θ; z) gives the following expression.
Theorem 8. Let z ∈ R α . Then, where l y is the unique l for which y ∈ Ξ α l . In other words, is a (i) cosine polynomial in θ of degree α with Fourier coefficients (ii) trigono-multilinear function in z of arity 2α with coefficients Proof.
(ii) Let l y be the unique element in {l ∈ N : y ∈ Ξ α l }. Then, where the last line follows from the fact that Next, we will use Theorem 8 to expand the biases Λ A (θ; x). But before we do so, we first prove the following lemma: (56) Proof. We shall prove the forward direction. By symmetry, the proof of the backward direction is obtained by switching the roles of a and c in the proof.
Consider the case when l > 0. Let where ∼ is the equivalence relation defined in Eq. (206). Since string reversal preserves ∼ (see Eq. (207)), Now, p(qp) l and (qp) l−1 q are palindromes and mapped to themselves under (·) R ; and (qp) l and p(qp) l−1 q are mapped to each other under (·) R . Hence, Eq. (59) becomes The proof for the case l = 0 proceeds similarly, with the last two clauses of each 'or' statement above deleted.
This lemma may be used to expand the ancilla-free bias.
where l a c is the unique l for which a1 c R ∈ Ξ 4L+1 l and In other words, (ii) trigono-multiquadratic function in x of arity 2L with coefficients In the above, s ≡ n t means s ≡ t (mod n). Proof.
(i) By Eq. (14), where Writing Substituting this back into Eq. (70) gives where < denotes any lexicographical ordering of strings.
First, we calculate by interchanging a and c Hence, where we used the fact that for all α, β ∈ Z, where ν a is given by Eq. (63). Therefore, Note that replacing a < c with c < a does not change the value of 2 + 3 ( * * ). Indeed, , by switching the labels a and c where the last line follows from the facts that By taking the average of Eqs. (77) and (78), we obtain Next, we calculate which can be expressed as Substituting Eq. (79) and (81) into Eq. (73) gives (ii) By arranging the terms in the sum differently, we obtain which completes the proof of the theorem.
Note that the Fourier coefficients (65) can also be expressed as where Next, we expand the ancilla-based bias.
Theorem 11. Let x ∈ R 2L . Then, where l y is the unique l for which y ∈ Ξ 2L l and ν s is given by Eq. (63).
In other words, (ii) trigono-multilinear function in x of arity 2L with coefficients Proof.
Therefore, the Fourier coefficients (90) can be simplified as (ii) From Eqs. (93) and (92), In summary, Theorems 10 and 11 give the expansion formulas for the ancilla-free and ancilla-based biases respectively, which we will use in Section 4. At least two special cases of these expansion formulas yield nice simple expressions and are of interest: (i) when the angles x are chosen to be (π/2) 2L and (ii) when L = 1. We study Case (i) in Section 2.4 and as mentioned above, Case (ii) in Appendix E. Finally, in Appendix F, as an application of the expansion formulas, we derive expressions for the leading terms in the cosine expansions (65) and (90).

Special case: Chebyshev likelihood functions
Here we will consider the special case when the tunable parameters x ∈ R 2L in Eq. (10) are chosen to be x = (π/2) 2L and show how the results in Sections 2-2.3 simplify in this case. In particular, we shall show that the biases of the likelihood function in both the ancilla-free and ancilla-bassed schemes can be written in terms of Chebyshev polynomials in 0 | P (θ) |0 . Due to this, we refer to the likelihood functions (10) with parameters x = (π/2) 2L as Chebyshev likelihood functions (CLFs).
Setting α = β = π/2 in Eqs. (7) and (8) gives Hence, Eq. (9) evaluates to where the matrix above is written in the basis {|0 , |1 }. By making use of Proposition 1, for example, the ancilla-free and the ancilla-based biases may be expressed as Hence, by Eq. (10) the likelihood functions corresponding to these biases are By rewriting θ in terms of the expectation value 0 | P (θ) |0 using Eq. (2), the above biases can be expressed in terms of Chebyshev polynomials: where T m (x) = cos(m arccos x), for |x| ≤ 1, is the nth Chebyshev polynomial of the first kind. As explained above, it is for this reason that the likelihood functions in (99) are called Chebyshev likelihood functions. Note that the biases (98) can trivially be expanded as Fourier series: Hence, the Fourier coefficients given by Eqs. (65) and (90) can be read off to be 3 The expected posterior variance: a Bayesian perspective In this section, we develop tools for understanding the expected posterior variance, which will be useful in Section 4 when we apply them to the quantum-generated likelihood functions that we introduced in Section 2.
The treatment in this section, which can be read independently of Section 2, is fairly general and applicable to a broad range of likelihood functions.

General form
Suppose that we have a (continuous) prior distribution p(θ) = p θ (θ) that reflects our current state of knowledge about the value of some parameter θ ∈ Θ, where Θ ⊆ R. To update our knowledge about θ, we may design an experiment that yields measurement outcomes d ∈ Ω, where the set of possible measurement outcomes Ω ⊆ N is assumed to be a discrete set. The probability of obtaining an outcome d given the unknown parameter θ is captured by the (continuous) likelihood function L(θ; d) = P d|θ (d|θ). Our knowledge of θ after performing Bayesian updating is described by the (continuous) posterior distribution where is the marginal distribution of d. For Eq. (103) to be well-defined, the outcome d must have a nonzero probability of occurring, i.e. d ∈ Ω ′ := {d ∈ Ω : P d (d) = 0}. Note that different experiments could give rise to different likelihood functions, and hence, different amounts of information gain about θ. Our goal is to engineer likelihood functions that allow us to minimize the expected posterior variance, defined as In the above formula, Var θ|d (θ|d) is the variance of the posterior distribution upon obtaining outcome d, i.e. where are the first and second moments of p θ|d (·|d) respectively. The expression for the expected posterior variance as given by Eqs. (105)-(108) involves the computation of several integrals, which may be computationally intensive in general. Hence, our goal in this section is to provide various simplifications of the formula (105) as we specialize to specific experiments that are relevant to this work. To this end, our first step is to show that the expected posterior variance can be written in terms of the prior mean and prior variance as follows: Theorem 12. The expected posterior variance is given by is the kth moment of the function L( · ; d)p(·). Proof.
where we used the fact that in the last line.
Note that Eq. (111) can also be expressed in the following form: We shall call the symbol V defined by Eq. (113) the variance reduction factor. The motivation for introducing V is that working with V turns out to be more convenient than working directly with the expected posterior variance when we specialize to specific domains Ω, prior distributions p(θ) and likelihood functions L(θ; d). We refer the reader to Figure 3.1 for a summary of the specializations that we will consider in Sections 3.2-3.4.1 as well as the results we obtained.

Two-outcome likelihood functions
In the rest of this paper, we specialize to the case when Ω = {0, 1}. In this case, we show that the expression for the expected posterior variance simplifies as follows.
Proof. Consider d∈{0,1} Equivalently, We first consider the case when I 0 = I 0 (0) = 1. In this case, Since L(θ; 1) and p(θ) are both continuous and nonnegative, it follows that This implies that Since Ω ′ = {0}, it follows that By symmetry, the case when I 0 = 0 is similar, and also gives E d Var θ|d (θ|d) = σ 2 . Finally, we consider the case when I 0 / ∈ {0, 1}. In this case, The last term of the above expression can be simplified as d∈{0,1} Hence, It turns out that Eq. (115) can be simplified if we expressed the expected posterior variance in terms of the bias, which we now define. For a two-outcome likelihood function L(θ; d), where d ∈ Ω = {0, 1}, we define the bias to be Λ(θ) = 2L(θ; 0) − 1.
This gives the following expression for the likelihood function in terms of the bias Let us now define We shall call b the expected bias and χ the chi function. It is straightforward to check that b and χ can be expressed in terms of I 0 and I 1 , which were defined in Eq. (116), as follows: Substituting these expressions into Eq. (115) gives with the variance reduction factor (113) given by 3.3 Two-outcome likelihood functions with a Gaussian prior

Variance reduction factor with a Gaussian prior
In this section, we fix the prior distribution to be the Gaussian distribution with prior mean µ ∈ R and prior variance σ 2 ∈ R + . As before, we denote the bias by Λ(θ). The expected bias and the chi function are given by The Gaussian prior has the following nice property 4 : differentiating the expected bias with respect to the prior mean gives the chi function, i.e.

Bias as a Taylor series
We will now derive series expansions for b(µ, σ) and χ(µ, σ) when Λ(θ) is written as a Taylor series at µ, i.e.
Substituting this into Eq. (137) gives where in the last line we used the following identity: for σ > 0 and n ∈ N, where (with the empty product equal to 1) denotes the double factorial of n.
Differentiating this expression with respect to µ gives Equivalently, the derivatives of the expected bias and the chi function are given as follows:

Bias as a trigonometric Fourier series
Next, we will derive series expansions for b(µ, σ) and χ(µ, σ) when Λ(θ) is written as a trigonometric Fourier series with period 2π, i.e. where where δ l is the Kronecker delta which is equal to 1 if l = 0 and 0 otherwise.
where in the last line we used the following identities: for σ > 0 and µ, l ∈ R, Differentiating Eq. (152) with respect to µ gives

Connection to Fisher information
Throughout this section, we will assume that the prior distribution p(θ; µ, σ) is Gaussian and given by Eq. (136), and that the bias Λ(θ) can be expressed as the Taylor series given by Eq. (141). We will consider the limiting behavior of the expected posterior variance as σ vanishes and show the relationship between this quantity and Fisher information. The Fisher information is commonly used to capture the power of a likelihood function in the estimation process [13]. The Fisher information is defined as Larger Fisher information indicates that the data is expected to be more informative of the value of the unknown parameter θ. In practice, however, we cannot engineer a likelihood function to maximize the value of the Fisher information because we do not know the actual value of θ. Nevertheless, we can show that the Fisher information is closely related to the variance reduction factor V.
In the case of the two-outcome likelihood function, the Fisher information evaluates to In terms of the bias of the likelihood function (128), we can express the Fisher information as We now show that V can be approximated by the Fisher information when σ is small. Expanding the expression of the expected bias given by Eq. (145) gives Expanding the expression of the chi function given by Eq. (145) gives Hence, as long as 5 |Λ(µ)| = 1 (which implies that Λ / ∈ {±1}), the variance reduction factor (140) as σ goes to zero is equal to the Fisher information at θ = µ, Therefore, using Eqs. (134), the expected posterior variance when σ is small is approximately linear in the Fisher information:

Engineered likelihood functions
In this section, we apply the tools that we developed in Section 3 to the quantum-generated likelihood functions from Section 2. The problem that we wish to solve may be phrased as an optimization problem, which we will state in Section 4.1 (see Eq. (185)). In Section 4.3, we numerically solve this optimization problem to compare the performance of various engineered likelihood functions with each other and with the fixed-angle Chebyshev likelihood functions.

Minimizing the expected posterior variance
Our goal is to engineer quantum likelihood functions by choosing appropriate tunable parameters x ∈ R 2L in the parametrized quantum-generated likelihood functions given by Eq. (10). Specifically, we will choose these tunable parameters x to minimize the expected posterior variance (105) of the unknown parameter θ = arccos( 0 | P |0 ) given by Eq. (2). The likelihood functions that arise from such a minimization are called engineered likelihood functions. We will take the prior distribution to be the Gaussian distribution with probability density function given by p(θ; µ, σ) (see Eq. (136)) and the likelihood function to be the quantum-generated likelihood function L A (θ; d, x) = 1 2 1 + (−1) d Λ A (θ; x) given by Eq. (10). We will consider both the ancilla-free scheme (A = AF) and the ancilla-based scheme (A = AB).
To explicitly indicate dependence on the prior mean µ, the prior variance σ, the tunable parameters x ∈ R 2L and the scheme A, we shall denote the expected bias (137), the chi function (138) and the variance reduction factor (140) by respectively. By Eq. (134), the expected posterior variance may be expressed in terms of the variance reduction factor as Next, we find series expansions for the functions (176)-(178). By Theorems 10 and 11, the biases Λ A (θ; x), for A ∈ {AF, AB}, can be written as the cosine polynomials where and µ A l ( x)'s are given by Eq. (65) and (90). The series (180) allows us to use the machinery introduced in Section 3.3.3: by Eqs. (152) and (155), the bias and the chi function can be written as the sums and the variance reduction factor may be written as Our goal is to find tunable parameters x = (x 1 , . . . , x 2L ) ∈ R 2L that minimize the expected posterior variance (179). Due to the inverse relationship between the expected posterior variance and the variance reduction factor (see Eq. (179)), minimizing the former is equivalent to maximizing the latter. Since V(µ, σ; x) is 2π-periodic in each coordinate x i , it suffices to restrict the search space of each x i to (−π, π]. In other words, the optimization problem we wish to solve may be stated as: Note that the input prior variance σ in the optimization problem (185) is required to be positive to guarantee that Eq. (184) is well-defined. For the case when σ → 0, the results of Section 3.4 may be used. In particular, Eqs. (163) and (173) imply the following.
We will present some numerical results obtained by solving the optimization problem (185) in Section 4.3. Before we do that, we study the behavior and properties of the variance reduction factor (184) in the special case where the angles x are chosen to give rise of Chebyshev likelihood functions.
The following proposition lists a few useful properties of the variance reduction factor (191).
1. Periodicity (in µ) with period π q : For all µ ∈ R, 2. Minimum: For all µ ∈ R, with equality if and only if µ ∈ π q Z. 3. Maximum: For all µ ∈ R, with equality if and only if µ ∈ π 2q Z odd .
In the above, q = q(A) is given by Eq. (181). Proof.
1. This follows directly from Eq. (191) and the fact that sin 2 (qµ) and cos 2 (qµ) are both periodic and have period π q .
Note that Eq. (194) can be used to give an upper bound for the variance reduction factor that is independent of L: since the function q → q 2 e −q 2 σ 2 achieves a maximum of (eσ 2 ) −1 at q = 1 σ , it follows that with equality if and only if q = 1 σ and µ ∈ π 2q Z odd . Finally, we conclude with a proposition that characterizes the limiting behavior of the Chebyshev variance reduction factor as σ → 0: where q = q(A) is given by Eq. (181).
Proof. We first note that the bias (98) and its first two derivatives are given by where q and r are given by Eq. (181) and (190) respectively. If µ / ∈ π q Z, then Λ A (µ; x) = 1. By using Eq. (186), we obtain If µ ∈ π q Z, it follows from the expressions in Eq. (199) that Therefore, in this case, we have Hence, by Eq. (187), we obtain which completes the proof of the proposition.

Numerical simulations
The goal here is to solve the optimization problem (185). The objective function, which we seek to maximize, is the variance reduction factor, whose analytical expression is given by Eq. (184). To solve this optimization problem, we performed the following steps using Wolfram Mathematica [14]: (i) compute the Fourier coefficients µ A l ( x)'s using the expansion formulas given in Eq. (65) and (90).
(ii) compute the bias (182) and the chi function (183) and plug the resulting expressions into Eq. (184) for the variance reduction factor.
We present the results of this optimization in Figures 4.1-4.3, where we plot graphs of the variance reduction factor V A (µ, σ; x) versus the prior mean µ for different values of σ for L = 1, 2, 3. In each graph, we compare the engineered likelihood function (ELF) with the Chebyshev likelihood function (CLF) for both the ancilla-free (AF) and ancilla-based (AB) schemes. As seen from the plots, in both the AF and AB schemes, there exist values of µ for which the ELFs outperform the CLFs (i.e. the ELF variance reduction factor is larger than the CLF variance reduction factor). This gap in performance decreases as σ goes to zero, suggesting that using ELFs would be most beneficial when the prior variance σ is large.
Another property of the plots is that the ancilla-free schemes yield much larger values for the expected posterior variance than for the ancilla-based case. This can be explained by the fact that as cosine polynomials, the ancilla-free bias has degree 2L + 1 (see Eq. (64)), while the ancilla-based bias has only degree L (See Eq. (89)).

Concluding remarks
In this paper, we developed tools for characterizing and analyzing ELFs, focusing on the ancilla-based and ancilla-free schemes. Both these schemes involve alternate applications of generalized reflection operators, which may be visualized as rotations in a two-dimensional subspace. This visualization can be used to show that each of these schemes produces likelihood functions that can be written as cosine polynomials whose degree scales with the number of alternations. We showed that these polynomials can be used to derive analytical expressions for the expected posterior variance describing the parameter of interest. Finally, we presented simulation results to compare the performance of various ELFs with each other and to CLFs.
The results in this paper may be extended in a number of ways. Firstly, while we have limited the scope of this paper to only noiseless ELFs, the results here can be generalized to the case where the ELFs are noisy. This case-which arises when the states, transformations and measurements in circuits in Figure 2.1 are replaced by imperfect noisy versions of themselves, and which is arguably more relevant in this noisy intermediate-scale quantum [15] era, where near-term quantum devices are subject to high levels of noise-is treated in detail in a separate paper [12], which builds on the foundations laid here (see Appendix G for a brief discussion of incorporating noise into the ELF framework).
Secondly, while we have modeled the prior distribution by a Gaussian random variable (136), it might be appropriate in certain cases to model it using other distributions. We leave the sensitivity analysis on the prior distribution chosen to future work. Thirdly, while we have focused our attention on two specific schemes, namely the ancilla-based scheme and the ancilla-free scheme, we note that this framework can be extended to variants or extensions of these schemes. We leave this consideration for future work.

A List of mathematical symbols
We list in this appendix some of the mathematical symbols that appear in this paper.

B A product-of-sums expansion B.1 String reductions
Let s, t ∈ {p, q} * be strings. We say that s 1-reduces to t if there exist t 1 , t 2 ∈ {p, q} * such that where juxtaposition of strings in the above notation indicates string concatenation.
Also, we say (trivially) that s 0-reduces to t if s = t. Say that s reduces to t if there exists k ∈ N such that s k-reduces to t. In other words, s reduces to t if t can be obtained from s by repeatedly deleting substrings pp and qq. We write s → t if s reduces to t. For example, pppqqq → pq.
We say that s is irreducible if there does not exist r ∈ {p, q} * such that s → r and |r| < |s|. We will make use of the following notation: for u ∈ F 2 , let where ε is the empty string. Define It is straightforward to check that t (ukv) satisfies the following properties: 1. For all u, v ∈ F 2 and for all k ∈ N, the string t (ukv) is irreducible.
2. For all s ∈ {p, q} * , there exist unique u, v ∈ F 2 and k ∈ N such that s → t (ukv) .
It is easy to see that for each n ∈ N, the relation ∼ is an equivalence relation on the set of strings {p, q} n . For example, pqqpq ∼ ppqpp since they both reduce to q. Note that ∼ is preserved by string reversal, i.e. Let denote the set of strings s that reduce to t (ukv) . Note that M ukv forms a partition of {p, q} * .

B.2 The set Θ n ukv
We are now ready to define the set Θ n ukv . Let n ∈ Z + , k ∈ N and u, v ∈ F 2 . Define In other words, Θ n ukv is the set of strings x = x 1 x 2 . . . x n ∈ F n 2 for which the string r xn . . . p x4 q x3 p x2 q x1 reduces to p u (qp) k q v , where r = p if n is even and r = q if n is odd. By convention, for k / ∈ N, we take Θ n ukv = ∅.
The following theorem characterizes the set of k values for which Θ n ukv is nonempty.
Theorem 17. Let n ∈ Z + , u, v ∈ F 2 and k ∈ N. Then, Proof. We will consider the even and odd cases of n separately.
which implies that • First, we show that k ≤ m. By Eq. (217), • Second, we show that k = m. Suppose, for the sake of contradiction, that k = m. By Eq. (217), which implies that But By Eqs. (222) and (223), we get which implies that Substituting this into Eq. (217) gives which is a contradiction. Hence, k = m.
Note that x is a well-defined string in {0, 1} 2m+1 , i.e. each of the substrings in the definition (237) have non-negative length. To see this, note that when u = 0, m − k ≥ m − (m − u) = 0; and when u = 1, Therefore, Hence, This implies that Θ n ukv = ∅.

B.3 Product-of-sums expansion formula
We start by proving the following lemma.
Lemma 18. Let n ∈ Z + and P 2 = Q 2 = I. Let Then for all x ∈ Θ n ukv , Proof. Consider Lemma 19. Let n ∈ Z + and P 2 = Q 2 = I. Let {a y x : x ∈ F 2 , y ∈ [n]} ⊂ C. Then, (a n 0 + a n 1 R) . . . a 4 0 + a 4 1 P a 3 0 + a 3 1 Q a 2 0 + a 2 1 P a 1 0 + a 1 1 Q where R = P if n is even and R = Q if n is odd.
Proof. Consider (a n 0 + a n 1 R) . . . a 4 0 + a 4 1 P a 3 0 + a 3 1 Q a 2 0 + a 2 1 P a 1 0 + a . . a n xn R xn n . . . R x1 Note that by Theorem 17, Eq. (245) can also be written as (a n 0 + a n 1 R) . . . a 4 0 + a 4 1 P a 3 0 + a 3 1 Q a 2 0 + a 2 1 P a 1 0 + a 1 1 Q = u,v∈F2 C Cardinalities of Θ n ukv and Ξ α l What is the space complexity of storing each of the Fourier coefficients, of say, Eq. (51) and (65)? To address this question, it suffices to find the cardinality of the sets Ξ α l . To begin, we prove the following theorem, which gives the cardinality of the set Θ n ukv .
• Case: n = 2m even We first prove the following identity: for m ∈ Z + , if P 2 = Q 2 = I, then To prove Eq. (251), we make use of mathematical induction. The base case m = 1 is clearly true. Assume that Eq. (251) holds for m. Then, by the induction hypothesis, [(I + P )(I + Q)] m+1 = (I + P + Q + P Q) By Pascal's rule, and hence, which completes the inductive step and the proof of Eq. (251).
Next, by setting n = 2m and a x y = 1 for all x, y in Eq. (247), we get Comparing Eqs. (251) and (255) gives • Case: n = 2m + 1 odd We first prove the following identity: for m ∈ N, if P 2 = Q 2 = I, then Now, by expanding the sum J k , we obtain When k = 0, Eq. (259) evaluates to When k ≥ 1, Eq. (259) evaluates to Substituting these expressions for J k into 1 gives where the last line follows from the fact that which completes the proof of Eq. (257).
Next, by setting n = 2m + 1 and a x y = 1 for all x, y in Eq. (247), we get Comparing Eqs. (257) and (265) gives The following theorem gives the cardinality of the set Ξ α l .
Theorem 21. Let α ∈ Z + and l ∈ N. Then, i.e. for m ∈ Z + , Proof. We first consider the case when α = 2m is even. Since the sets in the union represented by Eq. Here, and Therefore, if l = 0, And if l ≥ 1, by Pascal's rule. Next, we consider the case when α = 2m + 1 is odd. As before, since the sets in the union represented by Eq. (27) Here, and 4 = 2m Therefore, if l = 0, And if l ≥ 1, which completes the proof of the theorem.

D Trigono-multivariate polynomial functions
Let k, d ∈ Z + . A k-ary function f : R k → C is a trigono-multivariate polynomial function of degree d if for all y ∈ {0, 1} kd , there exists ξ y ∈ C such that for all x ∈ R k , Denote the set of k-ary trigono-multivariate polynomial functions of degree d by T k d . Note that the definition (280) generalizes the notions of trigono-multilinearity and trigono-multiquadraticity: from Eqs. (33) and (34), T k 1 and T k 2 are the sets of k-ary trigono-multilinear and trigono-multiquadratic functions respectively.
It is easy to check that the sets T k d satisfy the following simple closure properties.
Proposition 22. Let k, d, e ∈ Z + . The sets T k d satisfy the following properties.
1. If f, g ∈ T k d , then f + g ∈ T k d .
2. If f ∈ T k d and g ∈ T k e , then f g ∈ T k d+e .
In particular, the product of two trigono-multilinear functions is a trigono-multiquadratic function.
Next we describe some properties of trigono-multilinear and trigono-multiquadratic functions. Recall that we have defined these functions by expressing them as the sum of exponentially many terms as in Eqs. (33) and (34), respectively. But sometimes it is more convenient to work with the following equivalent definitions of these functions.
Proposition 23. Let k ∈ Z + . A k-ary function f : R k → C is trigono-multilinear if and only if for all j ∈ [k], there exist (k − 1)-ary functions C j , S j : R k−1 → C such that where x = (x 1 , . . . , x k ) and x ¬j = (x 1 , . . . , x j−1 , x j+1 , . . . , x k ). We call C j and S j the cosine-sine-decomposition (CSD) functions of f with respect to x j .
Proof. The necessity of the given condition is easy to prove. Suppose f ( x) = y∈{0,1} k ξ y ζ y ( x). Then we set where z • 0 = z 1 . . . z k−1 0 and z • 1 = z 1 . . . z k−1 1, and obtain Eq. (281). Next, we prove the sufficiency of the given condition by induction on k. It is obvious for k = 1. Suppose f satisfies the given condition, i.e. f ( x) = C j ( x ¬j ) cos (x j ) + S j ( x ¬j ) sin (x j ) for some C j and S j , for all j ∈ [k]. Let w = (w 1 , . . . , w k−1 ) ∈ R k−1 be arbitrary. Let a = w • 0 = (w 1 , . . . , w k−1 , 0) and b = w • π/2 = (w 1 , . . . , w k−1 , π/2). Then we have whereĈ j ( w ¬j ) = C j ( a ¬j ) andŜ j ( w ¬j ) = S j ( a ¬j ), and . This means that both C k and S k satisfy the given condition for (k − 1)-ary functions. So by induction hypothesis, we know that both C k and S k are (k − 1)-ary trigonomultilinear functions, i.e. they can be expressed as in Eq. (33). It follows that f ( x) = C k ( x ¬k ) cos (x k ) + S k ( x ¬k ) sin (x k ) can be also expressed as in Eq. (33), i.e. it is a k-ary trigono-multilinear function.
Proposition 24. Let k ∈ Z + . A k-ary function f : R k → C is trigono-multiquadratic if and only if for all j ∈ [k], there exist (k − 1)-ary functions C j , S j , B j : R k−1 → C such that where x = (x 1 , . . . , x k ) and x ¬j = (x 1 , . . . , x j−1 , x j+1 , . . . , x k ). We call C j , S j and B j the cosine-sine-biasdecomposition (CSBD) functions of f with respect to x j .
We say that f ∈ T k d is real if its range is contained in R, i.e. f ( x) ∈ R for all x ∈ R k . It turns out that for real trigono-multilinear and trigono-multiquadratic functions, if we fix the values of all variables except x j , then we can easily determine the value of x j that maximizes (or minimizes) the function, provided that we can efficiently evaluate the CSD or CSBD coefficient functions of the function with respect to x j .
Similarly, suppose f : R k → C satisfies the condition in Proposition 24. Then arg max y |f (x 1 , . . . , x j−1 , y, x j+1 , . . . , x k )| = Arg[sgn (B j ) (C j ( x ¬j ) + iS j ( x ¬j ))] 2 , and max y |f (x 1 , . . . , x j−1 , y, x j+1 , . . . , x k )| = C j ( x ¬j ) 2 + S j ( x ¬j ) 2 + |B j ( x ¬j )|, where sgn (x) = 1 if x ≥ 0 and −1 otherwise. Note that if C j ( x ¬j ) = S j ( x ¬j ) = 0, then f ( x) = B j ( x ¬j ) does not depend on x j . So we can pick arbitrary x j ∈ R to maximize f ( x) in this case. The above properties of trigono-multilinear and trigono-multiquadratic functions have proved to be useful in [12] for the design of quantum algorithms for amplitude estimation based on Bayesian inference with engineered likelihood functions. E Example: L = 1 In this appendix, we consider the special case when L = 1. In particular, we show how the results in Sections 2 and 4 specialize in this case.
F Leading terms in the cosine series expansions of the biases In this appendix, we use the expansion formulas in Section 2.3.3 to show that the leading terms of the cosine expansions (65) and (90) can be written as products of sine functions.
Proposition 25. Let x ∈ R 2L . Then the leading terms of the cosine expansions (65) and (90) are given by sin(x i ).

G On noisy likelihood functions
As we show in [12], depolarizing noise that occurs after each rotation operator V (·) in the circuits in