Amplitude filtering is concerned with identifying basis-states in a superposition whose amplitudes are greater than a specifie d threshold; probability filtering is define d 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 the probability for the latter problem) of each state in superposition, then comparing each estimate against the threshold for marking 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. The main technical ingredient is an amplitude amplification algorithm that amplifies the “good state” even when the “good state” operator has a small probability of being incorrect. We provide an algorithm to perform this amplification, and we improve upon the space complexity of the previously known algorithms. As an immediate reward, the above algorithms for the filtering problems directly improve the upper bounds on the space-bounded query complexity of problems such as non-linearity estimation of Boolean functions and a version of -distinctness. In addition, we present the query lower bounds of the amplitude and probability filtering problems where we show that our algorithms are tight with respect to each of the individual parameters.
The framework ofered by these problems supports interesting tasks. For example, a binary
search over (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 -Distinctness problem
generalizes the well-studied element-distinctness problem: whether an array has at least
repetitions of any element. Consider the distribution over the domain of the array elements. If
any element appears at least times, then its mode will be at least / ( denoting the size
of the array), and vice versa. Our algorithm for probability filtering can be used to design an
algorithm for -Distinctness that makes an optimal number of queries (up to logarithmic
factors) when = Ω( ), and that too using ˜(1) qubits. Previous quantum algorithms for
large have an exponential query complexity and require a larger number of qubits [
When space is not a constraint, the query complexity of a discrete problem with -sized inputs 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. Thus, it should not appear as a surprise that we sometime end up making super-linear queries in an attempt to restrict the number of qubits to ˜(1).
The ProFil and AmpFil problems can be solved using an intuitively simple idea of doing amplitude estimation for each basis state 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 be reduced to the problem of biased-oracle amplitude amplification. Biased Amplitude Amplification in Log-space (section 2) In the above mentioned amplification problem, the oracle to mark “good” states is allowed to err with some probability 1
− . Hoyer et al. [
To reduce the qubit footprint of our algorithms, we designed our own algorithm for biased oracle amplitude amplification based on Grover’s algorithm which has a space complexity of (log( )) qubits. For arbitrary > 1/2, our algorithm uses (− 12)2√ It is to be noted that the performance of our algorithm worsens when ≈ use in algorithms for ProFil and AmpFil, our biased amplitude amplification algorithm can 1/2. In addition to
︁( be used in the NISQ era, where the marking oracles are generally erroneous; this could be of independent interest to the community. Algorithms for ProFil and AmpFil (section 3) Our objective was to design a ˜( 1 )-query algorithm to decide if there is any state with amplitude (rather, its absolute value) crosses the threshold , given the promise that either there is some such state or all states have amplitude at most − for some >
0. We designed our AmpFil algorithm by combining the idea of parallel value of an amplitude using (1/ ) queries. The ˜( estimation with our algorithm for biased amplitude amplification, where we first use amplitude estimation in parallel to estimate the amplitude and follow it with a biased-oracle amplitude amplification. We show that this algorithm uses ˜( 1 ) queries. While the quantum amplitude estimation algorithm is widely known for obtaining an -estimate of a probability in (1/ ) queries 1, a closer look at its analysis reveals that it directly returns an -estimate of the absolute √
obtained by reducing it to AmpFil. One should note that the ProFil and AmpFil problems can also be solved if we were to replace our algorithm for biased amplitude amplification with the one proposed by Hoyer et al; however, the space complexity increases significantly.
For the ProFil problem, we show that our algorithm is tight with respect to the parameters
and individually, i.e., we show a lower bound of Ω( 1 + √1 ) queries. Further, we show
an almost tight lower bound of Ω( 1 + 1 ) queries for the AmpFil problem. Both the lower
bounds use standard approaches like the adversary method [
Applications of ProFil and AmpFil (section 5)
The results in this work can be used to
design low-space 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 some have been
omitted due to space constraints, but the implications are interesting, as discussed below.
• Our algorithm for -Distinctness makes an optimal number of queries (up to logarithmic
factors) when = Ω(), and that too using ˜(1) qubits (see section 5). Previous quantum
algorithms for large have an exponential query complexity in limited space [
) qubits; it also generates a superposition of such items along
∈ (0, 1] indicates the inaccuracy in frequency estimation.
with estimates of their frequencies. The best algorithms for identifying heavy hitters in
low space classical algorithms are of streaming nature but require ˜( 1 ) space [
To summarize, our techniques yield the current best algorithms for non-linearity estimation of Boolean functions, -Distinctness for = Ω(), and -Distinctness for constant with ˜(1)-qubits; further, these algorithms almost match their lower bounds.
Given an oracle that marks a state of interest (say |⟩) and an algorithm such that |0⟩ = | ⟩, we know that the amplitude amplification algorithm allows us to obtain |⟩ w.h.p. from | ⟩ quadratically faster as compared to classical approaches using as a black-box. We use , to denote such an amplitude amplicfiation algorithm, the key ingredient of which is the Grover iterator , = − |0⟩†. Here, |⟩ denotes the reflection operator 2 |⟩ ⟨| − I. The standard assumption is that, with probability 1, the oracle marks only the ‘good’ state |⟩ with probability 1, i.e., |⟩ |⟩ = |⟩ | ⊕ 1⟩ if is ‘good’ and |⟩ |⟩ = |⟩ |⟩ if is ‘bad’.
with some probability ∈ (1/2, 1), then the naive amplitude estimation algorithm does not work as intended since ^ would also mark the ‘bad’ states with probability at most 1 − . With each iteration of the amplification algorithm, the probability of these false positives will also increase, thus potentially giving an erroneous output.
Previous Works: Hoyer et al. [
Hoyer et al. hinted at another approach to solve the bounded-error search problem. In this approach, a single call to the oracle ^ in the Grover iterator is replaced by (log(1/ ))-many independent calls to ^ and using the majority value over those copies for marking the state of interest. For any > 1/2 that is at least constant away from 12 , the majority value of (log(1/ )) outputs of ^ would reduce the marking error to . Thus, the error accumulates to * * *
.... .... ...
* * * ...
* * * * * .... * * * * ....
* * * ... * * Iteration 1
Iteration 2
(a) The interleaving algorithm proposed by Hoyer et al. in [
Iteration 1
Iteration 2
(b) The biased oracle amplitude amplification algorithm suggest by Hoyer et al. in [
Iteration 1 of FPAA
Iteration 2 of FPAA (c) Our Algorithm. ( √ ) after (√ ) iterations of the Grover iterate. (log(1/ )) ancillae qubits are required for performing the majority in each iteration. However, due to their entanglement with the workspace qubits, it is not possible to uncompute all the ancillae qubits cleanly to |0⟩. Hence, the space complexity would asymptotically remain (√ ). We present a detailed description 2: Apply to 1. 3: for in 1 to do
Algorithm 1 Constructing the algorithm ^,^, Require: Bounded-error oracle ^, the initial algorithm and . 1: Initialize 1 to |0⟩. Next + 1 registers 2122 · · · 2 are initialized to |0⟩. 6: Apply a conditional majority gate, using 1 as the control, using the registers 2122 . . . 2 as inputs to the majority circuit, and storing the majority value in . of these two algorithms in Appendix B.
Our Work: Now we describe our technique that uses just log-space to solve the boundederror search problem using (√ log(1/ )) queries to ^ 2. The idea is to replace the operator in the amplification iterator with a newly constructed operator ^ that internally uses ^ to enhance . The role of ^ will be to generate a state in which the good and the bad states are explicitly marked using an additional register whose state is |1⟩ or |0⟩, accordingly, and furthermore, the probability of marking a bad state can be made arbitrarily low. The algorithm for constructing such an ^ is presented as Algorithm 1.
Lemma 1. Suppose that we are given an algorithm that generates the initial state |0⟩ = ∑︀ |⟩, a bounded-error oracle ^ as defined above and an error parameter ; further, let denote the set of good states, and the set of bad states. Choose an appropriate = (− 1/2)2 log(︀ 1 )︀ ︁) , and construct a quantum circuit ^ as described in Algorithm 1. Then, ︁( 2 ∈ ∈ ⃒ = ∑︁ |⟩ [︁ such that | 0|2 ≤ and | 1|2 ≤ (we have ignored the ancillae).
The result can be understood by taking → 0 and analysing the observation upon measuring the output of ^ ⃒⃒ 0++1⟩︀ . For ∈ , we are more likely to observe |⟩ |. . .⟩ |1⟩ as compared to |⟩ |. . .⟩ |0⟩, and for ∈ , |⟩ |. . .⟩ |0⟩ is the more likely outcome, i.e., the information about being good or bad is encoded in the final qubit, w.h.p.. We present the proof of Lemma 1 in Appendix C.
The next step is straightforward. We run one of the amplification routines using ^ as the
state preparation oracle and amplifying the probability of states of the form |⟩ |. . .⟩ |1⟩ as
presented in Algorithm 2. Note that, apart from amplifying states corresponding to ∈ ,
this would also amplify states corresponding to ∈ . However, if we choose suficiently
small, we can ensure that the probability of states of the form |⟩ |. . .⟩ |1⟩ for ∈ , would be
extremely small, and hence, would be within tolerable limits as the algorithm terminates. We
present a pictorial comparison between the three algorithms in Figure 1. One can easily note
that the number of qubits in the workspace increases with each iteration for the algorithms
proposed in [
The details of Algorithm 2 and the proof of Theorem 2 are included in Appendix D; here, we
briefly discuss its query complexity. Let be the probability of obtaining some good state on
measuring | ⟩ if some good state is present in | ⟩; formally, = min(| |2) over all “good”
. We will use the fact that FPAA [
1/2. ∑︀ Theorem 2. Given an -qubit algorithm that generates the initial state |0⟩ = | ⟩ = ∈{0,1} |⟩, a bounded-error oracle ^ as defined above and an error parameter , there exists an algorithm that uses ︁( (− 12)2√ (− 1/2)2 log(1/ ) qubits and outputs a good state with probability at least 1 − , if one exists and outputs “No Solution” with probability at least 1 − if there is no good state in | ⟩. Algorithm 2 Amplitude amplification using a biased oracle Require: Bounded-error oracle ^, the initial algorithm and .
2122 · · ·
2 are initialized to |0⟩. 3: Apply the fixed point amplitude amplification algorithm (FPAA) on 2: Use Algorithm 1 to construct ^,^,. Then, apply ^,^, on 12122 · · · 2 . 1: Initialize + 2 registers such that the first register 1 is initialize to |0⟩ and the next + 1 registers using the good state as |1⟩ and with error at most / 2. Stop if the number of iterations crosses the limit of ˜( √1 ) set by the FPAA algorithm. 4: Measure as . If = |0⟩, output “No Solution”. Else, measure 1 as and output .
The filtering problems are formally defined as follows: Problem 1 (Amplitude and Probability Filtering). Suppose that we are given a quantum algorithm that generates a distribution : ( = | |2)=1 on measuring the first log() qubits of ⃒⃒⃒ 0log()+⟩ =
∑︁ ∈{0,1}log() |⟩ | ⟩ = |Ψ⟩ (say) in the standard basis. In addition, we are also provided a threshold and a parameter 0 < < . • The amplitude filtering problem, denoted
AmpFil(, , ), is to decide if | | < − for one of the two cases. all ∈ {0, 1}log() or there exists some such that | | ≥ given the promise that it is at least 1 − . • The probability filtering problem, denoted ProFil(, , ), is to decide if = | |2 < − for all ∈ {0, 1}log() or there exists some such that ≥ given the promise that it is We first present an algorithm for the amplitude filtering problem. The first step is to design an appropriate biased oracle, AmpFilBOrcl, for amplitude filtering as described in algorithm 3. The oracle is used for marking a basis state to be good if its amplitude, as required, is more than . Then, use our amplitude amplification algorithm for biased-oracle (see Section 2) to amplify the probability of finding a marked state if one exists. We summarise the behaviour of the amplitude filtering algorithm in the following theorem.
Theorem 3 (Additive-error algorithm for AmpFil). For any choice of parameters 0 < < for additive accuracy and for error, there exists a quantum algorithm that uses (︀ (log() + is measured in the standard basis, we observe the following. 1 )︀
qubits and makes ( 1 log 1 ) queries to such that when its final state 1. If | | < − for all then the output register is observed in the state |0⟩ with probability the state |1⟩ and some such that | | ≥ is returned as output.
2. If | | ≥ for any , then with probability at least 1 − the output register is observed in 21:: SSeett 1==lo⌊︁g2(si)n+−1(, ′)′⌋︁=. 21 (1 + − 8 ), = ⌈log(︀ 1 )︀
Algorithm 3 Constructing biased-oracle AmpFilBOrcl for amplitude filtering Require: Oracle (with parameters , ), threshold , and accuracy .
Require: Input register 1 set to some basis state |⟩ and output register 5 set to |0⟩.
⌉ + 5 and = + 3. 3: Initialize ancillae registers 234 of lengths , and 1, respectively, and set 3 = | 1⟩. 4: Stage 1: Apply EQAmpEst (sans measurement) with 2 as the input register, 4 as the output register and is used as the state preparation oracle. 1 is used in to determine the “good state”. EQAmpEst is called with error at most 1 − 82 and additive accuracy 21 . 5: Stage 2: Set 5 to 1 if the estimate, calculated using 4, is at least 1. 6: 7: 8:
Use HD on 3 and 4 individually.
Use HD† on 3 and 4 individually.
Use CMP on 3 = | 1⟩ and 4 as input registers and 5 as output register.
Now, we explain how we implemented the biased oracle (listed in Algorithm 3). The role of the oracle is to mark the basis states whose amplitude is at least , with at most some small error probability. Its construction involves two stages: an estimation stage followed by a marking stage. For the AmpFilBOrcl, we use EQAmpEst to estimate the amplitudes of each basis state in superposition. EQAmpEst is an extension of the well-known amplitude estimation where the basis state whose amplitude (or probability) we want to estimate is provided in a separate register instead of as an oracle. We have presented a more detailed treatment of EQAmpEst in Appendix A.2. In the marking stage, the algorithm uses straight-forward quantum operations to compare the estimate in one register with , hardcoded in a suitable encoding in another AmpFilBOrcl marks the good basis states with probability at least 8/ 2. register. Since EQAmpEst performs an estimation with error probability that is at most 1 − 82 , AmpFilBOrcl algorithm are discussed in Appendix G.
The query complexity arising from biased-oracle amplitude amplification (see Section 2) scales as ˜( √1 ) where = min | |2 among all that are good. For amplitude filtering, we want to amplify any state |⟩ such that | | ≥ , so, ≥ 2. Thus, amplitude amplification will call AmpFilBOrcl ˜( 1 ) times, each of which requires ( 1 ) calls to . The details of the
Probability filtering can be easily reduced to amplitude filtering with very little overhead. Lemma 4. Any instance of ProFil(, , ) can be reduced to an instance of AmpFil(, √ , / 2).
A proof is explained in Appendix F. This reduction gives us an algorithm for ProFil.
at least 1 − .
Corollary 5 (Additive-error algorithm for ProFil). For any choice of parameters 0 < < for additive accuracy and for error, there exists a quantum algorithm that uses (︀ (log() + 1 )︀ qubits and makes ( √
1 log 1 ) queries to such that when its final state is measured in the standard basis, we observe the following.
1. If < − for all then the output register is observed in the state |0⟩ with probability the state |1⟩ and some such that | | ≥ is returned as output. 2. If ≥ for any , then with probability at least 1 − the output register is observed in With access to unbounded space, it is easy to see that one can estimate the distribution with additive accuracy using (1/ 2) and (1/ ) queries to the oracle in the classical and quantum settings respectively which can then be used to solve the ProFil problem. However, in the case of ˜(1) space, classically, one would be required to make (/ 2) queries to answer the ProFil problem. In contrast, our algorithm solves the same in ˜(1) space using just ˜(1/ √ ) queries to . Notice that for constant , our algorithm is optimal up to some log factors.
The CountDecision problem takes as input a binary string of length and decides if the number
and Wu proved that any quantum algorithm takes Ω(√︀/Δ + √︀(2 −
queries to solve the CountDecision problem [
-bit string with 1 = 2 and 2 = 2 + to ProFil. Observe that the frequencies of 0 and 1
in the string induce a distribution . So, an oracle to can be used to implement an oracle
to the distribution . By Corollary 1.2 of [
sion 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 of size and a threshold ′ ∈ [1, ] we have to decide if there exists any element whose frequency is greater than ′. We then show a reduction from mode decision problem to ProFil to get a lower bound on it.
The main theorem of the quantum adversary method can be stated as below [
Then any quantum algorithm uses Ω︁( √︁ ·· ′′ )︁ queries to compute on ⋃︀ .
Consider the mode decision problem. Let ′ ∈ [1, ] be a threshold and set = ′− 1 . Let be a Boolean function such that () = 1 if is an array whose modal value is greater than or equal to ′ and () = 0 if the modal value of is strictly less than ′.
Let be the set containing one array such that contains all unique elements with frequency ′ − 1. Let the unique elements be denoted 1, 2, · · · , . Let be the set that contains the arrays for all 2 ≤ ≤ where is the array that is exactly the same as except that the first occurrence of is changed to 1. Notice that the modal element in any is 1. Define relation as = × .
For any ∈ , we can see that there is exactly one element ∈ such that (, ) ∈ since | | = 1. For ∈ , there is exactly − 1 elements ∈ such that (, ) ∈ as || = − 1. Similarly, for any ∈ and any ∈ [], there is at most one element ∈ such that [] ̸= [] and (, ) ∈ . For ∈ and any ∈ [], there is at most one element ∈ such that [] ̸= [] and (, ) ∈ .
From these, we can derive that the quantum query complexity of computing is Ω(√︁ − 1·11· 1 ) = Ω(√) = Ω(√︀/ ′ − 1).
Now, the reduction from the mode decision problem to ProFil can be trivially done by setting the threshold of ProFil as = ′/. This would imply that the quantum query lower bound of ProFil is Ω(1/√ ) for = 1 .
We know from Theorem 4 that any instance of ProFil(, , ) can be reduced to an instance of AmpFil(, √ , / 2). We obtain the following theorem using this reduction and Theorem 6. Theorem 8. Any quantum algorithm that solves AmpFil (, , ) requires Ω( 1 + 1 ) queries.
From these lower bounds, we can note that our algorithms for AmpFil and ProFil, with complexities ˜( 1 ) and ˜( √1 ) are tight with respect to the parameters and individually.
The ElementDistinctness problem [
Problem 2 (-Distinctness). Given an oracle to an -sized -valued array , decide if has distinct indices with identical values.
An -valued array means one whose entries are from {0, . . . , − 1}. Observe that Distinctness can be reduced to ProFil with = , assuming the ability to uniformly sample.
The best-known classical algorithm for -Distinctness uses sorting and has a time
complexity of ( log()) with a space complexity (). In the quantum domain, apart from = 2,
the = 3 setting has also been studied earlier [
The = 2 version is the ElementDistinctness problem, which was first solved by Buhrman
et al. [
Thus, it appears that even though eficient algorithms may exist for small values of , the situation is not very pleasant for large , especially = Ω() — the learning graph idea may not work (even if the corresponding algorithm could be implemented in a time-eficient manner) and the quantum walk algorithm uses Ω() space.
We propose to use ProFil to solve -Distinctness by (a) implementing an oracle from the array (this is straightforward) and then calling our algorithm for probability filtering using = / (see Theorem 5), and = 1/ to ensure that estimates (which are always of the form /) are well-separated.
Lemma 9. There exists a bounded-error algorithm for -Distinctness, for any ∈ [], that uses ( √3/2 log(︀ 1· )︀ ) queries and (︀ (log() + log()) log(︀ · 1 )︀ 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 ˜(1) qubits, and as an added benefit, it works for any . Further, it improves upon the algorithm proposed by Ambainis for ≥ 4 when we require that ˜(1) space be used, and moreover, its query complexity does not increase with . Remember that the query complexity of -Distinctness (or any other problem) with unbounded space is trivially but need not be so with bounded space.
For that is large, e.g. Ω(), the query complexity of Ambainis’ algorithm is exponential in ,
and that of ours is (3/2). Montanaro used a reduction from the CountDecision problem [
Hadamard coeficient [ Non-linearity is an important cryptographic measure of a Boolean function. Non-linearity of a function : {0, 1}→− { 0, 1} is defined in terms of the largest absolute-value of its Walsh18] as ( ) = 12 − 1 ^ where ^ = max |^()| and ^() is the 2 Walsh-Hadamard coeficient of
at the point . Boolean functions with low non-linearity can be easily approximated by linear functions.
Ab initio, the non-linearity can be estimated from an estimate of ^. Recall that the output
state of the Deutsch-Jozsa circuit is ∑︀ ^() |⟩, i.e., the probability of observing |⟩ is ^()2. It
immediately follows that we can utilize the ProFil algorithm in conjunction with a binary search
on the interval (0, 1] to estimate ^2, and hence, non-linearity, with additive inaccuracy. This
approach is presented as Algorithm 1 in [
algorithm presented in [
AmpFil with inaccuracy , instead of calling ProFil with inaccuracy in the query complexity in the form of ˜( 2. Given that the query complexity of AmpFil is ˜(1/ ), this leads to a quadratic improvement 1 ^
). log(︀ 1 )︀ log ︁(
1 ︁) ^ √ Lemma 10. Given an oracle to an -bit Boolean function, an accuracy parameter and an error parameter , there exists an algorithm that returns an estimate ˜ such that | − ˜ | ≤ with 1 probability at least 1 − using ( ^ ) queries to the oracle.
Bera et al. ([
This shows that our non-linearity estimation algorithm based on AmpFil is close to optimal.
be reduced to ˜(1/ 2^) with a slightly tighter analysis of their Algorithm 1.
3Although the query complexity of this algorithm has been proved to be ˜(1/ 3) in [
In this section, we present details on the quantum amplitude amplification subroutine and the MAJ operator which are used as part of our algorithms.
|⟩; i.e., acts as The amplitude amplification algorithm (AA) is a generalization of the novel Grover’s algorithm. Given an -qubit algorithm that outputs the state |⟩ = ∑︀ |⟩ on |0⟩ and a set of basis states = {|⟩} of interest, the goal of the amplitude amplification algorithm is to amplify the amplitude corresponding to the basis state |⟩ for all |⟩ ∈ such that the probability that the final measurement output belongs to is close to 1. In the most general setting, one is given access to the set via an oracle that marks all the states |⟩ ∈ in any given state ∑︁ |⟩ |0→⟩−
∑︁ |⟩ |0⟩ + ∑︁ |⟩ |1⟩ . ∈/ ∈ Now, for any , any state |⟩ = ∑︀ |⟩ can be written as |⟩ = ∑︁ |⟩ = sin( ) | ⟩ + cos( ) | ⟩
amplification algorithm can then be given as where sin( ) = √︀∑︀∈ | |2, | ⟩ = √∑︀∑︀ ∈∈ ||⟩|2 and | ⟩ = √∑︀∑︀∈/ |⟩ . Notice that the ∈/ | |2 states | ⟩ and | ⟩ are normalized and are orthogonal to each other. The action of the amplitude = (︀ sin( ) | ⟩ + cos( ) | ⟩ )︀ |0→⟩− √︀(1 − ) | ⟩ |1⟩ + √︀ | ⟩ |0⟩ where satisfies
| | < and is the desired error probability. This implies that on measuring the final state of AA, the measurement outcome |⟩ belongs to with probability |1 − | which
at least 1 − interval | − ˜| ≤ 2 ˜ = with certainty. √
some basis state (in the standard basis — this can be easily generalized to any arbitrary basis).
controlled- to output an estimate ˜ ∈ [
Given an accuracy parameter ∈ (0, 1), the amplitude estimation problem is to estimate the
probability of observing |⟩ upon measuring | ⟩ in the standard basis, up to an additive
accuracy . Brassard et al. [
The following corollary is obtained from the above theorem by setting = 1 and = + 3. interval | − ˜| ≤ or 1 then ˜ = with certainty.
Corollary 13. The amplitude estimation algorithm returns an estimate ˜ that has a confidence 21 with probability at least 82 using + 3 qubits and 2+3 − 1 queries. If = 0
Setting 21 = , the amplitude estimation algorithm returns an estimate ˜ that has a confidence interval | − ˜| ≤ with probability at least 82 using log(︀ 1 )︀ ︁) qubits and (︀ 1 )︀ queries. ︁(
We use the subscript in QAEAlgo to remind the reader that the circuit for amplitude estimation depends on the algorithm that generates the state | ⟩ from |0⟩.
Now, let be the probability of obtaining the basis state |⟩ on measuring the state | ⟩. The amplitude estimation circuit referred to above uses an oracle, denoted , to mark the “good state” |⟩, and involves measuring the output of the QAEAlgo circuit in the standard basis; actually, it sufices to only measure the second register. We can summarise the behaviour of the QAEAlgo circuit (without the final measurement) in the following lemma. as |0⟩ = | ⟩, QAEAlgo on an input state |00 . . . 0⟩ |0⟩ generates the following state. Lemma 14. Given an oracle that marks |⟩ in some state | ⟩ and the algorithm that acts
QAEAlgo, |00 . . . 0⟩ |0→⟩− , | ⟩ |^⟩ + , | ⟩ |⟩ |⟩ =
∑︁ ∈{0,1} ̸∈{^,+,^,− } Here, | ,|2, the probability of obtaining the good estimate, is at least 82 , and |^⟩ is an qubit normalized state of the form |^⟩ = + |^,+⟩ + − |^,− ⟩ such that both sin2( ^2,+ ) and sin2( ^2,− ) approximate up to − 3 bits of accuracy. Further, |⟩ is an -qubit error state (normalized) such that any basis state in |⟩ corresponds to a bad estimate, i.e., we can write , |⟩ in which | sin2 (︀ 2 − | > 2− 3 for any such .
)︀ 1
In an alternate setting where the oracle is not provided, QAEAlgo can still be performed if the basis state |⟩ is provided, say, in a diferent register. One can construct a quantum circuit, say , that acts on basis states as |⟩ |⟩ ↦→ (− 1) , |⟩ |⟩. Now perform QAEAlgo in which we replace all calls to by whose first input is set to name this circuit as EQAmpEst that implements the following operation. |⟩ from the new register. We
EQAmpEst(︀ |⟩ |00 . . . 0⟩ |0⟩ →)︀− | ⟩ (︀ , | ⟩ |^⟩ + , | ⟩ |⟩ ︀) sition ∑︀ |⟩. We would be using EQAmpEst in this mode in this work. Further, since EQAmpEst is a quantum circuit, we could replace the state |⟩ by any superpoEQAmpEst ︁( ∑︁ |⟩ |00 . . . 0⟩ |0⟩ )︁ →−
∑︁ , |⟩ | ⟩ |^⟩ + ∑︁ , |⟩ | ⟩ |⟩ . Let denote the probability of observing the basis state |⟩ when the state | ⟩ is measured. Notice that on measuring the first and the third registers of the output, with probability | ,|2 ≥ 82 | |2 we would obtain as measurement outcome a pair |⟩ |^⟩ where sin2( 2^ ) = ˜ is within ± 21− 3 of . Observe in this setting that the subroutine essentially estimates the probabilities corresponding to all the basis states |⟩ 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.
Like probability, one could be interested in estimating the absolute value of an amplitude | | of a basis state |⟩ in | ⟩ with an accuracy of . Naively, one can estimate the probability = | |2 with 2 accuracy as ˜ and then return √˜. It is easy to show that √˜ is an estimate of | |. The query complexity of this process would scale as 12 . However, this can be improved to ( 1 ). A close inspection of the quantum amplitude estimation algorithm reveals that the output of the algorithm is an angle ˜. Moreover, | − ˜| ≤ / 3 implies | sin2 ˜ − | = | sin2 ˜ − sin2 | ≤ . Nonetheless, it can be shown that | − | ≤ / 3 also ˜ implies | sin ˜− sin | = ⃒⃒ sin ˜− | |⃒⃒ ≤ , thus also providing an -estimate of | | with ( 1 ) queries. This suggests that any extension of the original amplitude amplification algorithm, like EQAmpEst, can also be used to estimate the absolute value of the amplitude of interest.
Let 1 . . . be Bernoulli random variables with success probability > 1/2. Let denote their majority value (that appears more than /2 times). Using Hoefding’s bound 4, it can be easily proved that has a success probability at least 1 − , for any given , if we choose 2 ≥ (− 1/2)2 ln 1 . We require a quantum formulation of the same.
Suppose we have copies of the quantum state | ⟩ = | 0⟩ |0⟩ + | 1⟩ |1⟩ in which we define “success” as observing |0⟩ (without loss of generality) and is chosen as above. Let = ‖ | 0⟩ ‖2 denote the probability of success. Suppose we measure the final qubit after applying (I ⊗ ) in which the operator acts on the second registers of each copy of | ⟩. Then it is easy to show, essentially using the same analysis as above, that
(I ⊗ ) | ⟩⊗ |0⟩ = |Γ0⟩ |0⟩ + |Γ1⟩ |1⟩ in which ‖ |Γ0⟩ ‖2 ≥ 1 − .
The MAJ operator can be implemented without additional queries and with () gates and log() qubits.
Hoyer et al., in [
|| ∈ |ℬ| ∈ℬ 4Pr[∑︀ − [∑︀ ] ≥ ] ≤ exp(︁ − 22 )︁
Then, the initial state can be given as | 0⟩ = 0 | ⟩ |0⟩ + 0 | ⟩ |0⟩, where the first register 01 contains the superposition, the second register 02 is the ancilla qubit for the oracle operation, and | 0|2 is the probability of obtaining a ‘good’ state when measuring | ⟩ in the standard basis. After the amplification phase, the state evolves to ⃒⃒ 0′⟩︀ = 0′ |Γ0⟩ |1⟩ + 0′ ⃒⃒ Γ0⟩︀ |1⟩ + 0′ | 0⟩ |0⟩, where |Γ⟩0 is a superposition of |⟩ such that ∈ and ⃒⃒ Γ0⟩︀ is that of |⟩ such that ∈ ℬ
ifrst, where denotes the iteration number. Then, conditioned on the state of 02 being |1⟩, oracle is invoked on () qubits, and the majority of these qubits is computed and stored in . a new register 04. For the next iteration, 01, 02 and 03 are considered together as the first register 11 and 04 is considered as the second register 12 to get the state | 1⟩ = 1 |Γ1⟩ |1⟩ +
For any , the state after the ℎ iteration can be given as | ⟩ = |Γ⟩ |1⟩ + ⃒⃒ Γ⟩︀ |1⟩ + | ⟩ |0⟩. Performing this for (√ ) iterations yields a ‘good’ state with a high probability. Note that at the end of each iteration, the qubits in the first and second registers are highly entangled due to computing the majority. So it is impossible to cleanly uncompute the () being query-optimal, i.e., (√ ), its space complexity shoots to (√ ). qubits to get |0⟩. This blows up the space complexity after each iteration. Despite the algorithm
In addition to the above discussed algorithm, Hoyer et al. presented another approach to solve the bounded-error search problem. In this approach, a single call to the oracle ^ in the Grover iterator is replaced by the following sub-circuit for marking: make (log(1/ ))-many independent calls to ^, then compute the majority over those copies, and finally use the majority value for marking the state of interest. By taking the majority value of (log(1/ )) outputs of ^, one can reduce the marking error of the oracle to , for any > 1/2 that is at least constant away from 12
. When this sub-circuit is replaced for the bounded-error oracle ^ in Grover’s algorithm, the error accumulates as ( space complexity is still (√ ). error by tweaking appropriately. Naturally, the ancillae qubits required for performing the majority in each of the (√ ) calls is (log(1/ )). However, not all the ancillae qubits can be cleaned up for reuse due to their entanglement with the workspace qubits. Therefore, the √ ), which can be reduced to any desired
Lemma 1. Suppose that we are given an algorithm that generates the initial state |0⟩ = ∑︀ |⟩, a bounded-error oracle ^ as defined above and an error parameter ; further, let denote the set of good states, and the set of bad states. Choose an appropriate = (− 1/2)2 log(︀ 1 )︀ ︁) , and construct a quantum circuit ^ as described in Algorithm 1. Then, ︁(
2 ⃒
Proof. We use the construction in algorithm 1 to prove this. After initializing the registers, on applying on 1, we can see that the state in 1 is | ⟩ = ∑︀ ∈{0,1} |⟩. Next, on apply ^ on all the 2 registers, we obtain the state of the complete system as | 1⟩ =
∑︁ ︂( √ | ()⟩ + √︀1 Now, using Chernof bounds, it is straightforward that on on computing majority over ≥ 1 − ⃒ () , the probability of obtaining the majority as () is at least 1 − . Since, for each |⟩, we perform a majority over all the registers 2 and save it in , the probability obtaining () in with the condition that 1 is 1 is at least 1 − . ⃒ ⃒ 0 | ⟩ ⟩
there exists an algorithm that uses (− 12)2√ Theorem 2. Given an -qubit algorithm that generates the initial state |0⟩ = | ⟩ = ∑︀∈{0,1} |⟩, a bounded-error oracle ^ as defined above and an error parameter , (− 1/2)2 log(1/ ) qubits and outputs a good state with probability at least 1 − , if one exists and outputs “No Solution” with probability at least 1 − if there is no good state in | ⟩.
Set = ( (− 1/2)2 log(1/ ′)) for a ′ = 4 2 and construct ^,^,. This ^ (dropping the 2 ^ |0⟩ ⃒⃒ 0⟩ ⃒ |0⟩ = ∑︁ |⟩ (︀ ,0 |,0⟩ |0⟩ + ,1 |,1⟩ |1⟩ )︀ = |Ψ⟩
where | ,()|2 ≥ 1
− ′ for any ; here () indicates the “goodness” of .
Now, two cases can happen.
Case (i): Let () = 0 for all . We analyse the situation that the algorithm does not output “No Solution”, in other words, was observed as |1⟩.
Now, the output state after ^ would be such that | ,1|2 ≤ ′ for all . So, the probability of measuring |1⟩ as output is ∑︀ | ,1|2 ≤ ′ ∑︀ | | 2 = ′. Can such a state, with final qubit as |1⟩, appear with overwhelming probability after (1/ ) 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 be the angle made by the superposition of those states of |Ψ⟩ whose last qubit is in |1⟩. Then, we have sin2( )
≤ ′ = 4 2. 14 (︀ sin− 1(√ 2)/ sin− 1(√ 1)︀) . Since < sin− 1( ), we have
For any state | ⟩ if the probability of obtaining a good state is sin2( ) = 1 and if we would like to boost the probability to 2, then it easy to show that the number of iterations needed in the amplitude amplification algorithm is = ⌈︁ 1 (︀ sin− 1(√ 2)/ sin− 1(√ 1) − 2 ︀) 2 1 ⌉︁ > 1 4 > (︀ sin− 1(√︀ 2)/ sin− 1(√︀ 1)︀) > 4 1 ︀( √︀ 2/ sin− 1(√︀ 1)︀) . This says that the number of amplification iterations required for improving the probability of obtaining |1⟩ from 2 2 to is at least 1/4 . But since the maximum number of iterations performed in the amplification routine is ( √1 ), the probability of obtaining |1⟩ on measuring the last qubit of the state after amplitude amplification is at most (most likely quite less).
Case (ii): Let () = 1 for some . In this case, for all such that () = 1, we will have | ,1|2 ≥ ∑︀:()=1 | ,1|2 ≥ (1 − ′) > / 2 (since < 0.5). Now, using the fixed point amplitude amplification subroutine, in ( √1 ) iterations, we obtain a final state post amplification such 1 − ′. Then the probability of measuring the last qubit as |1⟩ is at least that with probability 1
− we obtain |1⟩ on measuring the register.
Let the post-measurement state, after observing in the state |1⟩, be denoted | ⟩. We want to clarify that it is not immediately obvious that we shall observe a good state on probability. This requires an a additional analysis. measuring the first register of | ⟩ since the biased oracle also marks the bad states with some ∈ G on measuring the first register of | ⟩ is at least 3/4.
Proof. The state just before amplification can be given as Claim 15. Let | ⟩ be the post-measurement state obtained on measuring the last qubit as |1⟩. If the set of good state G = { : () = 1} is non-empty, then the probability of obtaining some |Ψ⟩ = ∑︁ |⟩ (︀ ,0 |,0⟩ |0⟩ + ,1 |,1⟩ |1⟩ )︀ where by |⟩1 that
[︁ So, we have ︁) .
In our case, we have 1 = 4 2 and 2 = . So, the number of iterations required is > 1 (︁ √ 4 / sin− 1(√ 4 2))︁ = 1 (︁ √ 4 / sin− 1( 2 ) . we have 2 ≤ 0.5 < 0.75. Hence we have, For any ≤ 0.75, it is easy to see that sin− 1( ) < √ . Since, we set < 0.5 and since ≤ 1, > 1 (︁ √ 4 / sin− 1( 2 )︁) > 1 (︁ √ 4 / √ 2 )︁ = 1 4 [︁ [︁ |⟩1 |1⟩ |1⟩ ]︁ ]︁ where | ,()|2 ≥ condition that the qubit is |1⟩ is 1 − ′ for any . The probability of obtaining some good state on the
∑︀∈G | ,1|2 = ∑︀ ∈G | ,1|2 + ∑︀∈/G | ,1|2 =
+ (say) ]︁ we denote the probability of obtaining some good state in 1. We know = ∑︁ | ,1|2 = ∑︁ | |2| ,1|2 ≤ ′ ∑︁ | |2 ≤ ′.
∈/G
⃒ [︁ |⟩1 ⃒⃒ |1⟩
∈/G ]︁ = ∈/G = + ≥ + ′
1 . Now, ′ ′ ′ = ∑︀∈G | |2| ,1|2 ≤ (1 − ′) ∑︀∈G | |2 ≤ (1 − ′) ′ 4 2 ≤ = (1 − 4 2)
1/4 1 − (1/4) ︀( Since | |2 ≥ for ∈ G
︀) =
3 2
1 1 + (1/3) = .
3 4 3/4, we obtain |⟩ as measurement outcome for which () = 1.
This gives us that if was measured as |1⟩ then on measuring 1, with probability at least
In this section we first present a few subroutines that are used in the construction of ProbFilBOrcl and AmpFilBOrcl oracles.
where = 1 if = for all ∈ [], and = 0 otherwise.
EQ: Given two computational basis states |⟩ and |⟩ each of qubits, EQ checks if the -sized prefix of and that of are equal. Mathematically, EQ|⟩ |⟩ = (− 1) |⟩ |⟩ HD: When the target qubit is |0⟩, and with a − bit string in the control register, HD computes the absolute diference of from 2− 1 and outputs it as a string where is the integer corresponding to the string . It can be represented as HD |⟩ |⟩ = | ⊕ , ∈ {0, 1} and ˜ is the bit string corresponding to the integer ⃒⃒ 2− 1 ⃒ ˜⟩ |⟩ where − ⃒ . Even though the operator HD requires two registers, the second register will always be in the practical purposes, this operator can be treated as the mapping |⟩ ↦→ |˜⟩.
state |0⟩ and shall be reused by uncomputing (using †) after the CMP gate. For all CMP: The CMP operator is defined as CMP |1⟩ |2⟩ |⟩ = |1⟩ |2⟩ | ⊕ (2 ≤ 1)⟩ where 1, 2 ∈ {0, 1} and ∈ {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 Cond −
MAJ operator is defined as ∏︀ (︀ |⟩ ⟨| ⊗ )︀ where |1⟩ · · · | ⟩ | ⊕ (˜ ≥ /2)⟩ where ˜ = ∑︀ and , ∈ {0, 1}. |⟩ ⟨| ⊗ acts on computational basis states as |1⟩ · · · | ⟩ |⟩ =
Here we present the proof of the fact that probability estimation is very easily reduced to amplitude estimation.
Lemma 4. Any instance of ProFil(, , ) can be reduced to an instance of AmpFil(, √ , / 2). Proof. To show the reduction we prove that the following holds for any : • If ≥ , then | | ≥ • If < − 2 , then | | < √ − .
√ . ifrst part of the reduction. Now, let < − 2 . This gives that | | < √
Consider the case when ≥ . This gives | |2 ≥ which implies | | ≥ √
proving the − 2 . Now, see that Using this we have, | | < √ − 2 ≤
− which proves the second part of the reduction.
2: Set 1 = ⌊︁ 2 sin− 1( ′)⌋︁
Algorithm 4 Constructing biased-oracle AmpFilBOrcl for probability filtering Require: Oracle (with parameters , ), threshold , and accuracy .
1: Set = log() + , ′ = 21 (1 + − 8 ), = ⌈log(︀ 1 )︀ ⌉ + 5 and = + 3. Require: Input register 1 set to some basis state |⟩ and output register 5 set to |0⟩. 3: Initialize ancillae registers 234 of lengths , and 1, respectively, and set 3 = | 1⟩. 4: Stage 1: Apply EQAmpEst (sans measurement) with 2 as the input register, 4 as the output register and is used as the state preparation oracle. 1 is used in to determine the “good state”. EQAmpEst is called with error at most 1 − 82 and additive accuracy 21 . 5: Stage 2: Set 5 to 1 if the estimate of the probability, calculated using 4, is at least . 6: 7: 8:
Use HD on 3 and 4 individually.
Use HD† on 3 and 4 individually.
Use CMP on 3 = | 1⟩ and 4 as input registers and 5 as output register.
The algorithm is described in Algorithm 4. It uses the following two subroutines. HD: When the target qubit is |0⟩, and with a − bit string in the control register, HD computes the absolute diference of from 2− 1 and outputs it as a string where is the integer corresponding to the string . It can be represented as HD |⟩ |⟩ = | ⊕ ˜⟩ |⟩ where , ∈ {0, 1} and ˜ is the bit string corresponding to the integer ⃒⃒ 2− 1 − ⃒⃒ . Even though the operator HD requires two registers, the second register will always be in the practical purposes, this operator can be treated as the mapping |⟩ ↦→ |˜⟩. state |0⟩ and shall be reused by uncomputing (using †) after the CMP gate. For all the first register is at most that in the second register.
CMP: The CMP operator is defined as CMP |1⟩ |2⟩ |⟩ = |1⟩ |2⟩ | ⊕ (2 ≤ 1)⟩ where 1, 2 ∈ {0, 1} and ∈ {0, 1}. It simply checks if the integer corresponding to the basis state in In Stage 1 of the algorithm, EQAmpEst estimates the absolute value of the amplitude of |⟩ in |0⟩ in 4, and in Stage 2, this estimate is compared with to set or unset 5. This makes
calls to the state preparation oracle, in this case, , and no one else adds to this. The overall behaviour is summarised below.
Lemma 16. AmpFilBOrcl makes (1/ ) calls to . |⟩ ⃒⃒ 02++1⟩︀ |0⟩, we observe the following with probability at least 82 .
Upon measuring its output on AmpFilBOrcl |⟩ ⃒⃒ 02++1⟩ |0⟩ =⇒ {︃|⟩ |⟩ |0⟩ , if < − , |⟩ |⟩ |1⟩ , if ≥ .
where |⟩ is a normalized state of the form |⟩ = + |,+⟩+ − |,− ⟩ outputs ∈ {,+, ,+} which is an -bit string that behaves as ⃒ sin | ,|2 ≥ 82 and | ,|2 ≤ 1 − 82 .
⃒ ⃒ that on measurement ︁( )︁ 2 − | |⃒⃒ ≤ 21 ,
We denote the set {,+, ,− } by . Essentially, for any , EQAmpEst stores the correct estimate of the absolute value of the amplitude of in |Ψ⟩ into 4 with probability at least 82 .
The correctness of stage-2 is exactly the same as that in the proof for Theorem 16.
Lemma 16. AmpFilBOrcl makes (1/ ) calls to . |⟩ ⃒⃒ 02++1⟩︀ |0⟩, we observe the following with probability at least 82 .
Upon measuring its output on AmpFilBOrcl |⟩ ⃒⃒ 02++1⟩ |0⟩ =⇒ {︃|⟩ |⟩ |0⟩ , if < − , |⟩ |⟩ |1⟩ , if ≥ . |⟩ |0⟩ ⃒⃒ 0⟩︀ ⃒⃒ 0⟩︀ 0 state transforms to Proof. We analyse the algorithm on the input state on registers 12122345 as on 124 with 2 as the input register and 4 as the output register and 1 for marking the “good” state whose amplitude we desire to estimate (using, of course, the oracle), the input | ⟩ where = 2 + + 1. We set 3 = | 1⟩. On applying EQAmpEst | 1⟩ = |⟩ |Ψ⟩ , |⟩ + , |⟩
︁) | 1⟩ |0⟩ = , |⟩ |Ψ⟩ |⟩ | 1⟩ |0⟩ + , |⟩ |Ψ⟩ |⟩ | 1⟩ |0⟩ = , | 1,⟩ + , | 1,⟩ Query Complexity : plexity is (1/ ).
All calls to are made by EQAmpEst and the latter’s query com
Recall that the non-linearity of a Boolean function : {0, 1}→− { 0, 1} is defined as ( ) = 1 2 − 1 ^ 2 where ^ = max | (^)| and ^() is the Walsh coeficient of a decision problem, namely the ^ decision problem, as follows: given a Boolean function : {0, 1}→− { given the promise that one of the two cases is true. It is quite straight forward that the ^ 0, 1}, a threshold and a parameter , decide if ^ ≥ or if ^ < − problem can be directly reduced to the problem of non-linearity estimation. So, to show a lower at the point . We define bound for the non-linearity estimation problem, we show a reduction from the CountDecision problem to the ^ decision problem. First consider the following lemma which will help prove the required reduction.
Lemma 17. The query complexity of any quantum algorithm that solves CountDecision (/4, /4 − Δ) is Ω(/Δ) for any 0 < Δ ≤ /5.
Proof. Using Corrolary 1.2 of [
√︃(︂ 4 − Δ 4 − Δ Δ √︁ 136 2 + Δ − Δ2 )︃ Δ Lemma 11. Any quantum algorithm uses Ω(1/ ) queries to estimate the non-linearity of any given Boolean function.
Proof. For simplicity let be some power of 2. Consider the CountDecision (/4, /4 − Δ) problem for some 0 < Δ ≤ /5. The task is to decide if the Hamming weight of the given string is /4 or /4 −
Δ.
()() = where = log( ). We show that the problem of deciding if the Hamming weight of is /4 or /4 − Δ can be solved by deciding if ^() is 12 or 21 + 2Δ .
Let be any string of Hamming weight /4. Let () be the Boolean function constructed using . We know that the Walsh coeficient of function at is defined as
∑︁
21 [︁⃒⃒ { ∈ {0, 1} : () = · }⃒⃒ − ⃒⃒ { ∈ {0, 1} : () ̸= · }⃒⃒ ]︁.
Intuitively, |^()| gives the diference in the fraction of inputs for which the function matches with the linear function · and the fraction of inputs for which the function does not match with · . From this we can compute the Walsh coeficient of () at 0 to be So, we have the Walsh coeficient of () at any ̸= 0 as Now, let ̸= 0 be some -bit string. Then, · is a linear function with equal number of 0’s and 1’s in its output. See that, for any Boolean function whose Hamming weight5 is /4, the maximum number of inputs such that () = · is bounded above by 3/4 where /2 inputs has to be such that · = 0 = () and /4 inputs has to be such that · = 1 = (). So, we have that ^() = 12 and it occurs at 0. constructed from . For (), we have that
Next, let be a string of Hamming weight /4 − ^()(0) =
4 − Again, for any Boolean function of Hamming weight /4 − Δ where /2 inputs has to be such that · = 0 = () Δ, the maximum number of and /4 − Δ inputs has to be such that · = 1 = (). So, we get that the Walsh coeficient ^()() ≤
Thus, we get that ^() = 12 + 22Δ and it occurs at 0.
Consequently, any algorithm that solves the ^ decision problem for the parameters overhead. Now, using Lemma 17, we get that any quantum algorithm that solves the ^ Δ) problem without any query 5By the Hamming weight of a Boolean function , we mean the number of 1’s in the output of .
−