# Few Quantum Algorithms on Amplitude Distribution

Debajyoti Bera<EMAIL_ADDRESS>Department of Computer Science, IIIT-D, New
Delhi, India.  Tharrmashastha SAPV<EMAIL_ADDRESS>Department of
Computer Science, IIIT-D, New Delhi, India.

###### Abstract

Amplitude filtering is concerned with identifying basis-states in a
superposition whose amplitudes are greater than a specified threshold;
probability filtering is defined analogously for probabilities. Given the
scarcity of qubits, the focus of this work is to design log-space algorithms
for them.

Both algorithms follow a similar pattern of estimating the amplitude (or,
probability for the latter problem) of each state, in superposition, then
comparing each estimate against the threshold for setting up a flag qubit upon
success, finally followed by amplitude amplification of states in which the
flag is set. We show how to implement each step using very few qubits by
designing three subroutines. Our first algorithm performs amplitude
amplification even when the “good state” operator has a small probability of
being incorrect — here we improve upon the space complexity of the previously
known algorithms. Our second algorithm performs “true amplitude estimation” in
roughly the same complexity as that of “amplitude estimation”, which actually
estimates a probability instead of an amplitude. Our third algorithm is for
performing amplitude estimation in parallel (superposition) which is difficult
when each estimation branch involves different oracles.

As an immediate reward, we observed that the above algorithms for the
filtering problems directly improved the upper bounds on the space-bounded
query complexity of problems such as non-linearity estimation of Boolean
functions and $k$-distinctness.

##  1 Introduction

A quantum circuit is always associated with a distribution, say $\mathcal{D}$,
over the observed outcomes 111We assume measurement in the standard basis in
this paper, however, it should not be difficult to extend our algorithms to
accommodate measurements in another basis. that can, in principle, encode
complex information. Given a threshold $\tau$, and a blackbox to run the
circuit, it may be useful to know if there is an outcome with a probability of
at least $\tau$. We call this problem Probability Filtering (denoted ProFil).
We also introduce Amplitude Filtering (denoted AmpFil) that determines if the
absolute value of the amplitude of any basis state is above a given threshold;
even though this problem appears equivalent to ProFil, an annoying difference
crawls in if we allow absolute or relative errors with respect to the
threshold. We are not aware of prior algorithms for these problems, as stated
in their most general form. The most interesting takeaway from this work are
$\tilde{O}(1)$-qubit222$\tilde{O}$ hides $\log$ factors. algorithms for the
ProFil and the AmpFil problems whose query complexities, measured as the
number of calls to the circuit, are independent of the domain size of
$\mathcal{D}$.

The framework offered by these problems supports interesting tasks. For
example, a binary search over $\tau$ (tweaked to handle the above annoyance)
can be a way to compute the largest probability among all the outcomes and can
be used to find the modal outcome. We have observed that several combinatorial
problems can be reduced to finding the mode of a distribution or identifying
if the mode is greater than something. For instance, the $k$-Distinctness
problem generalizes the well-studied element-distinctness problem: whether an
array has at least $k$ repetitions of any element. Consider the distribution
over the domain of the array elements. If any element appears at least $k$
times, then its mode will be at least $k/N$ ($N$ denoting the size of the
array), and vice versa. Our algorithm for probability filtering can be used to
design an algorithm for $k$-Distinctness that makes an optimal number of
queries (up to logarithmic factors) when $k=\Omega(N)$, and that too using
$\tilde{O}(1)$ qubits. Previous quantum algorithms for large $k$ have an
exponential query complexity and require a larger number of qubits [3]. We
hope that the frameworks of ProFil and AmpFil would be useful for designing
more quantum algorithms.

When space is not a constraint, query complexity of a discrete problem with an
$n$-sized domain is $O(n)$ which is achievable by querying and caching the
entire input at the beginning. However, this is not feasible when space is
limited. In contrast, our algorithms are allowed only constant many
logarithmic-sized registers. To restrict the number of qubits to
$\tilde{O}(1)$ we end up using super-linear queries for many problems.

###  1.1 Summary of Results

The algorithms for ProFil and AmpFil are built on three different algorithms.

##### Biased Amplitude Amplification in Log-space (section 5)

The ProFil problem can be solved using an intuitively simple idea of doing
amplitude estimation for each outcome in superposition, using the threshold as
a marking function, and then doing amplitude amplification with respect to the
marking. Doing this while ensuring that the errors inherent in the estimation
step do not increase significantly in the amplification step can actually be
reduced to the problem of biased-oracle amplitude amplification.

In the latter problem, the oracle to mark “good” states is allowed to err with
some probability $1-p$. Hoyer et al. [15] studied this problem earlier for
$p=9/10$. They proposed an algorithm that uses $O(\sqrt{1/\lambda})$ queries
to obtain a marked element with high probability where $\lambda$ is the
probability of obtaining any marked element out of a total $N$ elements. This
algorithm performs an “error reduction step” after each iteration of amplitude
amplification. This step uses one new qubit for reducing the error; however,
since that additional qubit becomes completely entangled with the other
qubits, a fresh qubit is required for each error reduction step. Thus, the
number of qubits required would grow as much as $O(\sqrt{1/\lambda})$ in the
worst case.

To reduce the qubit footprint of our algorithms, we designed our own algorithm
for biased oracle amplitude amplification for arbitrary $p>1/2$ that uses
$O\Big{(}\frac{p}{(p-\frac{1}{2})^{2}\sqrt{\lambda}}\log(\frac{1}{\lambda\delta})\Big{)}$
queries and just
$\log(N)+O\Big{(}\frac{2p}{(p-1/2)^{2}}\log(1/\lambda\delta)\Big{)}$ qubits
(which is $\tilde{O}(1)$ for $p>2/3$ and $\lambda=1/poly(N)$).

##### True Amplitude Estimation (section 3)

The algorithm for biased amplitude amplification can be used to solve a
promise version of ProFil almost optimally, and the latter could be used to
solve AmpFil, but only sub-optimally. The reason is that this approach
performs amplitude estimation for each outcome; however, amplitude estimation
would actually estimate the probabilities of the outcomes. Suppose we
represent a state in the following manner:
$\ket{\psi}=\alpha\ket{Good}+\beta\ket{Bad}$, and we want to estimate
$|\alpha|$ within an small additive error $\epsilon$. The standard amplitude
estimation technique can be used to estimate $|\alpha|^{2}$ with error
$\epsilon^{2}$, which can be used to indirectly obtain an estimate of
$|\alpha|$ with error $\epsilon$. However, this requires $O(1/\epsilon^{2})$
queries.

To speed up this approach, we present an algorithm for true amplitude
estimation (TrueAmpEst) 333We use “true” to differentiate it from the well-
known “amplitude estimation” algorithm (AmpEst), which as explained above, is
a misnomer. that estimates the amplitude (rather, its norm) with a query
complexity of $O(\frac{1}{\epsilon})$ queries, using a similar number of
qubits as that required for amplitude estimation. The algorithm uses the
native amplitude estimation algorithm, denoted AmpEst, and a variant of the
Hadamard test as a subroutine. 444The algorithm is an extension of the
amplitude estimation algorithm, and could have been used earlier. Since we did
not find it anywhere, we are including it for the sake of completeness.

##### Multidistribution Amplitude Estimation in Log-space (section 4)

The final challenge comes in trying to run TrueAmpEst algorithm in
superposition to estimate the amplitudes of every $\ket{x}$ in a state
$\sum_{x}\alpha_{x}\ket{x}$. This boils down to running AmpEst in
superposition. It is quite easy to parallelly estimate the probabilities
associated with different basis states in a fixed superposition, e.g.,
estimating $|\alpha_{x}|^{2}$ for all $x$ in a state
$\sum_{x}\alpha_{x}\ket{x}$. In fact, we would be following this approach for
ProFil. Apeldoorn et al. had studied a similar problem named multidimensional
amplitude estimation [21]. Their objective was to estimate each
$|\alpha_{x}|^{2}$ separately with each estimate in a separate register. They
provided an $O(1/\epsilon)$-query algorithm but its space requirement is
understandably $\Omega(n)$, in fact, it requires $O(n/\epsilon)$ qubits of
space.

Now consider a different parallel estimation problem, that of parallelly
estimating the probability associated with a fixed basis state in different
superpositions, e.g., estimating $|\alpha_{y,0}|^{2}$ for all $y$ in a
superposition of $\sum_{x}\alpha_{y,x}\ket{x}$ over several $y$’s. Recall that
AmpEst uses two operators as a black-box – one for generating the state on
which estimation should be performed and another for marking the “good
states”. Technically speaking, we face the difficult problem of parallelizing
AmpEst where a different state generation operator is employed in each branch
of a superposition 555This was not a problem for the above algorithm for
ProFil since the state generation oracle was common and the marking oracles
were implemented using the register that was in superposition.. We name this
task as multidistribution amplitude estimation (MDistAmpEst).

We designed a quantum algorithm for the above problem with the same query
complexity as a single estimation procedure viz., $O(1/\epsilon)$ queries and
$O(\log(n/\epsilon))$ space. The query complexity of a straightforward
implementation has an overhead of $n$, the number of branches in the
superposition, against a single amplitude estimation. We managed to keep the
query complexity low by pushing controlled operations deep inside the
algorithm to identify and eliminate redundant calls to the oracle.

##### Algorithms for ProFil and AmpFil (section 6)

Using our biased amplitude amplification algorithm with the amplitude
estimation, we could solve a promise version of ProFil in which either there
is some outcome with probability more than the threshold $\tau$ or the
probability of every outcome is less than $\tau-\epsilon$. Our query
complexity is $\tilde{O}(\tfrac{1}{\epsilon\sqrt{\tau}})$.

Our next objective was to design a $\tilde{O}(\tfrac{1}{\epsilon\tau})$-query
algorithm for a similar promise version of the AmpFil problem. Here, the
algorithm for ProFil could be directly employed, using threshold as
$\tau^{2}$; however, the query complexity would scale as
$\tfrac{1}{\epsilon^{2}}$ instead of the desired $\tfrac{1}{\epsilon}$. This
situation arises since the amplitude estimation step actually estimates the
probability and not the amplitude, so the estimation inaccuracy too scales
quadratically with respect to the latter. We use TrueAmpEst to work around
this hurdle. Thus, we obtain an algorithm for the AmpFil problem that follows
the same overall approach as that of ProFil but with vastly different
subroutines: estimating the amplitude of all the states in superposition
(using TrueAmpEst and MDistAmpEst), marking the states whose amplitude’s
modulus is larger than the given threshold in parallel, and then amplifying
the probability of finding a marked state (using biased amplitude
amplification). We show that the AmpFil problem can be solved in
$\tilde{O}(\frac{1}{\epsilon\tau})$ queries.

For, the ProFil problem, we show that our algorithm is tight with respect to
the parameters $\epsilon$ and $\tau$ individually, i.e, we show a lower bound
of $\Omega(\frac{1}{\epsilon}+\frac{1}{\sqrt{\tau}})$ queries. Further, we
show an almost tight lower bound of
$\Omega(\frac{1}{\epsilon}+\frac{1}{\tau})$ queries for the AmpFil problem.
Both the lower bounds use standard approaches like the adversary method [2]
and reduction from a counting problem [19]. The details on the lower bounds is
presented in Section 7.

##### Applications of ProFil and AmpFil

The results in this work can be used to design low-space, often
$\tilde{O}(1)$, algorithms for several problems which have received recent
attention. These problems can now be solved using a logarithmic number of
qubits — often exponentially less compared to the existing approaches, and
have a better query complexity, thus leading to better space-time
complexities. The reductions are mostly straightforward and are omitted due to
space constraints, but the implications are interesting, as discussed below.

  * •

Our approach for $k$-Distinctness makes an optimal number of queries (up to
logarithmic factors) when $k=\Omega(n)$, and that too using $\tilde{O}(1)$
qubits (see section 8). Previous quantum algorithms for large $k$ have an
exponential query complexity in limited space or require a polynomial number
of qubits [3].

  * •

Our algorithm for ProFil can be used to identify the presence of high-
frequency items in an array (those above a given threshold — this problem is
also known as “heavy hitters”) using $\tilde{O}(\log\tfrac{1}{\epsilon})$
qubits; it also generates a superposition of such items along with estimates
of their frequencies. The best algorithms for identifying heavy hitters in low
space classical algorithms are of streaming nature but require
$\tilde{O}(\tfrac{1}{\epsilon})$ space [12]. Here $\epsilon\in(0,1]$ indicates
the inaccuracy in frequency estimation.

  * •

Our ProFil and AmpFil algorithms can be used to binary search for the largest
threshold, which essentially yield the largest probability and the largest
amplitude, respectively.

  * •

Valiant and Valiant showed that $\tilde{O}(\tfrac{m}{\epsilon^{2}})$ samples
of an $m$-valued array are sufficient to classically estimate common
statistical properties of the distribution of values in the array [20].
Recently it was shown that fewer samples of the order of
$\tilde{O}(\tfrac{1}{g^{2}})$ could be used if we want to identify the item
with the largest probability (denoted $p_{\max}$) [13]; here $g$ denotes the
gap between $p_{\max}$ and the second largest probability which is always less
than $p_{max}$. A binary search using ProFil makes only
$\tilde{O}(\tfrac{1}{g\sqrt{p_{\max}}})$ queries and is able to locate such an
item.

  * •

The non-linearity of a Boolean function can also be calculated in terms of the
amplitude with the largest norm among the output superposition of the Deutsch-
Jozsa circuit. An algorithm based on this connection was recently proposed
that employed binary search using ProFil to estimate the non-linearity of any
Boolean function with additive accuracy $\lambda$ using $\tilde{O}(1)$ qubits
and $\tilde{O}(\tfrac{1}{\lambda^{2}\hat{f}_{max}})$ queries [6]; here
$\hat{f}_{max}$ denotes the largest absolute value of any Walsh coefficient of
the function, also the largest amplitude in the output state of the Deutsch-
Jozsa circuit. Now, we can use AmpFil instead of ProFil to do the same but
using only $\tilde{O}(\tfrac{1}{\lambda\hat{f}_{max}})$ queries (this also
involves doing a binary search over all $|\hat{f}(x)|$). It should be noted in
this context that the best known lower bound for non-linearity estimation is
$\Omega(\tfrac{1}{\lambda})$ (Appendix I).

##  2 Background: Quantum amplitude estimation (QAE)

Consider a quantum circuit $A$ on $n$ qubits whose final state is $\ket{\psi}$
on input $\ket{0^{n}}$. Let $\ket{x}$ be some basis state (in the standard
basis — this can be easily generalized to any arbitrary basis). Given an
accuracy parameter $\epsilon\in(0,1)$, the amplitude estimation problem is to
estimate the probability $p$ of observing $\ket{x}$ upon measuring
$\ket{\psi}$ in the standard basis, up to an additive accuracy $\epsilon$.
Brassard et al. [7] proposed a quantum amplitude estimation circuit, which we
call $\textsc{QAEAlgo}_{A}$, that acts on two registers of size $n$ and $m$
qubits and makes $2^{m}-1$ calls to controlled-$A$ to output an estimate
$\tilde{p}\in[0,1]$ of $p$ that behaves as follows.

######  Theorem 1.

The amplitude estimation algorithm returns an estimate $\tilde{p}$ that has a
confidence interval $|p-\tilde{p}|\leq 2\pi
k\frac{\sqrt{p(1-p)}}{2^{m}}+\pi^{2}\frac{k^{2}}{2^{2m}}$ with probability at
least $\frac{8}{\pi^{2}}$ if $k=1$ and with probability at least
$1-\frac{1}{2(k-1)}$ if $k\geq 2$. It uses exactly $2^{m}-1$ evaluations of
the oracle. If $p=0$ or 1 then $\tilde{p}=p$ with certainty.

The following corollary is obtained from the above theorem by setting $k=1$
and $m=q+3$.

######  Corollary 2.

The amplitude estimation algorithm returns an estimate $\tilde{p}$ that has a
confidence interval $|p-\tilde{p}|\leq\frac{1}{2^{q}}$ with probability at
least $\frac{8}{\pi^{2}}$ using $q+3$ qubits and $2^{q+3}-1$ queries. If $p=0$
or 1 then $\tilde{p}=p$ with certainty.

Setting $\frac{1}{2^{q}}=\epsilon$, the amplitude estimation algorithm returns
an estimate $\tilde{p}$ that has a confidence interval
$|p-\tilde{p}|\leq\epsilon$ with probability at least $\frac{8}{\pi^{2}}$
using $O\Big{(}\log(\frac{1}{\epsilon})\Big{)}$ qubits and
$O\big{(}\frac{1}{\epsilon}\big{)}$ queries.

We use the subscript in $\textsc{QAEAlgo}_{A}$ to remind the reader that the
circuit for amplitude estimation depends on the algorithm $A$ that generates
the state $\ket{\psi}$ from $\ket{0^{n}}$.

Now, let $p_{x}$ be the probability of obtaining the basis state $\ket{x}$ on
measuring the state $\ket{\psi}$. The amplitude estimation circuit referred to
above uses an oracle, denoted $O_{x}$ to mark the “good state” $\ket{x}$, and
involves measuring the output of the $\textsc{QAEAlgo}_{A}$ circuit in the
standard basis; actually, it suffices to only measure the second register. We
can summarise the behaviour of the $\textsc{QAEAlgo}_{A}$ circuit (without the
final measurement) in the following lemma.

######  Lemma 3.

Given an oracle $O_{x}$ that marks $\ket{x}$ in some state $\ket{\psi}$ and
the algorithm $A$ that acts as $A\ket{0^{n}}=\ket{\psi}$, QAEAlgo on an input
state $\ket{00\ldots 0}\ket{0^{m}}$ generates the following state.

$\textsc{QAEAlgo}_{A,O_{x}}\ket{00\ldots
0}\ket{0^{m}}\xrightarrow{}\beta_{x,s}\ket{\psi}\ket{\hat{p_{x}}}+\beta_{x,\overline{s}}\ket{\psi}\ket{E_{x}}$

Here, $|\beta_{x,s}|^{2}$, the probability of obtaining the good estimate, is
at least $\frac{8}{\pi^{2}}$, and $\ket{\hat{p}_{x}}$ is an $m$-qubit
normalized state of the form
$\ket{\hat{p}_{x}}=\gamma_{+}\ket{\hat{p}_{x,+}}+\gamma_{-}\ket{\hat{p}_{x,-}}$
such that both $\sin^{2}(\pi\frac{\hat{p}_{x,+}}{2^{m}})$ and
$\sin^{2}(\pi\frac{\hat{p}_{x,-}}{2^{m}})$ approximate $p_{x}$ up to $m-3$
bits of accuracy. Further, $\ket{E_{x}}$ is an $m$-qubit error state
(normalized) such that any basis state in $\ket{E_{x}}$ corresponds to a bad
estimate, i.e., we can write
$\displaystyle\ket{E_{x}}=\sum_{\begin{subarray}{c}t\in\\{0,1\\}^{m}\\\
t\not\in\\{\hat{p}_{x,+},\hat{p}_{x,-}\\}\end{subarray}}\gamma_{t,x}\ket{t}$
in which $|\sin^{2}\left(\pi\tfrac{t}{2^{m}}\right)-p_{x}|>\tfrac{1}{2^{m-3}}$
for any such $t$.

In an alternate setting where the oracle $O_{x}$ is not provided,
$\textsc{QAEAlgo}_{A}$ can still be performed if the basis state $\ket{x}$ is
provided, say, in a different register. One can construct a quantum circuit,
say $EQ$, that acts on basis states as
$\ket{x}\ket{y}\mapsto(-1)^{\delta_{x,y}}\ket{x}\ket{y}$. Now perform
$\textsc{QAEAlgo}_{A}$ in which we replace all calls to $O_{x}$ by $EQ$ whose
first input is set to $\ket{x}$ from the new register. We name this circuit as
$\textsc{EQAmpEst}_{A}$ that implements the following operation.

