# Quantum Computing

#### u-will-neva-no

Joined Mar 22, 2011
230
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!

#### Wendy

Joined Mar 24, 2008
22,337
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.

#### steveb

Joined Jul 3, 2008
2,436
'what is so great about quantum computing'?

Thanks!

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

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

#### vpoko

Joined Jan 5, 2012
267
An abrupt phrase that i would like answered is 'what is so great about quantum computing'?
Thanks!
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/

#### u-will-neva-no

Joined Mar 22, 2011
230
Great post vpoko, thanks!

#### steveb

Joined Jul 3, 2008
2,436
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. #### nsaspook Joined Aug 27, 2009 8,181 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. #### steveb Joined Jul 3, 2008 2,436 It's a dubious bet on it's face trying to prove a scientific negative. 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.

... of course scalable quantum computing can exist.
You seem to be certain. What is the basis to be certain?

#### nsaspook

Joined Aug 27, 2009
8,181
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.

You seem to be certain. What is the basis to be certain?
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:

#### steveb

Joined Jul 3, 2008
2,436
In other words he could just say no or yes for any reason that satisfies him. I think I'll stick with "dubious".

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.

First, quantum mechanics is the best-confirmed physical theory of all time (it's been tested but still not fully understood) and is the under-structure for all known forces 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.
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:

#### nsaspook

Joined Aug 27, 2009
8,181
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.
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.

Although quantum computers may be faster than classical computers, those described above can't solve any problems that classical computers can't solve, given enough time and memory (however, those amounts might be practically infeasible). A Turing machine can simulate these quantum computers, so such a quantum computer could never solve an undecidable problem like the halting problem. The existence of "standard" quantum computers does not disprove the ChurchTuring thesis.[51] It has been speculated that theories of quantum gravity, such as M-theory or loop quantum gravity, may allow even faster computers to be built. Currently, defining computation in such theories is an open problem due to the problem of time, i.e. there currently exists no obvious way to describe what it means for an observer to submit input to a computer and later receive output.[52]
The optical quantum computer is one of the few experimental systems to have demonstrated small scale quantum information processing. Making use of cavity quantum electrodynamics approaches to operator measurements, we detail an optical network for the deterministic preparation of arbitrarily large two-dimensional cluster states. We show that this network can form the basis of a large scale deterministic optical quantum computer that can be fabricated entirely on chip.
http://arxiv.org/pdf/0805.3592v2