«
»

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…

Email, RSS Follow

This entry was posted on Thursday, September 21st, 2006 at 5:54 pm and is filed under Quantum. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

6 Responses to “Only eight annoying questions to go”

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

    I ask.

  2. Scott Says:
    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 some Hadamard basis.

  3. aram harrow Says:
    Comment #3 September 22nd, 2006 at 5:16 am

    Eight??

    Did I miss one getting solved?

    Please don’t leave us all in suspense!

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

    Yes, another one was knocked off here.

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

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

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

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