$\textsc{EQAmpEst}_{A}\big{(}\ket{x}\ket{00\ldots
0}\ket{0^{m}}\big{)}\xrightarrow{}\ket{x}\big{(}\beta_{x,s}\ket{\psi}\ket{\hat{p}_{x}}+\beta_{x,\overline{s}}\ket{\psi}\ket{E_{x}}\big{)}$

Further, since $\textsc{EQAmpEst}_{A}$ is a quantum circuit, we could replace
the state $\ket{x}$ by any superposition $\sum_{x}\alpha_{x}\ket{x}$. We would
be using $\textsc{EQAmpEst}_{A}$ in this mode in this work.

$\textsc{EQAmpEst}_{A}\Big{(}\sum_{x}\alpha_{x}\ket{x}\ket{00\ldots
0}\ket{0^{m}}\Big{)}\xrightarrow{}\sum_{x}\alpha_{x}\beta_{x,s}\ket{x}\ket{\psi}\ket{\hat{p}_{x}}+\sum_{x}\alpha_{x}\beta_{x,\overline{s}}\ket{x}\ket{\psi}\ket{E_{x}}.$

Let $p_{x}$ denote the probability of observing the basis state $\ket{x}$ when
the state $\ket{\psi}$ is measured. Notice that on measuring the first and the
third registers of the output, with probability
$|\alpha_{x}\beta_{x,s}|^{2}\geq\frac{8}{\pi^{2}}|\alpha_{x}|^{2}$ we would
obtain as measurement outcome a pair $\ket{x}\ket{\hat{p}_{x}}$ where
$\sin^{2}(\pi\frac{\hat{p}_{x}}{2^{m}})=\tilde{p}_{x}$ is within
$\pm\frac{1}{2^{m-3}}$ of $p_{x}$. Observe in this setting that the subroutine
essentially estimates the probabilities $p_{x}$ corresponding to all the basis
states $\ket{x}$ according to the distribution implicit in the superposition.
This shows how amplitude estimation can be parallelized to identify all the
probabilities in a single distribution. In a later section, we discuss another
approach to parallelize amplitude estimation across multiple distributions.

##  3 True Amplitude Estimation

Let’s recall amplitude estimation. We are given access to a state preparation
oracle $A$ such that $A\ket{0^{n}}=\sum_{x\in\\{0,1\\}^{n}}\alpha_{x}\ket{x}$,
denoted $\ket{\psi}$, and we are also given a “good state” $\ket{y}$. With
probability at least $8/\pi^{2}$, AmpEst outputs an estimate
$\tilde{\alpha}_{y}$ of the probability $\alpha_{y}$ with $\epsilon$ bits of
accuracy using $O(\frac{1}{\epsilon})$ calls to $A$. Notice that contrary to
the name, the algorithm does not estimate the ‘amplitude’ of $\ket{y}$ up to
$\epsilon$ bits of accuracy; rather, what it estimates is its ‘probability’
$p_{y}=|\alpha_{y}|^{2}$.

If one wishes to estimate the absolute value of the amplitude of $\ket{y}$ up
to $\epsilon$ accuracy, one could use AmpEst to estimate $p_{y}$ up to
$\epsilon^{2}$ accuracy as $\tilde{p}_{y}$ and output $\sqrt{\tilde{p}_{y}}$.
It can be easily seen that $\sqrt{\tilde{p}_{y}}$ is an $\epsilon$-estimate of
$|\alpha_{y}|$. However, now the query complexity worsens to
$O(1/\epsilon^{2})$. We circumvent this issue and obtain an algorithm that
performs an $\epsilon$-estimation of
$|\alpha_{y}|=\sqrt{\real(\alpha_{y})^{2}+\imaginary(\alpha_{y})^{2}}$ in
$O(1/\epsilon)$ by using a modified Hadamard test to separately estimate the
real and the imaginary parts of $\alpha_{y}$. Although the modified Hadamard
test is well-known, to the best of our knowledge we could not find it in the
form presented here. We first explain the modified Hadamard test which is one
well-known method for estimating the inner product of two states.

Say, we have two algorithms $A_{\psi}$ and $A_{\phi}$ that generate the states
$A_{\psi}\ket{0^{n}}=\ket{\psi}$ and $A_{\phi}\ket{0^{n}}=\ket{\phi}$,
respectively, and we want to produce a state
$\ket{0}\ket{\xi_{0}}+\ket{1}\ket{\xi_{1}}$ such that the probability (say
$p_{0}$) of observing the first register to be in the state $\ket{0}$ is
linearly related to $|\innerproduct{\psi}{\phi}|$. Though swap-test is
commonly used for this purpose, there the probability is proportional to
$|\innerproduct{\psi}{\phi}|^{2}$; this subtle difference becomes a bottleneck
if we are trying to use amplitude estimation to estimate $p_{0}$ with additive
accuracy, say $\epsilon$. We show that the Hadamard test can do the estimation
using $O(1/\epsilon)$ queries to the algorithms whereas it would be
$O(1/\epsilon^{2})$ if we use the swap test.

The Hadamard test circuit denoted $HT_{A_{\psi},A_{\phi}}$ requires one
additional qubit, initialized as $\ket{0}$ on which the $H$-gate is first
applied. Then, we apply a conditional gate controlled by the above qubit that
applies $A_{\psi}$ to the second register, initialized to $\ket{0^{n}}$, if
the first register is in the state $\ket{0}$, and applies $A_{\phi}$ if the
first register is in the state $\ket{1}$. Finally, the $H$-gate is again
applied to the first register. The probability of observing the first register
in the state $\ket{0}$ is
$\frac{1}{2}\big{(}1+Re\big{(}|\bra{\psi}\ket{\phi}|\big{)}\big{)}$.

Thus, to obtain $Re\big{(}|\bra{\psi}\ket{\phi}|\big{)}$ with $\epsilon$
accuracy, it suffices to estimate
$\frac{1}{2}\big{(}1+Re\big{(}|\bra{\psi}\ket{\phi}|\big{)}\big{)}$ with
$\epsilon/2$ accuracy. This can be accomplished with AmpEst in which
$HT_{A_{\psi},A_{\phi}}$ is used for state preparation and good states are
defined as those with $\ket{0}$ in the first register. This requires
$O(1/\epsilon)$ queries to $A_{\phi}$ and $A_{\psi}$.

The Hadamard test can also be used to estimate
$Im\big{(}|\bra{\psi}\ket{\phi}|\big{)}$ with a slight bit of modification to
the original algorithm. One can see that on slipping an $S^{\dagger}$-gate
after the first $H$-gate in the above algorithm, the final state of the
algorithm will be such that the probability of measuring the register $R_{1}$
to be in $\ket{0}$ is

$Pr\big{[}\ket{0}_{R_{1}}\big{]}=\Big{\|}\frac{1}{2}\big{(}\ket{\psi}-\iota\ket{\phi}\big{)}\Big{\|}^{2}=\frac{1}{2}\big{(}1+Im\big{(}\big{|}\bra{\psi}\ket{\phi}\big{|}\big{)}\big{)}.$

As before, by estimating
$\frac{1}{2}\big{(}1+Im\big{(}\big{|}\bra{\psi}\ket{\phi}\big{|}\big{)}\big{)}$
with $\epsilon/2$ accuracy, it is possible to obtain an estimate of
$Im\big{(}|\bra{\psi}\ket{\phi}|\big{)}$ with $\epsilon$ accuracy.

######  Algorithm 1 (TrueAmpEst).

Suppose that we are given a circuit $A$ that generates the state
$A\ket{0^{n}}=\ket{\psi}$ and another circuit $A_{y}$ that generates the state
$A_{y}\ket{0^{n}}=\ket{y}$. Then, the probability of observing $\ket{0}$ in
the first register of the output of the modified Hadamard test can be used to
compute $|\real(\innerproduct{y}{A|0^{n}})|$. This probability can be
estimated with $\epsilon$-additive error using classical means (requiring
$O(1/\epsilon^{2})$ calls to $A$ and $A_{y}$), or quantum means such as
QAEAlgo, or MDistAEAlgo that we describe later, both of which require
$O(1/\epsilon)$ calls to $A$ and $A_{y}$. A similar approach using a slightly
modified test (described above) can be used to compute
$|\imaginary(\innerproduct{y}{A|0^{n}})|$.

Now, it can be proved using elementary algebra that for any complex number
$Z=C+iD$ such that $|Z|^{2}\leq 1$, $\epsilon/\sqrt{2}$-estimates (additive)
of $|C|$ and $|D|$ are sufficient to obtain an $\epsilon$-estimate (additive)
of $|Z|$. So, the actual absolute value $|\innerproduct{y}{A|0^{n}}|$ can
therefore be also obtained with $\epsilon$-additive error after individually
obtaining its real and complex part, both requiring $O(1/\epsilon)$ calls to
$A$ and $A_{y}$.

##  4 Multidistribution Amplitude Estimation (MDistAmpEst)

The popularly known amplitude estimation problem is concerned with estimating
the probability of a “good/desired state”, say $\ket{\gamma}$, when the output
of a quantum algorithm $A$ on the input state $\ket{0^{l}}$ is measured, i.e.,
estimating $|\innerproduct{\gamma}{A|0^{l}}|^{2}$. Traditionally, it takes as
input a fixed $\ket{00\ldots 0}$ state, and uses two oracles, $A$ for
preparing the state to analyse, and a marking oracle $O_{\gamma}$ to mark the
good state:
$O_{\gamma}=-\outerproduct{\gamma}{\gamma}+\sum_{x\not=\gamma}\outerproduct{x}{x}$.

There can be two ways to formulate parallel versions of this problem, i.e., in
a superposition. First is simultaneous estimation of
$|\innerproduct{\gamma^{y}}{A|0^{l}}|^{2}$ for a set of basis states
$\\{\ket{\gamma^{y}}\\}_{y}$. That is, we want to perform the following
operation:

$\sum_{y}\alpha_{y}\ket{y}\ket{00\ldots
0}\longrightarrow\sum_{y}\alpha_{y}\ket{y}\ket{\bar{\beta}_{y}},$

where, $\bar{\beta}_{y}$s are $\epsilon$-additive estimates of
$|\innerproduct{\gamma^{y}}{A|0^{l}}|^{2}$. The complexity would be defined as
the number of queries to $A$. Even though this appears to involve a different
marking oracle in every branch of the superposition, given that we want to
mark only basis states, this can effectively be solved using EQAmpEst
discussed earlier in section 2. Parallelization of this kind can be found in
the works ([14, 16]) that use variable-time amplitude amplification.

A variant of this problem was recently studied by Apeldoorn in the name of
multidimensional amplitude estimation [21] where the goal was to obtain all
the estimates in as many registers, not in a superposition.

For the second manner, suppose that we are given a family of oracular quantum
algorithms $\\{A^{O}_{y}\leavevmode\nobreak\ :\leavevmode\nobreak\ y=1\ldots
N\\}$ each making $k$ queries to an oracle $O$, for some known constant $k$.
Let $\ket{\gamma}$ be some fixed state as above. We want to simultaneously
estimate $|\innerproduct{\gamma}{A^{O}_{y}|0^{l}}|^{2}$ for all $y\in[N]$. We
will henceforth drop the superscript $O$ and simply write $A_{y}$, but the
reader will find it convenient to remember that the number of calls to $O$
will be our final query complexity measure.

In fact, there is no reason to mandate a fixed $\ket{\gamma}$ for all $k$.
Suppose, in addition, we also have a family of states
$\\{\ket{\gamma^{y}}\\}_{y}$ ($\ket{\gamma^{y}}$ will be called as the
$y^{th}$ desired state). In our Multidistribution Amplitude Estimation problem
(MDistAmpEst), we want to estimate the values of
$|\innerproduct{\gamma^{y}}{A^{O}_{y}|0^{l}}|^{2}$ for all $y$, again in a
superposition as above. MDistAmpEst combines both the parallelization attempts
mentioned earlier.

The MDistAmpEst problem is formally defined below. $n$ will denote $\log(N)$.

######  Problem 1 (Multidistribution Amplitude Estimation Problem
(MDistAmpEst)).

Given $l$-qubit oracular quantum algorithms
$\mathcal{A}_{1}^{O},\mathcal{A}_{2}^{O},\cdots\mathcal{A}_{N}^{O}$ where each
$\mathcal{A}_{i}^{O}$ makes $k$ calls (wlog.) to an oracle $O$, and given a
family of reflection operators
$\\{S_{\gamma^{y}}=\mathcal{I}-2\ket{\gamma^{y}}\bra{\gamma^{y}}:1\leq y\leq
N\\}$ where $\gamma^{y}\in\\{0,1\\}^{l}$, we need a circuit for the following
operation:

$\ket{y}\ket{0^{l}}\ket{0^{\log{1/\epsilon}}}\xrightarrow{}\ket{y}\ket{\phi_{y}}\ket{\tilde{\beta}_{y\gamma^{y}}},$

where, for each $y$,
$\sin^{2}\Big{(}\frac{\pi}{2^{m}}\cdot\tilde{\beta}_{y\gamma^{y}}\Big{)}$ is
an estimate of $|\bra{\gamma^{y}}A_{y}^{O}\ket{0^{l}}|^{2}$ such that

$\bigg{|}\sin^{2}\Big{(}\frac{\pi}{2^{m}}\cdot\tilde{\beta}_{y\gamma^{y}}\Big{)}-|\bra{\gamma^{y}}A_{y}^{O}\ket{0^{l}}|^{2}\bigg{|}\leq\epsilon/8$

for some given $0<\epsilon\leq 1$ and $m=\log 1/\epsilon$. The query
complexity of the problem is defined as the total number of calls made to $O$.

Suppose that the first register contains the basis state $\ket{y}$. The
standard QAEAlgo algorithm would operate in two stages, first apply
$A_{y}\otimes\mathbb{I}$, and then the core estimation steps, which we denote
$AmpEst_{y}$; $AmpEst_{y}$ in-turn uses $A_{y}$ for preparing the state to
process and $S_{\gamma^{y}}$ to mark the good state. Thus, the overall
estimation algorithm looks like the following.

$AmpEst_{y}\left[\left(A_{y}\ket{0^{l}}\right)\otimes\ket{0^{\log
1/\epsilon}}\right]=\ket{\phi_{y}}\ket{\tilde{\beta}_{y\gamma^{y}}},\quad\mbox{
where }\ket{\phi_{y}}=A_{y}\ket{0^{l}}.$

The solution appears simple — implement the corresponding conditional
operators

$\mathbf{U}=\sum_{y}\outerproduct{y}{y}\otimes AmpEst_{y}\mbox{
(conditional-$AmpEst_{y}$,
and)}\quad\mathbf{V}=\sum_{y}\outerproduct{y}{y}\otimes A_{y}\mbox{
(conditional-$A_{y}$)}.$

It is easy to verify that

$\ket{y}\ket{\phi_{y}}\ket{\tilde{\beta}_{y\gamma^{y}}}=\Big{(}\sum_{y}\outerproduct{y}{y}\otimes
AmpEst_{y}\Big{)}\Big{(}\sum_{y}\outerproduct{y}{y}\otimes
A_{y}\otimes\mathbb{I}^{\log
1/\epsilon}\Big{)}\cdot\ket{y}\ket{0^{l}}\ket{0^{\log 1/\epsilon}}.$

Operators like $\mathbf{U}$ are common in quantum circuits, e.g., they appear
in the amplitude estimation circuit as $\sum_{y}\outerproduct{y}{y}\otimes
G_{f}^{2^{y}}$ where $G_{f}$ is the Grover’s iterator that internally calls
the oracle $U_{f}$. A naive approach to implement $\mathbf{U}$ is to serially
apply the sequence of $\outerproduct{y}{y}\otimes AmpEst_{y}$ operators for
each individual $y$. Each of these operators would perform amplitude
estimation with the good state as $\ket{\gamma^{y}}$ and the state preparation
oracle as $A_{y}$, conditioned on the first register being in $\ket{y}$. Then,
the total number of queries made by $\mathbf{U}$ to the oracle $O$ would be
$O(N\frac{k}{\epsilon})$ where $O(k/\epsilon)$ is the query complexity due to
a single amplitude estimation $AmpEst^{O}_{y}$. Similarly, the number of calls
made to $O$ for implementing $\mathbf{V}$ is $N$. Thus, the total number of
queries to the oracle $O$ would be $O(\frac{Nk}{\epsilon})$.

Our solution here is an algorithm MDistAEAlgo that performs the same task but
with just $O(\frac{k}{\epsilon})$ queries to $O$. The trick is to push the
control $\outerproduct{y}{y}$ deep inside $AmpEst_{y}$ and $A_{y}$.

######  Theorem 4 (Multidistribution Amplitude Estimation).

MDistAEAlgo uses $O(\frac{k}{\epsilon})$ queries to the oracle $O$ to solve
the Multidistribution Amplitude Estimation Problem, i.e., with probability at
least $\tfrac{8}{\pi^{2}}$ it outputs
$\ket{\Phi}=\sum_{y}\alpha_{y}\ket{y}\ket{\xi_{y}}\ket{\tilde{\beta}_{y\gamma^{y}}}$
given any initial state $\sum_{y}\alpha_{y}\ket{y}\ket{0^{l}}\ket{0^{m}}$,
where $\sin^{2}\big{(}\tilde{\beta}_{y\gamma^{y}}\frac{\pi}{2^{m}}\big{)}$ is
an $O(\epsilon)$-estimate of $|\bra{\gamma^{y}}A_{y}^{O}\ket{0^{l}}|^{2}$ for
each $y$.

The proof of this theorem is present in Appendix F.

##  5 Amplitude Amplification using Biased Oracle

Given an oracle $\mathcal{O}$, that marks a state of interest (say $\ket{x}$),
we know that the amplitude amplification algorithm allows us to obtain
$\ket{x}$ w.h.p. from any given state $\ket{\psi}=A\ket{0}$ quadratically
faster as compared to classical approaches using $A$ as a black-box. We use
$AA_{A,\mathcal{O}}$ to denote such an amplitude amplification algorithm, the
key ingredient of which is the Grover iterator
$G_{A,\mathcal{O}}=-AR_{\ket{0}}A^{\dagger}\mathcal{O}$; here, $R_{\ket{i}}$
denotes the reflection operator $2\ket{i}\bra{i}-\mathbb{I}$. The standard
assumption is that the oracle $\mathcal{O}$ marks the state $\ket{x}$ with
probability 1, i.e., $\mathcal{O}\ket{x}\ket{0}=\ket{x}\ket{1}$ if $x$ is
‘good’ or else, $\ket{x}\ket{0}$.

However, if we replace the oracle $\mathcal{O}$ with a bounded-error oracle
$\hat{\mathcal{O}}_{p}$ which marks $\ket{x}$ but with some probability
$p\in(1/2,1)$, then the naive amplitude estimation algorithm does not work as
intended since $\mathcal{O}$ would also mark the other states with probability
$1-p$, and this error will accumulate faster with each iteration of the
algorithm. Hoyer et al. [15] first investigated this setting for $p=9/10$ and
showed that by following each amplification step with an error reduction step,
it is possible to solve the bounded-error search problem using $O(\sqrt{N})$
queries to oracle $\hat{\mathcal{O}}_{p}$ for a search of $1$ good element
over $N$ elements. We observed that the algorithm increases the number of
ancillæ qubits in each error reduction step, and since, the number of error
reduction steps is $O(\sqrt{N})$, the space required for this algorithm
becomes $O(\sqrt{N})$ qubits; thus, we cannot use this algorithm as a
subroutine for this work.

