# 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 first two qubits as address qubits. The third qubit is the data qubit.

I want to be able to extract some arbitrary $$|\psi_i\rangle$$, but collapsing the first two qubits and post-selecting has a success probability of $$1/4$$. And this probability gets even worse with more address qubits: $$1/2^n$$.

Trying amplitude amplification on the address qubits does not work as the amplitudes of the data qubit also get modified.

Is there any procedure that allows me to increase the success probability of $$1/2^n$$? Or maybe some proof that it is not possible to do such thing?

• I'm confused as to your reason for amplitude amplification not working: assuming you fulfil the conditions of the algorithm (most importantly, having a unitary $U$ such that $U|0\rangle$ gives your initial state), it should work. Nov 24 at 15:46
• I assume the $|\psi_i\rangle$ are unknown, and (in general) not orthogonal? Nov 24 at 15:48
• @DaftWullie I think I wasn’t clear enough. I meant amplitude amplification only on the address qubits, which is why it doesn’t work. So this would be on a scenario were $U$ that prepares the three-qubit state is not efficient and we only want to act on the first two qubits after having the initial state. Nov 24 at 15:49
• But even if the U is inefficient, using it $\sqrt{2^n}$ times is better than using it $O(2^n)$ times in your collapsing qubits protocol. Nov 24 at 15:50
• @DaftWullie that makes sense, I’m thinking more of a situation where we want a database-like structure where we would only use the initialization unitary once and this is the extraction part, but I guess AA on the whole system is still the more efficient way. Then maybe QRAM is the way to go although it is more resource inefficient (what I wanted to avoid). Nov 24 at 15:55

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}(k)\rangle |+\rangle|k\rangle$$). Basically, you can infer there must be hard cases where the circuit achieving your task is going to have to be exponentially huge.