# What exactly is the reason why the Abrams - Lloyd algorithm does not allow implementation using unitary gates and ancillary qubits?

In their original paper (last part of the paper), Abrams and Lloyd present a quantum algorithm that could potentially efficiently solve NP complete problems (in linear time). Their algorithm, robust to small errors, depends on the possible implementation of a nonlinear OR gate. A short presentation can be found here .

Classical irreversible logical  gates can be simulated by unitary gates that involve some ancillary qubits, as can be seen here and here.

Question. What exactly is the reason why the Abrams - Lloyd algorithm does not allow implementation using unitary gates and ancillary qubits?

Note that these ancillary qubits can be set and measured when necessary, during the operation of the algorithm, and these operations introduce nonlinearity into the state evolution.

• After some effort, I found Abrams' PhD Thesis (partial, freely available on the Internet ) in which there is an answer to my question, pages 79-80 dspace.mit.edu/bitstream/handle/1721.1/85313/… – Cristian Dumitrescu May 26 '20 at 6:22
• If you use higher dimensional Hilbert spaces in order to imbed the nonlinear gate into higher dimensional unitary gates, then you cannot measure the garbage ancillary qubits at intermediate stages of the algorithm because you need to make sure the states can interfere with each other in future iterations. – Cristian Dumitrescu May 26 '20 at 6:47
• That means that you have to track the relevant qubits that carry the information you are interested in, and measure the qubits (including ancillary qubits) that you are interested in only in the final stages of the algorithm. I don't know whether that's possible, probably not, because the computational path you're interested in would have very small probability. – Cristian Dumitrescu May 26 '20 at 7:34
• Unless you can find a way to guarantee that all the other computational paths are innocuous (or at least with high probability ), that is they don't drastically decrease the number of states with a $\vert 1 \rangle$ for the final qubit. – Cristian Dumitrescu May 26 '20 at 7:47
• You get to something like a "superposition of computational paths", admittedly a poor characterization on my part, but intuitive. – Cristian Dumitrescu May 26 '20 at 8:05

However you could increase the dimensionality of the embedding unitary gate for each iteration (that means increasing the number of input/output qubits , including ancillary qubits ). In other words for the first iteration the nonlinear OR gate will be simulated by a unitary gate $$U_1$$ of dimension $$n+k$$ (where $$k$$ is a constant), with some ancillary qubits set on input to state $$\vert 0 \rangle$$ for example. All the $$n+k$$ output qubits of $$U_1$$ are entangled.  At the next iteration,  I simulate $$U_1$$ using a unitary $$U_2$$ gate of dimension $$n+2k$$ , by setting some extra ancillary qubits to $$\vert 0 \rangle$$.  At the next iteration,  I simulate $$U_2$$ using a unitary gate $$U_3$$ of dimension $$n+3k$$ , by setting some extra ancillary qubits to $$\vert 0 \rangle$$.  And so on. This way I can simulate the nonlinear OR gate for each iteration and I do not collapse the whole system to an eigenstate at any intermediate stage of the algorithm. We just have to track the right qubits to measure at the end of the algorithm.
In other words, there might be some hope related to the implementation of this algorithm, but I would not make a large bet on it, because simulating $$U_1$$ $$U_2$$ , $$U_3$$ , ..... is not exactly the same thing as simulating the nonlinear OR gate (even if $$U_1$$ with some ancillary qubits set to $$\vert 0 \rangle$$ does indeed simulate the nonlinear OR gate). When you set the ancillary qubits of $$U_2$$ to $$\vert 0 \rangle$$ you need $$U_2$$ to simulate $$U_1$$ when its own ancillary qubits are set to $$\vert 0 \rangle$$. (in order to simulate the nonlinear OR gate). When you set the ancillary qubits of $$U_3$$ to $$\vert 0 \rangle$$ you need $$U_3$$ to simulate $$U_2$$ when its own ancillary qubits are set to $$\vert 0 \rangle$$ , and so on. The problem requires a careful analysis, and at this point I don't know if it allows a solution.