Questions about Quantum Computing

[ASEI]

Okay, so I’ve sort of started to grasp what quantum computing is and how it works (after comments from some of my co-workers the other day). And I hate not understanding certain things – if things are explained to me and I still don’t understand, it bugs me to no end; and I in turn usually bug them to no end with more and more specific questions until I begin getting it at a basic level. I think my internet research to date has given me a preliminary concept though and I’m going to put it up and ask a few questions about it.

(Quantum physics stuff especially bugs me because people try explaining things like uncertainty or Bells inequality with buzzwords “multiple universes” and “superposition of concepts”, like “well sometimes it’s a particle and sometimes it’s a wave”. This doesn’t give me much of a picture of what’s going on, just a series of stories told about the topic. Someday I’m going to wade through an entire QP textbook, nasty field equations and all, just to keep myself sane when the topic comes up.)

Okay, well here is what I’ve gathered about how quantum computing works so far: You start with some data that you want to perform operations on. There is some process whereby several bits of information are encoded in one or more “quibit” vectors. These vectors can be imposed (method unknown) on the state of things like fluorine atoms suspended at extremely low temperatures, ect; where we can preserve quantum superposition of these states. (Quibits being quantum superpositions of on-states and off-states, the superposition can hold the whole vector (with analog probabilities assigned to each vector basis) worth of information, rater than just digital on or off states.)

Okay, so now you have many digital bits worth of information represented by the analog orientation of these quibit vectors. You can now perform other superposition operations between quibit vectors (addition, subtraction, and negation are apparently the limit. conditionals currently require us to collapse the state, reconvert the info, and digitally operate). You are effectively performing operations on all these different pieces of digital info simultaneously by adding the vectors.

Then you reconvert the quibits back into digital information so that you can see what you have. Actually, when you collapse the superposition of states of a quibit you just get either 1 or 0. But when you send the info through multiple times, you get 1 with probability a and 0 with probability b, {a,b} being the components of the resultant quibit vector, which can be re-converted back into digital info using the reverse of your encoding method.

(missing anything so far?)

Okay, so this brings me to some of my questions:

1. Maintaining superposition of states in fluorine atoms is a pain in the butt, requiring cool, yet bulky and expensive lab toys like near-absolute-zero temperatures and big NMRI machines to manipulate and read the state of the atoms. What would prevent you from doing the same operations with analog electric signals? If you have an analog signal a and b, you still have a 2d analog vector in which you can encode some number of digital bits and perform the same addition, subtraction, and negation operations. Furthermore, you don’t have to destroy the info (like you destroy quibits when you read them) to read an analog vector. One pass should give you the straight values of a and b, and thus the resultant vector.

2. QCs are supposed to allow us to solve currently infeasible problems much faster than conventional computers due to our ability to encode some arbitrary amount of information in quibits which can be passed through simultaneously. However, can you do something like matrix inversion without conditionals? Gaussian elimination requires you to look at what you have several times to see what the magnitude of the leading values are in the row are so you can appropriately scale the row you are doing the elimination with. Other iterative methods of inversion require matrix multiplication. (Can you “multiply” information within a quibit without having to collapse it to read how many times to add another quibit?)

[mugaliens]

It's a work in progress. The truth is, we really don't need quantum computing. Sure, it'd be nice for some things, like decypering the genetic sequence of sea monkies in less than six months, but the truth of the matter is that processor technologies haven't slowed down, despite having long since passed a theoretical absolute about a decade ago due to both tecnical and theoretical innovations, including new ways of imaging the circuitry, adding redundant, self-detecting and correcting circuitry to counter the statistical liklihood of a bad trace (or even a few dozen), more power-efficient designs than are many times faster than earlier designs but are no longer able to cook full-grown turkeys with their waste heat, and multi-thread and multi-processor designs which eliminate performance lags common to their more linear processing ancestors.

The Pentium chip was rather large, and the Pentium IV chip (the actual chip) is about 1/6 to 1/8th the size, yet screams while using 1/4 the power (depending on the model).

I forsee a future where, in 2012, the Pentium VII chip will incorporate 64 processors, running in parallel, be only slightly larger than the Pentium IV, and use, perhaps, just 50% more power. It'll cost less than $200, as will a 32" plasma display monitor, and the rest of the hardware, including your 2 TB (terabyte) drive, will run you less than $700.

