1 Introduction↩︎

One of the most widely used theoretical models for noise in experimental quantum systems is the \(n\)-qubit Pauli channel, a mixed-unitary channel that applies \(n\)-qubit Pauli operators to an input \(n\)-qubit quantum state according to a fixed probability distribution, referred to as the Pauli error rates. Pauli error estimation is the task of learning the Pauli error rates of an unknown channel to precision \(\epsilon\) in some metric. Since there are \(4^n\) Pauli error rates, yet we seek subexponential complexity, a natural choice for the precision metric is \(\ell_\infty\), as this means we need only find and estimate the largest \(1/\eps\) Pauli error rates. Pauli error estimation plays a central role in diagnosing and modeling errors in present-day experimental quantum setups. As such, we are practically motivated to design simple algorithms that do not involve entangling operations; i.e., algorithms that prepare unentangled states, pass them through the channel, and perform unentangled measurements (followed by classical postprocessing). Moreover, for relevance to real-world quantum implementations, it has long been considered desirable [4] to develop algorithms that are robust against state preparation and measurement (SPAM) errors. See, e.g., [5] for more on practical aspects of Pauli channel estimation in the presence of SPAM.

1.1 Our result↩︎

In this work, we give the first entanglement-free Pauli error estimation algorithm that is robust to SPAM errors modeled as depolarizing noise (see 3 for a precise definition). When SPAM is severe, the sample complexity is subexponential in \(n\), improving on previous SPAM-tolerant algorithms that required exponentially many samples; when SPAM is mild, the complexity reduces to \(\poly(n/\eps)\), essentially matching the SPAM-free setting. Here we briefly describe the setting (see [sec:prelims,sec:spam] for more complete definitions), and then state our main theorem.

1.1.0.1 Setup: the channel.

We assume access to an \(n\)-qubit Pauli channel \(\mathcal{E}\) with unknown error rates \(\pi\). That is, \(\pi\) is a probability distribution on \(\{I, X, Y, Z\}^n\), and \(\mathcal{E}\) may be modeled as drawing \(\bP \sim \pi\) and then applying the \(n\)-qubit Pauli unitary \(\bP\).³ In fact, for a completely general \(n\)-qubit channel, there is a natural notion of its “Pauli error rates”, arising from the technique of randomized compiling [6]. Our algorithm can easily be extended to learn Pauli error rates in this more general setting too; see [rem:rc].

1.1.0.2 Setup: SPAM.

We only consider algorithms that employ single-qubit state preparation and single-qubit measurements. Moreover, we assume these are subject to SPAM errors, governed by “retention parameters” \(r_{\textrm{prep}},\; r_{\textrm{meas}}\in [0,1]\), known to the algorithm (via prior calibration). As discussed in 3, several different natural operational interpretations of SPAM are all mathematically equivalent to the following model: after a state is prepared, it is passed through the depolarizing channel \(\rho \mapsto r_{\textrm{prep}}\cdot \rho + (1 - r_{\textrm{prep}})\cdot\frac{1}{2}I\); and, before it is measured, it is passed through the channel \(\rho \mapsto r_{\textrm{meas}}\cdot \rho + (1 - r_{\textrm{meas}})\cdot\frac{1}{2}I\). In particular, \(r_{\textrm{prep}}= r_{\textrm{meas}}= 1\) corresponds to no SPAM.

We may now state our main result:

1.1.0.3 Algorithm overview.

At a high level, the algorithm proceeds in three stages.

Stage 1: Data collection. Alice repeatedly prepares random unentangled \(n\)-qubit states (with each qubit chosen uniformly from \(\{\ket{0}, \ket{i}, \ket{+}\}\)), passes them through the channel, and measures each qubit in the corresponding basis (9).

Stage 2: Reduction to Population Recovery. Using the classical reduction of [1] (2.4), each such measurement round produces a noisy binary string that can be viewed as a sample from the Pauli error distribution \(\pi\) passed through a binary \(Z\)-channel \(\Xi\) (10). Under SPAM (3), this becomes the combination of a binary symmetric channel and a binary \(Z\)-channel, denoted as \(\textrm{BSC}_{\delta/2} \circ \textrm{Z}_{1/3}\). A branch-and-prune reduction ([prop:individ]) further reduces the full Population Recovery problem to Individual Recovery: estimating \(\pi(B)\) for a given string \(B\).

Stage 3: Individual Recovery. The Individual Recovery algorithm uses the methodology of [3], whose sample complexity is controlled by the quantity \(\eta(\eps)\) that we lower-bound in 5 via new complex-analytic techniques (5).

