Suppose I have N register qubits, so they can represent the range [0, 2^N-1]. They are initialized in the all-zeroes state. I want my final state to approximate $$|\phi \rangle = \frac{1}{2^{2^N-1}} \sum_{m=0}^{2^N-1} {2^N-1 \choose m} |m \rangle \, .$$ Can this be done with poly(N) 2-qubit + 1-qubit gates? How good an approximation can I get with poly(N) gates?
Asked
Active
Viewed 34 times
0
-
Do you allow for ancilla qubits? Then you could use those as coins to perform a classical random walk, which would give you a normal distribution, which your distribution also approaches for large $2^N$ (so it only requires moderately-sized $N$). – Quantum Mechanic Sep 09 '21 at 19:54
-
I don't want a distribution; I don't want my state to be randomly entangled with ancillary qubits. I want a pure state as above. – Craig Sep 14 '21 at 19:12
-
Right right, so you want some sort of diffusion process that's still coherent. For spins you can achieve that with a Hamiltonian quadratic in the generators (like $H=J_z+J_x^2$) but I might hesitate before counting the number of qubit gates you'd need to simulate that – Quantum Mechanic Sep 14 '21 at 22:00