To top things off, things like gene sequencing, cracking, and other data-diminuitive but processor-intensive activities will be running in everyone's background, and not just when the screen-saver is active. A Billion computers will be, literally, deciphering everything on the planet (except one-time cyphers, of course).

But this will only come true if an Independant Repmocratic Demoblican gets elected next term...

[satori]

faulty piece withdrawn

[Kwalish Kid]

Okay, so now you have many digital bits worth of information represented by the analog orientation of these quibit vectors. You can now perform other superposition operations between quibit vectors (addition, subtraction, and negation are apparently the limit. conditionals currently require us to collapse the state, reconvert the info, and digitally operate). You are effectively performing operations on all these different pieces of digital info simultaneously by adding the vectors.
Woah, there!

Do you actually perform those operations simulteneously? That depends on your interpretation of QM. If you believe the multiple worlds people, then you do. If you don't, then what you are doing might be analogous to making use of some special mathematical relationship that is available in the physical system that we don't know yet. So there may be a non-quantum way to do the calculation with a computer that used a certain mathematical process.

Remember, we never get out the results of all those calculations, we only get a single answer. The vast majority of the information in all those theoretical computation paths is lost.
1. Maintaining superposition of states in fluorine atoms is a pain in the butt, requiring cool, yet bulky and expensive lab toys like near-absolute-zero temperatures and big NMRI machines to manipulate and read the state of the atoms. What would prevent you from doing the same operations with analog electric signals? If you have an analog signal a and b, you still have a 2d analog vector in which you can encode some number of digital bits and perform the same addition, subtraction, and negation operations. Furthermore, you don’t have to destroy the info (like you destroy quibits when you read them) to read an analog vector. One pass should give you the straight values of a and b, and thus the resultant vector.
Well, nobody actually does anything with quantum computers for exactly the reason that you give there. However, there are algorithms that we know for quantum systems that will operate faster than we know how to do them on non-quantum systems. These all tend to be things where we are doing some comparison over the entire range of the information and want a result on some one aspect.
2. QCs are supposed to allow us to solve currently infeasible problems much faster than conventional computers due to our ability to encode some arbitrary amount of information in quibits which can be passed through simultaneously. However, can you do something like matrix inversion without conditionals? Gaussian elimination requires you to look at what you have several times to see what the magnitude of the leading values are in the row are so you can appropriately scale the row you are doing the elimination with. Other iterative methods of inversion require matrix multiplication. (Can you “multiply” information within a quibit without having to collapse it to read how many times to add another quibit?)
There are algorithms for mutliplication, I'm sure. Mutliplication is not always an easy task for normal computers, anyway. I'm not sure about matrix inversion, though I would guess that there are several good algorithms for that already.

[Weird Dave]

(Quantum physics stuff especially bugs me because people try explaining things like uncertainty or Bells inequality with buzzwords “multiple universes” and “superposition of concepts”, like “well sometimes it’s a particle and sometimes it’s a wave”. This doesn’t give me much of a picture of what’s going on, just a series of stories told about the topic. Someday I’m going to wade through an entire QP textbook, nasty field equations and all, just to keep myself sane when the topic comes up.)
Unfortunately, “well sometimes it’s a particle and sometimes it’s a wave” is pretty much accurate. Another way to think about it is, "ask a particle question, get a particle answer; ask a wave question, get a wave answer". The only reason you have trouble with this is that in our large world you only ever see "pure" waves or particles. The true nature of everything (as we understand it) is to have the properties of both, and it is just our hard luck that the human brain can't cope with that. There are details, of course...
Okay, well here is what I’ve gathered about how quantum computing works so far: You start with some data that you want to perform operations on. There is some process whereby several bits of information are encoded in one or more “quibit” vectors. These vectors can be imposed (method unknown) on the state of things like fluorine atoms suspended at extremely low temperatures, ect; where we can preserve quantum superposition of these states. (Quibits being quantum superpositions of on-states and off-states, the superposition can hold the whole vector (with analog probabilities assigned to each vector basis) worth of information, rater than just digital on or off states.) I'm afraid you're missing the point here. You're describing analogue computing, which is well established (if a bit niche - apparently some fighter jets use it) and runs perfectly well in electronic circuits. There are two important points of quantum computing. The first is that quantum bits (qubits) can be entangled. This effectively means that they start acting as one single system. So a qubit in one part of the algorithm can be manipulated, and this can subtly affect qubits entangled with it, in another part of the computer.

