PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Amplitude Amplification and Estimation

Gilles Brassard, Peter Hoyer, Michele Mosca, Alain Tapp

arXiv:quant-ph/0005055v1quant-ph

TL;DR

The paper seeks faster quantum methods for finding good solutions and estimating their success probability than repeated classical or measured quantum trials. It develops amplitude amplification and amplitude estimation, applying the latter to approximate counting, with optimal quantum algorithms in several settings.

  • Problem

    Repeatedly running a probabilistic or measured quantum algorithm requires an average of 1/a or 1/a_x trials to find a good solution.

    Source: §1 · pp. 2–3

  • Method

    The paper develops amplitude amplification, including exponentially increasing iteration counts when a is unknown, and amplitude estimation for estimating a and approximate counting.

    Source: §1 · pp. 3–4, §2 · p. 9

  • Results

    Amplitude amplification reduces the expected search effort to approximately 1/√a, while approximate counting uses O(√(N/t)) evaluations to estimate t within relative error ε with high probability.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The resulting quantum algorithms are proven optimal up to a multiplicative constant in the stated error models and are often quadratically faster than the best possible classical algorithms.

    Source: §5 · p. 26

    For some heuristics, the single-use success probability h_f may be small, although repeated random-seed uses can increase the chance of finding a solution.

    Source: §3 · p. 13

Abstract

from arXiv · show

Consider a Boolean function $\chi: X \to \{0,1\}$ that partitions set $X$ between its good and bad elements, where $x$ is good if $\chi(x)=1$ and bad otherwise. Consider also a quantum algorithm $\mathcal A$ such that $A |0\rangle= \sum_{x\in X} \alpha_x |x\rangle$ is a quantum superposition of the elements of $X$, and let $a$ denote the probability that a good element is produced if $A |0\rangle$ is measured. If we repeat the process of running $A$, measuring the output, and using $\chi$ to check the validity of the result, we shall expect to repeat $1/a$ times on the average before a solution is found. *Amplitude amplification* is a process that allows to find a good $x$ after an expected number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$, assuming algorithm $A$ makes no measurements. This is a generalization of Grover's searching algorithm in which $A$ was restricted to producing an equal superposition of all members of $X$ and we had a promise that a single $x$ existed such that $\chi(x)=1$. Our algorithm works whether or not the value of $a$ is known ahead of time. In case the value of $a$ is known, we can find a good $x$ after a number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$ even in the worst case. We show that this quadratic speedup can also be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform amplitude estimation, a process that allows to estimate the value of $a$. We apply amplitude estimation to the problem of *approximate counting*, in which we wish to estimate the number of $x\in X$ such that $\chi(x)=1$. We obtain optimal quantum algorithms in a variety of settings.

1 Introduction

The paper generalizes Grover’s search through amplitude amplification, achieving a quadratic improvement over repeated classical trials and extending it to heuristics, unknown success probabilities, and approximate counting.

Amplitude amplification

  • Amplitude amplification raises success amplitudes rather than probabilities, reducing expected repetitions from 1/a to approximately 1/√a.The method assumes algorithm A makes no measurements and uses A, its inverse, and the validity test.Source: §1 · p. 3

Grover search

  • Grover’s algorithm is the special case with a unique marked item and an equal superposition, requiring approximately √N evaluations instead of N.The equal-superposition construction has success probability 1/N under measurement.Source: §1 · p. 3

Known and unknown success probabilities

  • The approach remains effective when a is unknown, while known a permits worst-case success after a number of iterations proportional to 1/√a.For unknown a, exponentially increasing iteration counts overcome the lack of an appropriate predetermined value.Source: §1 · p. 3

Classical heuristics

  • Amplitude amplification also gives quadratic speedups over a broad class of classical heuristics rather than only exhaustive search.The paper compares the quantum procedure against heuristics that can already solve problems more efficiently than exhaustive search.Source: §1 · pp. 3–4

Amplitude estimation

  • Amplitude estimation estimates a with error at most 2π√(a(1−a))/M + π^2/M^2 with probability at least 8/π^2.One iteration runs A forwards and backwards and computes χ once.Source: §1 · p. 4

Approximate counting

  • Applied to approximate counting, the method estimates the number of marked inputs using about N/t evaluations for relative-error estimates and supports exact counting with high probability using proportional to N evaluations when t is unknown.If the answer is known to be either 0 or t0, certainty is achieved with proportional to N/t0 evaluations.Source: §1 · p. 4

2 Quantum amplitude amplification

Amplitude amplification boosts a quantum algorithm’s success amplitude through repeated applications of a unitary iterate, reducing expected search cost from 1/a to proportional to 1/√a. When a is known, modified iterations can achieve certainty; when unknown, QSearch preserves the quadratic speedup.