Another approach, as hinted by the authors of the above work, would be to
replace a single call to the oracle $\hat{\mathcal{O}}_{p}$ in the Grover
iterator by the following sub-circuit for marking: make
$O(\log(1/\delta))$-many independent calls to $\hat{\mathcal{O}}_{p}$, then
compute the majority over those copies, and finally use the majority value for
marking the state of interest. Naturally, the ancillæ qubits required for
performing the majority in each of the $O(\sqrt{N})$ calls is
$O(\log(1/\delta))$. However, not all the ancillæ qubits can be cleaned up for
reuse due to their entanglement with the workspace qubits. Hence, the space
complexity would asymptotically remain $O(\sqrt{N})$.

Therefore, we designed another technique that uses just log-space to solve the
bounded-error search problem using $O(\sqrt{N}\log(1/\delta))$ queries to
$\hat{\mathcal{O}}_{p}$ 666Careful readers will observe a logarithmic overhead
in the query complexity.. The idea is to replace the operator $A$ in the
Grover iterator with a newly constructed operator $\hat{A}$ that internally
uses $\hat{\mathcal{O}}_{p}$ to enhance $A$. The role of $\hat{A}$ will be to
generate a state in which the good and the bad states are explicitly marked
using an additional register whose state is $\ket{1}$ or $\ket{0}$,
accordingly, and furthermore, the probability of the bad state can be made
arbitrarily low.

######  Lemma 5.

Suppose that we are given an algorithm $A$ that generates the initial state
$A\ket{0^{n}}=\sum_{x}\alpha_{x}\ket{x}$, a bounded-error oracle
$\hat{\mathcal{O}}_{p}$ as defined above and an error parameter $\delta$;
further, let $G$ denote the set of good states, and $B$ the set of bad states.
Choose an appropriate
$k=O\Big{(}\frac{2p}{(p-1/2)^{2}}\log(\frac{1}{\delta})\Big{)}$, and construct
a quantum circuit $\hat{A}$ as described in Algorithm 1. Then, (ignoring the
states of ancillæ)

$\hat{A}\ket{0^{n+k+1}}=\sum_{x\in
G}\alpha_{x}\ket{x}\Big{[}\eta^{g}_{x0}\ket{\dots}\ket{0}+\eta^{g}_{x1}\ket{\dots}\ket{1}\Big{]}+\sum_{x\in
B}\alpha_{x}\ket{x}\Big{[}\eta^{b}_{x0}\ket{\dots}\ket{0}+\eta^{b}_{x1}\ket{\dots}\ket{1}\Big{]},$

such that $|\eta^{g}_{x0}|^{2}\leq\delta$ and $|\eta^{b}_{x1}|^{2}\leq\delta$.

Algorithm 1 Constructing the algorithm $\hat{A}_{A,\hat{\mathcal{O}}_{p},k}$

1:Bounded-error oracle $\hat{\mathcal{O}}_{p}$, the initial algorithm $A$ and
$k$.

2:Initialize $R_{1}$ to $\ket{0^{n}}$. Next $k+1$ registers
$R_{21}R_{22}\cdots R_{2k}R_{maj}$ are initialized to $\ket{0}$.

3:Apply $A$ to $R_{1}$.

4:for $i$ in $1$ to $k$ do

5: Apply $\hat{\mathcal{O}}_{p}$ to $R_{1}R_{2i}$.

6:end for

7:Apply a conditional majority gate, using $R_{1}$ as the control, using the
registers $R_{21}R_{22}\ldots R_{2k}$ as inputs to the majority circuit, and
storing the majority value in $R_{maj}$.

The result can be understood by taking $\delta\to 0$, and analysing the
observation upon measuring the output of $\hat{A}\ket{0^{n+k+1}}$. For $x\in
G$, we are more likely to observe $\ket{x}\ket{\dots}\ket{1}$ as compared to
$\ket{x}\ket{\dots}\ket{0}$, and for $x\in B$, $\ket{x}\ket{\dots}\ket{0}$ is
the more likely outcome — i.e., the information about $x$ being good or bad is
encoded in the final qubit, w.h.p..

The next step is pretty obvious. We run one of the amplification routines
using $\hat{A}$ as the state preparation oracle, and amplifying the
probability of states like $\ket{x}\ket{\dots}\ket{1}$. This would amplify
such states for $x\in G$ but, unfortunately, also for $x\in B$. However, if we
choose $\delta$ sufficiently small, we can ensure that the probability of
states like $\ket{x}\ket{\dots}\ket{1}$, where $x\in B$, would be extremely
small, and hence, would be within tolerable limits even after Algorithm 2.

Let $\lambda$ be the probability obtaining some good state on measuring
$\ket{\psi}$ if some good state is present in $\ket{\psi}$; formally,
$\lambda=\min_{x}(|\alpha_{x}|^{2})$ over all “good” $x$. We will use the fact
that FPAA [22] employed by the algorithm can amplify an unknown success
probability, lower bounded by $\lambda$, to any desired $1-\delta$ within
$O(\tfrac{1}{\sqrt{\lambda}}\log\tfrac{1}{\delta})$ iterations of Line 3.

######  Theorem 6.

Given an $n$-qubit algorithm $A$ that generates the initial state
$A\ket{0}=\ket{\psi}=\sum_{x\in\\{0,1\\}^{n}}\alpha_{x}\ket{x}$, a bounded-
error oracle $\hat{\mathcal{O}}_{p}$ as defined above and an error parameter
$\delta$, there exists an algorithm that uses
$O\Big{(}\frac{p}{(p-\frac{1}{2})^{2}\sqrt{\lambda}}\log(\frac{1}{\lambda\delta})\Big{)}$
queries to $\hat{\mathcal{O}}_{p}$ along with
$n+O\Big{(}\frac{2p}{(p-1/2)^{2}}\log(1/\lambda\delta)\Big{)}$ qubits and
outputs a good state with probability at least $1-\delta$, if one exists. If
there is no good state in $\ket{\psi}$ then the algorithm outputs “No
Solution” with probability at least $1-\delta$.

When $p$ is a constant, the number of queries is
$\tilde{O}(\tfrac{1}{\sqrt{\lambda}})$ and $\tilde{O}(1)$ additional qubits
are used.

Algorithm 2 Amplitude amplification using a biased oracle

1:Bounded-error oracle $\hat{\mathcal{O}}_{p}$, the initial algorithm $A$ and
$k$.

2:Initialize $k+2$ registers such that the first register $R_{1}$ is
initialize to $\ket{0^{n}}$ and the next $k+1$ registers $R_{21}R_{22}\cdots
R_{2k}R_{maj}$ are initialized to $\ket{0}$.

3:Use Algorithm 1 to construct $\hat{A}_{A,\hat{\mathcal{O}}_{p},k}$. Then,
apply $\hat{A}_{A,\hat{\mathcal{O}}_{p},k}$ on $R_{1}R_{21}R_{22}\cdots
R_{2k}R_{maj}$.

4:Apply the fixed point amplitude amplification algorithm (FPAA) on $R_{maj}$
using the good state as $\ket{1}$ and with error at most $\delta/2$. Stop if
the number of iterations crosses the limit of
$\tilde{O}(\tfrac{1}{\sqrt{\lambda}})$ set by the FPAA algorithm.

5:Measure $R_{maj}$ as $m$. If $m=\ket{0}$, output “No Solution”. Else,
measure $R_{1}$ as $y$ and output $y$.

###### Proof Sketch of Theorem 6.

Set $k=O(\frac{2p}{(p-1/2)^{2}}\log(1/\delta^{\prime}))$ for a
$\delta^{\prime}=\lambda^{4}\delta^{2}$ and construct
$\hat{A}_{A,\hat{\mathcal{O}}_{p},k}$. From Lemma 5, see that this $\hat{A}$
(dropping the subscripts) behaves as

$\hat{A}\ket{0^{n}}\ket{0^{k}}\ket{0}=\sum_{x}\alpha_{x}\ket{x}\big{(}\eta_{x,0}\ket{\phi_{x,0}}\ket{0}+\eta_{x,1}\ket{\phi_{x,1}}\ket{1}\big{)}=\ket{\Psi}$

where $|\eta_{x,f(x)}|^{2}\geq 1-\delta^{\prime}$ for any $x$; here $f(x)$
indicates the “goodness” of $x$.

Now, two cases can happen. We refer the reader to Appendix H for the complete
proof.

Case (i):  Let $f(x)=0$ for all $x$. For this case, we show that in order for
the probability of $\ket{1}$ in $R_{maj}$ to become at least $\delta$ post
amplification from the initial $\delta^{\prime}=\lambda^{4}\delta^{2}$, the
initial state needs to be amplified $\Omega(\frac{1}{\lambda})$ number of
times. However, since we perform only $O(\frac{1}{\sqrt{\lambda}})$ many
iterations of amplification, the probability of $\ket{1}$ in $R_{maj}$ remains
below $\delta$. Thus, the algorithm outputs “No solution” with high
probability.

Case (ii):  Let $f(x)=1$ for some $x$. In this case, for all $x$ such that
$f(x)=1$, we will have $|\eta_{x,1}|^{2}\geq 1-\delta^{\prime}$. Then the
probability of measuring the last qubit as $\ket{1}$ is at least
$\sum_{x:f(x)=1}|\alpha_{x}\eta_{x,1}|^{2}\geq\lambda(1-\delta^{\prime})>\lambda/2$
(since $\delta<0.5$). Now, using the fixed point amplitude amplification
subroutine, in $O(\frac{1}{\sqrt{\lambda}})$ iterations, we obtain a final
state post amplification such that with probability $1-\delta$ we obtain
$\ket{1}$ on measuring the $R_{maj}$ register.

One more step is needed here. One may argue that even though we obtain
$\ket{1}$ with probability $1-\delta$ in $R_{maj}$, the state $\ket{x}$
obtained on measuring $R_{1}$ need not be such that $f(x)=1$. However, we were
able to show that, with probability at least $3/4$ we will obtain a good $x$
upon measuring $R_{1}$ if we had obtained $\ket{1}$ in $R_{maj}$. ∎

##  6 Probability and Amplitude Filtering

The algorithms for both probability filtering and amplitude filtering follow a
similar pattern. The first step is to design appropriate biased oracles —
ProbFilBOrcl for probability filtering and AmpFilBOrcl for amplitude
filtering; they are described in algorithm 3 and algorithm 4. The oracles are
used for marking a basis state to be good if its probability or amplitude, as
required, is more than $\tau$. Then, use our amplitude amplification algorithm
for biased-oracle (see Section 5) to amplify the probability of finding a
marked state, if one exists. We summarise the behaviour of the filtering
algorithms in the following theorems.

######  Theorem 7 (Additive-error algorithm for AmpFil).

The AmpFil problem is given as input a $(\log(m)+a)$-qubit quantum algorithm
$O_{D}$ that generates a distribution
$D:\big{(}p_{x}=|\alpha_{x}|^{2}\big{)}_{x=1}^{m}$ upon measurement of the
first $\log(m)$ qubits of

$\displaystyle
O_{D}\ket{0^{\log(m)+a}}=\sum_{x\in\\{0,1\\}^{\log(m)}}\alpha_{x}\ket{x}\ket{\psi_{x}}=\ket{\Psi}$
(say)

in the standard basis, and also a threshold $\tau\in(0,1)$.

For any choice of parameters $0<\epsilon<\tau$ for additive accuracy and
$\delta$ for error, there exists a quantum algorithm that uses
$O\big{(}(\log(m)+\log(\frac{1}{\epsilon})+a)\log(\frac{1}{\delta\tau})\big{)}$
qubits and makes $O(\frac{1}{\epsilon\tau}\log\tfrac{1}{\delta\tau})$ queries
to $O_{D}$ such that when its final state is measured in the standard basis,
we observe the following.

  1. 1.

If $|\alpha_{x}|<\tau-\epsilon$ for all $x$ then the output register is
observed in the state $\ket{0}$ with probability at least $1-\delta$.

  2. 2.

If $|\alpha_{x}|\geq\tau$ for any $x$, then with probability at least
$1-\delta$ the output register is observed in the state $\ket{1}$ and some $x$
such that $|\alpha_{x}|\geq\tau$ is returned as output.

######  Theorem 8 (Additive-error algorithm for ProFil).

The ProFil filtering problem is given as input a $(\log(m)+a)$-qubit oracle
$O_{D}$ that generates a distribution $D=(p_{i})_{i=1}^{m}$ on the first
$\log(m)$ qubits of the state $O_{D}\ket{0^{\log(m)+a}}$, and also a threshold
$\tau$.

For any choice of parameters $0<\epsilon<\tau$ for additive accuracy and
$\delta$ for error, there exists a quantum algorithm that uses
$O\big{(}(\log(m)+\log(\frac{1}{\epsilon})+a)\log(\frac{1}{\delta\tau})\big{)}$
qubits and makes $O(\frac{1}{\epsilon\sqrt{\tau}}\log\tfrac{1}{\delta\tau})$
queries to $O_{D}$ such that when its final state is measured in the standard
basis, we observe the following.

  1. 1.

If $p_{x}<\tau-\epsilon$ for all $x$ then the output register is observed in
the state $\ket{0}$ with probability at least $1-\delta$.

  2. 2.

If $p_{x}\geq\tau$ for any $x$, then with probability at least $1-\delta$ the
output register is observed in the state $\ket{1}$ and some $x$ such that
$p_{x}\geq\tau$ is returned as output.

Algorithm 3 Constructing biased-oracle ProbFilBOrcl for probability filtering

1:Oracle $O_{D}$ (with parameters $m$, $a$), threshold $\tau$, and accuracy
$\epsilon$.

2:Input register $R_{1}$ set to some basis state $\ket{x}$ and output register
$R_{5}$ set to $\ket{0}$.

3:Set $r=\log(m)+a$, $\tau^{\prime}=\frac{1}{2}(1+\tau-\frac{\epsilon}{8})$,
$q=\lceil\log(\frac{1}{\epsilon})\rceil+5$ and $l=q+3$.

4:Set
$\tau_{1}=\left\lfloor{\frac{2^{l}}{\pi}\sin^{-1}(\sqrt{\tau^{\prime}})}\right\rfloor$

5:Initialize ancillæ registers $R_{2}R_{3}R_{4}$ of lengths $r,l$ and 1,
respectively, and set $R_{3}=\ket{\tau_{1}}$.

6:Stage 1: Apply EQAmpEst (sans measurement) with $R_{2}$ as the input
register, $R_{4}$ as the output register and $O_{D}$ is used as the state
preparation oracle. $R_{1}$ is used in $EQ$ to determine the “good state”.
EQAmpEst is called with error at most $1-\frac{8}{\pi^{2}}$ and additive
accuracy $\frac{1}{2^{q}}$.

7:Stage 2: Set $R_{5}$ to 1 if the estimate of the probability, calculated
using $R_{4}$, meets $\tau$.

8: Use HDl on $R_{3}$ and $R_{4}$ individually.

9: Use ${\tt CMP}$ on $R_{3}=\ket{\tau_{1}}$ and $R_{4}$ as input registers
and $R_{5}$ as output register.

10: Use HD${}^{\dagger}_{l}$ on $R_{3}$ and $R_{4}$ individually.

Algorithm 4 Constructing biased-oracle AmpFilBOrcl for real amplitude
filtering

1:Oracle $O_{D}$ (with parameters $m$, $a$), threshold $\tau$, and accuracy
$\epsilon$.

2:Input register $R_{1}$ set to some basis state $\ket{x}$ and output register
$R_{5}$ set to $\ket{0}$.

3:Set $r=\log(m)+a$, $\tau^{\prime}=\frac{1}{2}(1+\tau-\frac{\epsilon}{8})$,
$q=\lceil\log(\frac{1}{\epsilon})\rceil+5$ and $l=q+3$.

4:Set
$\tau_{1}=\left\lfloor{\frac{2^{l}}{\pi}\sin^{-1}(\sqrt{\tau^{\prime}})}\right\rfloor$

5:Initialize ancillæ registers $R_{21}R_{22}R_{3}R_{4}$ of lengths $1,r,l$ and
$l$, respectively. Set $R_{3}=\ket{\tau_{1}}$.

6:Stage 1: Apply MDistAEAlgo (sans measurement) with $R_{21}$ as the input
register, $R_{4}$ as the output register and $\ket{0}$ as the “good state”. A
controlled-Hadamard test, i.e., $\sum_{y}\outerproduct{y}{y}\otimes
HT_{A_{y},O_{D}}$ over the registers $R_{1},R_{21}$ and $R_{22}$ is used as
the state preparation oracle, of which only $R_{21}$ is used in MDistAEAlgo.
MDistAEAlgo is called with error at most $1-\frac{8}{\pi^{2}}$ and additive
accuracy $\frac{1}{2^{q}}$. Here, $\\{A_{y}\leavevmode\nobreak\
:\leavevmode\nobreak\ y\in\\{0,1\\}^{r}\\}$ is a family of oracles each of
which acts as $A_{y}\ket{0^{r}}=\ket{y}$.

7:Stage 2: Set $R_{5}$ to 1 if the estimate of the probability, calculated
using $R_{4}$, meets $\tau$.

8: Use HDl on $R_{3}$ and $R_{4}$ individually.

9: Use ${\tt CMP}$ on $R_{3}=\ket{\tau_{1}}$ and $R_{4}$ as input registers
and $R_{5}$ as output register.

10: Use HD${}^{\dagger}_{l}$ on $R_{3}$ and $R_{4}$ individually.

Now we explain how we implemented the biased oracles. The role of these
oracles is to mark the basis states whose probability or amplitude is at least
$\tau$, with at most some small error probability. Their construction involves
two stages: an estimation stage followed by a marking stage. For the
ProbFilBOrcl, we use EQAmpEst to estimate the probabilities of each basis
state in superposition. The construction of the AmpFilBOrcl differs from that
of the ProbFilBOrcl only in the estimation stage. Using EQAmpEst for
estimating the amplitudes would lead to a query complexity that depends
quadratically on $1/\epsilon$. To circumvent that we replace it with the
MDistAEAlgo which uses TrueAmpEst to estimate the absolute value of the
amplitudes of each of the basis states in superposition. In the marking stage,
the algorithm uses straight-forward quantum operations to compare the
estimate, in one register, with $\tau$, hardcoded in a suitable encoding in
another register. Since EQAmpEst and MDistAEAlgo perform estimation with error
probability that is at most $1-\frac{8}{\pi^{2}}$, both ProbFilBOrcl and
AmpFilBOrcl mark the good basis states with probability at least $8/\pi^{2}$.

The query complexity arising from biased-oracle amplitude amplification (see
Section 5) scales as $\tilde{O}(\tfrac{1}{\sqrt{\lambda}})$ where
$\lambda=\min|\alpha_{x}|^{2}$ among all $x$ that are good. For probability
filtering, we want to amplify any state $\ket{x}$ such that
$|\alpha_{x}|^{2}\geq\tau$, so, $\lambda\geq\tau$; on the other hand, for
amplitude filtering, we want to amplify any state $\ket{x}$ such that
$|\alpha_{x}|\geq\tau$, so $\lambda\geq\tau^{2}$. Thus, for the former
problem, amplitude amplification will call ProbFilBOrcl
$\tilde{O}(\tfrac{1}{\sqrt{\tau}})$ times, each of which requires
$O(\tfrac{1}{\epsilon})$ calls to $O_{D}$. Similarly, for the latter problem,
AmpFilBOrcl will be called $\tilde{O}(\tfrac{1}{\tau})$ times, each of which
requires $O(\tfrac{1}{\epsilon})$ calls to $O_{D}$.

