# Can a polynomial-sized superposition of computational basis states be prepared with a polynomial-sized quantum circuit?

Suppose I am working with a class of states which consist of a superposition of $$O(\text{poly}(N))$$ computational basis states on $$N$$ qubits. Examples of this would be the subspace of states of fixed Hamming weight $$k < N$$, or alternatively CISD states in quantum chemistry. If my goal is to implement arbitrary polynomial-sized states with this restriction, can I assume that there is a procedure to implement such states with a quantum circuit that also scales polynomially in $$N$$?

A sort-of brute force idea I had for how this could be done is to build each term in the superposition one by one. If each term can be added one-by-one with a polynomial circuit, then implementing the total state can also be done with a polynomial circuit. But I am not sure if this can be done in practice.

• You might start with a small superposition, but after applying a general operation (multiply in exponential matrix) you are adding more terms to the superposition. If you guarantee that the matrix will have "many" zeros, it might work. But this is super specific, and depends on your case. Jun 19 at 12:53
• @SolarFlare0 your state appears to be what Grilo, Kerenidis, and Sikora refer to as "subset states" here. There appear to be a number of QMA-complete problems with such subset states; however the [GKS] paper doesn't seem to go into the specific problem of building such a state when $|S|$ is polynomial as in your question. Jun 21 at 22:42

I think so. Let me rephrase what you're asking and hopefully it captures what you want: Suppose you have $$N$$ distinct circuits $$U_i$$ such that $$U_i|0\rangle = |\psi_i\rangle$$, each with complexity $$O(g(N))$$ for some $$g$$. Your goal is to prepare the state

$$\frac{1}{\sqrt{N}}\sum_{i=1}^N | i\rangle |\psi_i\rangle$$

Then you can absolutely do this with a brute-force approach. First, you create a superposition over $$i$$:

$$\frac{1}{\sqrt{N}}\sum_{i=1}^N |i\rangle$$

then in a (classical) loop of $$j$$ from $$1$$ to $$N$$, you would apply a circuit to check if $$i=j$$ and write the result to an ancilla:

$$\frac{1}{\sqrt{N}}\sum_{i=1}^N |i\rangle | i==j\rangle$$

and then apply controlled-$$U_j$$, using that ancilla qubit as a control. Then uncompute the ancilla qubit and move to the next value of $$j$$.

Once this loop finishes, you have the desired state.

Computing $$i==j$$ has complexity $$O(\log N)$$ since $$i$$ and $$j$$ have $$O(\log N)$$ bits. Since each circuit $$U_i$$ has complexity $$O(g(N))$$, and you apply $$N$$ such circuits, the total complexity will be $$O(Ng(N))$$. If $$g(N)$$ is polynomial, then the total complexity is still polynomial.

Whether this can be done "in practice" depends on what you mean by "in practice" (NISQ? small fault-tolerant? etc.). This technique (with some tricks for a bit more efficiency) is used (more or less) in a number of papers, e.g. https://arxiv.org/abs/1902.02134

• Are you sure the OP doesn't want to have the first register entangled with the second? Jun 21 at 22:35
• I'm not sure, but a pure superposition of $\sum_i |\psi_i\rangle$ will probably need a very domain-specific solution. Jun 22 at 8:00