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
3
votes
0answers
23 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 ...
2
votes
3answers
100 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 ...
2
votes
0answers
47 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 ...
2
votes
1answer
57 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$ ...
2
votes
1answer
22 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
2answers
25 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 ...
2
votes
0answers
20 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
1answer
30 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 ...
2
votes
1answer
62 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 ...
2
votes
1answer
67 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 ...
0
votes
0answers
22 views

How exactly does a chaotic amplitude amplifier work?

In this link (the bottom presentation) is described an application of Grover's algorithm for 3SAT (and a possible quantum version of Shoning's algorithm for 3SAT). I can find my way through the ...
1
vote
0answers
27 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. ...
7
votes
1answer
250 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 ...
4
votes
3answers
152 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 ...
5
votes
0answers
60 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 ...
1
vote
1answer
162 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 ...
2
votes
1answer
45 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 ...
3
votes
1answer
165 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 ...
3
votes
2answers
54 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 ...
2
votes
3answers
152 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 ...
3
votes
2answers
80 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 ...
2
votes
1answer
258 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 ...
3
votes
0answers
58 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 ...
6
votes
1answer
107 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 (...
7
votes
2answers
585 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 ...