Even though the problems are similar, we cannot directly use our algorithm for
ProFil for solving AmpFil. For the latter, we are interested to identify any
$x$ such that $|\alpha_{x}|\geq\tau$. Though this is identical to deciding if
$p_{x}=|\alpha_{x}|^{2}$ is greater than the threshold $\tau^{2}$, to reduce
it to ProFil we have to set the latter’s threshold to $\tau^{2}$ and estimate
$p_{x}$ with additive accuracy $\epsilon^{2}$; this leads to the dependency of
query complexity on $\epsilon$ as $1/\epsilon^{2}$. So, to reduce this
quadratic dependency to $1/\epsilon$, AmpFilBOrcl employs the modified
Hadamard test described in section 3 and uses MDistAEAlgo. The details of the
ProbFilBOrcl and AmpFilBOrcl algorithms are discussed in Appendix E and
Appendix C, respectively.

With access to unbounded space, it is easy to see that one can estimate the
distribution $\mathcal{D}_{p}$ with $\epsilon$ additive accuracy using
$O(1/\epsilon^{2})$ and $O(1/\epsilon)$ queries to the oracle $O_{D}$ in the
classical and quantum settings respectively which can then be used to solve
the ProFil problem. However, in the case of $\tilde{O}(1)$ space, classically,
one would be required to make $O(n/\epsilon^{2})$ queries to answer the ProFil
problem. In contrast, our quantum algorithm solves the same in $\tilde{O}(1)$
space using just $\tilde{O}(1/\epsilon\sqrt{\tau})$ queries to $O_{D}$. Notice
that for constant $\tau$, our algorithm is optimal up to some $\log$ factors.

##  7 Lower bounds for ProFil and AmpFil

For our lower bounds we reduce from the CountDecision problem that takes as
input a binary string of length $n$ and decides if the number of ones in $X$,
denoted $|X|$, is $l_{1}$ or $l_{2}>l_{1}$, given a promise that one of the
two cases is true. We use the following lower bound result proved by Nayak and
Wu in [19].

######  Theorem 9 (CountDecision lower bound [19]).

Let $l_{1},l_{2}\in[n]$ be two integers such that $l_{2}>l_{1}$, and $X$ be an
$n$-bit binary string. Further, let $l_{2}-l_{1}=2\Delta$ for some integer
$\Delta$. Then any quantum algorithm takes
$\Omega(\sqrt{n/\Delta}+\sqrt{(l_{2}-\Delta)(n-(l_{2}-\Delta))}/\Delta)$
queries to solve the CountDecision problem.

######  Theorem 10.

Any quantum algorithm that solves ProFil ($\mathcal{D},\epsilon,\tau$)
requires $\Omega(\frac{1}{\epsilon}+\frac{1}{\sqrt{\tau}})$ queries.

Formally, let CountDecision ($l_{1},l_{2}$) be the decision problem of
counting if the hamming weight of the given input string is $l_{1}$ or $l_{2}$
given the promise that it is one of them. To prove that ProFil requires
$\Omega(\tfrac{1}{\epsilon})$ queries, we reduce an instance of CountDecision
on a $n$-bit string $X$ with $l_{1}=\tfrac{n}{2}$ and
$l_{2}=\tfrac{n}{2}+\varepsilon n$ to ProFil. Observe that the frequencies of
$0$ and $1$ in the string $X$ induce a distribution $\mathcal{D}$. So, an
oracle to $X$ can be used to implement an oracle $O_{D}$ to the distribution
$\mathcal{D}$. By Corollary 1.2 of [19], the query complexity to decide the
above CountDecision instance is $\Omega(\tfrac{1}{\varepsilon})$. If
$|X|=\tfrac{n}{2}$ then $\Pr_{D}[0]=\Pr_{D}[1]=\tfrac{1}{2}$, and if
$|X|=\tfrac{n}{2}+\varepsilon n$, then $\Pr_{D}[1]=\tfrac{1}{2}+\varepsilon$.
Thus, the output of a ProFil algorithm with $\tau=\tfrac{1}{2}+\varepsilon$
and additive accuracy $\epsilon=\varepsilon$ can be used to decide our
CountDecision instance. This proves a lower bound of
$\Omega(\tfrac{1}{\varepsilon})$ for ProFil.

Next we prove a bound of $\Omega(\tfrac{1}{\sqrt{\tau}})$. For proving this
lower bound, instead of the CountDecision problem, we use the quantum
adversary method. We first use this method to obtain a lower bound on the mode
decision problem: Given an array $A$ of size $n$ and a threshold
$\tau^{\prime}\in[1,n]$ we have to decide if there exists any element whose
frequency is greater than $\tau^{\prime}$. We then show a reduction from mode
decision problem to ProFil to get a lower bound on it.

The main theorem of quantum adversary method can be stated as below [2]:

######  Theorem 11.

Let $F$ be a $n$-bit Boolean function and $X$ and $Y$ be two sets of inputs
such that $F(x)\neq F(y)$ for any $x\in X$ and $y\in Y$. Let $R\subseteq
X\times Y$ be a relation such that

  1. 1.

for every $x\in X$, $\exists$ at least $m$ different $y\in Y$ such that
$(x,y)\in R$.

  2. 2.

for every $y\in Y$, $\exists$ at least $m^{\prime}$ different $x\in X$ such
that $(x,y)\in R$.

  3. 3.

for every $x\in X$ and $i\in\\{1,...,n\\}$, $\exists$ at most $l$ different
$y\in Y$ such that $x_{i}\neq y_{i}$ and $(x,y)\in R$.

  4. 4.

for every $y\in Y$ and $i\in\\{1,...,n\\}$, $\exists$ at most $l^{\prime}$
different $x\in X$ such that $x_{i}\neq y_{i}$ and $(x,y)\in R$.

Then any quantum algorithm uses $\Omega\Big{(}\sqrt{\frac{m\cdot
m^{\prime}}{l\cdot l^{\prime}}}\Big{)}$ queries to compute $F$ on $X\bigcup
Y$.

Consider the mode decision problem. Let $\tau^{\prime}\in[1,n]$ be a threshold
and set $t=\frac{n}{\tau^{\prime}-1}$. Let $F$ be a Boolean function such that
$F(x)=1$ if $x$ is an array whose modal value is greater than or equal to
$\tau^{\prime}$ and $F(y)=0$ if the modal value of $y$ is strictly less than
$\tau^{\prime}$.

Let $Y$ be the set containing one array $B$ such that $B$ contains all unique
elements with frequency $\tau^{\prime}-1$. Let the unique elements be denoted
$b_{1},b_{2},\cdots,b_{t}$. Let $X$ be the set that contains the arrays
$A_{i}$ for all $2\leq i\leq t$ where $A_{i}$ is the array that is exactly the
same as $B$ except that the first occurrence of $b_{i}$ is changed to $a_{1}$.
Notice that the modal element in any $A_{i}$ is $b_{1}$. Define relation $R$
as $R=X\times Y$.

For any $A\in X$, we can see that there is exactly one element $B\in Y$ such
that $(A,B)\in R$ since $|Y|=1$. For $B\in Y$, there is exactly $t-1$ elements
$A\in X$ such that $(A,B)\in R$ as $|X|=t-1$. Similarly, for any $A\in X$ and
any $i\in[n]$, there is at most one element $B\in Y$ such that $A[i]\neq B[i]$
and $(A,B)\in R$. For $B\in Y$ and any $j\in[n]$, there is at most one element
$A\in X$ such that $A[j]\neq B[j]$ and $(A,B)\in R$.

From these we can derive that the quantum query complexity of computing $F$ is
$\Omega(\sqrt{\frac{t-1\cdot 1}{1\cdot
1}})=\Omega(\sqrt{t})=\Omega(\sqrt{n/\tau^{\prime}-1})$.

Now, the reduction from the mode decision problem to ProFil can be trivially
done by setting the threshold of ProFil $\tau$ as $\tau=\tau^{\prime}/n$. This
would imply that the quantum query lower bound of ProFil is
$\Omega(1/\sqrt{\tau})$ for $\epsilon=\frac{1}{n}$.

#####

For obtaining the lower bounds of AmpFil, it suffices to show that a ProFil
($\mathcal{D},2\epsilon,\tau$) instance can be reduced to an AmpFil
($\mathcal{D},\epsilon,\sqrt{\tau}$) instance. To show the reduction we prove
that the following holds for any $x$:

  * •

If $p_{x}\geq\tau$, then $|\alpha_{x}|\geq\sqrt{\tau}$.

  * •

If $p_{x}<\tau-2\epsilon$, then $|\alpha_{x}|<\sqrt{\tau}-\epsilon$.

Consider the case when $p_{x}\geq\tau$. This gives $|\alpha_{x}|^{2}\geq\tau$
which implies $|\alpha_{x}|\geq\sqrt{\tau}$ proving the first part of the
reduction. Now, let $p_{x}<\tau-2\epsilon$. This gives that
$|\alpha_{x}|<\sqrt{\tau-2\epsilon}$. Now, see that

$\displaystyle(\sqrt{\tau}-\epsilon)^{2}$
$\displaystyle=\tau+\epsilon^{2}-2\epsilon\sqrt{\tau}$
$\displaystyle\geq\tau-2\epsilon\sqrt{\tau}$ $\displaystyle\geq\tau-2\epsilon$
$\displaystyle\implies\sqrt{\tau}-\epsilon$
$\displaystyle\geq\sqrt{\tau-2\epsilon}$

Using this we have,
$|\alpha_{x}|<\sqrt{\tau-2\epsilon}\leq\sqrt{\tau}-\epsilon$ which proves the
second part of the reduction.

Using this reduction and Theorem 10, we obtain the following theorem.

######  Theorem 12.

Any quantum algorithm that solves AmpFil ($\mathcal{D},\epsilon,\tau$)
requires $\Omega(\frac{1}{\epsilon}+\frac{1}{\tau})$ queries.

##  8 Applications of ProFil and AmpFil

###  8.1 The $k$-Distinctness problem

The ElementDistinctness problem [9, 3, 1] is being studied for a long time
both in the classical and the quantum domain. It is a special case of the
$k$-Distinctness problem [3, 4] with $k=2$ which too has received a fair
attention.

######  Problem 2 ($k$-Distinctness).

Given an oracle to an $n$-sized $m$-valued array $A$, decide if $A$ has $k$
distinct indices with identical values.

By an $m$-valued array we mean an array whose entries are from
$\\{0,\ldots,m-1\\}$. Observe that, $k$-Distinctness can be reduced to ProFil
with $\tau=\tfrac{k}{n}$, assuming the ability to uniformly sample from $A$.

The best known classical algorithm for $k$-Distinctness uses sorting and has a
time complexity of $O(n\log(n))$ with a space complexity $O(n)$. In the
quantum domain, apart from $k=2$, the $k=3$ setting has also been studied
earlier [5, 11]. The focus of all these algorithms has been primarily to
reduce their query complexities. As a result their space requirement is
significant (polynomial in the size of the list), and beyond the scope of the
currently available quantum backends with a small number of qubits. Recently
Li et al. [17] reduced the problem of estimating the min-entropy to
$k$-Distinctness with a very large $k$ making this case additionally
important.

The $k$-Distinctness problem was further generalized to $\Delta$-Gapped
$k$-Distinctness by Montanaro [18] which comes with a promise that either some
value appears at least $k$ times or every value appears at most $k-\Delta$
times for a given gap $\Delta$. The $\textsc{F}_{\infty}$ problem [18, 10]
wants to determine, or approximate, the number of times the most frequent
element appears in an array, also known as the modal frequency. Montanaro
related this problem to the Gapped $k$-Distinctness problem but did not
provide any specific algorithm and left open its query complexity [18]. So it
appears that an efficient algorithm for $\Delta$-Gapped $k$-Distinctness can
positively affect the query complexities of all the above problems. However,
$\Delta$-Gapped $k$-Distinctness has not been studied elsewhere to the best of
our knowledge.

Table 1: Results for the $k$-Distinctness problem $k$-Distinctness
---
|  Prior upper bound [3] |  Our upper bound
$k\in\\{2,3,4\\}$ |  Setting $r=k$, $O((\frac{n}{k})^{k/2})$ queries, $O(\log(m)+\log(n))$ space |  $\tilde{O}(n^{3/2}/\sqrt{k})$ queries, $O\big{(}(\log(m)+\log(n))\log(\frac{n}{\delta k})\big{)}$ space
$k=\omega(1)$ and $k\geq 4$ |  $O(\frac{n^{2}}{k})$ queries, |
$O(\log(m)+\log(n))$ space for $r\geq k$ |  $\tilde{O}(n^{3/2}/\sqrt{k})$ queries, $O\big{(}(\log(m)+\log(n))\log(\frac{n}{\delta k})\big{)}$ space |
$k=\Omega(n)$ |  $O(n^{n/2})$ queries, |
$O(n\log(m)+\log(n))$ space |  $\tilde{O}(n)$ queries, $O\big{(}(\log(m)+\log(n))\log(\frac{n}{\delta k})\big{)}$ space |

#### Upper bounds for the $k$-Distinctness problem

The $k=2$ version is the ElementDistinctnessproblem which was first solved by
Buhrman et al. [9]; their algorithm makes $O(n^{3/4}\log(n))$ queries (with
roughly the same time complexity), but requires the entire array to be stored
using qubits. A better algorithm was later proposed by Ambainis [3] using a
quantum walk on a Johnson graph whose nodes represent $r$-sized subsets of
$[n]$, for some suitable parameter $r\geq k$. He used the same technique to
design an algorithm for $k$-Distinctness as well that uses $\tilde{O}(r)$
qubits and $O(r+(n/r)^{k/2}\sqrt{r})$ queries (with roughly the same time
complexity). Later Belovs designed a learning-graph for the $k$-Distinctness
problem, but only for constant $k$, and obtained a tighter bound of
$O(n^{\frac{3}{4}-\frac{1}{2^{k+2}-4}})$. It is not clear whether the bound
holds for non-constant $k$, and it is often tricky to construct efficiently
implementable algorithms base on the dual-adversary solutions obtained from
the learning graphs.

Thus it appears that even though efficient algorithms may exist for small
values of $k$, the situation is not very pleasant for large $k$, especially
$k=\Omega(n)$ — the learning graph idea may not work (even if the
corresponding algorithm could be implemented in a time-efficient manner) and
the quantum walk algorithm uses $\Omega(k)$ space.