2 Quantum amplitude amplification

  • Amplitude amplification replaces repeated probability boosting with amplitude boosting, requiring approximately 1/√a repetitions rather than 1/a.The construction assumes A makes no measurements so that A^-1 is available.Source: §2 · p. 5
  • The iterate Q acts within the two-dimensional subspace spanned by the good and bad components of A|0⟩, rotating success probability to sin^2((2m + 1)θ_a).The good and bad projections form a stable subspace under Q.Source: §2 · pp. 5–7
  • When a is known, choosing m from θ_a yields success probability at least max(1 − a, a) with Θ(1/√a) applications of A and A^-1.This improves the expected cost over the classical 1/a repetition strategy.Source: §2 · p. 7
  • For the unique-solution black-box problem, Grover’s algorithm is amplitude amplification with A equal to the Walsh-Hadamard transform and initial success probability 1/N.The resulting measurement probability is at least 1 − 1/N after the prescribed number of iterations.Source: §2 · p. 8
  • When a is unknown, QSearch uses exponentially increasing iteration ranges and finds a good solution in expected Θ(1/√a) applications when a > 0.If a = 0, QSearch runs forever.Source: §2 · pp. 8–10

2.1 Quantum de-randomization when the success probability is known

  • With known a, phase-modified final iterations can eliminate the bad component and produce a good solution with certainty using Θ(1/√a) applications.The phase choices make the final state orthogonal to the bad component.Source: §2.1 · pp. 11–12

3 Heuristics

The paper embeds classical probabilistic heuristics into amplitude amplification rather than treating search as uniform guessing. For a broad family of heuristics, this gives a quantum algorithm whose expected performance follows the heuristic’s success distribution with quadratic amplification.

3 Heuristics

  • Amplitude amplification remains useful for search problems with classical heuristics by incorporating those heuristics into the quantum procedure.The goal is a quadratic speedup compared with the corresponding classical heuristic.Source: §3 · pp. 12–13
  • A heuristic maps a function and random seed to a candidate, and is efficient when its success probability exceeds uniform random guessing.For f, this compares h_f/|R| with t_f/|X|.Source: §3 · p. 13
  • The heuristic guarantee is distributional: some individual functions may have small h_f, even though repeated seeded use can increase their solution probability.The expectation is taken over functions under a fixed distribution.Source: §3 · p. 13
  • Theorem 6 states that if heuristic G solves randomly drawn functions from distribution D in expected time T classically, quantum search finds a solution in the corresponding amplified expected time bound.The construction embeds G into the predicate used by QSearch and makes the heuristic reversible when necessary.Source: §3 · pp. 13–14

4 Quantum amplitude estimation

This section develops quantum amplitude-estimation methods for approximate and exact counting, formulating the task through the good-state probability and providing explicit guarantees. It presents Fourier-based algorithms, boundary and promised-case procedures, and an exact counting method with near-optimal query complexity and logarithmic space.

