## Only eight annoying questions to go

A month ago, I posed the following as the 10^{th} 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 2

^{n}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 2^{n} basis states have |amplitude| at least α. Clearly we can’t do better than α=sin^{n}(π/8). Montanaro and Shepherd conjecture that this is tight.

What’s the motivation? If you have to ask…

Comment #1 September 21st, 2006 at 9:07 pm

I ask.

Comment #2 September 21st, 2006 at 9:22 pm

The “motivation” is that it was so damnned annoying!

Oh, alright: the question arose a few years ago in my paper with Gottesman on stabilizer circuits (quant-ph/0406196). But there we only needed a special case (stabilizer states), which we were able to get directly.

I don’t know if the general result has any applications. Philosophically, you can think of it as a combinatorial version of Heisenberg’s uncertainty principle. Instead of saying that any state is indeterminate in either the position or momentum basis, now we’re saying that any n-qubit state is “completely indeterminate” in

someHadamard basis.Comment #3 September 22nd, 2006 at 5:16 am

Eight??

Did I miss one getting solved?

Please don’t leave us all in suspense!

Comment #4 September 22nd, 2006 at 9:16 am

Yes, another one was knocked off here.

Comment #5 September 22nd, 2006 at 1:07 pm

Indeed, technically there are only seven left, since question #1 was just a metaquestion.

Comment #6 September 24th, 2006 at 4:29 pm

Wow! Congratulations! For Scott and the authors of the paper.