We proposed to use ProFil to solve $k$-Distinctness by (a) implementing an
oracle $O_{D}$ from the array $A$ (this is straight forward), and then calling
our algorithm for probability filtering using $\tau=k/n$ (see Theorem 8, and
$\epsilon=1/n$ to ensure that estimates (which are always of the form $t/n$)
are well-separated.

######  Lemma 13.

There exists a bounded-error algorithm for $k$-Distinctness, for any
$k\in[n]$, that uses $O(\tfrac{n^{3/2}}{\sqrt{k}}\log(\tfrac{1}{\delta\cdot
k}))$ queries and $O\big{(}(\log(m)+\log(n))\log(\frac{1}{\delta\cdot
k})\big{)}$ qubits.

See Table 1 for a comparison of our method with respect to the others. This
algorithm has a few attractive features. It is specifically designed to use
$\tilde{O}(1)$ qubits, and as an added benefit, it works for any $k$. Further,
it improves upon the algorithm proposed by Ambainis for $k\geq 4$ when we
require that $\tilde{O}(1)$ space be used, and moreover, its query complexity
does not increase with $k$. One might be puzzled with the fact that the query
complexities are larger than $n$ as it is well known that in unbounded space,
the query complexity of $k$-Distinctness is trivially $n$. However, when the
available space is restricted to $O(\log(n))$ space, then the query complexity
of $k$-Distinctness need not be bounded by $n$.

There have been separate attempts to design algorithms for specific values of
$k$. For example, for $k=3$ Belovs designed a slightly different algorithm
compared to the above [5] and Childs et al. [11] gave a random walk based
algorithm both of which uses $O(n^{5/7})$ queries and $O(n^{5/7})$ space.
These algorithm improved upon the $O(n^{3/2})$-query algorithm proposed
earlier by Ambainis [3]. Our algorithm provides an alternative that matches
the query complexity of the latter and can come in handy when a small number
of qubits are available.

For $k$ that is large, e.g. $\Omega(n)$, the query complexity of Ambainis’
algorithm is exponential in $n$ and that of ours is $O(n^{3/2})$. Montanaro
used a reduction from the CountDecision problem [19] to prove a lower bound of
$\Omega(n)$ queries for $k=\Omega(n)$ — of course, assuming unrestricted space
[18]. Our algorithm matches this lower bound, but with only $\tilde{O}(1)$
space.

###  8.2 The Non-linearity Estimation Problem

Non-linearity is an important cryptographic measure of a Boolean function.
Non-linearity of a function $f:\\{0,1\\}^{n}\xrightarrow{}\\{0,1\\}$ is
defined in terms of the largest absolute-value of its Walsh-Hadamard
coefficient [6] as

$\eta(f)=\tfrac{1}{2}-\tfrac{1}{2}\hat{f}_{max}$

where $\hat{f}_{max}=\max_{x}|\hat{f}(x)|$ and $\hat{f}(x)$ is the Walsh-
Hadamard coefficient of $f$ at the point $x$. Boolean functions with low non-
linearity can be easily approximated by linear functions. One of the
conditions that any Boolean function needs to satisfy to be used in
cryptographic applications is that its non-linearity is high. Notice from the
definition that to estimate the non-linearity of a function, it suffices to
obtain an estimate of $\hat{f}_{max}$ of that function. Recall that the output
state of the Deutsch-Jozsa circuit is $\sum_{x}\hat{f}(x)\ket{x}$, i.e., the
probability of observing $\ket{x}$ is $\hat{f}(x)^{2}$. It immediately follows
that we can utilize the ProFil algorithm in conjunction with a binary search
on the interval $(0,1]$ to estimate $\hat{f}_{max}^{2}$, and hence, non-
linearity, with additive inaccuracy. This approach is presented as Algorithm 1
in [6]. However, this would lead to a query complexity of
$\tilde{O}(1/\lambda^{2}\hat{f}_{max})$ 777Although the query complexity of
this algorithm has been proved to be $\tilde{O}(1/\lambda^{3})$ in [6], the
query complexity can be reduced to $\tilde{O}(1/\lambda^{2}\hat{f}_{max})$
with a slightly tighter analysis of their Algorithm 1. to estimate non-
linearity to within $\lambda$ additive accuracy.

Alternately, we can replace ProFil with AmpFil to estimate $\hat{f}_{max}$
instead of $\hat{f}_{max}^{2}$ in the algorithm presented in [6]. This reduces
the number of queries since to estimate $\hat{f}_{max}$ within $\pm\lambda$,
it now suffices to call AmpFil with inaccuracy $\lambda$, instead of calling
ProFil with inaccuracy $\lambda^{2}$. Given that the query complexity of
AmpFil is $\tilde{O}(1/\lambda)$, this leads to a quadratic improvement in the
query complexity in form of $\tilde{O}(\frac{1}{\lambda\hat{f}_{max}})$.

######  Lemma 14.

Given a Boolean function $f:\\{0,1\\}^{n}\xrightarrow{}\\{0,1\\}$ as an
oracle, an accuracy parameter $\lambda$ and an error parameter $\delta$, there
exists an algorithm that returns an estimate $\tilde{\eta}_{f}$ such that
$|\eta_{f}-\tilde{\eta}_{f}|\leq\lambda$ with probability at least $1-\delta$
using
$O(\frac{1}{\lambda\hat{f}_{max}}\log(\frac{1}{\lambda})\log(\frac{1}{\delta\hat{f}_{max}}))$
queries to the oracle of $f$.

Bera et al., ([6]) also showed a lower bound of $\Omega(1/\sqrt{\lambda})$ for
the non-linearity estimation. This can further improved to $\Omega(1/\lambda)$
via a reduction from the CountDecision problem to the non-linearity problem.

######  Lemma 15.

Any quantum algorithm uses $\Omega(1/\lambda)$ queries to estimate the non-
linearity of any given Boolean function.

The proof of Lemma 15 is given in Appendix I. This shows that the modified
algorithm for non-linearity estimation that uses AmpFil is close to optimal.

## References

  * [1] Scott Aaronson and Yaoyun Shi.  Quantum lower bounds for the collision and the element distinctness problems.  Journal of the ACM, 51(4):595–605, 7 2004.
  * [2] Andris Ambainis.  Quantum lower bounds by quantum arguments.  Journal of Computer and System Sciences, 64(4):750–767, 2002.
  * [3] Andris Ambainis.  Quantum Walk Algorithm for Element Distinctness.  SIAM Journal on Computing, 37(1):210–239, 1 2007.
  * [4] Aleksandrs Belovs.  Learning-Graph-Based Quantum Algorithm for k-Distinctness.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 207–216. IEEE, 10 2012.
  * [5] Aleksandrs Belovs.  Applications of the adversary method in quantum query algorithms.  arXiv preprint arXiv:1402.3858, 2014.
  * [6] Debajyoti Bera and Sapv Tharrmashastha.  Quantum and randomised algorithms for non-linearity estimation.  ACM Transactions on Quantum Computing, 2(2), jul 2021.
  * [7] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation.  Contemporary Mathematics, 305:53–74, 2002.
  * [8] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation.  Contemporary Mathematics, 305:53–74, 2002.
  * [9] Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, and Ronald de Wolf.  Quantum Algorithms for Element Distinctness.  SIAM Journal on Computing, 34(6):1324–1330, 1 2005.
  * [10] Mark Bun, Robin Kothari, and Justin Thaler.  The polynomial method strikes back: Tight quantum query bounds via dual polynomials.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 297–310, 2018.
  * [11] Andrew M Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez.  A time-efficient quantum walk for 3-distinctness using nested updates.  arXiv preprint arXiv:1302.7316, 2013.
  * [12] Graham Cormode and S. Muthukrishnan.  An improved data stream summary: The count-min sketch and its applications.  J. Algorithms, 55(1):58–75, April 2005.
  * [13] S. Dutta and A. Goswami.  Mode estimation for discrete distributions.  Mathematical Methods of Statistics, 19(4):374–384, 2010.
  * [14] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd.  Quantum algorithm for linear systems of equations.  Phys. Rev. Lett., 103:150502, Oct 2009.
  * [15] Peter Høyer, Michele Mosca, and Ronald de Wolf.  Quantum search on bounded-error inputs.  In International Colloquium on Automata, Languages, and Programming, pages 291–299. Springer, 2003.
  * [16] Stacey Jeffery.  Quantum subroutine composition.  arXiv preprint arXiv:2209.14146, 2022.
  * [17] Tongyang Li and Xiaodi Wu.  Quantum Query Complexity of Entropy Estimation.  IEEE Transactions on Information Theory, 65(5):2899–2921, 5 2019\.
  * [18] Ashley Montanaro.  The quantum complexity of approximating the frequency moments.  Quantum Information and Computation, 16(13-14):1169–1190, 2016\.
  * [19] Ashwin Nayak and Felix Wu.  Quantum query complexity of approximating the median and related statistics.  Conference Proceedings of the Annual ACM Symposium on Theory of Computing, pages 384–393, 1999.
  * [20] Gregory Valiant and Paul Valiant.  Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new clts.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 685–694, 2011.
  * [21] Joran van Apeldoorn.  Quantum probability oracles & multidimensional amplitude estimation.  In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [22] Theodore J Yoder, Guang Hao Low, and Isaac L Chuang.  Fixed-point quantum search with an optimal number of queries.  Physical review letters, 113(21):210501, 2014.

##  Appendix A Amplitude amplification, amplitude estimation and majority

In this section, we present details on the quantum amplitude amplification
subroutine and the $\mathtt{MAJ}$ operator which are used as part of our
algorithms.

###  A.1 Amplitude amplification

The amplitude amplification algorithm (AA) is a generalization of the novel
Grover’s algorithm. Given an $n$-qubit algorithm $A$ that outputs the state
$\ket{\phi}=\sum_{k}\alpha_{k}\ket{k}$ on $\ket{0^{n}}$ and a set of basis
states $G=\\{\ket{a}\\}$ of interest, the goal of the amplitude amplification
algorithm is to amplify the amplitude $\alpha_{a}$ corresponding to the basis
state $\ket{a}$ for all $\ket{a}\in G$ such that the probability that the
final measurement output belongs to $G$ is close to 1. In the most general
setting, one is given access to the set $G$ via an oracle $O_{G}$ that marks
all the states $\ket{a}\in G$ in any given state $\ket{\phi}$; i.e., $O_{G}$
acts as

$O_{G}\sum_{k}\alpha_{k}\ket{k}\ket{0}\xrightarrow{}\sum_{a\notin
G}\alpha_{a}\ket{a}\ket{0}+\sum_{a\in G}\alpha_{a}\ket{a}\ket{1}.$

Now, for any $G$, any state $\ket{\phi}=\sum_{k}\alpha_{k}\ket{k}$ can be
written as

$\ket{\phi}=\sum_{k}\alpha_{k}\ket{k}=\sin(\theta)\ket{\nu}+\cos(\theta)\ket{\overline{\nu}}$

where $\sin(\theta)=\sqrt{\sum_{a\in G}|\alpha_{a}|^{2}}$,
$\ket{\nu}=\frac{\sum_{a\in G}\alpha_{a}\ket{a}}{\sqrt{\sum_{a\in
G}|\alpha_{a}|^{2}}}$ and $\ket{\overline{\nu}}=\frac{\sum_{a\notin
G}\alpha_{a}\ket{a}}{\sqrt{\sum_{a\notin G}|\alpha_{a}|^{2}}}$. Notice that
the states $\ket{\nu}$ and $\ket{\overline{\nu}}$ are normalized and are
orthogonal to each other. The action of the amplitude amplification algorithm
can then be given as

$AA\Big{(}\sum_{k}\alpha_{k}\ket{k}\ket{0}\Big{)}=AA\big{(}\sin(\theta)\ket{\nu}+\cos(\theta)\ket{\overline{\nu}}\big{)}\ket{0}\xrightarrow{}\sqrt{(1-\beta)}\ket{\nu}\ket{1}+\sqrt{\beta}\ket{\overline{\nu}}\ket{0}$

where $\beta$ satisfies $|\beta|<\delta$ and $\delta$ is the desired error
probability. This implies that on measuring the final state of AA, the
measurement outcome $\ket{a}$ belongs to $G$ with probability $|1-\beta|$
which is at least $1-\delta$.

###  A.2 $\mathtt{MAJ}$ operator

Let $X_{1}\ldots X_{k}$ be Bernoulli random variables with success probability
$p>1/2$. Let $Maj$ denote their majority value (that appears more than $k/2$
times). Using Hoeffding’s bound888$\Pr[\sum X_{i}-E[\sum X_{i}]\geq
t]\leq\exp(-\frac{2t^{2}}{n})$, it can be easily proved that $Maj$ has a
success probability at least $1-\delta$, for any given $\delta$, if we choose
$k\geq\tfrac{2p}{(p-1/2)^{2}}\ln\tfrac{1}{\delta}$. We require a quantum
formulation of the same.

Suppose we have $k$ copies of the quantum state
$\ket{\psi}=\ket{\psi_{0}}\ket{0}+\ket{\psi_{1}}\ket{1}$ in which we define
“success” as observing $\ket{0}$ (without loss of generality) and $k$ is
chosen as above. Let $p=\|\ket{\psi_{0}}\|^{2}$ denote the probability of
success. Suppose we measure the final qubit after applying
$(\mathbb{I}^{k}\otimes MAJ)$ in which the $MAJ$ operator acts on the second
registers of each copy of $\ket{\psi}$. Then it is easy to show, essentially
using the same analysis as above, that

$(\mathbb{I}^{k}\otimes MAJ)\ket{\psi}^{\otimes
k}\ket{0}=\ket{\Gamma_{0}}\ket{0}+\ket{\Gamma_{1}}\ket{1}$

in which $\|\ket{\Gamma_{0}}\|^{2}\geq 1-\delta$.

The $\mathtt{MAJ}$ operator can be implemented without additional queries and
with $poly(k)$ gates and $\log(k)$ qubits.

##  Appendix B Some Useful Subroutines

In this section we present a few subroutines that are used in the construction
of ProbFilBOrcl and AmpFilBOrcl oracles.

EQm:

Given two computational basis states $\ket{x}$ and $\ket{y}$ each of $k$
qubits, EQm checks if the $m$-sized prefix of $x$ and that of $y$ are equal.
Mathematically, EQm$\ket{x}\ket{y}=(-1)^{c}\ket{x}\ket{y}$ where $c=1$ if
$x_{i}=y_{i}$ for all $i\in[m]$, and $c=0$ otherwise.

HDq:

When the target qubit is $\ket{0^{q}}$, and with a $q-$bit string $y$ in the
control register, HD computes the absolute difference of $y_{int}$ from
$2^{q-1}$ and outputs it as a string where $y_{int}$ is the integer
corresponding to the string $y$. It can be represented as ${\tt
HD}_{q}\ket{y}\ket{b}=\ket{b\oplus\tilde{y}}\ket{y}$ where
$y,b\in\\{0,1\\}^{q}$ and $\tilde{y}$ is the bit string corresponding to the
integer $\absolutevalue{2^{q-1}-y_{int}}$. Even though the operator HD
requires two registers, the second register will always be in the state
$\ket{0^{q}}$ and shall be reused by uncomputing (using $HD^{\dagger}$) after
the CMP gate. For all practical purposes, this operator can be treated as the
mapping $\ket{y}\mapsto\ket{\tilde{y}}$.

CMP:

The ${\tt CMP}$ operator is defined as ${\tt
CMP}\ket{y_{1}}\ket{y_{2}}\ket{b}=\ket{y_{1}}\ket{y_{2}}\ket{b\oplus(y_{2}\leq
y_{1})}$ where $y_{1},y_{2}\in\\{0,1\\}^{n}$ and $b\in\\{0,1\\}$. It simply
checks if the integer corresponding to the basis state in the first register
is at most that in the second register.

Cond-MAJ:

The ${\tt Cond-MAJ}$ operator is defined as
$\prod_{x}\big{(}\ket{x}\bra{x}\otimes MAJ\big{)}$ where
$\ket{x}\bra{x}\otimes MAJ$ acts on computational basis states as
$MAJ\ket{a_{1}}\cdots\ket{a_{k}}\ket{b}=\ket{a_{1}}\cdots\ket{a_{k}}\ket{b\oplus(\tilde{a}\geq
k/2)}$ where $\tilde{a}=\sum_{k}a_{k}$ and $a_{i},b\in\\{0,1\\}$.

##  Appendix C Bounded oracle for amplitude filtering

###  C.1 Construction of AmpFilBOrcl to mark high amplitude states

Algorithm 5 Constructing biased-oracle AmpFilBOrcl for real amplitude
filtering

1:Oracle $O_{D}$ (with parameters $m$, $a$), threshold $\tau$, and accuracy
$\epsilon$.

2:Input register $R_{1}$ set to some basis state $\ket{x}$ and output register
$R_{5}$ set to $\ket{0}$.

3:Set $r=\log(m)+a$, $\tau^{\prime}=\frac{1}{2}(1+\tau-\frac{\epsilon}{16})$,
$q=\lceil\log(\frac{1}{\epsilon})\rceil+5$ and $l=q+3$.

4:Set
$\tau_{1}=\left\lfloor{\frac{2^{l}}{\pi}\sin^{-1}(\sqrt{\tau^{\prime}})}\right\rfloor$

5:Initialize ancillæ registers $R_{21}R_{22}R_{3}R_{4}$ of lengths $1,r,l$ and
$l$, respectively. Set $R_{3}=\ket{\tau_{1}}$.

6:Stage 1: Apply MDistAEAlgo (sans measurement) with $R_{21}$ as the input
register, $R_{4}$ as the output register and $\ket{0}$ as the “good state”. A
controlled-Hadamard test, i.e., $\sum_{y}\outerproduct{y}{y}\otimes
HT_{A_{y},O_{D}}$ over the registers $R_{1},R_{21}$ and $R_{22}$ is used as
the state preparation oracle, of which only $R_{21}$ is used in MDistAEAlgo.
MDistAEAlgo is called with error at most $1-\frac{8}{\pi^{2}}$ and additive
accuracy $\frac{1}{2^{q}}$. Here, $\\{A_{y}\leavevmode\nobreak\
:\leavevmode\nobreak\ y\in\\{0,1\\}^{r}\\}$ is a family of oracles each of
which acts as $A_{y}\ket{0^{r}}=\ket{y}$.

7:Stage 2: Set $R_{5}$ to 1 if the estimate of the probability, calculated
using $R_{4}$, meets $\tau$.

8: Use HDl on $R_{3}$ and $R_{4}$ individually.

9: Use ${\tt CMP}$ on $R_{3}=\ket{\tau_{1}}$ and $R_{4}$ as input registers
and $R_{5}$ as output register.

10: Use HD${}^{\dagger}_{l}$ on $R_{3}$ and $R_{4}$ individually.

The algorithm is described in Algorithm 5. The controlled-Hadamard test on
$\ket{x}\ket{0}\ket{0^{r}}$ is same as $\ket{x}\otimes
HT_{A_{x},O_{D}}(\ket{0}\ket{0^{r}})$, essentially performing the test on
$R_{21}$ and $R_{22}$ between $A_{x}\ket{0^{r}}=\ket{x}$ and
$O_{D}\ket{0^{r}}$. Had we measured the output state of $R_{21}$, we would
have observed $\ket{0}$ with probability
$\frac{1}{2}\big{(}1+Re\big{(}|\innerproduct{x}{O_{D}|0^{r}}|\big{)}\big{)}$.
MDistAEAlgo estimates this probability in $R_{4}$. The steps in Stage 2 are to
compare this estimate with the threshold, and set or unset the output register
$R_{5}$ accordingly. After minute analysis of errors, one can prove that the
algorithm almost always marks a state if the real-value of its amplitude is
above $\tau$.

Extending this algorithm to consider the absolute value of an amplitude
follows the expected path of estimating both the real and the complex parts
using Hadamard tests (see Section 3), estimating the absolute value from those
two, and then using the latter for marking.

Further, note that queries to $O_{D}$ are only made by MDistAEAlgo, and that
too as part of the state-preparation oracle — the controlled Hadamard test.
MDistAEAlgo makes $O(1/\epsilon)$ calls to the test, and each of them involves
one call to $O_{D}$, leading to an overall query complexity of
$O(1/\epsilon)$. The entire behaviour is summarised below.

######  Lemma 16.

AmpFilBOrcl makes $O(1/\epsilon)$ queries to $O_{D}$ and behaves as given
below.

$\textsc{AmpFilBOrcl}\ket{x}\ket{0^{2l+r+1}}\ket{0}=\ket{x}\Big{(}\eta_{x,0}\ket{\phi_{x,0}}\ket{0}+\eta_{x,1}\ket{\phi_{x,1}}\ket{1}\big{)}$

where $|\eta_{x,0}|^{2}\geq\tfrac{8}{\pi^{2}}$ if $|\alpha_{x}|<\tau-\epsilon$
and $|\eta_{x,1}|^{2}\geq\tfrac{8}{\pi^{2}}$ if $|\alpha_{x}|\geq\tau$.

Intuitively, AmpFilBOrcl correctly marks a given $x$ with probability at least
$\tfrac{8}{\pi^{2}}$ if $|\alpha_{x}|\geq\tau$ and erroneously marks $x$ with
probability at most $1-\tfrac{8}{\pi^{2}}$ if $|\alpha_{x}|<\tau-\epsilon$,
which leads to the claim that AmpFilBOrcl is a biased oracle with error
$1-\tfrac{8}{\pi^{2}}$.

###  C.2 Analysis of AmpFilBOrcl

We first assume that all amplitudes are real.

See 16

We require a few technical results to proceed with the proof. These can be
proved easily using standard identities.

######  Proposition 17.

For any $\alpha_{x}$, a threshold $\tau$ and some $\epsilon$,

  1. 1.

$|\alpha_{x}|\geq\tau+2\epsilon\iff\frac{1}{2}\big{(}1-|\alpha_{x}|\big{)}\leq\frac{1}{2}\big{(}1-\tau\big{)}-\epsilon$.

  2. 2.

$|\alpha_{x}|<\tau\iff\frac{1}{2}\big{(}1-|\alpha_{x}|\big{)}>\frac{1}{2}\big{(}1-\tau\big{)}$.

######  Proposition 18 (Proposition 4.1,[6]).

For any two angles $\theta_{1},\theta_{2}\in[0,\pi]$,

$\sin{\theta_{1}}\leq\sin{\theta_{2}}\iff\sin^{2}{\theta_{1}}\leq\sin^{2}{\theta_{2}}\iff\absolutevalue{\frac{\pi}{2}-\theta_{1}}\geq\absolutevalue{\frac{\pi}{2}-\theta_{2}}.$

######  Proposition 19 (Proposition 4.3,[6]).

If two constants $\tau^{\prime}$ and $\tau_{1}$ are related as
$\tau_{1}=\left\lfloor{\frac{2^{l}}{\pi}\sin^{-1}(\sqrt{\tau^{\prime}})}\right\rfloor$,
then they satisfy
$0\leq\tau^{\prime}-\frac{2\pi}{2^{l}}\leq\sin^{2}(\frac{\pi\tau_{1}}{2^{l}})$.

###### Proof of Lemma.

We analyse Algorithm 5 stage by stage for registers
$R_{1}R_{21}R_{22}R_{3}R_{4}R_{5}$ with the input
$\ket{x}\ket{0}\ket{0^{r}}\ket{0^{l}}\ket{0^{l}}\ket{0}$.

##### Stage-1:

Consider the registers $R_{1}R_{21}R_{22}R_{4}$. We set
$R_{3}=\ket{\tau_{1}}$. In Section 4 we identified that the MDistAEAlgo can be
given as product of two operators $U=\sum_{y}\outerproduct{y}{y}\otimes
AmpEst_{y}$ and $V=\sum_{y}\outerproduct{y}{y}\otimes
B_{y}\otimes\mathbb{I}^{l}$. In the construction of the oracle, we have
$B_{y}=HT_{A_{y},O_{D}}$ and $A_{y}$ is such that $A_{y}\ket{0^{r}}=\ket{y}$.
We analyze the state of the register after each of these operations. For
simplicity we assume that
$O_{D}\ket{0^{r}}=\sum_{x}\alpha_{x}\ket{x}=\ket{\phi}$ (ignoring the
$\ket{\xi_{x}}$ states).

The state of the registers $R_{1},R_{21}$ and $R_{22}$ after applying $V$ on
$\ket{x}\ket{0}\ket{0^{r}}$ can be given as

$\ket{\psi_{1}^{\prime}}=\frac{1}{2}\ket{x}\big{(}\ket{0}(\ket{x}+\ket{\phi})+\ket{1}(\ket{x}-\ket{\phi})\big{)}.$

Given that the state in $R_{1}$ is $\ket{x}$, the probability of obtaining
$\ket{0}$ in $R_{21}$ can then be given as

$Pr(\ket{0}_{R_{21}})=\frac{1}{4}||\ket{x}+\ket{\phi}||^{2}=\frac{1}{4}\Big{(}2+2Re\big{(}\bra{x}\ket{\phi}\big{)}\Big{)}=\frac{1}{2}(1+|\alpha_{x}|).$

Using this, $\ket{\psi_{1}^{\prime}}$ can be given as

$\ket{\psi_{1}^{\prime}}=\ket{x}\Big{(}\nu_{x0}\ket{0}\ket{\eta_{x0}}+\nu_{x1}\ket{1}\ket{\eta_{x1}}\Big{)}=\ket{x}\ket{\nu_{x}}\text{\leavevmode\nobreak\
(say)}$

for some normalized states $\ket{\eta_{x0}}$ and $\ket{\eta_{x1}}$ where
$|\nu_{x0}|^{2}=\frac{1}{2}(1+|\alpha_{x}|)$.

Notice that the operation $U$ is applied on the registers $R_{1}R_{21}R_{4}$.
This operation is given as $\sum_{x}\outerproduct{x}{x}\otimes AmpEst_{x}$
where $AmpEst_{x}$ uses the Grover iterator
$G_{x}=-B_{x}U_{\overline{0}}B_{x}^{\dagger}U_{0}$. On applying $U$ on
$R_{1}R_{21}R_{4}$, we obtain a state of the registers
$R_{1}R_{21}R_{22}R_{3}R_{4}R_{5}$ as,

$\displaystyle\ket{\psi_{1}}$
$\displaystyle=\ket{x}\ket{\nu_{x}}\ket{\tau_{1}}\Big{(}\beta_{x,s}\ket{a_{x}}+\beta_{x,\overline{s}}\ket{E_{x}}\Big{)}\ket{0}$
$\displaystyle=\beta_{x,s}\ket{x}\ket{\nu_{x}}\ket{\tau_{1}}\ket{a_{x}}\ket{0}+\beta_{x,\overline{s}}\ket{x}\ket{\nu_{x}}\ket{\tau_{1}}\ket{E_{x}}\ket{0}$
$\displaystyle=\beta_{x,s}\ket{\psi_{1,s}}+\beta_{x,\overline{s}}\ket{\psi_{1,\overline{s}}}$

where $\ket{a_{x}}$ is a normalized state of the form
$\ket{a_{x}}=\gamma_{+}\ket{a_{x,+}}+\gamma_{-}\ket{a_{x,-}}$ that on
measurement outputs $a\in\\{a_{x,+},a_{x,+}\\}$ which is an $l$-bit string
that behaves as
$\displaystyle\left|\sin^{2}\left(\frac{a\pi}{2^{l}}\right)-|\nu_{x0}|^{2}\right|\leq\tfrac{1}{2^{q}}$,
$|\beta_{x,s}|^{2}\geq 1-\frac{8}{\pi^{2}}$ and
$|\beta_{x,s}|^{2}\leq\frac{8}{\pi^{2}}$. We denote the set
$\\{a_{x,+},a_{x,-}\\}$ by $S_{a_{x}}$. Essentially, for any $x$, MDistAEAlgo
stores the correct estimate of the probability of $x$ in $\ket{\nu_{x}}$ into
$R_{4}$ with probability at least $1-\frac{8}{\pi^{2}}$ and errors with
probability at most $\frac{8}{\pi^{2}}$.

##### Stage-2:

Notice that stage 2 affects only the registers $R_{3},R_{4}$ and $R_{5}$. Here
we are interested only in the state $\ket{\psi_{1,s}}$ that contains the
correct estimate. For any computational basis state $\ket{u}$ and $\ket{v}$,
the transformation of a state of the form $\ket{u}\ket{v}\ket{0}$ due to stage
2 can be given as

$\ket{u}\ket{v}\ket{0}\xrightarrow{}\ket{u}\ket{v}\ket{\mathbb{I}\\{u\geq
v\\}}\mbox{ where \leavevmode\nobreak\ }\mathbb{I}\\{u\geq v\\}=1\mbox{ if
$u\geq v$ and $0$ else}.$ (1)

The reason for indicating “$u\geq v$” as 1 and not the other way around is due
to the reversal of the direction of the inequality in Proposition 18. Then,
stage 2 transforms the state

$\ket{\psi_{1,s}}=\ket{x}\ket{\nu_{x}}\ket{\tau_{1}}\ket{a_{x}}\ket{0}=\ket{x}\ket{\nu_{x}}\ket{\tau_{1}}\Big{[}\gamma_{+}\ket{a_{x,+}}\ket{0}+\gamma_{-}\ket{a_{x,-}}\ket{0}\Big{]}$

to the state

$\ket{\psi_{2,s}}=\ket{x}\ket{\nu_{x}}\ket{\tau_{1}}\Big{[}\gamma_{+}\ket{a_{x,+}}\ket{\mathbb{I}\\{a_{x+}\leq\tau_{1}\\}}+\gamma_{-}\ket{a_{x,-}}\ket{\mathbb{I}\\{a_{x-}\leq\tau_{1}\\}}\Big{]}$

We will analyse the states $\ket{\mathbb{I}\\{a_{x\pm}\leq\tau_{1}\\}}$ by
considering two types of index $x\in[m]$.

##### Scenario (i):

Let $x$ be such that $|\alpha_{x}|<\tau-\epsilon$. Now, any computational
basis state $a$ in $\ket{a_{x}}$ will be such that
$\tilde{a}_{x}(say)=\sin^{2}(\frac{a\pi}{2^{l}})\in[|\nu_{x0}|^{2}-\tfrac{1}{2^{q}},|\nu_{x0}|^{2}+\tfrac{1}{2^{q}}]$.
Therefore,
$\tilde{a}_{x}\leq|\nu_{x0}|^{2}+\tfrac{1}{2^{q}}=\frac{1}{2}(1+|\alpha_{x}|)+\frac{1}{2^{q}}<\frac{1}{2}(1+\tau-\epsilon)+\tfrac{1}{2^{q}}$
and since $q$ was chosen such that $2^{q}\geq\frac{32}{\epsilon}$,
$\tilde{a}_{x}<\frac{1}{2}(1+\tau-\frac{7\epsilon}{16})$.

Since we have $2^{l}>2^{q+1}\geq\frac{64}{\epsilon}$, we get that
$\frac{2\pi}{2^{l}}<\frac{2\pi\epsilon}{64}<\frac{6\epsilon}{32}$. Using this,
we have
$\frac{1}{2}(1+\tau-\frac{7\epsilon}{16})=\tau^{\prime}-\frac{6\epsilon}{32}<\tau^{\prime}-\frac{2\pi}{2^{l}}<\sin^{2}(\frac{\pi\tau_{1}}{2^{l}})$
using Proposition 19. Since,
$\tilde{a}_{x}<\frac{1}{2}(1+\tau-\frac{7\epsilon}{16})$, we have
$\tilde{a}_{x}=\sin^{2}(\frac{a\pi}{2^{l}})<\frac{1}{2}(1+\tau-\frac{7\epsilon}{16})<\sin^{2}(\frac{\pi\tau_{1}}{2^{l}})$.

Now on applying HDl on $R_{3}$ and $R_{4}$, we obtain $\ket{\hat{\tau}_{1}}$
and $\ket{\hat{a}}$ respectively in $R_{3}$ and $R_{4}$ such that
$\hat{a}=|2^{l-1}-a|$ and $\hat{\tau}_{1}=|2^{l-1}-\tau_{1}|$. Using
Proposition 18 on the fact that
$\tilde{p}_{x}=\sin^{2}(\frac{a\pi}{2^{l}})<\sin^{2}(\frac{\pi\tau_{1}}{2^{l}})$
we get $\hat{a}=|2^{l-1}-a|>\hat{\tau}_{1}=|2^{l-1}-\tau_{1}|$.

Since $\hat{a}>\hat{\tau}_{1}$ corresponding to any
$\ket{a}\in\\{\ket{a_{x,-}},\ket{a_{x,+}}\\}$, after using CMP on $R_{3}$ and
$R_{4}$, we get in $R_{5}$ the state
$\ket{\mathbb{I}\\{a_{x,-}\leq\tau_{1}\\}}=\ket{\mathbb{I}\\{a_{x,+}\leq\tau_{1}\\}}=\ket{0}$.
Since the state $\ket{\psi_{1,s}}$ which contains the correct estimate exists
with probability at least $1-\frac{8}{\pi^{2}}$ in $\ket{\psi_{1}}$, in this
case, the output state $\ket{\psi_{2}}$ after stage-2 is such that with
probability at least $1-\frac{8}{\pi^{2}}$ the state $\ket{x}$ is not marked.
In other words, if $x$ is such that $|\alpha_{x}|<\tau-\epsilon$ then
$\ket{\psi_{2}}$ contains
$\ket{x}\ket{\nu_{x}}\ket{\tau_{1}}\ket{a_{x}}\ket{0}$ with probability at
least $1-\frac{8}{\pi^{2}}$.

##### Scenario (ii):

$z$ be such that $|\alpha_{z}|\geq\tau$. Now, any computational basis state
$a$ in $\ket{a_{z}}$ will be such that
$\tilde{a}_{z}(say)=\sin^{2}(\frac{a\pi}{2^{l}})\in[|\nu_{x0}|^{2}-\tfrac{1}{2^{q}},|\nu_{x0}|^{2}+\tfrac{1}{2^{q}}]$.
Therefore,
$\tilde{a}_{z}\geq|\nu_{x0}|^{2}-\tfrac{1}{2^{q}}=\frac{1}{2}(1+|\alpha_{z}|)-\frac{1}{2^{q}}\geq\frac{1}{2}(1+\tau)-\frac{1}{2^{q}}$
and since $q$ was chosen such that $2^{q}\geq\frac{32}{\epsilon}$,
$\tilde{a}_{z}=\sin^{2}(\frac{a\pi}{2^{l}})>\frac{1}{2}(1+\tau)-\frac{\epsilon}{32}=\tau^{\prime}$.

This gives us $\sin(\frac{a\pi}{2^{l}})>\sqrt{\tau^{\prime}}$ since
$\frac{a\pi}{2^{l}}\in[0,\pi]$. Furthermore, since $\tau_{1}$ is an integer in
$[0,2^{l}-1]$ and
$\tau_{1}=\left\lfloor\frac{2^{l}}{\pi}\sin^{-1}(\sqrt{\tau^{\prime}})\right\rfloor\leq\frac{2^{l}}{\pi}\sin^{-1}(\sqrt{\tau^{\prime}})$,
we get $\sqrt{\tau^{\prime}}\geq\sin(\frac{\tau_{1}\pi}{2^{l}})$. Combining
both the inequalities above, we get
$\sin(\frac{a\pi}{2^{l}})>\sin(\frac{\tau_{1}\pi}{2^{l}})$.

Now, on applying HDl on $R_{3}$ and $R_{4}$, we obtain $\ket{\hat{\tau}_{1}}$
and $\ket{\hat{a}}$ respectively in $R_{3}$ and $R_{4}$ such that
$\hat{a}=|2^{l-1}-a|$ and $\hat{\tau}_{1}=|2^{l-1}-\tau_{1}|$. Using
Proposition 18 on the fact that
$\sin(\frac{a\pi}{2^{l}})>\sin(\frac{\tau_{1}\pi}{2^{l}})$, we get
$\hat{a}<\hat{\tau}_{1}$.

As above, since $\hat{a}<\hat{\tau}_{1}$ corresponding to any
$\ket{a}\in\\{\ket{a_{x,-}},\ket{a_{x,+}}\\}$, after using CMP on $R_{3}$ and
$R_{4}$, we get in $R_{5}$ the state
$\ket{\mathbb{I}\\{a_{x,-}\leq\tau_{1}\\}}=\ket{\mathbb{I}\\{a_{x,+}\leq\tau_{1}\\}}=\ket{1}$.
Again since the state $\ket{\psi_{1,s}}$ exists with probability at least
$1-\frac{8}{\pi^{2}}$ in $\ket{\psi_{1}}$, the output state $\ket{\psi_{2}}$
after stage-2 in this case is such that with probability at least
$1-\frac{8}{\pi^{2}}$ the state $\ket{x}$ is marked, i.e, if $x$ is such that
$|\alpha_{x}|\geq\tau$ then $\ket{\psi_{2}}$ contains
$\ket{x}\ket{\nu_{x}}\ket{\tau_{1}}\ket{a_{x}}\ket{1}$ with probability at
least $1-\frac{8}{\pi^{2}}$.

##### Query Complexity :

In stage-1, from Theorem 4 we get that the number of queries made by
MDistAEAlgo to $O_{D}$ is $O(1/\epsilon)$. CMP and HDq operators does not
require any oracle queries. Hence, the total number of queries made to $O_{D}$
for the construction of AmpFilBOrcl is $O(1/\epsilon)$.

∎

#####  AmpFilBOrcl for complex-valued amplitudes:

The algorithm given for Lemma 16 works if the amplitudes corresponding to the
basis states in $\ket{\Psi}=O_{D}\ket{r}$ are real. In the case of complex
amplitudes, we need a few additions in the construction of AmpFilBOrcl.
Alongside estimating the real part of the amplitudes with $\epsilon$ accuracy,
we also estimate the complex part of the amplitudes with $\epsilon$ accuracy
for all $\ket{x}$ (in superposition) using Algorithm 1. We now use the
estimates of the real and the complex parts to compute the norm of the
amplitudes for all $\ket{x}$. From the discussions in Section 3, it is clear
that the computed estimates of the absolute value of amplitudes are also
$\epsilon$ accurate estimates. We then use this estimate of the norm to
compare against $\ket{\tau_{1}}$ in stage-3.

##  Appendix D Analysis of the algorithm for AmpFil

See 7

Intuitively, Lemma 16 says that for any given $x$, AmpFilBOrcl correctly marks
$x$ with probability at least $1-\delta$ if $|\alpha_{x}|\geq\tau$ and
erroneously marks $x$ with probability at most $\delta$ if
$|\alpha_{x}|<\tau-\epsilon$. Notice that AmpFilBOrcl is a biased oracle with
error $\delta$. Our algorithm for amplitude filtering makes use of that.

###### Proof.

Initialize registers $R_{1}R_{21}R_{22}R_{3}R_{4}R_{5}$ as
$\ket{0^{r}}\ket{0^{l}}\ket{0^{r}}\ket{0^{l}}\ket{0}$ and apply $O_{D}$ on
$R_{1}$. The state of the registers can be given as

$\ket{\psi}=\sum_{x\in[m]}\alpha_{x}\ket{x,\xi_{x}}\ket{0^{l}}\ket{0^{r}}\ket{0^{l}}\ket{0}$

Next, apply AmpFilBOrcl on the registers. Finally, use the amplitude
amplification algorithm for biased oracle given as Algorithm 2 with $\ket{1}$
in $R_{5}$ as the good state. Now, if there is a good $x$ in $\ket{\psi}$,
then we know that $|\alpha_{x}|\geq\tau$ or $|\alpha_{x}|^{2}\geq\tau^{2}$.
Using Theorem 6 with $p=1-\frac{8}{\pi^{2}}$ and Lemma 16, we obtain the
required proof. ∎

##  Appendix E Bounded oracle for probability filtering

###  E.1 Construction of ProbFilBOrcl to mark high probability states

Algorithm 6 Constructing biased-oracle ProbFilBOrcl for probability filtering

1:Oracle $O_{D}$ (with parameters $m$, $a$), threshold $\tau$, and accuracy
$\epsilon$.

2:Input register $R_{1}$ set to some basis state $\ket{x}$ and output register
$R_{5}$ set to $\ket{0}$.

3:Set $r=\log(m)+a$, $\tau^{\prime}=\frac{1}{2}(1+\tau-\frac{\epsilon}{8})$,
$q=\lceil\log(\frac{1}{\epsilon})\rceil+5$ and $l=q+3$.

4:Set
$\tau_{1}=\left\lfloor{\frac{2^{l}}{\pi}\sin^{-1}(\sqrt{\tau^{\prime}})}\right\rfloor$

5:Initialize ancillæ registers $R_{2}R_{3}R_{4}$ of lengths $r,l$ and 1,
respectively, and set $R_{3}=\ket{\tau_{1}}$.

6:Stage 1: Apply EQAmpEst (sans measurement) with $R_{2}$ as the input
register, $R_{4}$ as the output register and $O_{D}$ is used as the state
preparation oracle. $R_{1}$ is used in $EQ$ to determine the “good state”.
EQAmpEst is called with error at most $1-\frac{8}{\pi^{2}}$ and additive
accuracy $\frac{1}{2^{q}}$.

7:Stage 2: Set $R_{5}$ to 1 if the estimate of the probability, calculated
using $R_{4}$, meets $\tau$.

8: Use HDl on $R_{3}$ and $R_{4}$ individually.

9: Use ${\tt CMP}$ on $R_{3}=\ket{\tau_{1}}$ and $R_{4}$ as input registers
and $R_{5}$ as output register.

10: Use HD${}^{\dagger}_{l}$ on $R_{3}$ and $R_{4}$ individually.

The algorithm is described in Algorithm 6. It uses the following two
subroutines.

HDq:

When the target qubit is $\ket{0^{q}}$, and with a $q-$bit string $y$ in the
control register, HD computes the absolute difference of $y_{int}$ from
$2^{q-1}$ and outputs it as a string where $y_{int}$ is the integer
corresponding to the string $y$. It can be represented as ${\tt
HD}_{q}\ket{y}\ket{b}=\ket{b\oplus\tilde{y}}\ket{y}$ where
$y,b\in\\{0,1\\}^{q}$ and $\tilde{y}$ is the bit string corresponding to the
integer $\absolutevalue{2^{q-1}-y_{int}}$. Even though the operator HD
requires two registers, the second register will always be in the state
$\ket{0^{q}}$ and shall be reused by uncomputing (using $HD^{\dagger}$) after
the CMP gate. For all practical purposes, this operator can be treated as the
mapping $\ket{y}\mapsto\ket{\tilde{y}}$.

CMP:

The ${\tt CMP}$ operator is defined as ${\tt
CMP}\ket{y_{1}}\ket{y_{2}}\ket{b}=\ket{y_{1}}\ket{y_{2}}\ket{b\oplus(y_{2}\leq
y_{1})}$ where $y_{1},y_{2}\in\\{0,1\\}^{n}$ and $b\in\\{0,1\\}$. It simply
checks if the integer corresponding to the basis state in the first register
is at most that in the second register.

In Stage 1 of the algorithm, EQAmpEst estimates the probability of $\ket{x}$
in $O_{D}\ket{0^{r}}$ in $R4$, and in Stage 2, this estimate is compared with
$\tau$ to set or unset $R_{5}$. This makes ProbFilBOrcl a biased oracle with
error $1-\tfrac{8}{\pi^{2}}$. Further, observe that EQAmpEst makes
$O(1/\epsilon)$ calls to the state preparation oracle, in this case, $O_{D}$,
and no one else adds to this. The overall behaviour is summarised below.

######  Lemma 20.

ProbFilBOrcl makes $O(1/\epsilon)$ calls to $O_{D}$. Upon measuring its output
on $\ket{x}\ket{0^{2l+r+1}}\ket{0}$, we observe the following with probability
at least $\tfrac{8}{\pi^{2}}$.

$\textsc{ProbFilBOrcl}\ket{x}\ket{0^{2l+r+1}}\ket{0}\Longrightarrow\begin{cases}\ket{x}\ket{\phi_{x}}\ket{0}&\text{,
if }p_{x}<\tau-\epsilon,\\\ \ket{x}\ket{\phi_{x}}\ket{1}&\text{, if
}p_{x}\geq\tau.\\\ \end{cases}$

###  E.2 Analysis of ProbFilBOrcl

See 20

Observe that the algorithm ProbFilBOrcl differs from that of AmpFilBOrcl only
at Stage 1. Stage 2 is identical.

###### Proof.

We analyse the algorithm on the input state on registers
$R_{1}R_{21}R_{22}R_{3}R_{4}R_{5}$ as
$\ket{x}\ket{0^{r}}\ket{0^{l}}\ket{0^{l}}\ket{0}$ where $t=2l+r+1$. We set
$R_{3}=\ket{\tau_{1}}$. On applying $\textsc{EQAmpEst}_{O_{D}}$ on
$R_{1}R_{2}R_{4}$ with $R_{2}$ as the input register and $R_{4}$ as the output
register and $R_{1}$ for marking the “good” state whose probability we desire
to estimate (using, of course, the $EQ$ oracle), the input state transforms to

$\displaystyle\ket{\psi_{1}}$
$\displaystyle=\ket{x}\ket{\Psi}\Big{(}\beta_{x,s}\ket{a_{x}}+\beta_{x,\overline{s}}\ket{E_{x}}\Big{)}\ket{\tau_{1}}\ket{0}$
$\displaystyle=\beta_{x,s}\ket{x}\ket{\Psi}\ket{a_{x}}\ket{\tau_{1}}\ket{0}+\beta_{x,\overline{s}}\ket{x}\ket{\Psi}\ket{E_{x}}\ket{\tau_{1}}\ket{0}$
$\displaystyle=\beta_{x,s}\ket{\psi_{1,s}}+\beta_{x,\overline{s}}\ket{\psi_{1,\overline{s}}}$

where $\ket{a_{x}}$ is a normalized state of the form
$\ket{a_{x}}=\gamma_{+}\ket{a_{x,+}}+\gamma_{-}\ket{a_{x,-}}$ that on
measurement outputs $a\in\\{a_{x,+},a_{x,+}\\}$ which is an $l$-bit string
that behaves as
$\displaystyle\left|\sin^{2}\left(\frac{a\pi}{2^{l}}\right)-|\alpha_{x}|^{2}\right|\leq\tfrac{1}{2^{q}}$,
$|\beta_{x,s}|^{2}\geq\frac{8}{\pi^{2}}$ and $|\beta_{x,s}|^{2}\leq
1-\frac{8}{\pi^{2}}$.

We denote the set $\\{a_{x,+},a_{x,-}\\}$ by $S_{a_{x}}$. Essentially, for any
$x$, EQAmpEst stores the correct estimate of the probability of $x$ in
$\ket{\Psi}$ into $R_{4}$ with probability at least $\frac{8}{\pi^{2}}$.

The correctness of stage-2 is exactly the same as that in the proof for
Theorem 16.

##### Query Complexity :

All calls to $O_{D}$ are made by EQAmpEst and the latter’s query complexity is
$O(1/\epsilon)$. ∎

##  Appendix F Algorithm for MDistAmpEst = $\mathbf{U}\cdot\mathbf{V}$

First, we discuss how to implement the conditional $A^{O}_{y}$ operator
$\mathbf{V}=\sum_{y}\outerproduct{y}{y}\otimes A^{O}_{y}$, that acts on two
registers, and operates $A^{O}_{y}$ on the second register when the first
register is in the basis state $y$ — without loss of generality, we can assume
that $\\{y\\}$ forms the standard basis. Let $m$ denote the precision of
amplitude estimation as stated above, i.e., $\log 1/\epsilon$.

Observe that for each $y$, $A^{O}_{y}$ can be expressed as
$A^{O}_{y}=U_{(k,y)}OU_{(k-1,y)}\cdots U_{(1,y)}OU_{(0,y)}$ with suitable
$U_{(i,y)}$ unitaries. Controlling a sequence of gates is equivalent to a
sequence of controlled-gates. So, we can express the conditional $A^{O}$
operator in the following manner.

$\displaystyle\sum_{y}\outerproduct{y}{y}\otimes
A^{O}_{y}=\sum_{y}\outerproduct{y}{y}\otimes U_{(k,y)}OU_{(k-1,y)}\cdots
U_{(1,y)}OU_{(0,y)}$ $\displaystyle=$
$\displaystyle\big{(}\sum_{y}\outerproduct{y}{y}\otimes
U_{(k,y)}\big{)}\big{(}\sum_{y}\outerproduct{y}{y}\otimes
O\big{)}\big{(}\sum_{y}\outerproduct{y}{y}\otimes
U_{(k-1,y)}\big{)}\ldots\big{(}\sum_{y}\outerproduct{y}{y}\otimes
O\big{)}\big{(}\sum_{y}\outerproduct{y}{y}\otimes U_{(0,y)}\big{)}$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\big{(}\sum_{y}\outerproduct{y}{y}\otimes
U_{(k,y)}\big{)}\big{(}\mathbb{I}\otimes
O\big{)}\big{(}\sum_{y}\outerproduct{y}{y}\otimes
U_{(k-1,y)}\big{)}\ldots\big{(}\mathbb{I}\otimes
O\big{)}\big{(}\sum_{y}\outerproduct{y}{y}\otimes U_{(0,y)}\big{)}$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
U^{\prime}_{(k,y)}\circ\big{(}\mathbb{I}\otimes O)\circ
U^{\prime}_{(k-1,y)}\circ\big{(}\mathbb{I}\otimes O\big{)}\circ
U^{\prime}_{(k-2,y)}\ldots U^{\prime}_{(1,y)}\circ\big{(}\mathbb{I}\otimes
O\big{)}\circ U^{\prime}_{(0,y)}$

in which the operator $U^{\prime}_{t,y}$ denotes
$\big{(}\sum_{y}\outerproduct{y}{y}\otimes U_{(t,y)}\big{)}$ that does not
involve any call to $O$. Therefore, the query complexity of one call to $V$ is
$k$ — the query complexity of any $A^{O}$. We want to note here that in the
case where each $A^{O}_{y}$ makes different number of calls to $O$, $k$ can be
taken to be the maximum of the individual query complexities since each
$A^{O}_{y}$ can be suitably padded to include more calls to $O$. We also point
out that the reduction in query complexity comes at the expense of additional
non-$O$ gates (e.g., gates required to implement $U^{\prime}_{(k,y)}$), the
number of which can even be exponential in $n$.

The idea above can be extended to the implementation of
$\mathbf{U}=\sum_{y}\outerproduct{y}{y}\otimes AmpEst_{y}$ as well. The
amplitude estimation operator due to Brassard et al. [7], excluding the
initial state preparation, can be expressed as
$AmpEst=(F_{m}^{-1}\otimes\mathbb{I})\cdot\Lambda_{m}(G)\cdot(F_{m}\otimes\mathbb{I})$
where $F_{m}$ is the Fourier transform on $m$ qubits, $\Lambda_{m}(G)$ is the
conditional operator defined as $\sum_{x}\outerproduct{x}{x}\otimes G^{x}$,
$G=-AS_{0}A^{\dagger}S_{\chi}$ is the Grover iteator, $G^{x}$ implies that the
$G$ operator is applied $x$ times in succession, and $S$ are reflection
operators which do not involve $O$. In a similar manner, $AmpEst_{y}$ can be
expressed as
$AmpEst_{y}=(F_{m}^{-1}\otimes\mathbb{I})\cdot\Lambda_{m}(G_{y})\cdot(F_{m}\otimes\mathbb{I})$
where $G_{y}=-A_{y}S_{0}A_{y}^{\dagger}M_{\gamma^{y}}$.

Let’s focus on the controlled version of $AmpEst_{y}$. Controlling a sequence
of gates is equivalent to a sequence of controlled-gates. That is,

$\displaystyle\mathbf{U}$ $\displaystyle=\sum_{y}\outerproduct{y}{y}\otimes
AmpEst_{y}$
$\displaystyle=\sum_{y}\outerproduct{y}{y}\otimes\Big{(}(F_{m}^{-1}\otimes\mathbb{I})\circ\Lambda_{m}(G_{y})\circ(F_{m}\otimes\mathbb{I})\Big{)}$
$\displaystyle=\Big{(}\sum_{y}\outerproduct{y}{y}\otimes(F_{m}^{-1}\otimes\mathbb{I})\Big{)}\circ\Big{(}\sum_{y}\outerproduct{y}{y}\otimes\Lambda_{m}(G_{y})\Big{)}\circ\Big{(}\sum_{y}\outerproduct{y}{y}\otimes(F_{m}\otimes\mathbb{I})\Big{)}$
$\displaystyle=\Big{(}\sum_{y}\outerproduct{y}{y}\otimes(F_{m}^{-1}\otimes\mathbb{I})\Big{)}\circ\Big{(}\sum_{y}\outerproduct{y}{y}\otimes\sum_{x}\outerproduct{x}{x}\otimes
G_{y}^{x}\Big{)}\circ\Big{(}\sum_{y}\outerproduct{y}{y}\otimes(F_{m}\otimes\mathbb{I})\Big{)}.$

Both the first and the third operator from the last expression do not involve
any calls to $O$ and can be ignored for the purpose for query complexity.
Using similar ideas as above, we show how to implement the middle operator
efficiently in the number of queries, i.e, independent of the number of state
preparation oracles.

######  Lemma 21.

The operator
$W=\sum_{y}\outerproduct{y}{y}\otimes\sum_{x}\outerproduct{x}{x}\otimes
G_{y}^{x}$ can be implemented using $O(k2^{m})$ calls to $O$ where $m$ is the
size of the last register,
$G_{y}=-A^{O}_{y}S_{0}A_{y}^{O\dagger}M_{\gamma^{y}}$, and $k$ denotes the
query complexity of $A^{O}_{y}$.

To prove Lemma 21, we require the following technical result on conditional
operators. Here $\mathbf{C}^{(i,p)}(U)$ denotes the operator
$\mathbb{I}^{i-1}\otimes\outerproduct{p}{p}\otimes\mathbb{I}^{m-i}\otimes U$.
The proof of the below result is straightforward and algebraic in nature, and
is available in the Appendix G.

######  Lemma 22.

For any two unitaries $A$ and $B$, we have
$\sum_{y}\outerproduct{y}{y}\otimes\big{[}\mathbf{C}^{(i,1)}(A\circ
B)+\mathbf{C}^{(i,0)}(\mathbb{I})\big{]}=\Big{\\{}\sum_{y}\outerproduct{y}{y}\otimes\big{[}\mathbf{C}^{(i,1)}(A)+\mathbf{C}^{(i,0)}(\mathbb{I})\big{]}\Big{\\}}\circ\Big{\\{}\sum_{y}\outerproduct{y}{y}\otimes\big{[}\mathbf{C}^{(i,1)}(B)+\mathbf{C}^{(i,0)}(\mathbb{I})\big{]}\Big{\\}}$

###### Proof of Lemma 21.

We first simplify an important component of $W$ [8].

$\displaystyle\sum_{x}\outerproduct{x}{x}\otimes
G_{y}^{x}=\prod_{i=1}^{m}\bigg{(}\Big{[}\mathbb{I}^{i-1}\otimes\outerproduct{1}{1}\otimes\mathbb{I}^{m-i}\otimes
G_{y}^{2^{i}}\Big{]}+\Big{[}\mathbb{I}^{i-1}\otimes\outerproduct{0}{0}\otimes\mathbb{I}^{m-i}\otimes\mathbb{I}\Big{]}\bigg{)}$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{m}\mathbb{I}^{i-1}\otimes\left(\outerproduct{0}{0}\otimes\mathbb{I}^{m-i}\otimes\mathbb{I}+\outerproduct{1}{1}\otimes\mathbb{I}^{m-i}\otimes
G_{y}^{2^{i}}\right)$

that is essentially a sequence of conditional-$G_{y}^{2^{i}}$ gates,
conditioned on the $i$-th qubit of the first register of this operator.

This allows us to rewrite $W$ in the following manner.

$\displaystyle W=$
$\displaystyle\sum_{y}\outerproduct{y}{y}\otimes\sum_{x}\outerproduct{x}{x}\otimes
G_{y}^{x}$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{m}\bigg{[}\sum_{y}\outerproduct{y}{y}\otimes\bigg{(}\Big{[}\mathbb{I}^{i-1}\otimes\outerproduct{1}{1}\otimes\mathbb{I}^{m-i}\otimes
G_{y}^{2^{i}}\Big{]}+\Big{[}\mathbb{I}^{i-1}\otimes\outerproduct{0}{0}\otimes\mathbb{I}^{m-i}\otimes\mathbb{I}\Big{]}\bigg{)}\bigg{]}$
(using the notation of $\mathbf{C}^{(i,p)}(U)$) $\displaystyle=$
$\displaystyle\prod_{i=1}^{m}\bigg{[}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\Big{(}G_{y}^{2^{i}}\Big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{]}=\prod_{i=1}^{m}W^{\prime}_{i}\quad\mbox{(say)}$
(1)

Now see that for any $i$, $W^{\prime}_{i}=$

$\displaystyle\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\Big{(}(-A_{y}S_{0}A_{y}^{\dagger}M_{\gamma^{y}})^{2^{i}}\Big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}$
$\displaystyle=$
$\displaystyle\Bigg{[}\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}-A_{y}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{\\}}\circ\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}S_{0}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{\\}}\leavevmode\nobreak\
\circ$ $\displaystyle\hskip
28.45274pt\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}A_{y}^{\dagger}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{\\}}\circ\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}M_{\gamma^{y}}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{\\}}\Bigg{]}^{2^{i}}$
$\displaystyle=$
$\displaystyle\Bigg{[}\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}-A_{y}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{\\}}\circ\bigg{\\{}\mathbb{I}^{n}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}S_{0}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{\\}}\leavevmode\nobreak\
\circ$ $\displaystyle\hskip
28.45274pt\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}A_{y}^{\dagger}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{\\}}\circ\bigg{\\{}\mathbb{I}^{n}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}M_{\gamma^{y}}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{\\}}\Bigg{]}^{2^{i}}$
$\displaystyle=$
$\displaystyle\Bigg{[}\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}-A_{y}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{\\}}\circ
D_{i}\leavevmode\nobreak\
\circ\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}A_{y}^{\dagger}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\bigg{\\}}\circ
E_{i}\Bigg{]}^{2^{i}}$

