# Gate Cost to Transform Superposition of Hamming weight 1 states to superposition of arbitrary basis states?

Say you have something like a general-coefficient $$n$$-qubit W-state, i.e.,

$$|\psi\rangle\equiv\sum_{j=1}^n a_j X_{j}|0\rangle^{\otimes n} \ ,$$ where $$a_j$$ are normalized complex coefficients. Using $$X$$, $$CNOT$$, $$SWAP$$, Toffoli gates and the like, how many gates do we need to change the superposition basis from the set of $$n$$ Hamming weight $$1$$ states to an arbitrary set of $$n$$ length-$$n$$ bitstrings?

I have a feeling it's going to be exponentially large but I'm not sure.

• Just to be clear: the number of basis states you're using is the same as the number of qubits? May 10, 2021 at 16:03
• I think it is $O(n)$ based on the fact that preparing the state you're starting with is $O(n)$ (so run that circuit backwards), and note preparing uniform superpositions is also $O(n)$ arxiv.org/pdf/1904.07358.pdf for reference to the first part. May 10, 2021 at 16:06

Split the problem into two phases: expansion and erasure.

During the expansion phase, each input position $$k$$ is used as a control to set some output qubits to $$f(k)$$. Prepare your output qubits into the $$|0\rangle$$ state. Then, for each input position $$k$$, for each output position $$b$$, perform $$CNOT_{in(k) \rightarrow out(b)}$$ if the $$b$$ bit in $$f(k)$$ is set. The hamming-weight-1 property makes this step very convenient, since each individual case has its own dedicated control.

During the erasure phase you have to clear the input qubits by conditioning on the output. The simplest thing to do is to perform $$X_k$$ conditioned on the output containing $$f(k)$$, and do this for each possible $$k$$. Note that each $$f(k)$$ must be unique or the operation you're describing wouldn't be unitary.

Once you've finished erasing the inputs, use swap gates to put the outputs where they're supposed to be.

You can often make the erasure phase more efficient by using knowledge about $$f$$. For example, there may be some bits that you don't have to condition on or certain multi-bit expressions that you can compute once and then reuse several times.

I have a feeling it's going to be exponentially large but I'm not sure.

The gate count is at most $$O(nm)$$ where $$n$$ is the number of input qubits and $$m$$ is the number of output qubits.