Slashdot Mirror
Significant Advance in Quantum Computing
wcitech writes "Apparently scientists have been able to create circuitry that mimics the behavior of atom pairs by using superconductors." From the article: "The work, reported in the Feb. 25 issue of the journal Science, demonstrates that it is possible to measure the quantum properties of two interconnected artificial atoms at virtually the same time. Until now, superconducting qubits--quantum counterparts of the 1s and 0s used in today's computers--have been measured one at a time to avoid unwanted effects on neighboring qubits." The second Quantum computing revelation this month, in fact.
I don't think it works that way.
"Two entangled qubits, meanwhile, can simultaneously evaluate four inputs. Put another way, a traditional memory register with eight bits can store only one of a possible 28, or 256, digital "words," but a quantum register with eight qubits can represent and compute with all 256 words at once."
link
If you could have 32 entangled qubits, you could simultaneously evaluate 2^32 inputs, which is more than 4 billion possibilities.
Wikipedia has a good comparison of the differences between a traditional register and a quantum register (qubits).
Illegal? Samir, This is America.
A quantum computer will probably never have 'registers' in the conventional sense since deterministic I/O like in a standard register would alter the quantum state every time a photon hit the qubits. In fact, beyond solving certain specific types of problems don't expect a quantum computer to be running minesweeper anytime soon. IANAP but from what I've seen of current experiments, the results aren't even exact like you would expect from a regular CPU, rather, a whole crapload of qubit runs are executed at once, and the most probable realized state is considered to be the 'answer'. I'm not even sure if it is possible to 'reset' the qubits after the operation without destroying them. Physcists, feel free to chime in now.
AntiFA: An abbreviation for Anti First Amendment.
Quantum computers probably won't ever displace conventional computers completely; while there are some tasks at which they excel, they would be incredibly inefficient for typical computer tasks. A more realistic role for a quantum computer would be a coprocessor - when the host CPU is presented with a problem that could be better solved by a quantum computer, it offloads that problem to a dedicated quantum computer to which it is attached.
It would be a tremendous waste of technology to use a quantum computer to evaluate operations which are serial, rather than parallel, in nature. While this may someday change - there was, after all, a day when all the computers in the world didn't have as many transistors as are in a single modern desktop - it is likely that for the forseeable future, quantum computers will remain far too valuable and rare to be used for anything a more conventional computer could do as well.
That's it. I'm no longer part of Team Sanity.
Quantum computing: a view from the enemy camp
Quantum computing relies on processing information within a quantum system with many continuous degrees of freedom. The practical implementation of this idea requires complete control over all of the 2^n independent amplitudes of a many-particle wavefunction, where n>1000. The principles of quantum computing are discussed from the practical point of view with the conclusion that no working device will be built in the forseeable fu
using 32 qubits gives you ((2^32)-1) and the ability to examine 4'294'967'295 solutions simultaneously you'd need 6 qubits to examine at least 32 states and no more than 63 states
From my understanding, you aren't getting all possible answers simultaneously. You are evaluating all possible answers simultaneously and statistically getting the "right" answer.
This is very interesting. Where does /.'ers get their ideas from? http://hilbert.math.uni-mannheim.de/~seiler/cray.j pg/
The previous poster was right. The q-registers are QM wavefunctions where the eigenstates represent possible solutions to the problem being computed. You are allowed to manipulate the wave function via quantum (hamiltonian IIRC) operators to your heart's content, but you can only measure one of the eigen states at a time. the tricky part is manipulating a q-register wave function such that the right answers are represented by eigenstates that are more probable than the ones that are wrong. It solves probablistic algorithms, and you don't a QC to do that. What a QC gives you is a way of operating on all possible states at once, whereas a regular turing machine type of computer can only act on one state at a time. This ability allows for a greater range of problems to be tackled in polynomial time by QM probablistic algorithms, such as, famously, factoring a number into its primes.
Quantum computers can change the rate at which problems are solved, but not whether or not a solution is technically achievable through computation.
Goldbachs' conjecture and the Riemann hypothesis might be provable through an accelerated brute forcing of all possible proofs if, for example, P=NP and algorithmic degrees and coefficients are reasonable, but this is only because such a brute force may be doable already with a sufficiently ginormous length of time (assuming that they are in fact provable to begin with, which some true propositions are not (unless our math is internally inconsistent)).
The halting problem cannot be solved for arbitrary Turing machines. Period. No algorithm, as we think of them, using quantum computers or not, will get around the fact that such a solution would create a logical inconsistency (a program could determine whether or not it itself would halt, and then do the opposite, but then it would have been wrong, which it can't be by assumption, and so reality bursts into flames). The only possible catch is that a technique that cannot be encoded in a Turing machine would not cause this particular logical inconsistency to arise. Basically this leaves an opportunity for solution through revelation. Or not, depending on your philosophical persuasion towards flaimbait and the rest of existence.
Again, though, quantum computers do not allow one to execute algorithms that are beyond simulation (albeit more slowly) on classical computers. What ifs are fun, but this one, at least in part, is worse than baseless.
policy analysis and political satire
You've hit on the basic power of quantum computing. In rough terms, while we have to go from 32 to 64 bits to double the processing power of a classical computer, we double the power of a quantum computer by adding just one more bit. This change in scaling allows you to do things like search a database in O(Sqrt[N]) time and factor a large number in polynomial time.
wait a sec buddy... flux quantization is definitely a quantum effect and that is what this is based on at the core....hell superconductivity is a quantum in nature. Quantum != small... nano==small. So although this is not a nonoscale implementation of a quantum bit(s), it is a quantum bitbit(s). Plus this is macroscopic implementation so it can be easily fabricated using standard photolith techniques.
That's the trick of designing a quantum algorithm. You set things up so that the "right" answer results in constructive interference, while the "wrong" answers interfere destructively. At the end of the quantum computation, all the probability rests in the answer, but in the course of the computation the system has explored many more possibilities through superposition.
You actually only get one answer, but all possibilities have been "computed" and the probabiliy that the answer you get is the correct one is atleast above 50%. So, if you need to be certain, you repeat.
It basic computational theory terms, it is a true non-deterministic fintite automata. For example, suppose you want to compute the sortest route covering all the edges on a graph (if you dont understand that, imagine streets as edges, and that you want to travel down every street).
This is a classic NP problem, the traveling salesman problem. It is very simple to devise a method of computing a solution, but for a graph of N nodes, the complexity is O(x^n), or exponential growth. In other words, 2 nodes isnt bad, but 10 nodes takes x^8 times as long (x is some constant btw), so for any non trivial TSP, that is quite a long time.
A quantum computer, however, can solve it in roughly O(N) time, because it computes all possible paths at once, and then the shortest is "probably" the resulting state.
Simple in concept, but implemention is another thing... Google for Shor's algorithm if you want more information.
Ummm... the halting problem is PROVEN to be unsolvable. Check any introductory computational theory text.
Ok, it works like this: you start off by initializing your qubits to a uniform superposition of states. That is every different possible string of 1s and 0s of a length n has an equal chance of occurring if you take a measurement at this point. Then you perform an operation on this state. The Cliff's notes version of things is that you should pick an operation that transforms each state onto one that is likely to be the answer. Then when you measure the outcome you are likely to get the answer you're looking for. So long as the probability of getting the wrong answer has some upper bound less than one you can just rerun the algorithm until you have get the right answer.
All of the basic theoretical work is in place. We've got algorithms, we've got error correcting methods, we've got quantum programming languages and we have every reason to believe it will work. Based on other experiments in quatum mechanics all of the basic principles work.
The biggest problem with quantum computing is that it's going to be expensive for a long time. These systems are fragile and must be shielded from outside events. Implimentation hasn't caught up with theory yet. We've got problems such as storing a qubit for an extended period of time and it may be a while before useful memory densities are achieved.
There's a lot left to be done, but quantum computing isn't a scam.
Thode PDFs don't speak about quantum computers. They speak about using quantum devices to build more efficient classical computers (the fact that they call it quantum cellular automata doesn't mean that it is a quantum computer, it just uses quantum dots for operation). Indeed, they depend on inelastic processes, exactly those processes which actually pose the biggest problem in quantum computing.
Not every computing which uses quantum mechanics is quantum computing (indeed, otherwise our current computers would have to be quantum computers since semiconductor physics just cannot be done classically).
Quantum computers are computers which specifically work with quantum information (i.e. superpositions and entanglement). The papers you cited use quamtum dots to more efficiently process classical information.
Now that doesn't mean that the QCA work is less important (indeed, I think it's far more probable that you'll at some time work with computers based on QCAs than that you'll ever see a real quantum computer in your life). It's just that QCAs are not QCs.
And yes, I am a quantum physicist (although I don't work on quantum computing).
The Tao of math: The numbers you can count are not the real numbers.
There's no need to speculate on how a quantum computer will work. We already have working examples, and we already know the generic properties of them. Instead of trying to figure it out on your own, go read the vast amounts of information on the topic available.
The three properties of the QC that are most important:
1. You can set the state of the qubits to whatever you like.
2. You have some transformation that the qubits will go through. This can be arbitrarily complex, and will be the most interesting part of the machine.
2. You can get a really good estimate of the state by doing the operation from the same initial state several times. See, when you go to measure a quantum state, you get one possibility of many. You have to make a lot of measurements to figure out what is really happening.
The best comparison is to think of the single-slit experiments you did in High School physics. You take a parallel light source (sunlight, laser, light from a distance) and have it strike a plate with a very thin slit. Then you hold a piece of paper where the light comes out. You will see bands of light, and some chromatic aberrations (you will see colors).
If you consider a single photon travelling from the light source and approaching the slit, passing "through" the slit, and then travelling off into any one of the finite number of directions, you ask the question: How can we predict which way it will go?
The answer is you can't. You have to do it a lot (like with a beam of light) and you can easily see what the probabilities are from that.
You can probably think of the experiment I described above as a very simple form of a quantum computer. You set the input - the light travelling into the slit. You have the transformation - the slit. And you can read the results by doing it several times.
That's all quantum computing will do for you. It's up to the really smart guys in white lab coats to figure out how to turn that into something useful.
I believe this will all be abstracted away from your eyes, just like today you don't worry about which register your integers is stored in and such. You will merely say, "Run the calculations on this set of data and give me the result" and it will do it before you can blink.
Heck, ordinary people won't even get to own a quantum computer until two things happen: (1) We find a better use for them than hacking into banks and stealing people's identities, and (2) we have built up enough of a reportoire of transformations that some subset of that is actually useful to solve the problems we face in computing today.
The radical sect of Islam would either see you dead or "reverted" to Islam.
NP stands for Nondeterministic Polynomial Time so, yes, in theory, a quantum computer should be able to solve any NP problem in polynomial time, since any NP Complete problem (Im not sure if factoring ala Shor's algorithh is one) will reduce to any other NP problem in P time. As far as P = NP, a quantum computer would not resolce that, since it is still just a brute force attack on an NP problem. Resolving P v. NP is a theory problem, not a hardware problem. It might be more acuarate to call it a "non-deterministic" computer. You can currently similate a quantum computer (VERY slowly) on a serial device, and it could, eventualy, solve any NP problem. You actualy wouldn't need the simulation of the QC, but either way "eventualy," in most nontrivial cases, would mean after the sun burns out...
You can analyze the probability of an algorithm's success without knowing the answer it'll produce. This is a well-known technique even outside the realm of quantum computing. Here's a simple example: I have a number between 1 and 100; try to guess it. Of course, there's the standard O(log n) technique (which is probably the best one in this case!), but you could also just guess randomly until you find the number. In this case, you have a certain chance of finding the answer within, say, 200 steps (can't remember offhand but it should be fairly high). If you decide to arbitrarily terminate the search at this point, you can calculate the probability of the algorithm succeeding. Standard practice is to just prove that you have at least a 50% chance of success (at which point you can achieve an arbitrarily high chance of success by iterating the algorithm enough times) -- of course, 50% is an arbitrary number; any number above 0% would work from a theoretical point of view.
An example of a real algorithm that works this way is primality testing. There's an easy test that returns "false" for all primes, and returns "false" or "true" with equal probability for composites. (search for "Solovay-Strassen") Since the probability of a false negative is 50% (when you have a composite) if you pick enough samples and they all fail, you can say that there's a "high probability" that the number is prime. (for instance, 256 tests will get you odds of 1/(2^256) that the answer is wrong)
I don't pretend to understand quantum computing, but I do know that the basic processes are probabilistic, so it's not surprising that you end up with a probability of finding the right answer. Also bear in mind that there are only two (last time I checked, anyway) known algorithms for quantum computers, or at least only two that are significantly faster than the "standard" version, so it's not like QC is claimed to solve every open problem in computer science (despite what some guy above was saying).
Daniel
Hurry up and jump on the individualist bandwagon!