in which the $D_{i}$ and $E_{i}$ operators can be implemented without any
calls to $O$.

Next, since we have $A_{y}=U_{(k,y)}OU_{(k-1,y)}\cdots U_{(1,y)}OU_{(0,y)}$,
we can write

$\displaystyle\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}-A_{y}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}$
(2) $\displaystyle=$
$\displaystyle-\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}U_{(k,y)}OU_{(k-1,y)}\cdots
U_{(1,y)}OU_{(0,y)}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}$
$\displaystyle=$
$\displaystyle-\prod_{j=k}^{1}\Bigg{[}\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\bigg{(}\mathbf{C}^{(i,1)}\big{(}U_{(j,y)}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\bigg{)}\bigg{\\}}\circ\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\bigg{(}\mathbf{C}^{(i,1)}(O)+\mathbf{C}^{(i,0)}(\mathbb{I})\bigg{)}\bigg{\\}}\Bigg{]}\circ$
$\displaystyle\hskip
142.26378pt\sum_{y}\outerproduct{y}{y}\otimes\bigg{(}\mathbf{C}^{(i,1)}\big{(}U_{(0,y)}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\bigg{)}$
$\displaystyle=$
$\displaystyle-\prod_{j=k}^{1}\Bigg{[}\bigg{\\{}\sum_{y}\outerproduct{y}{y}\otimes\bigg{(}\mathbf{C}^{(i,1)}\big{(}U_{(j,y)}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\bigg{)}\bigg{\\}}\circ\bigg{\\{}\mathbb{I}^{n}\otimes\bigg{(}\mathbf{C}^{(i,1)}(O)+\mathbf{C}^{(i,0)}(\mathbb{I})\bigg{)}\bigg{\\}}\Bigg{]}\circ$
$\displaystyle\hskip
142.26378pt\sum_{y}\outerproduct{y}{y}\otimes\bigg{(}\mathbf{C}^{(i,1)}\big{(}U_{(0,y)}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\bigg{)}$

Each of the
$\Big{[}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}U_{(j,y)}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\Big{]}$
terms can be implemented as

$\prod_{y=0}^{N-1}\bigg{\\{}\Big{[}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}U_{(j,y)}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\Big{]}+\sum_{x\neq
y}\outerproduct{x}{x}\otimes\mathbb{I}^{m}\otimes\mathbb{I}\bigg{\\}}$

which can be identified as a sequence of $N$ controlled gates that do not
involve $O$.

The operator
$\Big{[}\mathbb{I}^{n}\otimes\Big{(}\mathbf{C}^{(i,1)}(O)+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\Big{]}$
is applied independent of the state in the first register. So, it can be
implemented as a controlled-$O$ operation controlled by the $i$th qubit of the
second register and that uses only 1 oracle query.

Therefore, we can can see that the number of oracle queries required to
implement
$\Big{[}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}-A_{y}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\Big{]}$
(operator in Equation 2) is exactly $k$. The query complexity of the operator
$\Big{[}\sum_{y}\outerproduct{y}{y}\otimes\Big{(}\mathbf{C}^{(i,1)}\big{(}A_{y}^{\dagger}\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\Big{)}\Big{]}$
is also $k$ using the same analysis. From this we get the query complexity of
$W^{\prime}_{i}$ as $2^{i}\cdot 2k$.

Now, using Equation 1, the total number of oracle queries required for $W$ is
$2^{m+2}k$. Since we have set $m=O(\log(1/\epsilon))$ we get the query
complexity of MDistAEAlgo as $O(k/\epsilon)$. ∎

##  Appendix G Useful Lemme to prove Lemma 22

######  Lemma 23.

Let $\\{A_{y}\\}$ and $\\{B_{y}\\}$ be two sets of indexed unitaries. Then,

$\sum_{y}\outerproduct{y}{y}\otimes(A_{y}\circ
B_{y})=\Big{(}\sum_{y}\outerproduct{y}{y}\otimes(A_{y})\Big{)}\circ\Big{(}\sum_{z}\outerproduct{z}{z}\otimes(B_{z})\Big{)}.$

###### Proof.

$\displaystyle\Big{(}\sum_{y}\outerproduct{y}{y}\otimes
A_{y}\Big{)}\circ\Big{(}\sum_{z}\outerproduct{z}{z}\otimes B_{z}\Big{)}$
$\displaystyle=\sum_{y,z(}\outerproduct{y}{y}\circ\outerproduct{z}{z})\otimes(A_{y}\circ
B_{z})$ $\displaystyle=\sum_{y}\outerproduct{y}{y}\otimes(A_{y}\circ B_{y})$

∎

######  Lemma 24.

For any two unitaries $A$ and $B$, we have

$\mathbf{C}^{(i,p)}(A)\circ\mathbf{C}^{(i,q)}(B)=\delta_{p,q}\cdot\mathbf{C}^{(i,p)}(A\circ
B)$

where $\delta_{p,q}=1$ if $p=q$ and $0$ otherwise.

###### Proof.

$\displaystyle\mathbf{C}^{(i,p)}(A)\circ\mathbf{C}^{(i,q)}(B)$
$\displaystyle=\big{(}\mathbb{I}^{i-1}\otimes\outerproduct{p}{p}\otimes\mathbb{I}^{m-i}\otimes
A\big{)}\circ\big{(}\mathbb{I}^{i-1}\otimes\outerproduct{q}{q}\otimes\mathbb{I}^{m-i}\otimes
B\big{)}$
$\displaystyle=\mathbb{I}^{i-1}\otimes(\outerproduct{p}{p}\circ\outerproduct{q}{q})\otimes\mathbb{I}^{m-i}\otimes(A\circ
B)$
$\displaystyle=\mathbb{I}^{i-1}\otimes\delta_{p,q}(\outerproduct{p}{p})\otimes\mathbb{I}^{m-i}\otimes(A\circ
B)$
$\displaystyle=\delta_{p,q}\big{(}\mathbb{I}^{i-1}\otimes\outerproduct{p}{p}\otimes\mathbb{I}^{m-i}\otimes(A\circ
B)\big{)}$ $\displaystyle=\delta_{p,q}\cdot\mathbf{C}^{(i,p)}(A\circ B)$

∎

See 22

###### Proof.

$\displaystyle\sum_{y}\outerproduct{y}{y}\otimes\big{[}\mathbf{C}^{(i,1)}(A\circ
B)+\mathbf{C}^{(i,0)}(\mathbb{I})\big{]}$
$\displaystyle=\sum_{y}\outerproduct{y}{y}\otimes\big{[}\big{(}\mathbf{C}^{(i,1)}(A)\circ\mathbf{C}^{(i,1)}(B)\big{)}+\mathbf{C}^{(i,0)}(\mathbb{I})\big{]}\leavevmode\nobreak\
\text{(Using Lemma\leavevmode\nobreak\ \ref{lemma:cproduct_1})}$
$\displaystyle=\sum_{y}\outerproduct{y}{y}\otimes\big{(}\big{[}\mathbf{C}^{(i,1)}(A)+\mathbf{C}^{(i,0)}(\mathbb{I})\big{]}\circ\big{[}\mathbf{C}^{(i,1)}(B)+\mathbf{C}^{(i,0)}(\mathbb{I})\big{]}\big{)}\leavevmode\nobreak\
\text{(Using Lemma\leavevmode\nobreak\ \ref{lemma:cproduct_1})}$
$\displaystyle=\Big{\\{}\sum_{y}\outerproduct{y}{y}\otimes\big{[}\mathbf{C}^{(i,1)}(A)+\mathbf{C}^{(i,0)}(\mathbb{I})\big{]}\Big{\\}}\circ\Big{\\{}\sum_{y}\outerproduct{y}{y}\otimes\big{[}\mathbf{C}^{(i,1)}(B)+\mathbf{C}^{(i,0)}(\mathbb{I})\big{]}\Big{\\}}\leavevmode\nobreak\
\text{(Using Lemma\leavevmode\nobreak\ \ref{lemma:product_distributive})}$

∎

##  Appendix H Proof of Theorem 6

See 6

Set $k=O(\frac{2p}{(p-1/2)^{2}}\log(1/\delta^{\prime}))$ for a
$\delta^{\prime}=\lambda^{4}\delta^{2}$ and construct
$\hat{A}_{A,\hat{\mathcal{O}}_{p},k}$. This $\hat{A}$ (dropping the
subscripts) behaves as

$\hat{A}\ket{0^{n}}\ket{0^{k}}\ket{0}=\sum_{x}\alpha_{x}\ket{x}\big{(}\eta_{x,0}\ket{\phi_{x,0}}\ket{0}+\eta_{x,1}\ket{\phi_{x,1}}\ket{1}\big{)}=\ket{\Psi}$

where $|\eta_{x,f(x)}|^{2}\geq 1-\delta^{\prime}$ for any $x$; here $f(x)$
indicates the “goodness” of $x$.

Now, two cases can happen.

Case (i):  Let $f(x)=0$ for all $x$. We analyse the situation that the
algorithm does not output “No Solution”, in other words, $R_{maj}$ was
observed as $\ket{1}$.

Now, the output state after $\hat{A}$ would be such that
$|\eta_{x,1}|^{2}\leq\delta^{\prime}$ for all $x$. So, the probability of
measuring $\ket{1}$ as output is
$\sum_{x}|\alpha_{x}\eta_{x,1}|^{2}\leq\delta^{\prime}\sum_{x}|\alpha_{x}|^{2}=\delta^{\prime}$.
Can such a state, with final qubit as $\ket{1}$, appear with overwhelming
probability after $O(1/\sqrt{\lambda})$ iterations of amplitude amplification?
We argue not by lower bounding the number of iterations needed to boost the
probability of such a state to almost certainty.

Let $\theta$ be the angle made by the superposition of those states of
$\ket{\Psi}$ whose last qubit is in $\ket{1}$. Then, we have
$\sin^{2}(\theta)\leq\delta^{\prime}=\lambda^{4}\delta^{2}$.

For any state $\ket{\chi}$ if the probability of obtaining a good state is
$\sin^{2}(\theta)=\delta_{1}$ and if we would like to boost the probability to
$\delta_{2}$, then it easy to show that the number of iterations needed in the
amplitude amplification algorithm is
$j=\Big{\lceil}\frac{1}{2}\big{(}\sin^{-1}(\sqrt{\delta_{2}})/\sin^{-1}(\sqrt{\delta_{1}})\big{)}-\frac{1}{2}\Big{\rceil}>\frac{1}{4}\big{(}\sin^{-1}(\sqrt{\delta_{2}})/\sin^{-1}(\sqrt{\delta_{1}})\big{)}$.
Since $\theta<\sin^{-1}(\theta)$, we have

$j>\frac{1}{4}\big{(}\sin^{-1}(\sqrt{\delta_{2}})/\sin^{-1}(\sqrt{\delta_{1}})\big{)}>\frac{1}{4}\big{(}\sqrt{\delta_{2}}/\sin^{-1}(\sqrt{\delta_{1}})\big{)}.$

In our case, we have $\delta_{1}=\lambda^{4}\delta^{2}$ and
$\delta_{2}=\delta$. So, the number of iterations required is

$j>\frac{1}{4}\Big{(}\sqrt{\delta}/\sin^{-1}(\sqrt{\lambda^{4}\delta^{2}})\Big{)}=\frac{1}{4}\Big{(}\sqrt{\delta}/\sin^{-1}(\lambda^{2}\delta)\Big{)}.$

For any $\beta\leq 0.75$, it is easy to see that
$\sin^{-1}(\beta)<\sqrt{\beta}$. Since, we set $\delta<0.5$ and since
$\lambda\leq 1$, we have $\lambda^{2}\delta\leq 0.5<0.75$. Hence we have,

$j>\frac{1}{4}\Big{(}\sqrt{\delta}/\sin^{-1}(\lambda^{2}\delta)\Big{)}>\frac{1}{4}\Big{(}\sqrt{\delta}/\sqrt{\lambda^{2}\delta}\Big{)}=\frac{1}{4\lambda}.$

This says that the number of amplification iterations required for improving
the probability of obtaining $\ket{1}$ from $\lambda^{2}\delta^{2}$ to
$\delta$ is at least $1/4\lambda$. But since the maximum number of iterations
performed in the amplification routine is $O(\frac{1}{\sqrt{\lambda}})$, the
probability of obtaining $\ket{1}$ on measuring the last qubit of the state
after amplitude amplification is at most $\delta$ (most likely quite less).

Case (ii):  Let $f(x)=1$ for some $x$. In this case, for all $x$ such that
$f(x)=1$, we will have $|\eta_{x,1}|^{2}\geq 1-\delta^{\prime}$. Then the
probability of measuring the last qubit as $\ket{1}$ is at least
$\sum_{x:f(x)=1}|\alpha_{x}\eta_{x,1}|^{2}\geq\lambda(1-\delta^{\prime})>\lambda/2$
(since $\delta<0.5$). Now, using the fixed point amplitude amplification
subroutine, in $O(\frac{1}{\sqrt{\lambda}})$ iterations, we obtain a final
state post amplification such that with probability $1-\delta$ we obtain
$\ket{1}$ on measuring the $R_{maj}$ register.

Let the post-measurement state, after observing $R_{maj}$ in the state
$\ket{1}$, be denoted $\ket{\psi_{m}}$. We want to clarify that it is not
immediately obvious that we shall observe a good state on measuring the first
register of $\ket{\psi_{m}}$ since the biased oracle also marks the bad states
with some probability. This requires an a additional analysis.

######  Claim 25.

Let $\ket{\psi_{m}}$ be the post-measurement state obtained on measuring the
last qubit as $\ket{1}$. If the set of good state $\mathscr{G}=\\{x:f(x)=1\\}$
is non-empty, then the probability of obtaining some $x\in\mathscr{G}$ on
measuring the first register of $\ket{\psi_{m}}$ is at least $3/4$.

###### Proof.

The state just before amplification can be given as

$\ket{\Psi}=\sum_{x}\alpha_{x}\ket{x}\big{(}\eta_{x,0}\ket{\phi_{x,0}}\ket{0}+\eta_{x,1}\ket{\phi_{x,1}}\ket{1}\big{)}$

where $|\eta_{x,f(x)}|^{2}\geq 1-\delta^{\prime}$ for any $x$. The probability
of obtaining some good state on the condition that the $R_{maj}$ qubit is
$\ket{1}$ is

$\displaystyle Pr\Big{[}\ket{g}_{R_{1}}\Big{|}\ket{1}_{R_{maj}}\Big{]}$
$\displaystyle=\frac{Pr\Big{[}\ket{g}_{R_{1}}\ket{1}_{R_{maj}}\Big{]}}{Pr\Big{[}\ket{1}_{R_{maj}}\Big{]}}$
$\displaystyle=\frac{\sum_{x\in\mathscr{G}}|\alpha_{x}\eta_{x,1}|^{2}}{\sum_{x\in\mathscr{G}}|\alpha_{x}\eta_{x,1}|^{2}+\sum_{x\notin\mathscr{G}}|\alpha_{x}\eta_{x,1}|^{2}}$
$\displaystyle=\frac{P_{g}}{P_{g}+P_{b}}\leavevmode\nobreak\ \text{ (say) }$

where by $Pr\Big{[}\ket{g}_{R_{1}}\Big{]}$ we denote the probability of
obtaining some good state in $R_{1}$. We know that

$P_{b}=\sum_{x\notin\mathscr{G}}|\alpha_{x}\eta_{x,1}|^{2}=\sum_{x\notin\mathscr{G}}|\alpha_{x}|^{2}|\eta_{x,1}|^{2}\leq\delta^{\prime}\sum_{x\notin\mathscr{G}}|\alpha_{x}|^{2}\leq\delta^{\prime}.$

So, we have

$Pr\Big{[}\ket{g}_{R_{1}}\Big{|}\ket{1}_{R_{maj}}\Big{]}=\frac{P_{g}}{P_{g}+P_{b}}\geq\frac{P_{g}}{P_{g}+\delta^{\prime}}=\frac{1}{1+(\delta^{\prime}/P_{g})}.$

Now,

$\displaystyle\frac{\delta^{\prime}}{P_{g}}$
$\displaystyle=\frac{\delta^{\prime}}{\sum_{x\in\mathscr{G}}|\alpha_{x}|^{2}|\eta_{x,1}|^{2}}$
$\displaystyle\leq\frac{\delta^{\prime}}{(1-\delta^{\prime})\sum_{x\in\mathscr{G}}|\alpha_{x}|^{2}}\leavevmode\nobreak\
\leavevmode\nobreak\ \big{(}\text{ Since }|\eta_{x,1}|^{2}\geq
1-\delta^{\prime}\leavevmode\nobreak\ \text{ for }x\in\mathscr{G}\big{)}$
$\displaystyle\leq\frac{\delta^{\prime}}{(1-\delta^{\prime})\lambda}\leavevmode\nobreak\
\leavevmode\nobreak\ \big{(}\text{ Since
}|\alpha_{x}|^{2}\geq\lambda\leavevmode\nobreak\ \text{ for
}x\in\mathscr{G}\big{)}$
$\displaystyle=\frac{\lambda^{4}\delta^{2}}{(1-\lambda^{4}\delta^{2})\lambda}=\frac{\lambda^{3}\delta^{2}}{1-\lambda^{4}\delta^{2}}\leq\frac{\delta^{2}}{1-\delta^{2}}$
$\displaystyle\leq\frac{1/4}{1-(1/4)}=1/3\leavevmode\nobreak\
\leavevmode\nobreak\ \big{(}\text{ Since }\delta\leq 1/2\big{)}.$

Using this, we get

$Pr\Big{[}\ket{g}_{R_{1}}\Big{|}\ket{1}_{R_{maj}}\Big{]}\geq\frac{1}{1+(\delta^{\prime}/P_{g})}\geq\frac{1}{1+(1/3)}=\frac{3}{4}.$

This gives us that if $R_{maj}$ was measured as $\ket{1}$ then on measuring
$R_{1}$, with probability at least 3/4, we obtain $\ket{x}$ as measurement
outcome for which $f(x)=1$. ∎

##  Appendix I Lower bound for Non-linearity Estimation

Recall that the non-linearity of a Boolean function
$f:\\{0,1\\}^{n}\xrightarrow{}\\{0,1\\}$ is defined as

$\eta(f)=\frac{1}{2}-\frac{1}{2}\hat{f}_{max}$

where $\hat{f}_{max}=\max_{x}|\hat{f(x)}|$ and $\hat{f}(x)$ is the Walsh
coefficient of $f$ at the point $x$. We define a decision problem, namely the
$\hat{f}_{max}$ decision problem, as follows: given a Boolean function
$f:\\{0,1\\}^{n}\xrightarrow{}\\{0,1\\}$, a threshold $\tau$ and a parameter
$\lambda$, decide if $\hat{f}_{max}\geq\tau$ or if
$\hat{f}_{max}<\tau-\lambda$ given the promise that one of the two cases is
true. It is quite straight forward that the $\hat{f}_{max}$ problem can be
directly reduced to the problem of non-linearity estimation. So, to show a
lower bound for the non-linearity estimation problem, we show a reduction from
the CountDecision problem to the $\hat{f}_{max}$ decision problem. First
consider the following lemma which will help prove the required reduction.

######  Lemma 26.

The query complexity of any quantum algorithm that solves CountDecision
($N/4,N/4-\Delta$) is $\Omega(N/\Delta)$ for any $0<\Delta\leq N/5$.

###### Proof.

Using Theorem 9, we obtain that the query complexity is

$\displaystyle Q_{\textsc{CountDecision}}$
$\displaystyle=\Omega\Bigg{(}\sqrt{\frac{N}{\Delta}}+\frac{\sqrt{\bigg{(}\frac{N}{4}-\Delta\bigg{)}\bigg{(}N-\bigg{(}\frac{N}{4}-\Delta\bigg{)}\bigg{)}}}{\Delta}\Bigg{)}$
$\displaystyle=\Omega\Bigg{(}\sqrt{\frac{N}{\Delta}}+\frac{\sqrt{\frac{3}{16}N^{2}+\Delta
N-\Delta^{2}}}{\Delta}\Bigg{)}$ $\displaystyle=\Omega(N/\Delta).$

∎

See 15

###### Proof.

For simplicity let $N$ be some power of $2$. Consider the CountDecision
($N/4,N/4-\Delta$) problem for some $0<\Delta\leq N/5$. The task is to decide
if the Hamming weight of the given string $x$ is $N/4$ or $N/4-\Delta$.

Now, for a given string $x$, construct a Boolean function
$f^{(x)}:\\{0,1\\}^{n}\xrightarrow{}\\{0,1\\}$ such that $f^{(x)}(i)=x_{i}$
where $n=\log(N)$. We show that the problem of deciding if the Hamming weight
of $x$ is $N/4$ or $N/4-\Delta$ can be solved by deciding if
$\hat{f}_{max}^{(x)}$ is $\frac{1}{2}$ or $\frac{1}{2}+\frac{2\Delta}{N}$.

Let $y$ be any string of Hamming weight $N/4$. Let $f^{(y)}$ be the Boolean
function constructed using $y$. We know that the Walsh coefficient of function
$f$ at $a$ is defined as

$\displaystyle\hat{f}(a)$
$\displaystyle=\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{f(x)\oplus a\cdot
x}$
$\displaystyle=\frac{1}{2^{n}}\Big{[}\big{|}\\{x\in\\{0,1\\}^{n}:f(x)=a\cdot
x\\}\big{|}-\big{|}\\{x\in\\{0,1\\}^{n}:f(x)\neq a\cdot x\\}\big{|}\Big{]}.$

Intuitively, $|\hat{f}(a)|$ gives the difference in the fraction of inputs $x$
for which the function $f$ matches with the linear function $a\cdot x$ and the
fraction of inputs for which the function does not match with $a\cdot x$. From
this we can compute the Walsh coefficient of $f^{(y)}$ at $0^{n}$ to be

$\hat{f}^{(y)}(0^{n})=\frac{1}{2^{n}}\Bigg{(}\frac{3N}{4}-\frac{N}{4}\Bigg{)}=\frac{1}{2}.$

Now, let $a\neq 0^{n}$ be some $n$-bit string. Then, $a\cdot x$ is a linear
function with equal number of $0$’s and $1$’s in its output. See that, for any
Boolean function whose Hamming weight999By the Hamming weight of a Boolean
function $f$, we mean the number of $1$’s in the output of $f$. is $N/4$, the
maximum number of inputs such that $f(x)=a\cdot x$ is bounded above by $3N/4$
where $N/2$ inputs has to be such that $a\cdot x=0=f(x)$ and $N/4$ inputs has
to be such that $a\cdot x=1=f(x)$. So, we have the Walsh coefficient of
$f^{(y)}$ at any $a\neq 0^{n}$ as

$\hat{f}^{(y)}(a)\leq\frac{1}{2^{n}}\Bigg{(}\frac{3N}{4}-\frac{N}{4}\Bigg{)}=\frac{1}{2}.$

So, we have that $\hat{f}_{max}^{(y)}=\frac{1}{2}$ and it occurs at $0^{n}$.

Next, let $z$ be a string of Hamming weight $N/4-\Delta$ and let $f^{(z)}$ be
the Boolean function constructed from $z$. For $f^{(z)}$, we have that

$\hat{f}^{(z)}(0^{n})=\frac{1}{2^{n}}\bigg{[}\Big{(}\frac{3N}{4}+\Delta\Big{)}-\Big{(}\frac{N}{4}-\Delta\Big{)}\bigg{]}=\frac{1}{2}+\frac{2\Delta}{2^{n}}.$

Again, for any Boolean function $f$ of Hamming weight $N/4-\Delta$, the
maximum number of inputs such that $f(x)=a\cdot x$ is $\frac{3N}{4}-\Delta$
where $N/2$ inputs has to be such that $a\cdot x=0=f(x)$ and $N/4-\Delta$
inputs has to be such that $a\cdot x=1=f(x)$. So, we get that the Walsh
coefficient of $f^{(z)}$ at any $a\neq 0^{n}$ is

$\hat{f}^{(z)}(a)\leq\frac{1}{2^{n}}\bigg{[}\Big{(}\frac{3N}{4}-\Delta\Big{)}-\Big{(}\frac{N}{4}+\Delta\Big{)}\bigg{]}=\frac{1}{2}-\frac{2\Delta}{2^{n}}.$

Thus, we get that $\hat{f}_{max}^{(z)}=\frac{1}{2}+\frac{2\Delta}{2^{n}}$ and
it occurs at $0^{n}$.

Consequently, any algorithm that solves the $\hat{f}_{max}$ decision problem
for the parameters $\tau=\frac{1}{2}+\frac{2\Delta}{N}$ and
$\lambda=\frac{\Delta}{N}$ can solve the CountDecision
($\frac{N}{4},\frac{N}{4}-\Delta$) problem without any query overhead. Now,
using Lemma 26, we get that any quantum algorithm that solves the
$\hat{f}_{max}$ decision problem is
$\Omega(\frac{N}{\Delta})=\Omega(\frac{1}{\lambda})$. ∎