Questions tagged [amplitude-amplification]
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)
61
questions
0
votes
0
answers
14
views
+50
Which applications of quantum singular value transformation use block-encodings in apriori unknown bases?
Quantum singular value transformation (QSVT) algorithm allows performing polynomial transformations on matrices that are block-encoded in a unitary. Typically, block encoding is assumed to be 'the top-...
- 1,375
1
vote
1
answer
220
views
Grover's algorithm for complex phases
Grover's algorithm traditionally inputs a phase oracle, $U_\omega$ such that $U_\omega | x \rangle = (-1)^{f(x)} | x \rangle$. The task is to find some $x$ such that $f(x) = 1$. In other words, the ...
- 227
1
vote
0
answers
26
views
Quantum Amplitude Estimation formulations (Brassard et. al. vs Montanaro)
I am puzzled on the relation between the two approaches (old and new).
(a) The original approach of QAE as described by Brassard et. al. uses two operators to form ${Q}$:
$$
{Q}={A} {S}_0 {A}^{\dagger}...
- 565
0
votes
0
answers
44
views
Using Quantum Amplitude Estimation to find integral
I am trying to use the Quantum Amplitude Estimation (QAE) algorithm to find the numerical integral of sin^2(x) in the range ...
- 515
2
votes
0
answers
35
views
Converting from amplitude encoding to basis encoding
The question is inspired from Preparing a quantum state from a classical probability distribution which shows how basis encoding $\frac{1}{\sqrt n}\sum_{x=0}^{n-1}|x\rangle|p(x)\rangle$ may be ...
- 31
1
vote
0
answers
27
views
Amplitude amplification when an exact input state is unknown but amplitude is known
Let initial quantum state be $|s\rangle = a|0\rangle|d_a\rangle + b|1\rangle|d_b\rangle$. I know value of amplitude $a$, but I do not know $|d_a\rangle$ and $|d_b\rangle$. These unknown states can be ...
- 31
1
vote
0
answers
28
views
An improved search algorithm based on weak value amplification?
I am having difficulties understanding this paper (arXiv:1910.12390), so asking this question.
As far as what I see from mathematics of this paper, all improvements over Grover's search disappear when ...
- 11
1
vote
1
answer
46
views
In the quantum mean computation circuit, how to apply the controlled rotation to the extra qubit?
I'm trying to implement quantum mean computation via amplitude estimation, as suggested in Example 8.3.5 in Kaye, LaFlamme, Mosca. I wonder about the actual circuit to accomplish this. This previous ...
- 873
0
votes
0
answers
68
views
How to derive phase angles for Fixed-Point Amplitude Amplification
I'm reading seminal paper of Fixed-point quantum search with an optimal number of queries(https://arxiv.org/abs/1409.3305).
My understanding is that by properly setting phase angles of $\alpha_i, \...
- 53
7
votes
2
answers
126
views
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 ...
- 173
1
vote
1
answer
63
views
Can one obliviously reflect about the *initial* state in fixed-point amplitude amplification?
It is normal to extend fixed-point amplitude amplification to an oblivious version, i.e.,
$1 - (1-e^{i \beta})|t\rangle \langle t | \rightarrow 1 - (1-e^{i \beta}) 1 \otimes |0\rangle \langle 0|$, ...
- 150
0
votes
1
answer
99
views
For the superposition state of a composite system, how to use the quantum amplitude amplification algorithm to simultaneously amplify several of them
For the superposition state $|\Phi \rangle =\frac{1}{16}\sum\limits_{i=0}^{15}{(|i\rangle |{{a}_{i}}\rangle )}$ (The second quantum system ${a}_{i}$ is not necessarily all orthogonal) of a composite ...
- 390
1
vote
0
answers
67
views
Amplitude Amplification applied to HHL Algorithm
I’m trying to understand and implement the amplitude amplification algorithm described in the HHL paper. I’m using the cirq implementation of the HHL algorithm as my starting point.
I have a couple of ...
- 11
3
votes
1
answer
146
views
Qiskit: Get number of iterations for Iterative Amplitude Estimation
Trying to count the number of uses of my circuit $A$ in Grover iterate circuit $Q= -AS_0A^{\dagger}S_x$.
However, Qiskit's amplitude estimation algorithms such as IAE or FAE
accept only precision ...
- 341
1
vote
1
answer
85
views
Reflection operator in amplitude amplification for block encoding
I am trying to figure out equation (2.33) here.
Given that
\begin{gather}
U_{\psi_0}|{0^m}\rangle|{0^n}\rangle=\sqrt{p_0}|{0^m}\rangle|{\psi_0}\rangle+\sqrt{1-p_0}|{\perp}\rangle,\\
(\Pi\otimes I_n)|{\...
- 1,740
1
vote
0
answers
61
views
Using rotation gates instead of Grover
I have a conceptual question about Grover's algorithm. In the textbook case, we always assume to have an oracle that singles out the correct states by giving them a negative phase. Then, we use phase ...
- 43
3
votes
0
answers
39
views
Why does QAA need QPE to estimate the probability of the good state?
I have some trouble understanding some aspects of the Quantum Amplification Algorithm (QAA). I am using this reference for the following discussion (section 4).
The QAA applies a certain operator $Q :=...
- 565
3
votes
1
answer
142
views
Amplitude amplification with or without ancilla state
I am trying to understand amplitude amplification and I am able to find two formulations (almost identical).
(A) No ancilla
Usually, and what I do understand quite well, is that you start with the ...
- 565
2
votes
0
answers
45
views
Amplifying states using partial information
Assume we have an initial state $(H^{\otimes n}|0\rangle)|0\rangle = \frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}|i\rangle|0\rangle$ in two $n$-qubit registers (let $N=2^n$). Then we feed this state through a ...
- 43
0
votes
1
answer
114
views
Using Grover on entangled states
I am trying to implement Grover's algorithm on an entangled state. The idea is that I will have a state $\sum_x\alpha_x|f(x),x\rangle$ and I want to measure the $x$, for which $f(x)=0$. Note that $f$ ...
- 43
2
votes
1
answer
603
views
Oblivious Amplitude Amplification
I've been looking for the OAA paper but I've been unsuccessful in finding it. (so any links will also be helpful)
My question is essentially this, given the state:
$$\vert 0good \rangle + \vert 1bad \...
- 500
3
votes
1
answer
203
views
In generals Amplitude Amplification algorithm, the initial state does not need to attain equally superposition?
In the beginning of this paper about amplitude amplification algorithm, the author stated the conventions of amplitude amplification which I quoted the important part for your convenience as follows:
...
- 2,772
2
votes
0
answers
100
views
Understanding Qiskit 0.32 's $\texttt{AmplificationProblem()}$ behaviour
This is related to my previous question.
To apply amplitude amplification in Qiskit, one needs to use AmplificationProblem() or ...
- 448
1
vote
2
answers
111
views
Setting the $\texttt{state_preparation}$ for $\texttt{AmplificationProblem()}$ in the scope of Grover's algorithm
I am having trouble setting the state_preparation parameter of AmplificationProblem() from ...
- 448
3
votes
1
answer
124
views
Amplifying entangled qubits
Suppose I have a three-qubit entangled state of the following form:
$$
|00\rangle|\psi_1\rangle + |01\rangle|\psi_2\rangle + |10\rangle|\psi_3\rangle + |11\rangle|\psi_4\rangle
$$
I refer to the ...
- 2,695
2
votes
0
answers
51
views
How to understand picking a random subcube in the Aaronson/Ambainis spatial search algorithm?
I am referring to the Quantum Search of Spatial Regions paper.
I must confess that the paper itself is a bit heavy for my level of mathematical fluency. Trying to understand it nevertheless and having ...
- 21
5
votes
1
answer
318
views
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 ...
- 183
2
votes
1
answer
121
views
Noise-induced amplitude amplification?
I wanted to share some results from an experiment which I find thought were deeply surprising.
The basic idea is to prepare a superposition in a main register then conditionally apply lots of random ...
- 53
0
votes
0
answers
208
views
How does the amplitude amplification in Grover's algorithm work?
As the question says - how does the amplitude amplification in Grover's algorithm work?
I am fine with adding the negative phase on the winning state, but how does one generate the diffuser to ...
- 1
2
votes
0
answers
55
views
Managing memory while running a high depth circuit simulation (amplitude amplification) using Qiskit
I am running an instance of amplitude amplification using Qiskit (v 26) on Google Colab.
The circuit is approximately 17 qubits in space and $O(ck)$ in depth where $k \in \left \{1,2,3....,22 \right \...
2
votes
1
answer
157
views
Amplitude Amplification for searching $|0\rangle$ in an unknown state
For one known (invertible) function that does:
$$f:H^{\otimes 2n}\times H^{\otimes 2n}:|x⟩|0⟩\mapsto|x⟩|y⟩$$
I want to find a similar (invertible) function that does:
$$g:H^{\otimes 2n}\times H^{\...
- 81
3
votes
1
answer
168
views
Combining Amplitude Amplification with HHL
I'm recently learning about how to apply Grover search techniques to other places. An example I've come across is to amplify the probability of measure a $\lvert 1 \rangle$ of the ancilla qubit in HHL ...
- 31
2
votes
1
answer
88
views
Manipulating the amplitude of state based on the state information
In the past, I thought I have seen quantum circuits/algorithm techniques to change the amplitude of state based on the state?
$\lvert \psi \rangle = \sum_x \ C_x \lvert x \rangle$, here $C_x$ is just ...
- 981
1
vote
0
answers
158
views
How to load time-series stock data into quantum amplitude estimation
Now I got some time-series data as showing example below:
I have spent a period of time realizing the QAE from qiskit, and I found that the tutorial used uncertainty model to reproduce data, while I ...
- 33
0
votes
1
answer
116
views
In the amplitude amplification algorithm in Nielsen and Chuang's book, why is the error probability $M/N$?
I was able to follow til the yellow-highlighted sentences, which seems to be important to understand. Why M/N is the probability of error? If so 1 - M/N would be the probability of success?
- 981
5
votes
2
answers
401
views
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 ...
- 981
5
votes
1
answer
178
views
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 ...
- 2,348
3
votes
0
answers
52
views
Is it possible to nest quantum Markov chain Monte Carlo, mean and minimum algorithms?
Montanaro A. 2015 Quantum speedup of Monte Carlo methods makes the following claim of an algorithm to estimate the mean output $\mu$ of an arbitrary algorithm A, with near-quadratic speedup over ...
- 397
2
votes
3
answers
444
views
Computing the CDF with QAE in Qiskit
I want to load a lognormal distribution and then use an IntegerComparator to flip a qubit ($|0\rangle$ to $|1\rangle$) if its value is less than a threshold. Then I want to use an Quantum Amplitude ...
- 23
2
votes
0
answers
163
views
A question about Grover's paper "Fixed-Point Quantum Search"
I am reading Grover's paper "Fixed-Point Quantum Search," (arXiv version with a different name) which improves on his earlier quantum research algorithm. However, I'm having difficulty in ...
- 291
2
votes
1
answer
115
views
Is Grover's algorithm only applicable to a pure state?
I've been trying to perform Grover's algorithm on entangled states, e.g. $|00\rangle + |11\rangle$. However, the algorithm apparently doesn't seem to amplify the amplitude of the state $|11\rangle$ ...
- 171
2
votes
1
answer
66
views
In amplitude amplification, isn't the speedup hindered by the realization of $S_o$?
In brassard et al. Amplitude Amplification work, they define the Q operator as
$$\mathbf{Q} = -AS_{o}A^{-1}S_{\chi}$$
where $S_{o}$ is an operator which flips the sign of the $|0 \rangle$ state.
Which ...
2
votes
2
answers
39
views
Qiskit implementation of Brassard Amplitude implementaion's Q operator
In Brassard's et al. work, the $Q$ operator is defined as
$$ Q =-\mathcal{A}\mathcal{S_0}\mathcal{A}^{-1}\mathcal{S_\chi}$$
I was wondering how is the negative sign at the leftmost side implemented ...
3
votes
0
answers
50
views
Amplitude estimation over subspace of problem
I've been searching about quantum amplitude estimation techniques and read that it is customary to use an extra qubit to separate good and bad states using algorithm $A$ as
$$ A|{0} \rangle^{\otimes^{...
1
vote
1
answer
98
views
Alternative Grover's Diffuse Operator [duplicate]
I was wondering if there is any good references where I could read to understand the construction of Unitary Operators such as the Diffuse Operator in Grover's Algorithm.
I am looking to build my own ...
3
votes
2
answers
132
views
Lemma 1 in the paper by Brassard, Hoyer, Tapp (1998) on Quantum counting
In the paper by Brassard, Hoyer, Tapp (1998) on Quantum Counting we have the following expression for the state:
$$|Y\rangle =\sum_{i\in\mathbb{Z}}x_i|i\rangle |Y_i\rangle.$$
Now we have a quantum ...
- 301
3
votes
1
answer
319
views
How to define Q-operator in Quantum Amplitude Estimation
I'm trying to implement a circuit for Quantum Amplitude Estimation in Qiskit using elementary gates.
I have created the circuit that represent my algorithm $A$ but now from the theory I know that I ...
- 91
1
vote
0
answers
82
views
Amplitude amplification for known state but unknown amplitude
I have a circuit that prepares a state $|s\rangle$ which is a superposition of the basis states $$\sum_{x=0}^{2^{n-1}}\alpha_x|x\rangle$$
with amplitude $\alpha_x$ for a circuit of $n$ qubits. ...
9
votes
1
answer
877
views
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 ...
- 1,771
5
votes
3
answers
257
views
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 ...
- 246