6

To find the differences between them, you only need to know the aim of the problems. The aim of AA is to find the answers from unstructured data(or more directly, amplify the probability of the right answer). The aim of PE is to find the phase, more specifically the $\phi$ in the book of Nielsen: Suppose a unitary operator $U$ has an eigenvector $\mid u\...


5

Grover's algorithm is a special case of the amplitude amplification algorithm where the number of good entries $G$ in the $N$-item database is $1$. In a nutshell: In the Grover's algorithm Wiki page that you linked, the keyword is "unique". Given $f:\{0, \ldots, N-1\} \to \{0, 1\}$ such that $f(x) = 1$ for exactly one $x$ (say $\omega$), Grover's ...


4

If you know, in advance, that the state you want to deamplify is specifically $|000\rangle$, there are a couple of strategies that you could follow. For example, introduce an ancilla and perform the multi-controlled not, targeting the ancilla, where it is controlled off every qubit in the original state being in the $|0\rangle$ state. So, you'd be doing $$ \...


4

You've understood it correctly. The whole point of amplitude amplification is that it generalises Grover's Search so that it works with non-uniform superpositions. One of the key applications of this is for effectively generating non-linear function applications (such as in the HHL algorithm) where you can produce an operation $$ |x\rangle|0\rangle\mapsto |x\...


3

Yes indeed you can! First a simple example: if you want to increase all the amplitudes of the all the states that look like $|\cdot \cdot \cdot 1\rangle$ then you just need to apply an $R_y$ gate on the final qubit. If on the other hand you want to increase the amplitudes of the specific states $|0110\rangle$ and $|1001\rangle$ by specific amounts, then you ...


3

Suppose we have two quantum circuits, the first computes (or at least approximates) the classical $\sqrt{\cdot}$ function $$S|x\rangle|0\rangle=|x\rangle |\sqrt{x}\rangle,$$ while the second circuit $A$ computes (again could probably just approximate) the $\arccos(\cdot)$ function $$A|x\rangle|0\rangle=|x\rangle |\arccos(x)\rangle.$$ Lastly, suppose we have ...


3

The original Amplitude Estimation algorithm (Brassard et al., 2002) uses Phase Estimation. So, it is OK to notice the similarity between them. Other approaches, however, have emerged in recent years that do not use PE for Amplitude Estimation like this and this.


3

Any state $|\Psi\rangle$ can be decomposed using a two-dimensional subspace comprising marked and unmarked states, $$ |\Psi\rangle=\alpha|\Psi_m\rangle+\beta|\Psi_u\rangle. $$ Part of the assumption is that you have a marking oracle that acts as $$ |\Psi\rangle|0\rangle\rightarrow\alpha|\Psi_m\rangle|1\rangle+\beta|\Psi_u\rangle|1\rangle. $$ This is exactly ...


3

There are several different answers to your question, but let me give the answer that computer scientists will find most satisfying here. As it comes to implementing general unitary operators $U$, I would like to refer you to section 4.5 in the book "Quantum Computation and Information" by Nielsen and Chuang. They give a construction which allows one to ...


3

The trick here is to not calculate $\mathcal{A}^{-1}|\Psi\rangle$ at all, because it's insufficiently defined! Instead, look at $$ \mathcal{A}(\mathbb{I}-2|0\rangle\langle 0|)\mathcal{A}^{-1}=\mathbb{I}-2\mathcal{A}|0\rangle\langle 0|\mathcal{A}^{-1} $$ by the fact that $\mathcal{A}$ is unitary. Now, by definition, $$ \mathcal{A}|0\rangle=|\Psi_0\rangle+|\...


3

Only a partial answer, the Deutsch-Jozsa algorithm is an example of an exact algorithm. In my view, the algorithms differ exactly in how the answer is given. Either with probability 1 for exact algorithms, or with a bounded probability for approximate ones. I would say you cannot use amplitude amplification in exact algorithms, as this would imply that ...


3

