Re: [cryptography] Grover's Algo Beaten?
On Sun, Jul 28, 2013 at 3:49 PM, Russell Leidich pke...@gmail.com wrote: Thanks, Noon. It's good to know that some searches are still hard in the sense of square root as opposed to log of classical. So based on his actual claims in the papers you cited, when the EE Times article says: And he claims the process worked so well that even the largest data set of all -- every bit in the universe, which he describes in his book *Programming the Universe* http://www.amazon.com/books/dp/1400033861, would only require a quantum computer with 300 q-bits to query in real-time. I don't know exactly what they mean by this. I guess he's just saying something like suppose I know that the number of bits of information the universe is less than some number K, then I only need log2(K) qubits to represent that many bits of information in a quantum computer. I'm not sure it's particularly interesting. ...they don't mean query in the literal sense of a text search for an exact match of Joe Smith. What they really mean is more like: given a database of billions of car photos (support vectors), then look at my new car photo, and tell me what brand it is. In short, a vector classifier. In the recent machine learning paper[1], they describe an algorithm that does supervised machine learning (i.e. deciding whether a thing is either truck-like or car-like, two choices for simplicity) in O(log (N M)) on a quantum computer, instead of O(poly (N M)) on a classical computer, where M is the number of samples from each of the clusters you're trying to assign to (say M truck-like things, and M car-like things), and N is the dimension of vector you're trying to assign (i.e. a thing that is either truck-like or car-like). Nevertheless, his putative exponential speedup over classical methods would be astounding, if it could be implemented, even if it really doesn't relate to Grover. It's a cool result, no doubt. But you'll note that the classical algorithm is already in P. The trouble is to find a quantum algorithm that solves a problem that is hard classically, but easy quantumly. More technically, it would be really astounding if we could separate BPP[2] and BQP[3]. -- Noon [1] http://arxiv.org/abs/1307.0411 [2] http://en.wikipedia.org/wiki/BPP_%28complexity%29 [3] http://en.wikipedia.org/wiki/BQP ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Grover's Algo Beaten?
On Jul 27, 2013, at 9:29 PM, Russell Leidich pke...@gmail.com wrote: Is this to be taken seriously... Massachusetts Institute of Technology professor Seth Lloyd claims to have developed a quantum search algo which can search 2^N (presumably unsorted) records in O(N) time. Grover’s original paper included a proof that his result was near a lower bound. I don’t understand QM well enough (my linear algebra sucks) to have understood the proof sufficiently to see clearly what assumptions it relies on. Cheers, -j ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Urea at NSA Utah Data Center
There are two spaces labeled Urea Tank Room in the NSA Utah Data Center's Generator Plant shown in construction drawings recently leaked: http://cryptome.org/2013-info/07/nsa-utah-dc/nsa-utah-dc.htm See Generator Plant floor plan drawing 11.2 A101 at bottom and top left, spaces labeled UT. Urea is used in fuel cells. Are there other uses of urea in generator or data processing equipment? ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Urea at NSA Utah Data Center
Generators use diesel, urea is a used to clean diesel emissions up - http://en.wikipedia.org/wiki/Diesel_exhaust_fluid Ryan -Original Message- From: cryptography [mailto:cryptography-boun...@randombit.net] On Behalf Of John Young Sent: Sunday, July 28, 2013 5:41 AM To: cryptography@randombit.net; cypherpu...@cpunks.org; crypt...@freelists.org Subject: [cryptography] Urea at NSA Utah Data Center There are two spaces labeled Urea Tank Room in the NSA Utah Data Center's Generator Plant shown in construction drawings recently leaked: http://cryptome.org/2013-info/07/nsa-utah-dc/nsa-utah-dc.htm See Generator Plant floor plan drawing 11.2 A101 at bottom and top left, spaces labeled UT. Urea is used in fuel cells. Are there other uses of urea in generator or data processing equipment? ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Grover's Algo Beaten?
Is it better than a radix sort? ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] NSA Utah Data Center Cabling, Emanations and Bizarre Planning
Not much publicly available on the cabling and emanations protection of the NSA Utah Data Center. Surely highly advanced measures are being applied. Google Earth shows a couple of stages of construction, Bing Maps a couple more. AP has published a dozen or so hi-rez photos of construction. A lot of earthwork was done to create a flat site on a mountain side (preceded by a small air field). No indication of underground construction except pits and trenches under the buildngs. With none on the surface there must be trenches for power and signal cable. No antenna have appeared on the site for transceiving data like those of other of its data centers, so presumably it is done by UG fiber optic (or antenna are hidden or remote). Photos of construction progress of the two data buildings show windowless envelopes made of panels and flat roofs without various rooftop ductwork, grilles, piping and the like which appear on roofs of other NSA and TLA facilities which might emanate signal although not likely. (Some are littered with the stuff which might be decoy.) Steel structural framing is shown at Utah despite its known transmittal of inadvertent signal, compared to say, reinforced concrete, metalized fabric or synthetics. although are ample countermeasures available. The pairing of structures at Utah, two of each type, data center, generator, AC, fuel tanks, etc., show redundancy also not seen elsewhere. Not much to see of protection against missiles and aerial attack but that is the same at other NSA facilities. Wonder what supports that confidence. The odd bent shape of the site plan, with buildings not parallel to one another is intriguing. Could be aesthetic but may have another role, say to disperse richochet of inadvertent emanations. Quite a few recent government buildings avoid the traditional rectilinear site planning of buildings long considered to be most cost effective and authoritarian. Some like NGA HQ, NSA Utah and several at Ft. Meade look almost byzantine in layout, if not a shrewd design to limit echo, amplification, richochet, or best, to befuddle satellite peepers. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
