Quantum Computing

Discussion in 'General Electronics Chat' started by u-will-neva-no, Jan 31, 2012.

  1. u-will-neva-no

    Thread Starter Member

    Mar 22, 2011
    230
    2
    Hey everyone, I was hoping that you guys could explain the basic principles of quantum computing.

    We currently use transistors for switching voltage levels which are equivalent to a '1' and a '0'. So the fundamental aspect of current computing are transistors (correct me if this is not so). For quantum computing, are we dealing with single atoms. I would like to know what the equivalent of the transistor would be in the quantum side.

    I respect that quantum computing is still in research but I would like to know what is actually being investigated.An abrupt phrase that i would like answered is 'what is so great about quantum computing'?

    Thanks!
     
  2. Wendy

    Moderator

    Mar 24, 2008
    20,766
    2,536
    How about the switching is occurring at atomic scales. The increase in density and speeds are going to be astounding, but we aren't even close yet.
     
    u-will-neva-no likes this.
  3. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    This link provides some hints at answers to some of your questions.

    http://www.cs.rice.edu/~taha/teaching/05F/210/news/2005_09_16.htm

    If there are any members at AAC well versed on this subject, I'd also be interested in more detailed answers.

    Basically, the answer to the question of what is so great about quantum computing, is not just the size and speed advantage that should be obtained, which may very well be significant, but also the effective quantum-enabled parallel processing that provides exponentially faster computations.

    This is really tricky stuff to understand, and I've been meaning to dive into the details at some point, but haven't done it yet. But look at this article and look at the predicted power to solve certain types of problems. If these things ever get developed, it will be a major revolution in computing, perhaps exceeding the advancements offered by integration of circuits on silicon.

    If you really want to understand the physics behind this, you have to get into the quantum mechanical calculations. If you are interested in that, look up Lectures by Leonard Susskind on YouTube. He covers many subjects, but his lectures on Quantum Entanglement and Quantum Mechanics, will give you quite a bit of detail on the basics. However, this may not be enough. I have a good working knowledge of Quantum Mechanics and still can't quite get my head around this quantum computing concept. The experts say it will work and say it will be powerful, so I expect it's true and will happen someday.
     
    u-will-neva-no likes this.
  4. u-will-neva-no

    Thread Starter Member

    Mar 22, 2011
    230
    2
    Thanks both of you, I will check out the post and also the youTube videos!
     
  5. vpoko

    Member

    Jan 5, 2012
    258
    47
    In principle, quantum computers can solve exactly the same problems that classical computers can solve (this is implied by the Church Turing Thesis, which while not provable - being a thesis - is widely believed to be true). However, a quantum computer can solve certain problems much more efficiently. In some cases, the improvement is so large that classically intractable problems (i.e., ones that would take longer than the lifetime of the universe to solve) become tractable on a quantum computer.

    An example of this tremendous speedup can be found in Shor's algorithm for factoring composite numbers into primes (according to the fundamental theorem of arithmetic, every number is either prime, or if composite, is the product of a unique set of primes. For example 100 is composite. 100 is 2*2*5*5 - this is the only set of primes that can be multiplied to make 100). With classical computers, if we want to take a composite number and find its prime factors, it takes O(2^n) operations (the notation I'm using is called "big-o notation", you should read it as "on the order of two to the power of n operations") where n is the number of bits required for the binary representation of the number to be factored. As you can imagine, for large n, the number of steps is astronomical. On a quantum computer, you can do it in O(n^c) time, where c is a constant independent of n. This lets you factor much, much (much!) larger numbers in a reasonable amount of time. Why do we want to factor numbers? Because the RSA cryptosystem in use everywhere is based on the difficulty of factoring.

    There are very few known quantum algorithms as dramatic as Shor's, and the application for Shor's algorithm is narrow. There is, however Grover's algorithm, which allows an unordered database search in O(sqrt n) time, while a classical computer takes O(n) time. This has very wide application, but the improvement isn't nearly as large as with Shor's.

    If you're interested in learning more, this is one of the best resources I know, from a professor at MIT specializing in quantum computation: http://www.scottaaronson.com/democritus/
     
    steveb and u-will-neva-no like this.
  6. u-will-neva-no

    Thread Starter Member

    Mar 22, 2011
    230
    2
    Great post vpoko, thanks!
     
  7. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    Here is an interesting article I just ran across on this subject.

    http://spectrum.ieee.org/tech-talk/computing/hardware/why-im-wagering-100000-on-quantum-computing?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+IeeeSpectrum+%28IEEE+Spectrum%29

    Scott Aaronson, a quantum computing researcher at MIT, has offered a $100,000 reward to anyone who can convince him that scalable quantum computing is impossible in the physical world. Apparently, he is very confident that it is possible and just a matter of time before the technology can be developed and scaled to useful and practical (even very powerful) levels.
     
    u-will-neva-no likes this.
  8. nsaspook

    AAC Fanatic!

    Aug 27, 2009
    2,910
    2,172
    It's a dubious bet on it's face trying to prove a scientific negative but of course scalable quantum computing can exist. Many researchers believe that the true origin of the intelligent thought process is quantum in nature. The question is can we artificially create a machine that works in the same way with advances in any currently technology. That, to me seems doubtful.
     
    u-will-neva-no likes this.
  9. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469
    I would say that it is difficult, more than dubious, assuming the prize is offered and judged in good faith, and with honesty.

    He is only asking that it be proved in a way that is convincing to him. I think he is basically looking for some combination of theoretcial and experimental evidence that creates an obstruction to realizing quantum computing at arbitrary scales.

    If we draw an analogy to conservation of energy COE and how it relates to the imposibility of making a perpetual motion machine, we have a case of a negative that is impossible to prove, yet scientists still hold to this principle. Our working theories are based on laws that have COE embedded too deeply in them. The theory describes observation and no observation has ever broken the law of COE. It's not proof, but is worthy of a $100,000 prize if one was offered.

    In this case, we have the principles of Quantum Mechanics that we find describe nature very well. If someone could mathematically show how these principles/assumptions lead to the impossibility of quantum computing working at arbitrary scales, and if experiments that are expected to work continually fail as time goes on, then you have the making of enough evidence to claim the prize. Here, one does not even need to convince all scientists, but only one. Hence, the prize might be claimed before the general scientific community conforms to the viewpoint.

    You seem to be certain. What is the basis to be certain?
     
  10. nsaspook

    AAC Fanatic!

    Aug 27, 2009
    2,910
    2,172
    In other words he could just say no or yes for any reason that satisfies him. I think I'll stick with "dubious".

    First, quantum mechanics is the best-confirmed physical theory of all time (it's been tested but still not fully understood) and is the current under-structure for the electromagnetic and nuclear forces (and maybe one day gravity) so it's possible to have large stable quantum structures and rules that control energy because they are in effect today in all matter. The feature we call the human mind exists in this quantum framework so to me it is possible by a complex process to create a arbitrary deterministic computer (Not an AI or intelligent machine) using the technology.

    The "Decoherence" problem of moving information from the quantum world to the "real" world seems to be the same type of scale that DNA solved for living creatures. Very tricky but not impossible with super-error correction and replication.
     
    Last edited: Feb 8, 2012
  11. steveb

    Senior Member

    Jul 3, 2008
    2,433
    469

    OK, dubious means you don't trust him to be honest, it seems. Certainly, he can avoid awarding the prize at his discression, but it will be at the cost of his own integrity. The rest of the scientific world has a good feel for what his intent is and what would constitue a reasonable demonstration.

    The money is not all that much. It is something he can afford, and something that would be money well spent since proof that his field is doomed to failure would be worth knowing so he can redirect his life's passion.

    But, no one can predict the actions of another, so dubious fits from that point of view.

    Yes, I agree with all of that, although I'm not sure why the evidence that the mind is a demonstration of an arbitrary determinicstic computer, proves that it is a quantum computer that utilizes the extra power possible with quantum computations. Who knows, maybe the mystery of what consciousness is can be tied in with quantum entanglement or other deep physics that goes beyond our classical concept of computation. But, it's not proved in any way.

    Anyway, this all does not seem to prove that there might not be a fundamental obstruction which prevents this type of quantum "entangled" structure to exist at arbitrary scales. I agree the evidence is highly compelling and the nay-sayers are few, but just as you say proving a negative is difficult, we have to acknowledge that proving the positive, while easier, is also difficult. What makes proving the positive case easier is that a demonstration proves the point. But, we have not seen this demonstration yet. We've only seen very small scale demonstrations, and no proof that it scales to 10 times, or 100 times, or (as needed for real practical use) a million or a billion times, without some fundamental limitation getting in the way.
     
    Last edited: Feb 8, 2012
    vpoko likes this.
  12. nsaspook

    AAC Fanatic!

    Aug 27, 2009
    2,910
    2,172
    The existence of the human mind just shows what's possible in our universe. As you say it's not a proof of what's possible by artificial means.

    The extra power that's gained is in time and storage requirements, it's not from a special logical computing process that only a quantum computer can do.

    http://arxiv.org/pdf/0805.3592v2
     
Loading...