Theoretical Computer Science

Is the D-Wave architecture a close implementation of quantum interactive proof?


A very high level architecture is, as mentioned here, shown in this picture.

The D-Wave architecture

The component on the left is classical while the one on the right is the D-Wave box. I understand that in QIP, Arthur is BQP. Here the classical component is always in BQP if we are not too restrictive. On the other hand, the D-Wave box although don't have unbounded computational resources is not violating any law of quantum mechanics. Let's consider this as not-so-strong Merlin.

Can we say that this architecture is an restricted implementation of quantum interactive proof system? My motivation for this question is that if we want to do the complexity analysis of the D-Wave architecture should we model it as QIP?




Solution

This question seems a little confused. The class of decision problems solvable efficiently on a quantum computer is BQP, while on a classical computer it is either P or BPP depending on exactly how you define things. An interactive proof is something entirely different. It is a protocol which allows a prover to prove, beyond reasonable doubt, the outcome of some decision problem, and allows the prover and verifier to interact. QIP is the class of interactive proofs where the verifier, not the prover, has access to a quantum computer. It turns out that this doesn't help very much since you can prove exactly the same things to a fully classical verifier. I think what you have in mind is something different: an interactive proof where the prover is limited to quantum computation. This is something that has been studied in recent years (see for example arXiv:0807.4154, arXiv:0810.5375 and arXiv:1209.0449). The extent of our current knowledge is that you can basically prove anything in BQP if you have either some limited quantum power for the verifier (the ability to prepare single qubit states, for example) or if you have several provers who do not communicate, but share entanglement.

The DWave machine does not implement anything like these schemes, and does not constitute any form of interactive proof. Actually, the problem of implementing such a scheme on DWave hardware has been something that has interested me for a while. There are a few hurdles to doing this. All of the known schemes are based in the circuit model or the closely related measurement based model, while the DWave machines use a very different model of computation. This introduces a few problems, as their system is not a general purpose quantum computer, and so cannot implement any of the known schemes directly. Further, it cannot really accept any kind of quantum input, which rules out many of the tricks used to construct the known schemes.

However, I don't mean this to be a criticism of DWaves device: virtually no other quantum device has been used to implement such a proof. The closest you get are things like violations of Bell's inequalities and the recent experimental demonstration of blind quantum computing in linear optic (arXiv:1110.1381). At this point, no one has yet published an experimental demonstration of a quantum prover interactive proof, so DWave isn't any better or worse in this respect than anyone else.

By the way, I apologise for linking to two of my own papers in the above, but this is a question I have been very interested in in recent years, and I think those papers are relevant to the question at hand. It's not intended as self-publicity.