4 Quantum amplitude estimation

  • For approximate counting, choosing A as W or F_N gives a = t/N, so an estimate of a directly yields an estimate of the number t of solutions.The formulation applies to N that is or is not a power of 2, using the corresponding preparation transformation.Source: §4 · pp. 14–15, Algorithm( Est · p. 20
  • Amplitude estimation estimates a, the probability of measuring a good state, by estimating the phase angle associated with Q's eigenvalues.The amplitudes oscillate sinusoidally under Q, with a = sin^2(θ_a); Fourier analysis or eigenvalue estimation recovers θ_a and hence a.Source: §4 · pp. 14–15

Algorithm( Est

  • The amplitude-estimation algorithm Est uses exactly M evaluations of f, with success probability at least 8/π² for k=1 and greater than 1−1/2^(k−1) for k≥2, and certainty when a=0 or when a=1 and M is even.It estimates θ_a, whose distance bounds translate via Lemma 7 into bounds on |ã−a|.Source: Algorithm( Est · pp. 19–20
  • The counting algorithm Count inherits the amplitude-estimation guarantees for t, including stated success probabilities and certainty when t is 0 or, for even M, N.Its real-valued output can be rounded to an integer for subsequent counting algorithms.Source: Algorithm( Est · p. 21

Algorithm( Basic

  • BasicCount obtains a relative-error estimate without prior knowledge of t by increasing the estimation scale until a nonzero result appears, then refining with a scale proportional to 1/(εL).The theorem provides a success guarantee and an expected evaluation complexity, but the supplied passage omits the displayed formulas.Source: Algorithm( Est · p. 21, Algorithm( Basic · p. 22
  • For a promise that t is either 0 or t0, a quantum algorithm determines the case with certainty and, when t=t0, outputs a random solution using Θ(·) evaluations of f.The supplied excerpt truncates the argument inside the asymptotic expression.Source: Algorithm( Basic · p. 23

Algorithm( Exact

  • ExactCount first obtains a rough estimate of t, chooses M from it, and then achieves |t′−t|<1 with high probability so rounding returns the exact integer t.Theorem 17 gives an expected evaluation complexity, but its displayed asymptotic expression is truncated in the supplied passage.Source: Algorithm( Exact · p. 24
  • The exact counting algorithm is optimal up to a constant factor and uses space only linear in log(N).Its analysis establishes exact recovery of t under the stated estimation guarantee.Source: Algorithm( Exact · p. 24
  • A lower bound shows that any high-probability quantum algorithm deciding whether |f^-1(1)| ≤ t requires at least the exact algorithm’s query-order complexity.Thus the exact counting procedure matches the lower bound up to a constant factor.Source: Algorithm( Exact · p. 25
  • Repeated Grover search can also perform exact counting, but constant success requires repeating until log(N) failures and incurs Θ(t) additional quantum memory.The memory requirement is described as prohibitive.Source: Algorithm( Exact · p. 25

5 Concluding remarks

The paper generalizes Grover-style search through amplitude amplification, extends quadratic speedups beyond unique-solution black-box search, and develops amplitude estimation for counting. Its counting algorithms are optimal in several error models, while genuinely structure-exploiting quantum search remains open.

Known solution counts

  • When the number of solutions is known to be either 0 or t0, the algorithm distinguishes the cases with certainty in O(√(N/t0)) queries and exhibits a solution when one exists.The best classical worst-case bound is N−t0+1 queries, so the improvement can exceed quadratic speedup when t0 is large.Source: §5 · p. 26

Heuristic search

  • The quadratic speedup persists beyond the black-box model when additional information supports efficient classical heuristics within the technique’s scope.The paper also states that it can amplify the success probability of classical and quantum search algorithms.Source: §5 · pp. 26–27

Counting

  • Quantum algorithms for counting are proven optimal up to a multiplicative constant across several error models and are often quadratically faster than the best known classical algorithms.For relative error ε, the quantum algorithm is quadratically faster for fixed ε and improves further when ε is not constant.Source: §5 · pp. 26–27

Amplitude amplification

  • Amplitude amplification finds a solution in expected O(1/√a) evaluations, or O(1/√a) in the worst case when a is known.This applies even when the solution is not unique or the number of solutions is unknown.Source: §5 · pp. 26–27

Amplitude estimation

  • Amplitude estimation efficiently estimates a quantum search algorithm’s success probability a and generalizes classical solution-count estimation.The paper applies this technique to approximate counting.Source: §5 · p. 27

Open problem

  • The paper leaves open whether quantum algorithms can exploit search or counting structure in a genuinely quantum way rather than applying amplitude amplification or estimation to a classical heuristic.Shor’s factoring algorithm is identified as an example of such structure exploitation in another setting.Source: §5 · p. 28

Counting

The paper combines Basic Count components to obtain an optimal approximate-counting algorithm. The stated theorem covers relative-error estimation with a success guarantee, including exact outputs when all elements are good or all are bad.

Counting

  • Combining Basic Count components yields an optimal algorithm for approximate counting.Optimality follows from Corollary 1.2 and Theorem 1.13 of Nayak and Wu.Source: Counting · p. 28
  • Theorem 18 gives a relative-error estimate of the number of solutions using an expected number of evaluations of f specified by the theorem.The supplied theorem statement fragments identify the success-probability and query-complexity guarantees but do not preserve their full formulas.Source: Counting · p. 28
  • When t=0 or t=N, the algorithm outputs the exact count with certainty.The approximate-counting setup assumes εN>1/3 because smaller instances reduce to exact counting.Source: Counting · p. 28
  • The algorithm’s construction approximates the different terms in Equation 17 and uses these estimates to assemble the counting procedure.The text notes that the resulting cost parameter S′ is in Θ(S), where S is defined in Theorem 18.Source: Counting · p. 29

Algorithm( Approx

The approximate-counting algorithm estimates auxiliary quantities, combines them through a minimum choice, and then applies Count with the resulting iteration parameter. Its overall success probability exceeds 2/3 and its expected query cost is O(S′).

Algorithm( Approx

  • The procedure first estimates auxiliary quantities L1 and L2, then uses M=min{M1,M2} to determine the final Count iteration parameter.The steps approximate the terms appearing in Equation 17 and select the smaller of two candidate parameters.Source: Algorithm( Approx · p. 29
  • The estimates for L1 and L2 are designed to satisfy their required bounds with high probability while keeping their expected evaluation costs within O(S′).The construction estimates the square root of the bad-output probability when determining L2.Source: Algorithm( Approx · pp. 29–30
  • The first candidate M1 satisfies its target bound with probability at least 0.952 and has expected size of the stated order.The second candidate M2 satisfies its corresponding bound with probability at least 0.95.Source: Algorithm( Approx · p. 30
  • After taking the minimum, M exceeds the required threshold with probability at least 0.953 and has expected value O(S′).The analysis uses that the expected minimum of two random variables is at most the minimum of their expectations.Source: Algorithm( Approx · p. 30
  • Applying Count with iteration parameter ⌈10πM⌉ produces a relative-error estimate with overall success probability greater than 2/3 and expected query complexity O(S′).The final success bound combines the probability of obtaining a suitable M with the conditional Count guarantee.Source: Algorithm( Approx · p. 31
Loading quant-ph/0005055v1…