Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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.
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.
