Slashdot Mirror
Tiny Holes Advance Quantum Computing
Nick writes "Worldwide, scientists are racing to develop computers that exploit the quantum mechanical properties of atoms - quantum computers. One strategy for making them involves packaging individual atoms on a chip so that laser beams can read quantum data. Scientists at Ohio State University have taken a step toward the development of quantum computers by making tiny holes that contain nothing at all. The holes - dark spots in an egg carton-shaped surface of laser light - could one day cradle atoms for quantum computing."
Indeed, talking about quantum computers as an improvment on silicon computers is like talking about jumbo jets as an improvement over cars. Ie not an improvment at all, unless you have something very specific to do (factor a large integer or cross an ocean). And you need the simpler alternative to use the more advanced one (car to get to the airport, regular computer to feed and extract data for quantum computing).
Quantum Leap was an excellent TV show that ran through the late 80's and early 90's. The premise was that "Dr. Sam Becket" (who now plays Captain Archer on Enterprise) invented a time machine that would allow him to reach points throughout his lifetime. The problem is that he never quite got the kinks worked out of his retrieval program, and now finds himself randomly leaping from life to life. The tagline of the show was, "striving to put right what once went wrong and hoping each time that his next leap will be the leap home." (Usually then followed by us seeing him leaping into someone's life. Something utterly confusing then happens to him and he utters the words, "Oh boy".)
And now you know... the rest of the story.
Javascript + Nintendo DSi = DSiCade
In fact, it would be very surprising if it turns out to be NP-complete, as it is in NP intersect co-NP. Also, no efficient quantum algorithms are known for NP-complete problems, and it is generally suspected that quantum computers won't be able to solve them efficiently. For example, see this semi-technical paper.
;)
You had better get that right in your undergrad thesis
I like to think of quantum computers as binary on the outside, analog on the inside. You can only read and write in binary, but the operators in the middle can be real valued (complex valued even).
Nielson and Chuang's book is neat (I have it sitting on my floor 3 feet from me ATM). It's mainly written for the physicist to learn quantum circuits and algorithms. It takes a year to read, but by the time you are done, you should be able to read and understand most of the papers in the field.
A much lighter book on the subject is "Explortions in Quantum Computing" by Williams and Clearwater. It gives a basic overview without much assumed knowledge.
Also "Problems & Solutions in Quantum Computing & Quantum Information" by Willi-Hans Steeb and Yorick Hardy has alot of fun problems in it. It's the kind of book thats good to read on a bus, or an airplane.
Not exactly. Quantum computers can simulate classical computers with no problems. That's one of the tenets of quantum computation.
If by "no problems" you mean "severe and most likely insurmountable quantum coherence issues". Any quantum computer big enough to simulate a modern sized classical computer will contain so many qubits as to have problems with interference from the outside world. IIRC the problem of quantum coherence is roughly exponential in the number of qubits in a system (one of the reason we don't have 1000 qubit computers sitting around). Just having enough qubits to remember my RAM would get pretty ridiculous.
The truth is that quantum computers, in the forseeable future, will likely be an orthogonal type of computing system to classical computers - a coprocessor used for certain problems with small memory requirements but large search spaces. Many of our most important computations lie in this regime, but I doubt quantum computers will outperform classical computers on most ordinary stuff (i.e. word processing, running a webserver, handling large databases) due to its seriality and memory intensive nature. (Insert quote like "640 k ought to be enough for anybody" here)
Also, the fact that quantum computers can factor large integers efficiently necessarily implies that they can do other NP-complete problems efficiently, such as the traveling salesman problem.
It implies no such thing. Traveling salesman problem is NP-complete, and while we have no solid proof that a quantum computer cannot solve an NP-complete problem in polynomial time, Shor's algorithm is also in no way any kind of proof, as integer factorization is merely NP, not fully NP-complete as you claimed.
Yes, IAWAUGTOQC (I am writing an undergrad thesis on quantum computation).
Yes, I do have a degree in physics. You may wish to check said thesis in light of errors explained above.
Yes, I do have a degree in physics. You may wish to check said thesis in light of errors explained above.
And I'm doing a Ph.D in physics on quantum computing. Sorry to be a prick about it, but you were a bit rough on the undergrad who posted above, and what goes around comes around. As long as that guy isn't doing his research on slashdot, he'll probably be OK..
If by "no problems" you mean "severe and most likely insurmountable quantum coherence issues". Any quantum computer big enough to simulate a modern sized classical computer will contain so many qubits as to have problems with interference from the outside world. IIRC the problem of quantum coherence is roughly exponential in the number of qubits in a system
No, the problem is not exponential in nature. It has been shown that if the error rates for storage, gates, etc. can be brought below certain thresholds (typically 10^-3 to 10^-6), then arbitrarily long computations can be performed. There are many papers on the subject, but here is one.
The only way in which decoherence could pose an insurmountable problem is if there is fundamentally new physics that plays a role in the regime between "quantum" and "classical". Nobel Laureate Tony Leggett has talked (in a recent issue of Science, and at the 2005 Gordon Research Conference) about how we might find such new laws of physics if they exist, or otherwise rule out their existence.
It implies no such thing.
You are correct. In the early days of the field, I think there was a little bit of confusion about whether quantum computers could do NP-complete, but it has long since been sorted out.
I recently attended a talk by Ike Chuang about general issues in the field. Chuang feels that quantum simulation and quantum communication will be the important applications, although he emphasized communication. I think quantum simulation is way, WAY underappreciated. Not only is it going to revolutionize protein folding, drug design, and other biomed applications, I have a hunch it may prove to be a prerequisite for advanced nanotech.
The article is not particularly good. The supposed problems that optical lattices will have in addressing qubits in the interior of a 3-D lattice are "solved" by using what is essentially a 2-D lattice on a chip. The same can easily be done with optical lattices.
Of course, addressing atoms inside a lattice of moderate size can be done using a high numerical aperature lens to focus an addressing beam onto a single atom. The addressing beam produces an AC Stark Shift of the appropriate hyperfine sublevels of the atom (in the case of Cesium-133 qubits, it shifts each of the mF sublevels of the F=3 and F=4 states), with the exact shift being different for different sublevels. This allows transitions in that particular atom to be driven by a microwave pulse which is detuned from all the other atoms in the lattice. Just how well can we address one atom while not disturbing atoms in adjacent planes? I'll know in a week or two. I'm currently simulating one and two qubit gates in this exact scheme. The actual experiment is also under construction, at Penn State.
Anyone interested in a distributed computing project to develop quantum computers? I could use help from developers, and later, also regular user input.