Slashdot Mirror
Quantum Computer Possible From Silicon Fab
Cash Mitchell writes: "This article from the EE Times says 'Researchers at the University of Wisconsin in Madison claim to have created the world's first successful simulation of a quantum-computer architecture that uses existing silicon fabrication techniques.... With existing fabrication techniques, the team estimates that a million-quantum-dot computer (1,024 x 1,024 array) could be built today and operated in the megahertz range.'"
Parallel processing. Instead of one operation at a time you can perform many.
Think, sequencing a DNA strand in one step or cracking large encryption keys in seconds.
This book is pretty good. It's used at my university to teach an intro course in quantum computing.
Physics: Making the universe open source.
Coventional quantum computing is described by a network diagram. This can be translated into a sequence of computational steps, one or two qubit gates acting on selected qubits. The simplest QC architecture would be to run one gate at a time.
Parallel exucution of gates can be arranged (as long as gates act on different qubits) but this is highly dependent on the actual physical system used (ion trap, neutral atom trap, optical lattice, solid state nuclear spin, electron dots, SQUIDs etc).
The key figure of merit is the ratio of gate execution time to the decoherence time. Current estimates of error correction efficiency place the upper bound of this ration at 10^-4 or so (this actually also depends on the ratio of the number logical qubits to physical qubits, sacrificing one for the other). Since quantum dots have very short relaxation times, this places severe constraints on the high speed control electronics. I'll wait for the pre-print or paper before coming to any conclusion on the report. There's still the problem of constructing the damn thing, the purity of the silicon, cooling, EM noise and readout (which isn't mentioned in the article). I'm wary of the heterostructure approach, getting pure silicon to work is hard enough (ask the UNSW guys).
Cheers,
D.
(Not a solid state expert)
Most experts would bet a lot of money on the *exact opposite* of what you just wrote.
Quantum computers almost certainly cannot solve NP-complete problems in polynomial time. Despite years of research, factoring couldn't be shown to be NP-complete, which is probably not a coincidence.
I truly take pride in this discovery... mostly because I attend UW. But I suppose a love of physics helps in that area, too.
Anyways, here's a somewhat technical article regarding the research (PDF).
Oh, and "On Wisconsin!"
IWARS.
People, in general, disappoint me. Politicians even more so.
I can't imagine a port would be necessart since Doom III uses entirely deterministic algorithms and the non-deterministic computation the quantum computer is capable of is a superset of deterministic computation.
It needs 2n + 1 qubits; you start with a superposition, raise it to a power, then measure the result, collapsing the first superposition into a subset of logarithms. The discrete log step is the clincher: once you know the number has a log, you can just perform a Fourier transform on the superposition of logs, and the rest is all number theory.
And yes, you realistically need a LOT of extra qubits for error-correcting codes.
(Just for completeness, the University of Portland used this text for a 400-level semester course on QC. It's not too bad, although it expects you to be quite fluent in number theory and linear algebra.)
IIRC, there have been some ideas that quantum computers could be used to more effectively model protein folding than we can now. Perhaps even allow the reverse problem of protein engineering (given a desired protein active site structure, to either find a structure that will fold to it or show that none will) to be tackled.
If course, just like everything else that would be revolutionary, the best things are those we can't think of yet.
I'm dubious of this though. I'll start believing it when I see a 10 by 10 demonstrator array running at a few kilohertz. Until then, it's just a nice idea.
I'm pleased as anyone to hear that the folks at U-W have developed an experimental implementation of quantum dot QC. Innovation, at any stage, is great.
That said, have the technology to construct something doesn't mean that the thing will work. A quantum device is much different than a traditional electrical device - quantum devices suffer from "decoherence" or a loss of information from the "qubits" to their surrounding environment. This process is EXTREMELY sensitive, and a huge limitation upon QC at the present time. A look at Ike Chuang's book on QC, and you'll see that nearly every implementation of QC is decoherence-limited in some way (quantum dots included).
The Dot people are also not alone - Prof.'s Monroe and Kielpinski at U-Michigan and NIST, respectively, have published a similar paper for ION TRAP-based QC. The ion trap they suggest (a Quantum CCD) is feasible to construct but immensely difficult to operate in practice. Prof. Chuang has produced a WORKING QC on a small scale in NMR. Simply suggesting a means to produced a trap is not enough to suggest working, large-scale QCs are around the corner.
Quantum computers work differently from computers today. In computer science there's something called Big O notation to sort of describe relative speeds of algorithms. Most brute-forcing methods probably have exponential times. SO if an algorithm had a O(2^n), adding a single extra-bit would double the time it took to brute force. Quantum computers can reduce this to polynomial time for a O(n^2). So if you add an extra bit, the time it takes is only increased slightly. And I think that key-lengths that take a long time to brute force with quantum computers, would be so large, that it wouldn't be feasible to use.
But there are different methods of encryption for quantum computers. Althought as far as I understand, they all work on the transmission medium, and not on the actual data, so I don't how this would apply to routed data, or stored data.
"Knowledge makes us accountable." - Che Guevara
There was a recent discussion about quantum computers (QCs) on sci.crypt. The consensus is, given a powerful enough QC, all public-key methods (RSA, Diffe-Helman, Elliptic Curve systems, etc) are badly broken by Shor's algorithm.
But symmetric ciphers (AES, DES, Blowfish, Serpent, etc) only have their effective key length cut in half, as a consequence of Grover's algorithm for searching an unordered list in O(sqrt(N)) time. So 64-bit keys become crackable with 2^32 work, and 128-bit keys in 2^64 work. Using 256-bit symmetric keys is considered sufficient to negate the threat of QCs.
I'm not sure about other cryptographic constructs such as PRNGs (Yarrow, ANSI X9.17) or hash functions (SHA-1, MD5), but I'm guessing at worst you would just have to double the size of the internal state to achieve security levels comparable to today.
Disclaimer: IANAC (I am not a cryptographer) but I do know quite a few.
Democracy is two wolves and a sheep voting on lunch.
Problem is that factoring is not equivalent to the discrete logarithm problem. Solving discrete logs implies factoring, but factoring does not (as far as anybody knows) imply solving discrete logs.
Note that, if given the ability to solve the discrete logarithm problem, we could obtain RSA private keys without actually factoring the modulus N. All we would need is one known plaintext-ciphertext pair (trivial to obtain), and then we would just run
Modulus = N;
Base = CipherText;
Result = PlainText;
SecretKey = SolveDiscreteLog(Base, Result, Modulus);
Alternately, you could run
Modulus = N;
Base = 3;
Result = 1;
Phi_N = SolveDiscreteLog(Base, Result, Modulus);
This will give you phi(N), which is (P - 1)(Q -1) where N = PQ. Then you just use the extended Euclidean algorithm to find the multiplicative inverse of the public exponent E mod N.
The latter approach assumes that 3 is not a factor N, by the way, so keep that in mind.