A month ago, I posed the following as the 10th most annoying question in quantum computing:
Given an n-qubit pure state, is there always a way to apply Hadamard gates to some subset of the qubits, so as to make all 2n computational basis states have nonzero amplitudes?
Today Ashley Montanaro and Dan Shepherd of the University of Bristol sent me the answer, in a beautiful 4-page writeup that they were kind enough to let me post here. (The answer, as I expected, is yes.)
This is a clear advance in humankind’s scientific knowledge, which is directly traceable to this blog. I am in a good mood today.
The obvious next question is to find an α>0 such that, for any n-qubit pure state, there’s some way to apply Hadamards to a subset of the qubits so as to make all 2n basis states have |amplitude| at least α. Clearly we can’t do better than α=sinn(π/8). Montanaro and Shepherd conjecture that this is tight.
What’s the motivation? If you have to ask…