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.'"

Comments

Re:So, what can a million qubits calculate?

[Misanthropic Lycanth]

Quantum computer science is still in its infancy. There are some algorithms out there which operate much quicker than their classical counterparts (e.g. factoring, searching). There are others that are impossible. For instance, it is impossible to copy a qubit.

This book is pretty good. It's used at my university to teach an intro course in quantum computing.

Re:megahertz?

[Anonymous Coward]

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)

For the physics-savvy

[carambola5]

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!"

Re:Several thousand qubits is enough...

[Uller-RM]

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.)

Re:uh-oh

[eddeye]

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.