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)

Filter by
Sorted by
Tagged with
1 vote
1 answer
35 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 ...
user avatar
  • 75
1 vote
0 answers
13 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)|{\...
user avatar
  • 1,478
1 vote
0 answers
44 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 ...
user avatar
  • 43
3 votes
0 answers
23 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 :=...
user avatar
  • 483
2 votes
1 answer
66 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 ...
user avatar
  • 483
2 votes
0 answers
33 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 ...
user avatar
  • 43
0 votes
1 answer
57 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$ ...
user avatar
  • 43
2 votes
1 answer
236 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 \...
user avatar
  • 196
3 votes
1 answer
144 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: ...
user avatar
  • 2,458
2 votes
0 answers
60 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 ...
user avatar
  • 438
1 vote
2 answers
83 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 ...
user avatar
  • 438
3 votes
1 answer
88 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 ...
user avatar
  • 2,631
2 votes
0 answers
44 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 ...
user avatar
5 votes
1 answer
186 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 ...
user avatar
2 votes
1 answer
104 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 ...
user avatar
0 votes
0 answers
114 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 ...
user avatar
2 votes
0 answers
40 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 \...
user avatar
2 votes
1 answer
102 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^{\...
user avatar
3 votes
1 answer
97 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 ...
user avatar
2 votes
1 answer
68 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 ...
user avatar
1 vote
0 answers
113 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 ...
user avatar
0 votes
1 answer
93 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?
user avatar
5 votes
2 answers
267 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 ...
user avatar
4 votes
1 answer
128 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 ...
user avatar
  • 2,218
3 votes
0 answers
41 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 ...
user avatar
2 votes
3 answers
323 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 ...
user avatar
2 votes
0 answers
116 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 ...
user avatar
  • 291
2 votes
1 answer
99 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$ ...
user avatar
  • 139
2 votes
1 answer
55 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 ...
user avatar
2 votes
2 answers
33 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 ...
user avatar
3 votes
0 answers
40 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^{...
user avatar
1 vote
1 answer
64 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 ...
user avatar
3 votes
2 answers
120 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 ...
user avatar
  • 181
3 votes
1 answer
224 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 ...
user avatar
1 vote
0 answers
58 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. ...
user avatar
9 votes
1 answer
667 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 ...
user avatar
  • 1,512
5 votes
3 answers
197 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 ...
user avatar
  • 146
6 votes
1 answer
124 views

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 ...
user avatar
  • 1,024
1 vote
1 answer
469 views

Grover diffusion operator for a 3 qubit system

I want to make a three qubit system that marks the states where the last qubit is 0. I have made an oracle function but when I try to run the reflection the amplitudes are only higher than the others ...
user avatar
  • 139
2 votes
1 answer
67 views

Negating amplitude in amplitude amplification when second qubit is 0 not working

I have experimented a bit with Grover's Algorithm, and I wanted to search for the states $|00\rangle$ and $|10\rangle$. I tried making a Quantum Circuit, which looks like the one below, but measuring ...
user avatar
  • 139
5 votes
1 answer
410 views

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 ...
user avatar
  • 327
4 votes
2 answers
90 views

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 ...
user avatar
3 votes
3 answers
272 views

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 ...
user avatar
  • 321
3 votes
2 answers
105 views

Amplitude suppression

On contrary to amplitude amplification, can I do some reflection such that my marked states' probability will vanish (ideally become zero but if there are small residuals also acceptable)? In order to ...
user avatar
  • 395
2 votes
1 answer
294 views

Amplitude Estimation Algorithm — Lambda (Q) Operator

I'm working on an implementation of the algorithms described Brassard et al. in the following paper: arXiv:quant-ph/0005055v1. I managed to make the amplitude amplification cases working but I'm ...
user avatar
  • 354
3 votes
0 answers
65 views

Does Brassard's algorithm for calculating the mean make implicit assumptions on distribution?

In An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance Brassard presents a quantum algorithm for finding ...
user avatar
6 votes
1 answer
140 views

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 (...
user avatar
  • 18.7k
7 votes
2 answers
856 views

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 ...
user avatar
  • 133