# How to implement a quantum array

I'm trying to implement a quantum array. That is one that stores qubits and can be indexed via qubits.

I can create one that handles setting values fairly easy. Have two registers, one for the position and one for the values in the array. Then use entanglement to set values. The hard part seems to be retrieving values, any idea on how to do this?

• Any collection of Qubits, or really anything can be considered an array. If you have $2^n$ Qubits that can itself we considered an array, if you would like to have a Quantum Indexing Scheme for the elements of that Array you would need $n$ Qubits; much like how computer memory works. Oct 4 at 18:14
• Just to be sure about what you mean by "can be indexed via qubits". You mean that your array is indexed classically, but you can query it on $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$ and it will return $\alpha|0\rangle|\texttt{array}\rangle+\beta|1\rangle|\texttt{array}\rangle$? Oct 4 at 19:13
• Sorta, I mean I can query classically. Sorry not sure how to use mathjax, but I mean |0> gives array, |1> gives array, so in your example that superposition would give a * array + b * array. Oct 4 at 23:07

Retrieving an arbitrary qubit, even using an ancilla qubit, would violate the no-cloning theorem. This can be seen in the simplest case where the array stores a single qubit and is indexed by a single qubit. So the array is of the form

$$\left|\psi\right> = a \left|00\right> + b \left|01\right> + c \left|10\right> + d\left|11\right>$$

where $$|a|^2 + |b|^2 + |c|^2 + |d|^2 = 1$$. Consider the special case where $$|a|^2 + |b|^2 = 1/2$$ and $$c = a$$, $$d=b$$, so

$$\left|\psi\right> = \bigl( \left|0\right> + \left|1\right>\bigr) \bigl(a \left|0 \right> + b \left|0 \right>\bigr) = \bigl( \left|0\right> + \left|1\right>\bigr) \left| \phi\right>$$

where $$\left| \phi \right> = a\left| 0 \right> + b \left| 1 \right>$$. Thus the qubit $$\left|\phi\right>$$ is stored in the array and indexed by either of the classical bits $$0$$ or $$1$$. (It could also be said to be indexed by any superposition $$c\left|0\right> + d \left|1 \right>$$.) It does not violate no-cloning to create this state: indeed, it is a separable tensor product of the normalized states $$\left|+\right> = \frac{1}{\sqrt{2}} \left|0\right> + \frac{1}{\sqrt{2}} \left|1\right>$$ and $$\sqrt{2} a\left|0\right> + \sqrt{2} b\left|1\right>$$.

We might hope to use an ancilla qubit and some combination of gates so that the input is $$\left|\psi\right> \left|0\right>$$ and the output is $$\left|\psi\right> \left|\phi\right>$$. But if we take the output $$\left|\psi\right>\left|\phi\right> = ( \left|0\right> + \left|1\right>) \left| \phi\right> \left|\phi\right>$$ and measure it in the $$Z$$-basis on the first qubit then the new state is always $$\left| \phi\right> \left|\phi\right>$$, meaning that we have cloned $$\left| \phi \right>$$.

• Ah thank you! That's very interesting. I had the question because I'm reading a paper that describes a quantum algorithm that requires updating and retrieving values of an array. I'm guessing this mean it is impossible to implement the algorithm? Oct 5 at 1:25
• Please could you add the reference? I think it all depends what one means by 'retrieval'. Maybe you are happy with my interpretation, but it's not the only one. For instance, if you're willing to destroy the array in the process of retrieval, then much more is possible. Oct 5 at 7:35