The other point is superposition: in its simplest form, this means a qubit can be both 1 and 0 AT THE SAME TIME. So, suppose you are trying to find the period or frequency (as in a Fourier transform) of a function that takes 8 bits as an input. A classical (i.e., normal) computer can set those bits to be any one of 2^8=256 different numbers. Feeding it through the function then gives one of the 256 possible answers, and to find the period it needs to try a large number of those inputs even before it can process them to get the frequency.

A quantum computer will start with 8 qubits in state 0, and its first action is often the Hadamard gate. This changes every qubit to being 1 AND 0, in equal proportions. Taken as a whole, those 8 qubits represent all of the 256 inputs. In a single step, the function will process all of those inputs, and return a result which is a combination of all the outputs AT THE SAME TIME. True, as KWALISH KID said, you can only get one answer out. But with clever processing (a quantum Fourier Transform) you can get an answer that depends on all those outputs as a whole - such as the frequency.

Or take sudoku. Set up your quantum computer with a superposition of every possible grid (1 and 2 and 3 and 4 and 5 ... and 9 in every square, all at the same time), and it can examine them all and spit out the one that obeys the initial conditions and the rules of sudoku.

For problems like factoring (which are related to quantum Fourier transforms) a quantum computer is exponentially faster than the best known classical methods. So, suppose you have one number of n digits and another of 2n digits. Your desktop takes m clock cycles to factor the first number, but the second number takes about m^2 cycles, which for large m is much, much larger than m. [Detail: apparently it is more like ~ m^(2^(1/3)), but it still increases by a power when you only multiply the length of the original number]. A quantum computer may take time t to solve the first problem, and 8t to solve the second. For large enough numbers, this makes the quantum computer almost unimaginably faster than the classical one - even if its speed in MHz seems sluggish. Just compare a graph of 2^(x/10) to x^10 to see what I mean.

The sudoku problem is related to a huge class of problems such as protein folding that are very important for real science. Quantum computers are faster here too. It is like trying to find someone in an alphabetical telephone directory if you have their phone number, not their name. A normal computer must look at each entry in turn to find him (half of them on average); a quantum computer takes time proportional to square root (number of entries).

Also, quantum computers are ideal for simulating other quantum systems, so us physicists will have use for them even if nobody else does.

I don't know anything about direct arithmetic, like matrix inversion, on quantum computers. I suspect that nobody has an efficient algorithm for it yet - it would be major news if you could beat classical computers on linear algebra because it is the basis of just about all mathematical physics, if not science in general.

[Detail: the quantum computer doesn't always give the right answer. You have to run it several times and check them to see if they work. But checking is very fast, and the timings above include running the algorithm the expected number of times.]

Nobody knows yet whther a useful quantum computer will ever be built. But there are many clever people all over the world trying to do it with a huge variety of different experiments, so I would be surprised if every approach fails.

[ASEI]

The other point is superposition: in its simplest form, this means a qubit can be both 1 and 0 AT THE SAME TIME. So, suppose you are trying to find the period or frequency (as in a Fourier transform) of a function that takes 8 bits as an input. A classical (i.e., normal) computer can set those bits to be any one of 2^8=256 different numbers. Feeding it through the function then gives one of the 256 possible answers, and to find the period it needs to try a large number of those inputs even before it can process them to get the frequency.

A quantum computer will start with 8 qubits in state 0, and its first action is often the Hadamard gate. This changes every qubit to being 1 AND 0, in equal proportions. Taken as a whole, those 8 qubits represent all of the 256 inputs. In a single step, the function will process all of those inputs, and return a result which is a combination of all the outputs AT THE SAME TIME. True, as KWALISH KID said, you can only get one answer out. But with clever processing (a quantum Fourier Transform) you can get an answer that depends on all those outputs as a whole - such as the frequency.


Right. But what does all this mean on an operational level?

[Weird Dave]

Right. But what does all this mean on an operational level?
Sorry, I don't quite understand what you mean by "at an operational level".