For questions about the amplitude-amplitude algorithm. Do NOT use for general Grover's algorithm related question. Amplitude amplification is a technique in quantum computing which generalizes the idea behind 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 and independently rediscovered by Lov Grover in 1998. (Wikipedia)
Questions tagged [amplitude-amplification]
86 questions
10
votes
1 answer
Preparing a quantum state from a classical probability distribution
Suppose I have a black-box unitary $U_p$ which is described as follows: given a finite probability distribution $p:\{1,\ldots,n\}\rightarrow \mathbb{R}_{\geq0}$, where $\sum_{x=1}^n p(x)=1$, the action of the black box on a basis is given by…
Condo
- 2,196
- 7
- 31
8
votes
2 answers
What is the difference between amplitude amplification, amplitude estimation, and phase estimation?
I'm confused about the difference among Amplitude amplification (AA) , phase estimation (PE), and Amplitude Estimation.
I thought I understood AA and PE somewhat but when I heard the amplitude estimation and the circuit looked so similar to phase…
John Parker
- 1,181
- 6
- 15
7
votes
2 answers
The relationship between problem structure and exponential speedups under the query model
What problem structure(s) are required to admit an exponential speedup in the universal quantum model of computation under the query model?
Intuitively, it would seem that much of the benefit of the quantum model, as is often suggested, is due to…
Greenstick
- 1,086
- 8
- 23
7
votes
1 answer
Computing of the action of the amplification operator $\mathbf Q$ over $|\Psi_i\rangle$ in the quantum amplitude amplification algorithm
$\newcommand{\Q}{\mathbf{Q}}\newcommand{\S}{\mathbf{S}}\newcommand{\A}{{\mathcal A}}\newcommand{\H}{\mathcal H}$In the quantum amplitude amplification algorithm, as explained in Brassard et al. 2000 (quant-ph/0005055), the unitary performing the…
glS
- 27,510
- 7
- 37
- 125
7
votes
2 answers
How to increase the probability of successful measurement to find out the largest amplitude?
I have built a state
$$A|0\rangle = |\Psi \rangle = \sum _n c_n |n\rangle$$
Where $A$ is a circuit.
And I need to known, where is the largest $|c_n|$.
I find out that, I can simply do many measurements to find out which one is the largest.
However,…
Alexis
- 203
- 1
- 4
7
votes
2 answers
In amplitude amplification, how are the amplitudes of qubits changed?
I am relatively new to quantum computing and I feel like I don't fully understand the power of quantum computing due to a lack of understanding of how amplitude amplification works.
What is confusing me is that the amplitude of the qubit is the…
Eric Li
- 133
- 6
7
votes
1 answer
BHT algorithm implementation
Summary of Method
Amplitude Amplification Summary
The BHT algorithm uses amplitude amplification, a nice generalisation of Grover's algorithm, where there is a subset $G\subset X$ of good elements in the orthonormal basis $X$. Below is a brief…
Chris Long
- 213
- 1
- 7
6
votes
0 answers
Is amplitude estimation optimal?
Amplitude estimation requires $O(1/\epsilon)$ measurements if we want to estimate an amplitude to absolute precision $\epsilon$. Is this optimal? Why can't we do better than this?
I'm trying to see if there's an explanation in the literature but I'm…
confusion
- 195
- 8
5
votes
3 answers
What is an exact quantum algorithm?
In the literature, there is a distinction between exact and error-bounded quantum algorithms. The former must solve a problem with a zero probability of error, whereas the latter only needs to bound the probability of error away from some constant…
TWal
- 246
- 1
- 4
5
votes
1 answer
What is the difference between Grover's and Amplitude Amplification?
I'm confused about what precisely is the difference between Grover's Algorithm and Amplitude Amplification. I've heard some sources say they are different algorithms and others say they are the same thing. As I currently understand it,
In Grover's…
Paradox
- 337
- 1
- 7
5
votes
1 answer
Is it possible to tune the amplitude of superposition generated by Hadamard gates?
I had a question earlier about generating the superposition of all the possible states: Here. In that case, we could apply $H^{\otimes n}$ to the state $|0\rangle^{\otimes n}$, and each state has the same amplitude in the superposition:…
ZR-
- 2,408
- 9
- 24
4
votes
2 answers
Is there a quantum algorithm allowing to efficiently determine the state with the highest probability of occurring?
Is there a quantum algorithm allowing to determine the state with the highest probability of occurring (i.e. highest square amplitude), more efficiently than repeatedly measuring and estimating a histogram?
splinter123
- 141
- 1
4
votes
3 answers
How to amplify a specific part of the quantum state
I understand that, according to amplitude amplification, I can amplify states according to a partition over the state space. However, suppose I want to amplify or de-amplify a specific portion of the state after putting it into a superposition,…
Woody1193
- 361
- 1
- 10
4
votes
1 answer
Modified hadamard test with $O(\frac{1}{\epsilon})$ samples using amplitude estimation
On the wikipedia entry for the Hadamard test, it mentions the test can be used with amplitude estimation to only require $O(\frac{1}{\epsilon})$ samples, rather than $O(\frac{1}{\epsilon^2})$ samples. The wikipedia entry cites…
android_developer
- 63
- 4
4
votes
0 answers
Grover / amplitude amplification with exponentially high success probability
All the references on Grover / Amplitude Amplification (AA) (Mike&Ike, wiki, Lin Lin lecture notes, etc.) give a recipe for preparing the desired state (or amplifying the state) with probability $\gamma=O(1)$. Can one improve this result by provably…
mavzolej
- 2,271
- 9
- 18