But it only applies to estimation (like how well a population parameter can be estimated) in certain regimes, and not e.g. expected risk (like how well one can do at prediction), so I’m not sure how it would apply here.
Just speaking in terms of "quantum size" (and not computing power, which is not understood yet), it depends on the graph of possible entanglements among the qubits. If it were a complete graph (allowing arbitrary entanglement) then the size of the relevant Hilbert space would exactly double with each additional qubit (i.e. one would need twice as many complex numbers to describe any particular wave function in the space). But the D-Wave chips operate with a fixed topology that (I think) is far from fully-connected (e.g. the 128-bit chip used a "Chimera graph", which they describe in blog posts and publications). The growth would only be truly exponential with sufficient connectivity (e.g. a planar graph would mean sub-exponential growth).
It wasn't really shown to be faster; see http://www.scottaaronson.com/blog/?p=1400. To focus on the "3600 times" issue, I suggest searching for the strings " Ising" and "CPLEX". Don't miss the extremely thorough discussion in the comments, which includes comments from Cathy McGeoch (the author of the "3600 times" work), Peter Shor (as in Shor's factoring algorithm), Scott Aaronson, Greg Kuperberg, and many others.
It's not able to do full quantum annealing; it's only able to use stoquastic Hamiltonians on a fixed topology. Even if truly quantum effects were present (which is unclear at the moment, see Smolin and Smith arxiv posts), it's not known to be a useful quantum computing model. So it's not just an issue of "optimizing output".
To clarify, there are public-key cryptosystems with no known quantum attacks, but it's not known how to build such systems based on problems that are known to be QMA-complete (or NP-complete).
> Currently, our best candidates for such trapdoor OWF's are based on lattice problems, like the Shortest Vector Problem (SVP) that I described earlier. Whereas factoring reduces to the abelian hidden subgroup problem, which is solvable in quantum polynomial time, SVP is only known to reduce to the dihedral hidden subgroup problem, which is not known to be solvable in quantum polynomial time despite a decade of effort.
> Inspired by this observation, and building on earlier work by Ajtai and Dwork, Oded Regev has recently proposed public-key cryptosystems that are provably secure against quantum eavesdroppers, assuming SVP is hard for quantum computers.
What have I said that suggests "MIT is not to blame for very much at all"? My comments have dealt with factual issues; I don't see where I advanced any opinions on MIT's deserved level of blame.
The MIT report lays out facts (and not conclusions or judgements) for the express purpose of informing the debate. Many here would probably be interested in its contents if they weren't so busy expressing opinions about it.
It's not clear to me what Ms. Stinebrickner-Kauffman meant by her comment, since prosecution was entirely at the discretion of the DA (as with all criminal charges) and MIT (like JSTOR) had no involvement in the criminal charges. The report explains as much in careful detail and my poor paraphrasing is no substitute.
(Judging by tweet timestamps, Ms. Stinebrickner-Kauffman's statement may have been made about 18 minutes after the release of the report (8:31am @TarenSK vs 8:13am @MIT), so it's possible that the statement was not based on the entirety of the report's content. That is not based on precise knowledge of the report's actual time of release.)
Here is a personal opinion: Hal Abelson, founding director of both the Free Software Foundation (with RMS, GJS, and others) and Creative Commons (with Lawrence Lessig and others) and lead author of the MIT report, produced a thoughtful and thorough document and it should not be ignored.
If by "objected to FOIA requests" you mean "filed a motion, just like JSTOR, proposing the ability review and suggest redactions to the requested documents over a window of five days for the explicit purpose of ensuring the privacy and safety of its employees, especially in light of the threatening communications it has received". MIT never proposed preventing the documents from being released.
> 35. What influence, if any, did MIT exercise or could it have exercised in the plea negotiations? Did MIT really scuttle a plea bargain with no prison time?
> Answer: MIT played no role in any plea negotiations related to the Aaron Swartz case. For a description of these negotiations, please see the Report, section II.B.2 The federal prosecution. For a description of MIT’s position regarding the government’s prosecution, please see Part III MIT’s Response to the Prosecution. It is unclear whether MIT could have exercised influence on the plea bargain. Please see in particular section III.A.2 MIT is informed about the prosecution; and section III.C.3 MIT’s outside counsel speaks with the lead prosecutor.
What would it mean for MIT to "sign off" on a plea bargain? The prosecutor alone was pressing criminal charges; MIT was not pressing any civil charges and it was not involved in the proceedings.
> The report appears to find that MIT should not have changed its neutral stance, which is disappointing, and I'm skeptical.
The report does not have any findings about what MIT "should" have done, as it states many times, such as in the last paragraph of the Introduction section:
> It was not part of our charge in this review to draw conclusions, but rather to determine facts and to consider what can be learned from this tragedy. Part V accordingly poses questions, not answers.
and again in the 4th paragraph of Section V:
> The Review Panel was not asked to make recommendations in our report, but rather to suggest how MIT might learn from this history.
Your comment misrepresents the report's purpose as well as its content. I think the report deserves a more careful reading.
EDIT: Personally, I recommend reading the Conclusion section (p. 100) and searching for the string "neutral" in that section.
The USC group has a response to Smolin and Smith which explains how some quantitative features are still best explained by a simulated quantum annealer: http://arxiv.org/abs/1305.5837. So there's still some potential for evidence of quantum effects (though "maybe doing something nonclassical" is a far cry from all the marketing talk, especially since annealing with stoquastic Hamiltonions with a fixed topology is already a far cry from any known-to-be-useful quantum computing model).
That computation is probably something you were already familiar with in disguise: it's just the law of cosines [1][2] along with the fact that a matrix of inner products can be computed with a matrix-matrix multiplication [3].
The first claim is just that for vectors x and y in an inner-product space ||x-y||^2 = <x-y,x-y> = ||x||^2 + ||y||^2 - 2<x,y>, and the second claim is just that if you collect a bunch of vectors into the columns of X and another bunch into the columns of Y, then the (i,j) element of X'Y is <x_i,y_j>, i.e. the inner product of the i'th vector in X with the j'th vector in Y. (Bonus fact: you can use that relationship to translate the statement "this set of pairwise distances can be embedded in a Euclidean space" to an equivalent condition that some simple matrix is negative semidefinite on a subspace orthogonal to the all-ones vector. Euclidean metric embedding is very useful!)
I just ran Wes's benchmarks (not the BLAS call versions) on my machine with a Julia I built on 10/13 (17c3c13), and the timings have indeed improved. For the details, see this gist: https://gist.github.com/3901139 (including the comment I posted on it).
The highlight is
numpy: (x * y).sum() => 41.1 ms
julia: inner(x,y) => 37.4 ms
julia: x*y => 19.5 ms
cython: inner(x,y) => 13.8 ms
The numpy and Julia versions are much easier to write and run.
Disclaimers: I've never written or built cython code before just now, and I think Julia is the coolest.
EDIT: whoops, missed the most important one (inner() written in pure Julia). Added it. Any thoughts on why inner() in Julia isn't faster?
They actually point out a specific comparison to FFTW in the paper: their "preliminary implementation" is faster than FFTW for n=2^22 and k<=2^17, and they point out that this performance is a distinct advantage over previous algorithms, which were faster for only k<=2000 or so. In other words, it seems that this algorithm is faster than FFTW for a much larger number of non-zero frequencies than was previously possible.
I don't know how to estimate what values of n would be relevant for today's applications, but n=2^22≈4M doesn't seem like such a big number for images or video (if signal length roughly corresponds to number of pixels). Any thoughts?
Those are a lot of great links! But I disagree with your "BTW" line:
I don't think factor graphs are more popular than Bayes nets (a.k.a. directed graphical models), at least not in general machine learning (though perhaps in some particular subfield?). Directed graphs are usually most appropriate for generative models, which are very popular, especially in Bayesian approaches. In graphical models, directed, undirected, and factor graphs are all used in their appropriate contexts.
And it's not accurate to say that directed models (Bayes nets) are a special case of factor graphs: there are conditional independence structures that can be represented by Bayes nets that can't be captured exactly with factor graphs. The canonical example is
https://en.wikipedia.org/wiki/Cram%C3%A9r%E2%80%93Rao_bound
But it only applies to estimation (like how well a population parameter can be estimated) in certain regimes, and not e.g. expected risk (like how well one can do at prediction), so I’m not sure how it would apply here.