Right. So I guess this is where we come full circle back to the presentation.

Today nobody is using the D-Wave machines for anything (okay, okay, besides perhaps the research itself and for solving those odd ising spin problems less quickly than commodity hardware). So you can’t demerit these applications for not yet being fun. If you were, for no reason other than consistency, you would also need to demerit Shor’s algorithm and in fact everything in the slide deck.

The presentation is not about real-being-done-today applications but possible-might-be-done-sometime applications. It’s about ‘what do we want these machines for?’ So I would argue that you should consider expanding the slides to include EM scattering and software verification, wary of course of how far they sit in speculation land. I know you’re pretty good at that – better than yours truly, so I’ll leave you to that calculus.

Anyhow thanks for the informative discussion!

]]>My point was that the QC’s extra ability to query the Oracle in a superposition also breaks the rules (as did my Oracle O) and that to *fix* this we’d either need to remove this quantum ability or allow the classical machine to get additional state from the oracle.

I understand your comment about the black box setup being a thought experiment from which insight may be gained to produce algorithms like Shor’s, which does not by itself separate BQP from other classes, and that if we could solve Simon’s problem fast classically by having the Oracle return an additional yet trivial state then we might well be able to do the same for integer factorization.

I think it’s pretty interesting and worth thinking about what kind of trivial state a classical machine *might* need from the Oracle in order to solve Simon’s problem – and i confined this trivial state to be any state that may be captured by an X machine (on which the black-box runs) that’s efficiently simulated by the classical machine.

Anyway, that’s just one of the questions i had. I was also wondering if anyone has tried to exploit the Law of Total Probability for computation, e.g. maybe to compute the Fourier transform. You’ve mentioned that negative probabilities would be sufficient to match much of a QC’s power, but are negative probabilities that difficult to realize?

]]>Yes, there are lots of exciting advances these days in automated verification, and yes, I think it’s perfectly reasonable for DARPA to be funding such work. (For that matter, I think it’s *also* reasonable for them to fund quantum computing! Their mission is supposed to be broader than things with direct military applications; it has to do with keeping the US at the technological forefront.)

And *if* there were some spinoff from quantum computing research that benefited classical automated verification—well, it wouldn’t be the first time that QC had had an interesting classical spinoff.

And *if* you had a true fault-tolerant QC, you could try running the adiabatic algorithm or Grover search to get a speedup for software verification. We can’t say with confidence that you’d see any speedup over the best classical algorithms, but nor can we say with confidence that you wouldn’t.

The one thing I can tell you with confidence is that no one is using the quantum hardware that *exists today* to get any genuine speedups for software verification.

I would presume they are looking to verify _classical_ code with quantum algorithms – especially since it would be tough to get a QC up into the air…

But again I don’t know that there is any advantage in this case either.

Finally given the posterior of the (current) advances in automated verification of Probablistic Programming Language programs, and DARPA funding of such, how absurd are generalizations to/from the L2 norm and how small a prior do you give DARPA/Lockheed for having made private advances on this front?

]]>The behavior of this particular oracle is strange to me because it’s “architecture specific”.

Suppose we define an Oracle O that receives x and produces f(x)+**c**, where f(x) is some random noise and **c** is “yes” if **x** is a satisfiable boolean formula and “no” if **x** is not satifsfiable.

But here’s the catch, **c** is inaccessible to Quantum Computers – it’s always null.

That means BPP^O != BQP^O, but what is this *really* evidence of? What was shown by this oracle separation?

Of course, everyone who knows anything about this subject knows that black-box separations don’t rule out the possibility of a fast classical algorithm that “opens the black box”—that’s why we say, for example, that we can separate BPP from BQP *relative to an oracle*, rather than that we can separate them in the unrelativized world. At this point, this discussion feels like pure word-splitting to me; I don’t know what substantive point is at issue.