mathfun

Download

mathfun@mailman.xmission.com

October 2003

53 participants
92 discussions

[math-fun] Fwd: RE: Paterson's worms
by Ed Pegg Jr 03 Oct '03

03 Oct '03

This is *very* interesting stuff. I especially like his set of pictures detailing 59 billion steps of evolution. --Ed Pegg Jr Note: forwarded message attached.

1 0

RE: [math-fun] Researchers Create Super-Fast Quantum Computer Sim ulator
by Schroeppel, Richard 03 Oct '03

03 Oct '03

I looked at this a couple of weeks ago, and am leaning to the "mostly harmless" view. I don't have the real paper, just some abstracts. I'm inclined to give the science writer the benefit of the doubt on explaining factoring time. It's so oversimplified it's wrong, but for a target audience that needs an explanation of what factoring is at all, What can you do? Any article with the subexpression O(e^(1.923*cbrt(logN (loglog N)^2))) isn't going to be read by this audience. I did a little web searching for Fujishima, and he seems to have a real research (or teaching?) job at University of Tokyo. I located an abstract of an earlier paper at http://www.securecms.com/iscas2002/Papers/viewpapers.asp?papernum=2130 ISCAS 2002, IEEE International Symposium on Circuits and Systems Sunday, 26 May 2002 - Wednesday, 29 May 2002 Scottsdale Princess Resort, Scottsdale, Arizona ISCAS 2002 Theme: Circuits and Systems for Ubiquitous Computing Paper: 2130; Session: Nanoelectronics I; Location: Ballroom I Time: Wednesday, May 29, 2:00:00 PM - 2:15:00 PM; Presentation: Lecture Topic: Nanoelectronics and Giga-scale Systems: Giga-scale System Design, Memory, etc. Title: An 8-Qubit Quantum-Circuit Processor Authors: Shin-ichi O'uchi, Minoru Fujishima, Koichiro Hoh Abstract: Quantum-circuit processor (QCP) is a parallel processor that executes quantum algorithms at a processing speed comparable to a quantum computer. The QCP emulates the quantum superposition, utilizing massive silicon devices in the fractal hardware-architecture. Its design cost is relaxed due to that recursive structure although a huge amount of devices are required for it. In this paper, 8-qubit QCP was fabricated within a programmable logic device. This is the first realization of the 8-qubit-hardware quantum computing as far as we know. A factoring algorithm is demonstrated by using it in this paper. Mike Stay sent me an abstract of the paper that's raising the fuss. Unfortunately it's a 250K .pdf, but I'll be happy to send copies to people who don't mind that sort of thing. There's a page of text that explains the Quantum Index Processor, and a page of diagrams that try to convey the idea. The abstract is "75-qubit Quantum Computing Emulator" by Minoru Fujishima, Kento Inai, Tetsuro Kitasho, and Koichiro Hoh, mostly from the University of Tokyo. It's from Extended Abstracts of the 2003 International Conference on Solid State Devices and Materials, Tokyo, 2003, pp. 406-407. This paper claims to implement an FPGA simulator for a 75 qbit quantum computer. It seems to fully simulate 11 qbits with 2048 Processing Elements. [This part seems reasonable.] The PEs in turn represent 64 qbit registers with either bit vectors or probability vectors. [This part I don't get.] The paper mainly claims the gadget is useful for developing and testing quantum algorithms. The paper mentions Shor's factoring algorithm, and claims a 10^26 speedup of something or other. It doesn't explicitly say "we've broken factoring". I don't think it represents a factoring breakthrough, but I don't understand it well enough to be sure. A real 75-bit quantum computer could factor numbers of at most around 25 bits, making very generous assumptions about the number of intermediate temporary variables required. Factoring 75 bit numbers is easy with today's ordinary computers. If we make some guesses about scaling: Assume the 11 "full" qbits is 5 + log2(64-qbit register). A 2048-qbit register would be interesting for factoring, and would need 16 "real" qbits for QIP-style emulation. This would need 65536 PEs, with 2048 plain vanilla bits each. This is large for a chip, but would be practical for a program to emulate. This is too good to credit. As Mark Twain wrote in piece about the historical erosion rate of the Mississippi River, "That's the Beauty of Science: Such a wholesale return of Conjecture, from a trifling investment of Fact." Rich rcs(a)cs.arizona.edu

2 1