How is Quantum Mechanics (a Physics Concept) used in computing?

Question

I've been taking a course on Quantum Mechanics in which, right now, I'm learning about its application in Computing to give Quantum Computing. Quantum Mechanics is a concept that is applied to microscopic particles explaining their motion, behaviour etc. in the microscopic (quantum world). How is this correlated to computing? They seem entirely different things.

Answer 1

Here's a simple idea that relates the two: If you're going to build a computer, you have to build a computer out of something. What you can get that computer to do must be bound by what the stuff you've built it out of can do. So, physics is very important for telling you what a computer can do.

When I put it like this, there's a clear relation between the two. But it looks like physics is going to be a limiting factor, telling you that you can't do things. For example, there's a finite speed of communication between two physically separate entities (the bits in your computer), determined by the speed of light, so there's a maximum speed of operations. You can't put things (your bits) too close together, or they'l turn into a black hole, so there's a maximum density storage. OK, these numbers are crazy, and really not limits on existing hardware.

So, the real question here is how could physics possibly let you do something better? There's a cute example that I like. Think about two rooms. One room has 3 light switches, and the other has 3 light bulbs. Each switch switches exactly 1 bulb. Your job is to determine which switch matches each bulb, but you're only allowed to visit each room once.

Now, a computer scientist will look at this problem and tell you it's impossible. There are 6 possible ways of wiring up the switches to the bulbs. You need $\log_2(6)$ bits of information to describe that. But, by flicking some switches and observing the bulbs, you only get $\log_2(3)$ bits of information, which is insufficient.

A physicist has several tricks. For example, switch 2 bulbs one, and wait a long time. Then switch one off. Now go into the bulb room. One bulb is on, one is warm, and one is cold. So, you can perfectly map switches to bulbs.

The point here is that we've used physics to do better. The problem is that the computer scientist used an abstraction of the system that actually made several assumptions about the system, and the physicist exploited the difference between the assumption and the reality. It's kind of similar with classical versus quantum computers. In effect, the theory of classical computation assumes probability theory. But probability theory isn't always true; at the quantum level, you need probability amplitudes. These include simple probabilities (so quantum computation includes classical), but provides more options. Hence there's the possibility for doing some things better.