I want to say something about "tiling problems," an area I find very exciting. I ordinarily would not have commented on "quantum computers," but will make just a couple of comments, since I want to comment later on tilings. At 9:58 PM 9/22/96, Adam Back wrote: ...

I'm not sure about quantum computers, some people who know much more about particle physics than I do seemed initially sceptical, and didn't think it was doable. However I have read some optimistic sounding news clippings (on the list) which sounded as if things are progressing well, with techniques being found using redundancy to get around what were earlier problems of reliability. Is this accurate reporting (thinking of garbled stories by over enthusiastic journalists)? I'd be interested to hear opinions from anyone who does know about particle physics about the likihood of practical quantum computers being practical in the next 20 years or so.

Caveat: I'm a skeptic on quantum computers. I've read a couple of the early papers, but am not current. And I certainly am not an expert. For what it's worth: * I think it's nearly certain that no significant results will be gotten in the next 20 years, probably not in the next 50 years. (I personally am skeptical that significant results will be gotten in 200 years, and probably never, but this is a harder point to make.) * Sure, there may be demonstrations of a "collapsed quantum state" which is isomorphic to factoring a number like "42," but not 50-digit numbers anytime soon. And, I feel, a 300-digit number is probably many, many orders of magnitude harder. * Experts may point to partial successes, and maybe they're right. But I'm skeptical. The recent post by someone outlining a bunch of "promising approaches" has got me thinking of spending some more time looking at recent results, though. I doubt anything will happen in the next 20 years...that just isn't much time in the high-tech business (which may sound crazy, but it's true). (A way to "creatively visualize" this point is this: for those of you who are now 25, when you are 45 the world will probably _not_ be radically different. Sure, computers will be faster and cheaper, but most things will look _mostly_ the way they look today. Not a compelling argument, perhaps, but one which makes sense to me. When I was 25 I suppose I expected dramatic advances to come...largely, they haven't. I can elaborate on this if there's sufficient interest.)

One other area that did sound promising was some kind of mapping problem in n dimensional tiling that Tim was discussing at a physical meet while I was over in the US. A news clipping posted to

One of the most interesting books I've read is David Harel's "Algorithmics: The Spirit of Computing." (Warning: The book came out in a second edition, which as near as I can tell took out some parts and synopsized the book a bit. My reading was of the First Edition.) Harel described Huang's work on "tiling problems." These are easier to describe with pictures, and I don't have the time to try to generate ASCII representations of tiles. So, I refer people to Harel's book. Briefly, imagine a grid in a plane. Imagine a set of "dominoes" or "tiles" with different edge properties, e.g., some edges are blue, some red, some green, etc. (or the edges can be numbered, have symbols on them, etc.). Suppose one has an unlimited supply of, for example, N different type of tiles. Suppose a tile is placed at some place on the grid, and another tile (possibly a different tile, possibly the same type of tile) is placed some distance away on the grid. The problem is this: Can a "domino snake" be found which reaches from the first tile to the second tile, with the constraint that edges must match up on all tiles? (And all tiles must be in normal grid locations, of course) If the grid area is, say, a finite space, then clearly an exhaustive search of all legal domino snakes would answer the question. (However, even a relatively small grid of, say, 8 x 8, generates a truly enormous number of possible snakes, each of which must be tested. Of course, if a domino snake is "guessed" (a la the "nondeterministic" language one encounters in complexity theory), verification that it is answer is nearly instantaneous (one glances at the solution and verifies it). If the grid is unlimited, then even if the two initial tiles are located close together, there are of course an infinite number of possible snakes.... (Oddly, to me, the domino snake problem is "more undecidable" in the infinite half-plane that in the full infinite plane....) Huang proved that the domino tiling problem is formally equivalent to the standard set of NP problems (consult Harel, or Huang, for more details and more precise language...I'm just going from recollection here!). I like this approach because I can easily visualize the domino tiling problem and can make some points about expansion of knowledge into uncharted areas (research and tool-building is a kind of domino snake expansion, with local laws of physics, etc., the constraints on stepping stones (hand wave inserted here)). I find this easier to understand than more "algebraic" and "logical" versions, such as the representation problem and the word problem. (These other NP problems are also described in Harel (and in standard complexity books, such as Garey and Johnson, Papadimitrou, etc.). It has always been a great hope that some of the provably-hard problems be adapted for use in crypto. And yet factoring remains the core of popular modern crypto programs (discrete logs, too, for D-H). I don't think this is a major cause for worry, though. It's not as if factoring is suddenly going to become "easy." (I think the consensus is that factoring _is_ hard. Whether RSA is really equivalent to factoring also hasn't been proved, as folks have noted, but many think it is, loosely speaking.) --Tim May We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1,257,787-1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."