Notably, even in the presence of low SPAM error, which corresponds to the case where \(\delta < \delta_c\), our algorithm achieves sample complexity and runtime \(\poly(n/\eps)\). This matches, up to polynomial factors, the bounds previously established for the SPAM-free setting. The algorithm presented in [1], which assumes no SPAM error, has overall runtime \(O(n \log(n/\epsilon) \cdot \epsilon^{-3})\) and sample complexity \(m = O(\epsilon^{-2})\log(n/\epsilon)\).

We remark that although \(m\) is subexponential in \(n\), a dependence of \(\exp(n^{1/3})\) seems reasonably plausible in real-world settings with \(50 \leq n \leq 1000\), whereas prior work’s dependence of \(2^{\Omega(n)}\) is infeasible in such settings. Moreover, as we discuss below, there is strong evidence that any Pauli error estimation algorithm that tolerates even a tiny amount of SPAM must use the channel on the order of \(\exp(n^{1/3})\) times.

1.2 The connection with Population Recovery, and the difficulty of SPAM↩︎

Let us first recall how the Pauli error estimation problem would be solved if: (i) entangling operations were allowed; (ii) perfect state preparation and measurement is assumed. In this case, there is a simple algorithm based on superdense coding [7]: Prepare \(n\) Bell pairs in registers \(A_1B_1, \dots, A_n B_n\), pass \(A_1 \cdots A_n\) through the channel, and then measure each \(A_iB_i\) pair in the Bell basis. It is easy to show that if the channel applies \(n\)-bit Pauli operator \(\bP\) (which it does with probability \(\pi(\bP)\)), then \(\bP \in \{I, X, Y, Z\}^n\) can be perfectly “read off” from the measurement outcomes. Thus with entangling operations allowed and no SPAM, the problem reduces to a classical task: learning an unknown probability distribution on \([4]^n\) to \(\ell_\infty\)-precision \(\eps\), which is easily done with \(O(1/\eps^2)\) samples [8].

