Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Supercomputing Science

Significant Advance in Quantum Computing 180

Posted by Zonk from the they-put-the-q-in-quantum dept.
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.
This discussion has been archived. No new comments can be posted.

Significant Advance in Quantum Computing More

Significant Advance in Quantum Computing

Comments Filter:

  • Phew (Score:5, Funny)

    by qw0ntum ( 831414 ) on Friday February 25, 2005 @10:56PM (#11784965) Journal
    Before I go worrying about quantum computers, I need to get my own working. But in a quantum world, I guess they are working AND messed up at the same time.

    • Re:Phew (Score:3, Funny)

      by Pax00 ( 266436 )
      Before I go worrying about quantum computers, I need to get my own working. But in a quantum world, I guess they are working AND messed up at the same time.

      Broken and working at the same time.. how is that different than running windows?
    • Wouldn't they actually be neither broken nor working? Until you tried to use it, of course, at which point you'll have to decide whether to make funeral arrangements or provide a saucer of milk.

  • I'm not a quantum engineer (Score:5, Interesting)

    by GreyWolf3000 ( 468618 ) on Friday February 25, 2005 @10:58PM (#11784972) Journal

    This question may be stupid but...

    Would we need to read 32 quantum states at a time to get '32-bit' registers to build basic processors??

    • Re:I'm not a quantum engineer (Score:5, Informative)

      by Jeff DeMaagd ( 2015 ) on Friday February 25, 2005 @11:11PM (#11785044) Homepage Journal
      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 [technologyreview.com]

      If you could have 32 entangled qubits, you could simultaneously evaluate 2^32 inputs, which is more than 4 billion possibilities.

      • Re:I'm not a quantum engineer (Score:5, Interesting)

        by MOBE2001 ( 263700 ) on Friday February 25, 2005 @11:18PM (#11785084) Homepage Journal
        "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."

        So, If you get all possible answers simultaneously, how do you tell which one is the right answer to the problem you're working on?

        • Re:I'm not a quantum engineer (Score:4, Informative)

          by Jeff DeMaagd ( 2015 ) on Friday February 25, 2005 @11:27PM (#11785138) Homepage Journal
          From my understanding, you aren't getting all possible answers simultaneously. You are evaluating all possible answers simultaneously and statistically getting the "right" answer.
          • From my understanding, you aren't getting all possible answers simultaneously. You are evaluating all possible answers simultaneously and statistically getting the "right" answer.

            So are you saying that you already know the probability of the right answer before you compute it? Or are you saying that the QC already knows what answer you're looking for and somehow futzes with the probabilities so that when you collapse the wave function, voila! the correct answer is revealed, as if by magic?

            You know, the m

            • Re:I'm not a quantum engineer (Score:5, Insightful)

              by Creepy Crawler ( 680178 ) on Saturday February 26, 2005 @01:40AM (#11785593)
              ... so that when you collapse the wave function, voila! the correct answer is revealed, as if by magic?

              Most of the time.

            • Re:I'm not a quantum engineer (Score:2, Informative)

              by Anonymous Coward
              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 lookin
            • What you actually need is a function that flags 'this is the right answer', and then you just read off the inputs.

              For example, with a sufficiently large QC, you could find an input that matches a particular SHA-256 input INSTANTLY. Ie, "Give me the input where the output is equivalent to this hash".
            • 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'

          • Re:I'm not a quantum engineer (Score:5, Informative)

            by Anonymous Coward on Saturday February 26, 2005 @12:10AM (#11785343)
            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.
        • http://en.wikipedia.org/wiki/Quantum_computer#Bit s _vs_qubits [wikipedia.org] sez of an example 3-bit quantam operation...

          Upon termination of the algorithm, the 8-dimensional complex vector stored in the register must be somehow read off from the qubit register by a quantum measurement. However, by the laws of quantum mechanics, that measurement will yield a random 3 bit string (and it will destroy the stored state as well). This random string can be used in computing the value of a function because (by design) the proba

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

        • Re:I'm not a quantum engineer (Score:4, Informative)

          by aprilsound ( 412645 ) on Saturday February 26, 2005 @01:51AM (#11785642) Homepage
          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.
          • Is that how autistic people work? their brain is really a quantum computer, it just does all combinations instantly, but they get the correct one or know the correcy one, where us normal humans just dont know which is which or have no tap into the QC

            • Re:sounds like rainman autistic computer.... (Score:4, Interesting)

              by ByteSlicer ( 735276 ) on Saturday February 26, 2005 @03:39AM (#11785952)
              The similarity between brains and a quantum computer comes from the fact that the neurons in the brain also process the data in parallel. There is no quantum computing going on inside the brain. There recently was an article [slashdot.org] about an autistic savant explaining his calculation skills. Numbers are just shapes to him, and multiplying them means he just merges them in his head and reads back the emerged shape. Probably his visual cortex is doing the parallel operations on the shapes here (maybe similar to using the shader engines on your graphics card for doing calculations).
              • What leads you to believe that the brain does not take advantage of quantum effects?

                I read an article about 5 years ago that said that the human brain does take advantage of quantum effects, so if we want to design a computer as powerful as the brain, we will have to understand not only chemical, electrical, and biological processes, but quantum as well.

                So if you've heard differently, please share.

                • I'm not saying there are no quantum effects happening in the brain, just that the brain doesn't work as a quantum computer. The current understanding is that signaling between neurons is electro-chemical. Artificial neural nets were modelled after this, and although far from perfect, seem capable of doing things real brains can do (like recognizing faces). Neural networks don't work the same way quantum computers do. Their power comes from over 10^11 neurons working in parallel, each having maybe 1000 conne
          • Is there a way to use the quantum computer for TSP? The only quantum algorithms I know of is Shor's factoring and Grover's algorithm. That sort of put me off going too much into the QC area, aside from taking 2 or 3 classes on the subject (I have a comp sci degree). I know that searching and factoring are very important algorithms but what about others like: sorting, graph algorithms, SAT or fast matrix multiplication .
            • It seems that TSP, if not directly expressible as a searching algorithm, could certainly be expressed as one. In the end I guess we'll have to have a regular computer and quantum computer all within the same box, most likely with the quantum computer as a side processor kind of like an FPU (though presumably with a much more complex instruction set).
            • Is there a way to use the quantum computer for TSP?

              Nobody knows, as far as I know.

              TSP is NP-complete. As nifty as Shor's algorithm is, it only solves an NP problem in polynomial time. That implies either 1) nothing about solving other NP problems in polynomial time, 2) that it might be possible to solve other NP problems, or 3) that integer factorization is not NP - it's either P or some other computational class we haven't discovered yet.

          • this is dead wrong (Score:3, Insightful)

            by rufusdufus ( 450462 )
            there is no quantum algorithm to speed up np complete problems. this whole post is just not right
        • So, If you get all possible answers simultaneously, how do you tell which one is the right answer to the problem you're working on?

          Shhh! You'll screw with thier grant applications.
      • Here's a thought: how about when we've mastered the technology, we could create entire atoms and, eventually, entire components using entangled particles. So if the NSA had one computer and I had the same computer with an entangled network interface or video card, would I be able to surreptitiously spy on the NSA without them ever knowing?

        At the very least, it'd make a neat premise for a novel if someone hasn't written something like that already.
        • Yes, and NSA would be able to look at your porn. The result would be you spying on spys spying on your own porn. I think I just developed quantum masturbation... I'm going to go clear some shelf space for my Nobel.

      • This isnt right either.. (Score:4, Insightful)

        by rufusdufus ( 450462 ) on Saturday February 26, 2005 @01:34AM (#11785570)
        A quantum register does not actually represent all possible inputs. It represents a superposition of all possible inputs; this is a very important distinction.

        When the register is 'read' after a computation, it contains exactly one result representing the results of one random possible input. Using a classical algorithm with the register would be exactly like a normal computer with a random setting as the input.

        Getting anything special from a calculation from a qubit register is extremely tricky. Shor's algorithm does a special quantum fourier transform on the register to get the most common possible output [this is a metaphor] and only works because the values of the qbits are not independent (and thus do not represent all possibilites). The algorithm must be run several times to even get a statistically meaningful result.

    • Re:I'm not a quantum engineer (Score:5, Informative)

      by kernel_dan ( 850552 ) <slashdevslashtty ... m minus math_god> on Friday February 25, 2005 @11:13PM (#11785055)
      Wikipedia has a good comparison [wikipedia.org] of the differences between a traditional register and a quantum register (qubits).

    • Re:I'm not a quantum engineer (Score:5, Informative)

      by CajunArson ( 465943 ) on Friday February 25, 2005 @11:16PM (#11785073) Journal
      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.
      • Quantum computers would actually achieve a major goal for minesweeper development: the ability to dynamically change the mines to maximize frustration without invalidating previous moves and all in constant time.

      • We already know what they will look like (Score:5, Informative)

        by jgardn ( 539054 ) <jgardn@alumni.washington.edu> on Saturday February 26, 2005 @04:21AM (#11786020) Homepage Journal
        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.
    • Sort of. While it would be necessary to have 32 qubits to build a 32-bit processor, that processor would be radically different from the one that's probably in your computer right now.

      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 b

      • 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.
    • sort of...but the concepts of bits are different

      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

  • And the winner is... (Score:5, Funny)

    by dfn5 ( 524972 ) on Friday February 25, 2005 @11:00PM (#11784984) Journal
    Number 3 in a quantum finish

    No fair! You changed the outcome by measuring it!

  • I'm guessing... (Score:3, Interesting)

    by OneOver137 ( 674481 ) on Friday February 25, 2005 @11:02PM (#11784995) Journal
    the whole paradigm of 'xx-bit processor' will go out the window once the technology matures and software makes full use of the capabilities.

  • applicable quote (Score:5, Funny)

    by Triumph The Insult C ( 586706 ) on Friday February 25, 2005 @11:02PM (#11784996) Homepage Journal
    "So, computers. I hear they basically break down to a bunch of ones and zeroes. I don't know how that means I can see naked women on my screen, but God bless you people"
  • Scientists also announced that they had discovered a principle similar to Von Neuman's Catastrophe, namely The Slashdot Effect. This effect makes it impossible to both link to the story from Slashdot and read the story thus linked, as the very act of linking it renders the story impossible to read. To isolate these quantum fluctuations from the greater Slashdot Effect, scientists have suggested calling this specific quantum problem Commander Taco's Catastrophe...

  • Not so soon, may be never (Score:5, Informative)

    by karvind ( 833059 ) <karvind@NoSPAM.gmail.com> on Friday February 25, 2005 @11:21PM (#11785095) Journal
    A non BS critical review [arxiv.org].

    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

  • Man reminds me more and more of God every day. Creation in our own image, no?
  • Damn magnets. Seriously though, they're 'mimicking' a quantum effect, not using real quantum states. If it doesn't say 'Quantum' on the box then it's not quantum.

  • What's the point? (Score:3, Funny)

    by jholzer ( 301249 ) on Friday February 25, 2005 @11:33PM (#11785169)
    From http://en.wikipedia.org/wiki/Quantum_computer#Bits _vs_qubits
    "This dramatic advantage of quantum computers is currently known to exist for only those three problems: factoring, discrete log, and quantum physics simulations."

    I don't see Quake 10 on the list, so what's the point?

    • Re:What's the point? (Score:1, Insightful)

      by Anonymous Coward
      "I don't see Quake 10 on the list, so what's the point?"

      accurate video game physics down to the quantum level
      • "accurate video game physics down to the quantum level"

        Not to nitpick, but what's the point in that? Is any normal human being capable of being able to tell what's going on at the quantum level?
        Im afraid not, "quantum foam" (the distortion of space and time and seemingly impossible random things happening) is very volatile and unpredictable, however, like quantum computers, the randomness in all of this ends up with the one most likely result at the macroscopic level (things big enough that we can see th

    • Re:What's the point? (Score:4, Insightful)

      by Jerf ( 17166 ) on Saturday February 26, 2005 @12:44AM (#11785452) Journal
      I don't see Quake 10 on the list, so what's the point?

      The point, of course, is to solve the factoring, discrete log, and quantum physics simulation problems.

      Whether that is worth the resources being thrown at it is an exercise for the reader.

      (The more I learn about quantum computing, the less likely I think it is and the more I wonder what all the fury is about. I expect this will collapse in about two years and be remembered right next to the "great" AI era of the 80's. Hey, maybe I'm wrong... and hey, maybe 80's style AI programming really is the path to strong AI and we just didn't try hard enough... but I'm not holding my breath and the burden of proof remains on the researchers.

      It reminds me of FTL or teleportation; with every little "advance" physics fanboys crow about how much "closer" we are, whereas I see an ever-refined understanding of why the thing we are looking for is still impossible and the potential loopholes slamming shut.

      Preparing for "-1, troll" from physics fanboys in five... four... three...)
      • (The more I learn about quantum computing, the less likely I think it is and the more I wonder what all the fury is about. I expect this will collapse in about two years and be remembered right next to the "great" AI era of the 80's. Hey, maybe I'm wrong... and hey, maybe 80's style AI programming really is the path to strong AI and we just didn't try hard enough... but I'm not holding my breath and the burden of proof remains on the researchers.

        It reminds me of FTL or teleportation; with every little "a

        • Read that page, knew everything on it, assumption of ignorance wrong, mind not changed by pop-science overview.

          I think the "problems" you wave away with such glibness are exponential, and the most power we'll ever be able to being to bear on the problem is polynomial. Current research has done nothing to dissuade me of this, and the fact that such computers remain "small" are exactly what I mean; for small values we can hold it together, but it says little about our ability to build at large values. When s

    • Re:What's the point? (Score:3, Interesting)

      by Zeinfeld ( 263942 )
      "This dramatic advantage of quantum computers is currently known to exist for only those three problems: factoring, discrete log, and quantum physics simulations."

      Actually it is slightly more general. Having spoken with some high powered cryptographers (i.e. the ones with the Turing awards) there is a strong suspiscion that any problem which allows a public key cryptosystem to be created will turn out to be efficient on a QC machine.

      There seems to be something pretty fundamental going on there. The rea

      • You need to check with better cryptographers; a massive speedup does apply to symmetric ciphers, in the form of Grover's Algorithm. [wikipedia.org] It reduces the keyspace you have to search by an exponential factor of 0.5, meaning breaking 128-bit symmetric crypto by brute force is within the realm of well-funded private citizens.
        • You need to check with better cryptographers; a massive speedup does apply to symmetric ciphers, in the form of Grover's Algorithm. It reduces the keyspace you have to search by an exponential factor of 0.5, meaning breaking 128-bit symmetric crypto by brute force is within the realm of well-funded private citizens.

          But attempting to apply it to AES or even DES requires a vast quantum computer, you have to essentially unroll all the loops and apply it as hardware. So the complexity is much higher than break

        • All you have to do with symmetric crypto is double the bits to defeat Grover's algorithm. After the initial doubling, you're back to the same "arms race" between crypto and Moore's Law. That's a trivial situation compared to public key crypto. (Although, Shor's algorithm does require a QC with roughly 2n coherent qubits for an n-bit prime, which provides public key crypto with a bit of a reprieve. If the number of qubits in a QC follows the same pattern of growth that memory size has, another arms race m

  • It's only a matter of time before my quantum computer is produced, and it's powered by Lucky Charms and Beer.

    But in reality, I wonder if there's any advances in superconductivity?

  • cray icon (Score:2, Informative)

    by pulgabm89 ( 851427 )
    This is very interesting. Where does /.'ers get their ideas from? http://hilbert.math.uni-mannheim.de/~seiler/cray.j pg/ [uni-mannheim.de]
  • Will some one give me an idea of what this means for our current encryption systems and me as a private citizen ... kinda wishing to keep things still, ya know, private and without having access to the same horsepower?
    • Nothing.

      No, wait. It means that we're going to have to stop lying to ourselves, admit that no communication mechanism can ever be capital-S secure, and listen to the geeks who've been saying that security needs to be convincing people not to try, detecting when they do, and being able to recover from any intrusion.

  • Booor-ing... (Score:5, Interesting)

    by Goonie ( 8651 ) <robert,merkel&benambra,org> on Saturday February 26, 2005 @12:04AM (#11785314) Homepage
    Why merely crack RSA and radically speed up quantum physics simulations? That's aiming far too low.

    Instead, Tien Kieu [arxiv.org] from my university wants to solve arbitrary Diophantine equations [wolfram.com] using quantum effects. If he's a) correct, and b) it becomes possible to create the required quantum behaviours for arbitrary equation, the following problems become solvable:

    • The halting problem for arbitrary Turing machines, with all that that would imply.
    • The Riemann hypothesis.
    • Goldbach's conjecture

      Needless to say, to say people are sceptical of Kieu's ideas is an understatement, but it's fun to speculate about the "what if"...

    • Re:Booor-ing... (Score:5, Informative)

      by captain1010 ( 800750 ) on Saturday February 26, 2005 @12:37AM (#11785432)
      No.

      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.

      • More to it than that... (Score:4, Interesting)

        by Goonie ( 8651 ) <robert,merkel&benambra,org> on Saturday February 26, 2005 @12:50AM (#11785476) Homepage
        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.

        You've got it in one. According to Kieu, his system is a non-computable process; you can't simulate what it does on a Turing machine. Hence your objection doesn't apply to his claims.

        However, there are apparently lots of other objections.

    • Re:Booor-ing... (Score:3, Interesting)

      by IWannaBeAnAC ( 653701 )
      Interesting. I am somewhat familiar with the 'Quantum Adiabatic Theorem', but you need to remember that it is a 'theorem' in the physics sense, not mathematical. ie, there isn't a proof, and moreover, a lot of people (including me) have doubts about it.

      Originally the theorem was proposed as a means of solving NP-complete problems on a quantum computer. ie. to show that for a quantum computer, P=NP. I don't think many people actually believe that, and there are no known algorithms for NP problems. Tha

    • Re:Booor-ing... (Score:2, Informative)

      by aprilsound ( 412645 )
      Ummm... the halting problem is PROVEN to be unsolvable. Check any introductory computational theory text.
      • Actually, you could easily solve the halting problem for computers with a metacomputer.

        Now all you need to do is make that last sentance mean something.
      • Maybe his device contains a time machine as integral part. :-)
      • If you actually read all of your computational theory text rather than just the powerpointy lecture notes your professor gave you, you might be aware of the actual nature of the proof. The proof says that no Turing machine (or equivalently powerful system) is capable of deciding the halting problem.

        Now, the Church-Turing thesis says (roughly) that any computational system can be emulated by a Turing machine - in other words, if it's computable, it's computable on a Turing machine. This is not a mathemati

    • Needless to say, to say people are sceptical of Kieu's ideas is an understatement...

      Given that you have to start by throwing out the Church-Turing thesis, I'd think that's hardly surprising.

      The halting problem for arbitrary Turing machines, with all that that would imply.
      The Riemann hypothesis.
      Goldbach's conjecture

      So.....is he planning to do this before or after he proves that integer mathematics is logically consistent? ;-)

      Daniel
  • or does the guy in the picture look a lot like one of the creators of south park [yimg.com]?
  • Now I can sleep.
  • Some software developers test image, possibly gloating how he's the only one in the world who can view it?
  • From the article:

    ...demonstrates that it is possible to measure the quantum properties of two interconnected artificial atoms at virtually the same time.

    and the uncertainty in the energy of the quanta increases, due to the uncertainty relation!

    Also,

    ...virtually the same time.

    Time is relative to the observer, and quantum theory treats time linear but Einstein says otherwise. Take a look at an EPR situation in space-time [psu.edu] (talk by Roger Penrose [psu.edu]).

  • Here's another question (Score:3, Interesting)

    by Ryvar ( 122400 ) on Saturday February 26, 2005 @08:24AM (#11786447) Homepage
    If we can read the state of two entangled atoms, is communication at greater-than-light speed now possible? Wouldn't this violate causality?

    Just curious.

    --Ryv

    • No. This is one of the consequences of the No Cloning Theorem [wikipedia.org], which states that it's impossible to copy qubits. The gist is that, for Alice to send information to Bob, Bob would need to make more than one measurement of the same qubit without collapsing it. One measurement just tells him "clockwise" or "counterclockwise"; the only information he now knows is that Alice's qubit is the opposite of his, but he can't tell whether or not Alice had measured hers before he measured his (or otherwise detect any

  • I don't think I'm ready to use quantum computers but if someone would build a quantum entanglement NIC or networking device, it would be something anyone could use.

    Lowered network latency at long distances would make a world of difference especially with thin-client applications.

Slashdot Top Deals

Whoever dies with the most toys wins.

Close