Posted by: mick | September 4, 2008

## Alice’s $25 quantum challenge Hi I’m Alice (and by alice we mean mick and Dan) and this is my new blog. My friend Bob says that he has a quantum computer and I’m not really sure I believe him, and, in a lot of ways I’m not so sure that Bob believes himself either. It’s a good thing that I came across this paper (by Dan Shepherd and Michael Bremner) which suggests a game I might like to play with Bob so as to verify that he has something that can perform something like quantum computations. Rather than me trying to explain what they did in this paper, here’s their abstract: We examine theoretic architectures and an abstract model for a restricted class of quantum computation, called here instantaneous quantum computation because it allows for essentially no temporal structure within the quantum dynamics. Using the theory of binary matroids, we argue that the paradigm is nonetheless rich enough to enable sampling from probability distributions that cannot be efficiently sampled from classically. This paradigm also admits simple interactive proof games that may convince a skeptic of the existence of truly quantum effects. Furthermore, these effects can be created using signiﬁcantly fewer qubits than are required for running Shor’s Algorithm. So, having read their paper I thought I’d try my had at setting a challenge for Bob. The challenge I’ve just written a description of an IQP “X-Program” which Bob can try to run. If he wants a good description of what these programs are then he should have a look at this paper. The file specifying the program is right here. I should point out that I’m using the same “action” that Dan and mick specified in their paper, i.e. $\theta = \pi/8$. Why am I getting Bob to try to run this program in particular? Well, because hidden inside that program (which basically is a really big matrix made out of 1’s and 0’s) is a secret bit string that only I know. If he runs the correct “X-program” (and gives me enough data) I will be able to easily verify from the samples whether or not I see my secret string encoded within the output properly. Now, Bob is going to have to run this program a lot of times to ensure that he passes my hypothesis test. I’m guessing he’s going to have to do several thousand data runs. Unfortunately, I can’t say how many runs it is going to take to pass the test as I don’t know how `noisy’ his quantum computer is! If Bob is interested in the challenge he should have a look at the source code that I used to generate the data (obviously not containing the seed!) and which also specifies the hypothesis test I intend to use. That code can be found on this page. In order to make things extra interesting, Dan has thrown in NZ$25 for the first “Bob” that passes my test!

Can Bob cheat?

Well, he can try. As far as Dan and mick can tell there are two ways that he might like to try this:

1. He could try to classically simulate the program that I want him to run on his quantum computer. Well, he could try… If he manages to find one it will make for a great paper!
2. He could try to find out what my secret string is. That way, he could just find the string and then generate fake data that will pass our hypothesis test. I’m pretty sure that s is well hidden but I haven’t proven that. Again, if he manages to do this then that would be a great paper!
3. My hypothesis test isn’t perfect. He could get lucky and guess a way to fake passable data, but there’s no obvious way for him to check except by asking me to run my test using my secret value. And I’ll be suspicious if he fails 1000 times…

Think you are up to the challenge?

So Bob, if you want to have a go at this you can email me your data set at aliceschallenge [elephant] googlemail [a dot] com. I presume that you know what to do with the elephant…