Suppose now that we consider a more realistic setting, with a slight amount of state preparation or measurement noise (or both). In this setting, even if we allow entangling operations, the problem becomes much more difficult. For example, suppose we are even promised that the Pauli channel is only supported on \(\{I, X\}^n\) Pauli strings. In this case, the superdense coding strategy is unnecessary: without SPAM, we could simply repeatedly pass \(\ket{0}^{\otimes n}\) through the channel, measure in the \(\{\ket{0}, \ket{1}\}\) basis, and be reduced to the classical task of learning an unknown probability distribution on \(\{\textsf{0},\textsf{1}\}^n\). But suppose there is some small constant probability \(p > 0\) that each measurement outcome is flipped (with a similar observation being possible for state preparation error). Then we precisely have an instance of the classical Population Recovery problem [9], [10]: learning a probability distribution on \(\{0,1\}^n\) when the samples are passed through a binary symmetric channel with bit-flip probability \(p\). For this task it is known [2], [3] that any algorithm that succeeds must use at least \(\exp(\Omega(n^{1/3} \ln^{2/3}(1/\eps))\) samples. Thus even in this essentially classical version of the Pauli error estimation problem, any slight positive rate of SPAM error means that one cannot asymptotically improve on the “\(m\)” in our 1.

1.3 Prior work, and our improvements↩︎

A main prior work on SPAM-tolerant Pauli error estimation is by Flammia and Wallman [11]. Among other results, they gave a SPAM-tolerant Pauli error estimation algorithm that succeeds in the harder task of estimating the Fourier spectrum of the Pauli error rates. Its total complexity, however is \(\tilde{O}(\frac{1}{\Delta} \cdot 2^n/\eps^2)\), where \(\Delta\) is the “spectral gap”. In addition to having fully exponential complexity in \(n\), the dependence on \(\Delta\) may be unfavorable, as this quantity may be arbitrarily small, or even \(0\) for some simple channels. Some improvements to this result were made in [12], at the cost of adding entanglement with \(n\) ancilla qubits into the protocol.

Another relevant prior work is by Harper, Yu, and Flammia [13], who proposed a SPAM-robust Pauli estimation protocol under a specific noise model. Their approach assumes that the support of the Pauli channel is chosen uniformly at random, and measures sample complexity in terms of queries to an “eigenvalue oracle” with Gaussian noise, which can only heuristically be approximated by quantum measurements. By contrast, our protocol makes no assumptions on the support of the Pauli channel and uses standard quantum state preparations and measurements. The complexity scaling also differs: their method achieves polynomial complexity under their specific assumptions, whereas our \(\exp(n^{1/3})\) scaling applies to the fully general (depolarizing) SPAM setting.

By contrast, our approach builds on the subsequent paper by Flammia and O’Donnell [1], which was the first to make a connection between Pauli error estimation and Population Recovery. This work gave a novel method, using no entangling operations, that in the SPAM-free setting reduced Pauli error estimation to another form of Population Recovery: learning a probability distribution on \(\{\textsf{0},\textsf{1}\}^n\) in which the samples are passed to the learner through a “Z-channel” with crossover probability \(\frac{1}{3}\) (see 6). Z-channels had not previously been studied in the context of Population Recovery, but it was observed in [1] that prior Population Recovery algorithms for the binary erasure channel apply equally well for the Z-channel. By using such prior algorithms [9], [14], Flammia–O’Donnell obtained the same result 1 but with two differences:

• they used the channel only \(m = O(\log(n/\epsilon)/\epsilon^2)\) times;

• however, they assumed no SPAM errors.⁴

In this work, we first show that for the very general SPAM model we allow in 1, the Pauli error estimation problem can be reduced to yet another variant of Population Recovery: namely, one that combines \(\frac{1}{3}\)-rate Z-channel noise with \(\delta\)-rate BSC noise. This kind of channel is more general than all the ones previously studied for Population Recovery. Then, the main effort is to give a Population Recovery algorithm for this general channel; for this, we need to extend the approach from [2], [3], which in turn requires generalizing certain complex analysis theorems from [15].

2 Preliminaries↩︎

2.1 Quantum preliminaries↩︎

2.2 Population Recovery and classical channels↩︎

We first recall communication channels, in the sense of classical information theory:

The most typically studied examples are the following, both with \(\Sigma = \{\textsf{0},\textsf{1}\}\):

• the Binary Symmetric Channel with crossover probability \(p\) (abbreviation: BSC\({}_p\)), where \(\Gamma = \{\textsf{0},\textsf{1}\}\) and \(\Lambda\) flips the bit with probability \(p\);

• the Binary Erasure Channel with erasure probability \(p\) (abbreviation: BEC\({}_p\)), where \(\Gamma = \{\textsf{0},\textsf{1}, \textsf{?}\}\) and \(\Lambda\) preserves each bit with probability \(1-p\) and replaces it by \(\textsf{?}\) with probability \(p\).

[1] also showed the relevance of the following channel for Pauli error estimation:

Now we recall the classical problem of learning a distribution from noisy data, introduced in [9], [10] under the name “Population Recovery”:

Population Recovery has been well studied for the BSC and BEC channels (see, e.g., [2], [3], [9], [10], [14], [16]–[19]), as well as for the binary deletion channel.

A simplified version of Population Recovery is the following:

It is well known [2], [9] that Population Recovery efficiently reduces to Individual Recovery via a branch-and-prune strategy; e.g., Section 4.2 in [1] shows the following:

2.3 Complex analysis↩︎

We will make use of the following classical result from complex analysis in Section 5.

2.4 Recapping [1]↩︎

We use the algorithmic plan for Pauli error estimation from [1]. Following their exposition, two characters are introduced: Alice the learner, and Charlie the “channel operator”. In particular, we think of Charlie as implementing the Pauli channel with error rates \(\pi\) according to the following process: When Alice wants to pass a state \(\ket{\psi_A}\) through the channel, she sends it to Charlie, who picks a random \(\bC \sim \pi\), and then returns \(\sigma_{\bC} \ket{\psi_A}\) to Alice. In fact, our algorithm will only have Alice passing random \(n\)-qubit states composed of \(\ket{+}, \ket{i}, \ket{0}\) through the channel. Thus the setup can be summarized as below:

In the description of 9, Alice picks her random string \(\bA\) first, and then Charlie (independently) draws his random string \(\bC\) second. However, it is equivalent and more helpful to imagine Charlie “secretly” drawing \(\bC\) first, and then Alice picking \(\bA\) next (without knowledge of \(\bC\)); thus, we think of the probe based on \(\bA\) as acquiring information about Charlie’s outcome \(\bC = C\). With this interpretation in mind, it is not hard to see the following fact [1]:

(Briefly, this is because if Charlie will apply the identity Pauli \(\sigma_0\) to a qubit, it will never flip from a \(+1\) eigenvector to a \(-1\) eigenvector; but, if Charlie will apply a non-identity Pauli \(\sigma\) to a qubit, there is a \(\frac{2}{3}\) chance that Alice chose its state to be a \(-1\) eigenvector for \(\sigma\).)

Another way to say [fact:13] is that given \(C\), the readout \(\bR\) is distributed as \(\Xi(C)\), where \(\Xi\) is defined as follows:

Thus Alice’s strategy of random nontrivial probes transforms the Pauli channel estimation task into the Population Recovery problem with channel \(\Xi\).

We next observe another fact, [1]:

This means that for any \(B \in \{0,1,2,3\}^n\) of Alice’s choice, she can simulate the Population Recovery problem (with channel \(\Xi\)) under the “\(B\)-altered distribution” \(\pi^{\oplus B}\), defined by \(\pi^{\oplus B}(C) = \pi(B \oplus C)\). Finally, suppose that in this scenario she can efficiently estimate \(\pi^{\oplus B}(0^n) = \pi(B)\) for \(B\)’s of her choice. This means she can solve the Individual Recovery problem for \(\pi\) under \(\Xi\), hence the general Population Recovery problem (by [prop:individ]).

In summary, [1] show that Pauli error estimation efficiently reduces to the following Individual Recovery task: Given samples from \(\Xi \circ \pi\), estimate \(\pi(0^n)\) to additive precision \(\epsilon\). Finally, it is easy to observe that in this scenario, there is no harm in merging the Pauli symbols \(1,2,3\) into the bit \(\textsf{1}\); this does not change \(\pi(0^n)\), and it converts the channel \(\Xi\) into Z\({}_\frac{1}{3}\), the binary Z-channel with crossover probability \(\frac{1}{3}\). This completes the recap of how [1] reduces (SPAM-free) Pauli error estimation to Individual Recovery of \(\pi(\textsf{0}^n)\) under noise channel Z\({}_\frac{1}{3}\).

3 Modeling SPAM↩︎

Operationally, SPAM errors might occur in a variety of natural ways. To take state preparation errors for example, when an algorithm tries to prepare a certain state \(\ket{a}\), several things might happen: \(\ket{a}\) might be replaced by a random pure state at a fixed angle from \(\ket{a}\); or, \(\ket{a}\) might be replaced with a random mixed state \(\boldsymbol{\rho}\) having a fixed fidelity with \(\ket{a}\); or, \(\ket{a}\) might be replaced with the maximally mixed state with a certain probability. Mathematically, these are all equivalent to \(\ket{a}\) being passed through a depolarizing channel. We therefore make the following definition:

Similarly, for modeling measurement errors, there are several natural operational possibilities: when measuring \(\rho\) against an intended outcome \(\ket{a}\), one might actually get the result of measurement against some other random outcome \(\ket{\boldsymbol{b}}\) making a certain angle from \(\ket{a}\); or, \(\rho\) might get perturbed to a random state with a certain expected fidelity before the correct measurement is made, etc. Once again, these possibilities are mathematically equivalent to \(\rho\) being passed through the depolarizing channel.

To see this equivalence, note that any noise model in which the state \(\rho\) is replaced by a random state \(\boldsymbol{\rho}'\) whose expected Bloch vector satisfies \(\E[\vec{\boldsymbol{\rho}'}] = r_{\textrm{meas}}\cdot \vec{\rho}\) has the same outcome distribution as the depolarizing channel \(\rho \mapsto r_{\textrm{meas}}\cdot \rho + (1 - r_{\textrm{meas}}) \cdot \frac{1}{2}I\). This is because measurement outcome probabilities depend linearly on the Bloch vector: for a measurement in basis \(\{\ket{a}, \ket{a^\bot}\}\), the probability of outcome \(\ket{a}\) is \(\frac{1}{2}(1 + \vec{a} \cdot \vec{\rho'})\), and taking expectations gives \(\frac{1}{2}(1 + r_{\textrm{meas}}\cdot \vec{a} \cdot \vec{\rho})\), which matches the depolarized state.

We therefore define:

3.0.0.1 The algorithm under SPAM.

We may now consider how the combined SPAM error affects our algorithm. As described in 2.4, when learner Alice makes random nontrivial probes to the Pauli channel defined by error rates \(\pi\), we may imagine that Charlie first draws \(\bC \sim \pi\), obtaining some outcome \(C \in \{0, 1, 2, 3\}^n\). Given \(C\), everything else occurs in an unentangled fashion across qubits: For each \(j \in [n]\), Alice prepares a random \(\ket{\chi_+^{\bA_j}}\), state preparation error replaces this by \(r_{\textrm{prep}}\cdot \ket{\chi_+^{\bA_j}} \bra{\chi_+^{\bA_j}} + (1 - r_{\textrm{prep}})\cdot\frac{1}{2}I\), the channel changes this to \(r_{\textrm{prep}}\cdot \sigma_{C_j} \ket{\chi_+^{\bA_j}}\bra{\chi_+^{\bA_j}} \sigma_{C_j}^\dagger + (1 - r_{\textrm{prep}})\cdot\frac{1}{2}I\), and just before Alice’s measurement in the \(\ket{\chi_{\pm}^{\bA_j}}\) basis, measurement error changes the state to \(r_{\textrm{prep}}r_{\textrm{meas}}\cdot \sigma_{C_j} \ket{\chi_+^{\bA_j}}\bra{\chi_+^{\bA_j}} \sigma_{C_j}^\dagger + (1 - r_{\textrm{prep}}r_{\textrm{meas}}) \cdot \frac{1}{2} I\). This can be viewed as the SPAM-free result — namely, \(\sigma_{C_j}\) applied to \(\ket{\chi_+^{\bA_j}}\) — passed through the depolarizing channel with retention parameter \(r = r_{\textrm{prep}}\cdot r_{\textrm{meas}}\). In other words:

Given \(C\), for each \(j \in [n]\) independently, Alice gets the random readout she normally would (namely \(\Xi(C)\)) with probability \(r = r_{\textrm{prep}}\cdot r_{\textrm{meas}}\), and a uniformly random bit from \(\{\textsf{0}, \textsf{1}\}\) with probability \(\delta \mathrel{\vcenter{:}}= 1-r\). In other words, she receives \(\textrm{BSC}_{\frac{\delta}{2}} \circ \Xi(C)\).

It is easy to show that the reductions described after 10 in 2.4 continue to hold. Thus we finally obtain:

4 Individual recovery for combined noise channels↩︎

In the preceding sections, we reduced the Pauli error estimation problem (with SPAM) to an Individual Recovery task under the combined noise channel \(\textrm{BSC}_{\frac{\delta}{2}} \circ \textrm{Z}_{\frac{1}{3}}\) (2).

In this section, we derive the generating functions for this combined channel and establish the key quantity \(\eta(\eps)\) that controls the sample complexity of Individual Recovery. The main result of this section, 4, expresses \(\eta(\eps)\) as an optimization problem involving polynomials evaluated on a complex circle, which we will then lower-bound in 5.

The Individual Recovery problem is well understood separately for BSC and BEC [2], [3]. As noted in [1], the Z-channel behaves similarly to BEC in the context of Population Recovery. However, handling the combined channel \(\textrm{BSC}_{\frac{\delta}{2}} \circ \textrm{Z}_{\frac{1}{3}}\) from 2 will require more work. We will follow the methodology from [3].

4.1 Generating functions↩︎

Recall our goal is Individual Recovery of \(\calD(\textsf{0}^n)\), given samples from an unknown probability distribution \(\calD\) on \(\{\textsf{0}, \textsf{1}\}^n\), masked by a binary noise channel \(\Lambda\). As described in [3], it is easy to assume without loss of generality that \(\calD\) is symmetric, meaning it gives equal probability mass to all strings with the same Hamming weight, where Hamming weight is defined as the number of \(\textsf{1}\)s in the string. This is because, given an arbitrary distribution \(\mathcal{D}\), we can randomly permute each sample’s coordinates, which is equivalent to sampling a symmetric distribution \(\mathcal{D}^{\text{sym}}\), where \(\mathcal{D}^{\text{sym}}(\textsf{0}^n) = \mathcal{D}(\textsf{0}^n)\). Therefore, it suffices to be able to estimate in the symmetric setting.

Given this, let us introduce the row vector \(p = [p_0 \,\, p_1 \,\, \cdots \,\, p_n]\), where \(p_i\) denotes the total probability mass \(\calD\) has on Hamming weight \(i\). Thus the learner’s goal is to estimate \(p_0\). Note also that the learner only needs to observe the Hamming weights of the samples it obtains (this is true even when \(\Lambda\) is the BEC). Therefore, we can think of the learner as obtaining samples from \(\{0, 1, \dots, n\}\) distributed according to the probability row vector \(q = [q_0 \,\, q_1 \,\, \cdots \,\, q_n]\), where \[\label{eqn:A} q = pA^{(\Lambda)}, \quad A^{(\Lambda)}_{ij} = \Pr[\text{a weight i string becomes a weight j string under \Lambda noise}].\tag{1}\] The rows of each matrix \(A^{(\Lambda)}\) can be nicely expressed using generating functions. For example, [3] are the following:

Also, because both the BEC\({}_\lambda\) and the Z\({}_\lambda\) channels convert \(\textsf{1}\)’s to non-\(\textsf{1}\)’s with the same probability, \(\lambda\), it is easy to see:

We would now like to derive the generating function for our combined channel, \(\textrm{BSC}_{\frac{\delta}{2}} \circ \textrm{Z}_{\frac{1}{3}}\). Let us make a general definition:

The slightly strange parameterization makes formulas simpler, as \(\mathfrak{r}_1, \mathfrak{r}_2\) may be thought of as “retention rates”. For the Pauli error estimation problem with overall SPAM retention parameter \(r = r_{\textrm{prep}}\cdot r_{\textrm{meas}}\), we care about \[\mathfrak{r}_1 = \frac{2}{3}, \qquad \mathfrak{r}_2 = r.\]

To compute the generating functions for the ZFlip channel, we start with the following simple fact:

Now we can derive the generating function for the \(\text{ZFlip}_{\mathfrak{r}_1, \mathfrak{r}_2}\) channel:

Recall now that our task is to (with high probability) estimate \(p_0\) to additive precision \(\eps\), given samples drawn from distribution \(q = p A^{(\Lambda)}\), where \(\Lambda\) is the ZFlip channel of interest from 13. The work [3] precisely lower-bounds the sample complexity of this task, and gives an algorithmic upper bound matching to within polynomial factors:

In 3, we need to understand \(G_j(z)\)’s values for \(z\) on the complex unit circle. Recall from [prop:ourG] that for our ZFlip channel of interest, with the Möbius transformation \(w = \frac{b+(1-b)z}{(1-b)+bz}\), we have \[G_j(z) = ((1-b)+bz)^n \cdot ((1-\mathfrak{r}_1) + \mathfrak{r}_1 w)^j = \left(\frac{1-2b}{(1-b)-bw}\right)^n \cdot ((1-\mathfrak{r}_1) + \mathfrak{r}_1 w)^j,\] where we solved for \(z\) in terms of \(w\). It is easy to see that in the formula for \(w\), the numerator and denominator of \(w\) have the same squared length when \(|z| = 1\); i.e., we have \(|w|^2 = 1\). Since Möbius transformations map circles to circles, we conclude that the locus of \(w\) for \(|z| = 1\) is also the unit circle, \(|w| = 1\).⁵ Now writing \(w = e^{i\theta}\) for \(\theta \in (-\pi, \pi]\), we have \[G_j(\theta) = \left(\frac{\mathfrak{r}_2}{(1-b)-be^{i\theta} }\right)^n \cdot ((1-\mathfrak{r}_1) + \mathfrak{r}_1 e^{i\theta})^j,\] where recall \(b = \frac{1-\mathfrak{r}_2}{2}\). Using the notation \(Q(v) = \sum_{j=0} c_j v^j\), 3 tells us that for \(\Lambda = \textrm{ZFlip}_{\mathfrak{r}_1,\mathfrak{r}_2}\), \[\eta_{\Lambda}(\eps) \geq \min_{Q} \max_{-\pi < \theta \leq \pi} \;\left\vert\frac{\mathfrak{r}_2}{(1-b)-be^{i\theta} }\right\vert ^n \cdot \left|Q\left((1-\mathfrak{r}_1) + \mathfrak{r}_1 e^{i\theta}\right)\right|,\] where the minimum is over real-coefficient polynomials of degree at most \(n\) satisfying \(Q(0) > \eps\), \(Q(1) = 0\), and \(L(Q) \mathrel{\vcenter{:}}= \sum_j |c_j| \leq 2\). Finally, note that \[\begin{gather} \abs{(1-b)-be^{i\theta}}^2 = (1-b)^2 + b^2 - 2b(1-b) \cos\theta \\ = \frac{1+\mathfrak{r}_2^2}{2} - \frac{1-\mathfrak{r}_2^2}{2} \cos \theta = \frac{1+\mathfrak{r}_2^2}{2} - \frac{1-\mathfrak{r}_2^2}{2} (1-2\sin^2(\theta/2)) = \mathfrak{r}_2^2 + (1-\mathfrak{r}_2^2)\sin^2(\theta/2). \end{gather}\] Thus \[\left|\frac{\mathfrak{r}_2}{(1-b)-be^{i\theta} }\right|^n = \left(\frac{\mathfrak{r}_2^2}{\mathfrak{r}_2^2 + (1-\mathfrak{r}_2^2)\sin^2(\theta/2)}\right)^{n/2} = \left(1 + \frac{1-\mathfrak{r}_2^2}{\mathfrak{r}_2^2}\sin^2(\theta/2)\right)^{-n/2}.\] Putting everything together, we conclude:

5 Lower-bounding \(\eta(\epsilon)\)↩︎

We now turn to the main technical contribution of the paper: lower-bounding \(\eta(\eps)\) via 4. The quantity we must control is the modulus of a polynomial \(Q\) at the points \((1-\mathfrak{r}_1) + \mathfrak{r}_1 e^{i\theta}\), which trace out the circle of radius \(\mathfrak{r}_1\) centered at \(1 - \mathfrak{r}_1\). This circle passes through \(1\) on the real axis, where \(Q(1) = 0\). The difficulty is that we need \(|Q|\) to be large on an arc near this root, even though \(Q\) vanishes at the root itself and its coefficients are constrained. Classical results of [15] give such lower bounds, but only on the unit circle; our circle has smaller radius and a shifted center. The bulk of this section is devoted to extending their complex analysis to this setting.

The argument has three ingredients, developed in 5.2. The first is a Hadamard three-line lemma ([lem:threeline]) that lets us trade off bounds on nested arcs. The second is an arc lower bound for functions in a suitable analytic class on circles of radius slightly smaller than \(1\) (1). The third, 7, combines these two to give the arc lower bound we need on \(\partial D_{\mathfrak{r}_1}(1 - \mathfrak{r}_1)\). We apply the third in 5.3 to prove the bound on \(\eta(\eps)\).

5.1 Statement of the main bound↩︎

We will prove the following bound:

5.1.0.1 Setup for the proof.

Note that for \(-\pi < \theta < \pi\), \(\theta^2/16 \leq \sin^2(\theta/2) \leq \theta^2/4\). Using the fact that \(e^{-x} \leq (1 + x)^{-1}\) for all \(x \geq 0\), we have that \[\left(1 + \frac{1-\mathfrak{r}_2^2}{\mathfrak{r}_2^2}\sin^2(\theta/2)\right)^{-1} \geq \exp\left(-\frac{1-\mathfrak{r}_2^2}{4\mathfrak{r}_2^2} \theta^2 \right),\] and therefore, \[\label{eq:eta95gaussian95bound} \eta(\epsilon)\geq \min_{Q} \max_{-\pi < \theta \leq \pi} \exp\left(-\frac{1-\mathfrak{r}_2^2}{8\mathfrak{r}_2^2} \theta^2n \right) \cdot \left\vert Q((1 - \mathfrak{r}_1) + \mathfrak{r}_1 e^{i\theta})\right\vert.\tag{5}\]

Next, fix an arbitrary vector \(c = [c_0 \, c_1 \cdots c_n] \in \Delta\) with \(c_0 > \epsilon\). Let \(Q_c\) denote the polynomial \(Q\) with coefficients \(c\). We now define \[\label{eq:Fc95def} F_c = \max_{-\pi < \theta \leq \pi} \exp\left(-\frac{1-\mathfrak{r}_2^2}{8\mathfrak{r}_2^2} \theta^2n \right) \cdot \left\vert Q_c((1 - \mathfrak{r}_1) + \mathfrak{r}_1 e^{i\theta})\right\vert.\tag{6}\]

Since \(\eta(\epsilon) \geq \min_c F_c\), it suffices to lower-bound \(F_c\) for our arbitrary \(c\). \(F_c\) is controlled by \(\vert Q_c \vert\) on the circle \(\partial D_{\mathfrak{r}_1}(1 - \mathfrak{r}_1)\) of radius \(\mathfrak{r}_1\) centered at \(1 - \mathfrak{r}_1\), so we now need to establish a lower bound for the modulus of \(Q_c\) on this circle. Actually, we will prove a lower bound for a slightly modified polynomial \[\widetilde{Q}_c(z) = \frac{1}{c_0}Q_c(z) = \displaystyle\sum_{i=0}^n \tilde{c}_i z^i,\] where \(\tilde{c_0} = 1\), and \(\vert \tilde{c_i} \vert \leq \frac{1}{c_0}\) for all \(i\). In our proof, we will only need \(\widetilde{Q}_c\) to satisfy the following two properties:

For \(M \geq 1\) and \(0 < \gamma \leq 1\), \[\label{eq:Qtilde95properties} \left| \widetilde{Q}_c\left(\frac{1}{4M}\right)\right| \geq \frac{1}{2}, \quad\text{and}\quad |z| \leq 1-\gamma \;\Rightarrow\; |\widetilde{Q}_c(z)| \leq M/\gamma.\tag{7}\] These two properties play complementary roles in establishing a lower bound on \(\widetilde{Q}_c\) over an arc of the circle near the point \(z = 1\). The first guarantees that the modulus is non-negligible at an interior point of the disk. The second keeps the modulus from being too large on the subset of the circle boundary bounded away from \(z = 1\). This, together with the maximum modulus, forces \(|\widetilde{Q}_c|\) to be large on the arc near \(z = 1\), which is the bound we ultimately require.

The first property holds, since, if we set \(M\) to \(\frac{1}{c_0}\), and let \(z_0 = \frac{1}{4M}\), then \[\vert \widetilde{Q}_c(z_0) \vert \geq 1 - \sum_{i = 1}^n M(z_0)^i = 1 - \frac{Mz_0(1 - z_0^n)}{1 - z_0} \geq 1 - \frac{M z_0}{1 - z_0} \geq \frac{1}{2},\] as desired. The second property holds, since, for \(0 < \gamma \leq 1\) and for \(z \in \C\) such that \(\vert z \vert \leq 1 - \gamma\), we have that \[\vert \widetilde{Q}_c(z) \vert \leq \sum_{i = 0}^n \vert \tilde{c_i} \vert \vert z \vert^i \leq \sum_{i = 0}^n \frac{1}{c_0}\vert z \vert^i \leq \sum_{i = 0}^n M \vert z \vert^i= \frac{M(1 - \vert z \vert^{n+1})}{1 - \vert z \vert} \leq \frac{M}{\gamma}.\]

Since our proof only requires these two properties, we will prove our lower bound for the set of all polynomials that satisfy them, which we define in the following section.

5.2 Function class and key lemmas↩︎

We now introduce the function class and the key lemmas needed for the proof of 5. These are stated and proved independently, and are then combined in 5.3 to complete the argument.

(Recall from 7 that \(\widetilde{Q}_c \in \calC_{1/2,1}\) with \(M = 1/c_0 \geq 1/\eps\).) We will prove our lower bound for all polynomials in the set \(\calC_{\frac{1}{2}, 1}\), on an arc of the circle \(\partial D_{\mathfrak{r}_1}(1 - \mathfrak{r}_1)\) with central angle \(\theta \in (0, \pi)\). This arc has endpoints \(\alpha\) and \(\beta\), where \[\label{eq:alpha95and95beta} \alpha = \mathfrak{r}_1\left[\cos(\theta/2) + i \sin(\theta/2) \right] + 1 - \mathfrak{r}_1, \text{ and } \beta = \mathfrak{r}_1\left[\cos(\theta/2) - i \sin(\theta/2) \right] + 1 - \mathfrak{r}_1.\tag{8}\] Before delving into the proof, we must establish several lemmas. The first is derived from the Hadamard three-line theorem. We define \[I_t = \left\{ z \in \C \mid \arg\left(\frac{\alpha - z}{z - \beta} \right) = t \right\},\] following the notation used in [15]. Note that \[\arg\left(\frac{\alpha - z}{z - \beta} \right) = \arg(\alpha - z) - \arg(z - \beta).\] \(\arg(\alpha - z)\) represents the argument of the vector from point \(z\) to point \(\alpha\), while \(\arg(z - \beta)\) represents the argument of the vector from point \(\beta\) to point \(z\). The difference between these two arguments is 0 when \(z\) lies on the chord between \(\alpha\) and \(\beta\). Therefore, \(I_0\) corresponds to this chord. Furthermore, by the inscribed angle theorem, the difference between these two arguments is \(\frac{\theta}{2}\) when \(z\) lies on the smaller arc of \(\partial D_{\mathfrak{r}_1}(1 - \mathfrak{r}_1)\) with endpoints \(\alpha\) and \(\beta\), as shown below. Therefore, \(I_{\theta/2}\) corresponds to this arc.

We can again apply the inscribed angle theorem on the larger circle with center \(1 - 2\mathfrak{r}_1\) and radius \(2\mathfrak{r}_1\cos(\theta/4)\) to determine the arc that \(I_{\theta/4}\) corresponds to, as shown below.

Therefore, \(I_{\theta/4}\) is the arc with endpoints \(\alpha, \beta\) on the circle \(\partial D_{2\mathfrak{r}_1\cos(\theta/4)}(1 - 2\mathfrak{r}_1)\).
In the following lemma, \(I_0, I_{\theta/2}\), and \(I_{\theta/4}\) are mapped to three infinite vertical lines on the complex plane. Then, the Hadamard three-line theorem is applied to upper-bound the maximum modulus of a function on \(I_{\theta/4}\) using the maximum modulus of the same function on \(I_0\) and \(I_{\theta/2}\). This technique can be applied to any complex circle, not just \(\partial D_{\mathfrak{r}_1}(1 - \mathfrak{r}_1)\).

The next theorem we will need is only a slight generalization of [15], but we prefer to give a full proof here, as the one in [15] has a significant typo.

Note that if we instead have that \(g(\delta) \geq \kappa\) for some \(0 < \kappa \leq 1\), then \[\max_{z \in J} \vert g(z) \vert \geq \left(\frac{\delta\kappa}{\lambda M}\right)^{O(1/a)}.\] This follows from replacing \(g\) with \(g/\kappa\) and \(M\) with \(M/\kappa\) in 6.
In our proof, we will use the following corollary, which provides a lower bound for \(g\) on the arc of a circle with a slightly smaller radius that has a midpoint less than \(1\).

We will now prove our main result, which generalizes Theorem 3.1 in [15] to complex circles beyond the unit circle.

Note that the following corollary holds for 7:

5.3 Completing the proof of 5↩︎

We now combine the setup from 5 –7 with the complex-analytic lemmas from 5.2 to complete the proof.

Combining this bound with 2 yields 1.

References↩︎

---

1. Carnegie Mellon University, odonnell@cs.cmu.edu↩︎

2. Carnegie Mellon University, samvitts@cmu.edu↩︎

3. We use boldface to denote random variables.↩︎

4. Actually, [1] were able to tolerate a very limited form of “measurement error”; specifically, one where each measurement is either perfect, or else reports “error” with probability at most \(\frac{1}{4}\). They showed that such special measurement errors had the effect of increasing the Z-channel crossover probability up to \(\frac{1}{2}\), the threshold below which prior BEC Population Recovery algorithms worked just as efficiently.↩︎

5. Unless \(b = \frac{1}{2}\), in which case \(w\) is constantly \(1\). This corresponds to the trivial case of maximal SPAM, \(\mathfrak{r}_2 = 0\), which we henceforth exclude.↩︎