Only eight annoying questions to go

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…

6 Responses to “Only eight annoying questions to go”

  1. Anonymous Says:

    I ask.

  2. Scott Says:

    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 some Hadamard basis.

  3. aram harrow Says:


    Did I miss one getting solved?

    Please don’t leave us all in suspense!

  4. Mahdi Says:

    Yes, another one was knocked off here.

  5. Scott Says:

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

  6. Osias Says:

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