How to add the basis state $\vert 0 \rangle$ to an arbitrary uniform superposition state?

Question

There is an unknown uniform superposition state $$\vert \psi \rangle = \frac{1}{\sqrt{N}} (\vert k_1 \rangle + \vert k_2 \rangle + \cdots + \vert k_N \rangle),$$ where $$k_1 \neq k_2 \neq \cdots k_p \neq 0,$$ $k_i$ is unknown but $N$ is known. How to construct an efficient circuit satisfying $$U\vert \psi \rangle = \frac{1}{\sqrt{N+1}} (\vert 0 \rangle+\vert k_1 \rangle + \vert k_2 \rangle + \cdots + \vert k_N \rangle)?$$

Answer 1

This operation isn't possible to construct. It violates unitarity. For example, it would map the orthogonal states $|1\rangle$ and $|2\rangle$ to the non-orthogonal states $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ and $\frac{1}{\sqrt{2}}(|0\rangle + |2\rangle)$. But unitary operations always preserve orthogonality.

Answer 2

I guess I'll follow up a little on Craig's answer. Although the mappig isn't unitary, it can be implemented by some channel, so you can still implement the transformation you're looking for, if you're willing to accept with a small probability (or if you can post-select). You can turn this into an exponential time algorithm using amplitude amplification. I also think you can do a lot better than the implementation I'm going to give, but I'm just broaching the idea.

Let's call the space of all possible values of $k$ $X$. Then consider the following collection of unitaries: $$ U_{i} = \mathrm{id}_{\perp} + \begin{pmatrix}\sqrt{\frac{N-1}{N}} & \sqrt{\frac{1}{N}}\\ -\sqrt{\frac{1}{N}} & \sqrt{\frac{N-1}{N}}\end{pmatrix}_{0, i}\,. $$

Maybe I've made a mistake (sorry, I'm not checking everything in tons of detail), but basically the idea is that $U_i$ slightly rotates $|i\rangle$ to be $\sqrt{1/N} |0\rangle + \sqrt{(N-1)/N}|i\rangle$ (and maps $|0\rangle$ to whatever it needs to be to be orthogonal, and doesn't touch anything orthogonal to $0$ and $i$). Then we can apply the linear combination of unitaries to get the state you want. More precisely, we can do the following: Let $W = \sum_{i} |0\rangle\!\langle 0| \otimes U_i$, and start with the following state: $$ \left(\frac{1}{\sqrt{|X|}}\sum_{i} |i\rangle \right) \otimes |\psi\rangle\,. $$

Then apply $W$ to this state and measure the projector onto the even superposition (in other words, apply a QFT and measure in the computational basis). If you measure the uniform superposition (which will, admittedly, happen with probability that is something like $1/|X|$), the state will be what you want for any superposition of the form you wrote. Then you can use amplitude amplification to get a $O(\sqrt{|X|})$ time algorithm. If $|X|$ is efficient, then this works, but I'm guessing it's not exactly an answer to your question haha.

I'm not sure about lower bounds, but I suspect it's possible. A little observation is that since a random subset state is statistically indistinguishable from a Haar random state, I think that for a lower bound we should imagine that we're trying to do this with a Haar random state. Furthermore, a Haar random state on d dimensions is indistinguishable from a Haar random state on d-1 dimensions (up to $1/\sqrt{d}$ trace distance or something), so we can basically imagine that we got a Haar random state from the whole Hilbert space, and our task is to map a Haar random $|\psi\rangle$ to $\frac{1}{\sqrt{N}}|0\rangle + \sqrt{\frac{N-1}{N}}|\psi\rangle$. This seems hard, but I haven't worked out what to do from here.