The operation you're asking for is equivalent to postselection. You're trying to force a measurement result of the address register. If that were possible it would make BQP = PostBQP. There's no proof that they're not equal, but it would be very surprising. PostBQP can trivially solve NP complete problems (eg. imagine the state was $\sum_k |\text{IsSolution}(...


2

It seems that there is a missing $\mathrm{X}$ and $\mathrm{H}$ gates on qubit $q_2$. I used this Grover algoritm shape: Note 1: controlled $\mathrm{Z}$ is replaced by $\mathrm{CNOT}$ and Hadamards on both sides. Note 2: put your Oracle instead of dashed line. Note 3: you do not have to measure $q_2$.


2

EDIT: I completely misunderstood your question and thought that you were confused about what a negative amplitude means, and not about physical mechanisms. I'm leaving this up in case that actually was what you meant. whoops. For the implementation question, how a reflection is implemented physically depends on the qubit implementation you are using. I ...


2

The problem is that you have only two states in your database. So when you mark state $|00\rangle$ its amplitude is $-1$ while the other state has amplitued $1$ (note that I ignore normalization constants). Hence an average of amplitudes is zero. When you flip the amplitudes around the zero average, the amplitudes still have absoute value $1$. As a result, ...


2

Short answer: Check out qiskit.aqua.algorithms.amplitude_estimators.q_factory.QFactory which constructs $Q$ if you provide it with $A$. You can use the i_objective argument to specify the "good" state in $S_{\Psi_0}$. Long answer: The $S_0$ operation is flips the sign of the $|0\rangle$ state and leaves all the others in place. This can be ...


2

I asked basically the same question on CS stack exchange before this community was created. The answer is that the class of exact quantum algorithms has a name (EQP) but isn't very natural to study theoretically, because whether or not an exact algorithm can be executed depends entirely on the gate set that you have available, and moreover there's no ...


2

Say you want to factorise a large integer $N$. We know (inefficient) classical algorithms to do this, a naive example being: just check all combinations of smaller numbers until you find one that multiplies to $N$. You can make this into a quantum algorithm by simply converting each operation in your classical algorithm into a reversible one (there are ...


2

Where did the article say M/N is the probability of error? M/N in the article is only for the use of normalization. For example(2 qubits), after $H^{\otimes 2}$ acted on initial $\mid 0\rangle^{\otimes 2}$, the state becomes $\mid\psi\rangle\equiv1/2(\mid 00\rangle+\mid01\rangle+\mid10\rangle+\mid11\rangle)$ . If the answer is $| 01\rangle$, then the $\mid\...


2

It could have something to do with cross-talk and decoherence. By introducing the messy circuits, the other qubits are on idle as long as the messy circuits are being computed. Hence decoherence effects will certainly play a role here. As the qubits in the messy register are manipulated via randomized quantum gates, these manipulation can additionally have ...


2

You have to pass a circuit, but you can just remove the resets from your circuit with the initialize instruction as >>> from qiskit.circuit import QuantumCircuit >>> from qiskit.transpiler.passes import RemoveResetInZeroState >>> init = QuantumCircuit(3) >>> init.initialize([1, 0, 0, 0, 0, 0, 0, 0], init.qubits) >>&...


1

I think you've effectively answered this yourself in the question! The $1/\lambda_j$ coefficients are all rolled up into the $|\psi_1\rangle$. So you just do amplitude amplification to get the output $\approx |\psi_1\rangle|1\rangle$ which still contains the $1/\lambda_j$ terms because the relevant weights are the relative ones between the different $|\...


1

The matrix contains information about the vectors(states). To see this, the matrix form can be written as $U_{ij}=\langle i\mid U\mid j\rangle$ or the total form of $U$ mentioned by @Quantum Mechanic, i.e., $U=\sum_{ij}U_{ij}\mid i\rangle\langle j\mid$. To show it more vividly, the stabilizer code will be a good example. Another easier example is that: when ...


1

I had to exchange len(qr_state) with num_uncertainty_qubits in the code you posted # in run_ae_for_cdf ae_var = IterativeAmplitudeEstimation(state_preparation=state_preparation, epsilon=epsilon, alpha=alpha, objective_qubits=[num_uncertainty_qubits]) but then for me ...


1

I think it would be also useful to see your Quantum Circuit using %matplotlib inline and qc.draw('mpl') to see whether all gates are correctly connected. I had a similar problem with QAE and figured out by using this method that the order of qubits I tried to append the IntegerComparator onto was wrong. Cheers


1

I am also working with IterativeAmplitudeEstimation in qiskit. I was able to run QAE for 'Credit Analysis with Quantum Computing' as described in https://qiskit.org/documentation/tutorials/finance/09_credit_risk_analysis.html by preparing the quantum circuits from scratch. But when using the libraries as described on the page I got many errors (see below). I ...


1

No, not at all. Barenco et al.'s work is primarily saying that for certain specific gates (the multi-controlled phase gate, as required for $S_0$, being one), you can construct them in a time that is polynomial in $n$. Yes, the general case might require exponentially many, but not for every case, and it's the small number of non-exponential cases that we do ...


1

As per the description in Brassard paper page 5 " ... Operator Sx conditionally changes the sign of the amplitudes of the good states ....while the S0 operator changes the sign of the amplitude if and only if the state is the zero state |0>. ..." The amplitude is multiplied by eiƟ -> Sx(Ɵ=φ) and S0 (Ɵ=ϕ) .. as given in Theorem 4 further ...


1

The minus sign is a global phase. It can be ommited in case of operator $Q$ itself, however, it has to be included in controlled version of the operator. Controlled global phase is implemented by gate (I assume IBM Q environment) $U1 \otimes I$, where $U1$ gate acts on control qubit and identity operator on target qubit. $U1$ gate is given by matrix $$ \...


1

First observe that \begin{align*} S_0^{\phi} &= \phi \cdot |0 \rangle \langle 0| \otimes \mathbb{1} + |1 \rangle \langle 1| \otimes \mathbb{1} \\ &= \phi \cdot |0 \rangle \langle 0| \otimes \mathbb{1} + \Big(\mathbb{1} - |0 \rangle \langle 0|\Big) \otimes \mathbb{1} \\ &= \mathbb{1} \otimes \mathbb{1} - (1 - \phi) \cdot |0 \rangle \langle 0| \...


Only top voted, non community-wiki answers of a minimum length are eligible