<p>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 <strong>verifier</strong>, 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 <a href="http://arxiv.org/abs/0807.4154">arXiv:0807.4154</a>, <a href="http://arxiv.org/abs/0810.5375">arXiv:0810.5375</a> and <a href="http://arxiv.org/abs/1209.0449">arXiv:1209.0449</a>). 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.</p>

<p>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.</p>

<p>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 (<a href="http://arxiv.org/abs/1110.1381">arXiv:1110.1381</a>). 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. </p>

<p>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.</p>

CC BY-SA 3.0
2013-05-18T17:44:21.160Z
2013-05-18T17:49:43.040Z
2013-05-18T17:49:43.040Z
Joe Fitzsimons
<p>A very high level architecture is, as mentioned <a href="http://www.dwavesys.com/en/dev-tutorial-software.html" rel="nofollow noreferrer">here</a>, shown in this picture.</p>

<p><img src="https://i.sstatic.net/XTA2R.png" alt="The D-Wave architecture"></p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2013-05-18T17:10:50.283Z
Scott Aaronson's [blog post on this topic](http://www.scottaaronson.com/blog/?p=1400) should answer some of your questions.
Robin Kothari
CC BY-SA 3.0
2013-05-18T17:17:22.833Z
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.
András Salamon
CC BY-SA 3.0
2013-05-18T17:21:10.213Z
@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.
Omar Shehab
CC BY-SA 3.0
2013-05-18T17:21:33.717Z
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.
Peter Shor 
CC BY-SA 3.0
2013-05-18T17:36:21.500Z
@PeterShor, understood. Looks, I will be end up considering the architecture as optimization problem solver.
Omar Shehab
CC BY-SA 3.0
2013-05-20T05:05:43.017Z
@PeterShor, should I assume that you are preferring mathematical analysis to complexity analysis? I just started reading arXiv:0806.1859. It says, 'In some contrast to these situations on Quantum Adiabatic Evolution, studies of Quantum Annealing are often focused not on computational complexity but on the theoretical convergence conditions for infinite-time evolution and on the amount of errors in the final state within a fixed evolution time'. As D-Wave does QA, which is not a discrete automaton, computational complexity analysis is not appropriate, right?
Omar Shehab
CC BY-SA 3.0
2013-05-20T05:06:13.877Z
@PeterShor, moreover, Is it same for Adiabatic Quantum Computation? Because AQC is also analog computing.
Omar Shehab
CC BY-SA 3.0
2013-05-20T09:29:18.927Z
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.
Peter Shor 
<complexity-classes><quantum-computing><quantum-information><interactive-proofs><ar.hardware-architecture>
Is the D-Wave architecture a close implementation of quantum interactive proof?
Omar Shehab
# Is the D-Wave architecture a close implementation of quantum interactive proof?

(Asked by: username_0 on 2013-05-18)

A very high level architecture is, as mentioned [here](http://www.dwavesys.com/en/dev-tutorial-software.html), shown in this picture.

![The D-Wave architecture](https://i.sstatic.net/XTA2R.png)

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?

**Tags:** complexity-classes, quantum-computing, quantum-information, interactive-proofs, ar.hardware-architecture

> **Comments:**
> **username_1**: Scott Aaronson's [blog post on this topic](http://www.scottaaronson.com/blog/?p=1400) should answer some of your questions.  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_3**: 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.  
> **username_0**: @PeterShor, understood. Looks, I will be end up considering the architecture as optimization problem solver.  
> **username_0**: @PeterShor, should I assume that you are preferring mathematical analysis to complexity analysis? I just started reading arXiv:0806.1859. It says, 'In some contrast to these situations on Quantum Adiabatic Evolution, studies of Quantum Annealing are often focused not on computational complexity but on the theoretical convergence conditions for infinite-time evolution and on the amount of errors in the final state within a fixed evolution time'. As D-Wave does QA, which is not a discrete automaton, computational complexity analysis is not appropriate, right?  
> **username_0**: @PeterShor, moreover, Is it same for Adiabatic Quantum Computation? Because AQC is also analog computing.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2013-05-18. Score: 6 | Accepted answer

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](http://arxiv.org/abs/0807.4154), [arXiv:0810.5375](http://arxiv.org/abs/0810.5375) and [arXiv:1209.0449](http://arxiv.org/abs/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](http://arxiv.org/abs/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.


---

