Amplitude amplification

Amplitude amplification

Amplitude amplification is a technique in quantum computing which generalizes the idea behindthe Grover's search algorithm, and gives rise to a family of
quantum algorithms.It was discovered by Gilles Brassard and
Peter Høyer in 1997,cite journal
author=Gilles Brassard, Peter Høyer
title=An exact quantum polynomial-time algorithm for Simon's problem
journal=Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems
publisher=IEEE Computer Society Press
] and independently rediscovered by Lov Grover in 1998.cite journal
author=Grover, Lov K.
title=Quantum Computers Can Search Rapidly by Using Almost Any Transformation
journal=Phys. Rev. Lett.

In a quantum computer, amplitude amplification can be used to obtain aquadratic speedup over several classical algorithms.


The derivation presented here roughly follows the one given incite journal
author=Gilles Brassard, Peter Høyer, Michele Mosca, Alain Tapp
title=Quantum Amplitude Amplification and Estimation
] .Assume we have an N-dimensional Hilbert space mathcal{H}representing the state space of our quantum system, spanned by theorthonormal computational basis states mathbf{B} := { |x angle }_{x=0}^{N-1}.Furthermore assume we have a Boolean function:chi:mathbb{Z} o {0,1}.chi can be used to partitionmathcal{H} into a direct sum of two mutually orthogonal subspaces,:the "good" subspace mathcal{H}_1 = operatorname{span}{|x angle in mathbf{B} ;|; chi(x) = 1}, and:the "bad" subspace mathcal{H}_0 = operatorname{span}{|x angle in mathbf{B} ;|; chi(x) = 0}.

Given a (normalized) state vector |psi angle in mathcal{H}, we canuniquely decompose it as :|psi angle = a |psi_1 angle + b |psi_0 angle,where|psi_1 angle and |psi_0 angle are thenormalized projections of |psi angle into thesubspaces mathcal{H}_1 and mathcal{H}_0,respectively, and 0 < a < 1. This decomposition defines a two-dimensional subspacemathcal{H}_psi, spanned by the vectors|psi_0 angle and |psi_1 angle. The probability of finding the system in a "good" state when measuredis a^2. Furthermore we have a^2+b^2=1.

Define a unitary operatorQ(psi, chi) := -S_psi S_chi ,!,where:S_psi = I - 2|psi angle langlepsi|quad and:S_chi |x angle = (-1)^{chi(x)} |x angle.The action of this operator on mathcal{H}_psi is given by:Q |psi_0 angle = -S_psi |psi_0 angle = (1-2a^2)|psi_0 angle +2ab|psi_1 angle and:Q |psi_1 angle = S_psi |psi_1 angle = -2ab|psi_0 angle+(1-2a^2)|psi_1 angle.By defining heta := arcsin(a) ,!,0 < heta < pi/2 ,!, we can clearly see that in this subspace Qcorresponds to a rotation by the angle 2 heta,!::Q = egin{pmatrix}cos(2 heta) & sin(2 heta)\-sin(2 heta) & cos(2 heta)end{pmatrix}.

Applying Q(psi, chi),! repeatedly on the state|psi anglegives:Q^n |psi angle = cos((2n+1) heta) |psi_0 angle +sin((2n+1) heta) |psi_1 angle,rotating the state between the "good" and "bad" subspaces.After n applications the probability of finding thesystem in a "good" state is sin^2((2n+1) heta),!. The probability is maximized if we choose:n = leftlfloorfrac{pi}{4 heta} ight floor.Up until this point each application of Q increases the amplitude of the "good" states, hencethe name of the technique.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • amplification — [ ɑ̃plifikasjɔ̃ ] n. f. • XIVe; lat. amplificatio 1 ♦ Vx Agrandissement, accroissement. ♢ (1801) Opt. Grossissement. Techn. Opération consistant à accroître une amplitude ou une puissance à l aide d un amplificateur; valeur de cet accroissement… …   Encyclopédie Universelle

  • Amplitude-shift keying — (ASK) is a form of modulation that represents digital data as variations in the amplitude of a carrier wave.The amplitude of an analog carrier signal varies in accordance with the bit stream (modulating signal), keeping frequency and phase… …   Wikipedia

  • Amplitude modulation — Passband modulation v · d · e Analog modulation AM · …   Wikipedia

  • amplification en amplitude — amplitudės stiprinimas statusas T sritis automatika atitikmenys: angl. amplitude gain vok. Amplitudenverstärkung, f rus. усиление по амплитуде, n pranc. amplification en amplitude, f …   Automatikos terminų žodynas

  • amplitude gain — amplitudės stiprinimas statusas T sritis automatika atitikmenys: angl. amplitude gain vok. Amplitudenverstärkung, f rus. усиление по амплитуде, n pranc. amplification en amplitude, f …   Automatikos terminų žodynas

  • amplification — noun a) the act, or result of amplifying, enlarging, extending or adding to b) the act, or result of independently increasing some quantity, especially voltage, power or current See Also: ample, amplifiable, amplifier, amplificatory …   Wiktionary

  • amplitude — noun a) The measure of somethings size, especially in terms of width or breadth; largeness, magnitude. b) The maximum absolute value of the …   Wiktionary

  • Chirped pulse amplification — Diagramatic scheme of chirped pulse amplification. Chirped pulse amplification (CPA) is a technique for amplifying an ultrashort laser pulse up to the petawatt level with the laser pulse being stretched out temporally and spectrally prior to… …   Wikipedia

  • Algorithme de Grover — En informatique quantique, l´algorithme de Grover est un algorithme de recherche, permettant de rechercher un ou plusieurs éléments qui répondent à un critère donné parmi N éléments non classés en temps proportionnel à et avec un espace de… …   Wikipédia en Français

  • Квантовый алгоритм — Квантовый алгоритм  это алгоритм, предназначенный для выполнения на квантовом компьютере. Квантовый алгоритм представляет собой классический алгоритм, который задает последовательность унитарных операций (гейтов, или вентилей) с указанием,… …   Википедия