3
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 6
    $\begingroup$ Scott Aaronson's blog post on this topic should answer some of your questions. $\endgroup$
    – Robin Kothari
    May 18, 2013 at 17:10
  • 1
    $\begingroup$ If you are not satisfied with Scott's extensive discussions about what D-Wave's machines actually do, then you could try asking them directly. $\endgroup$
    – András Salamon
    May 18, 2013 at 17:17
  • $\begingroup$ @RobinKothari, I have already read that post. I understand that the post recognizes that for the first time the D-Wave box successfully demonstrated quantumness. A major part of the post discusses why the Amherst paper might not be useful. The blog post doesn't extend the discussion to the complexity class which is suitable to characterize the problems solved by the architecture. $\endgroup$
    – Omar Shehab
    May 18, 2013 at 17:21
  • 5
    $\begingroup$ No, I don't think you should. I think we should try to define a mathematical model of "quantum annealing" (or various mathematical models of quantum annealing; I think the stoquastic and the general cases would both be very interesting), and then ask what problems can be solved with them. But I don't see why looking at this as an interactive proof is likely to be fruitful. $\endgroup$
    – Peter Shor
    May 18, 2013 at 17:21
  • 3
    $\begingroup$ I think analyzing quantum annealing and quantum adiabatic computation with computational complexity tools is perfectly appropriate. I just don't see how these are connected with interactive proofs. $\endgroup$
    – Peter Shor
    May 20, 2013 at 9:29

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.