What is a quantum computer?

covfefe (30)in #technology • 7 years ago

Below is an accurate complete description of quantum computing. We will explain the quantum computer as a shell game without using physics or math. Inside each shell (qubit) there is either a pea or a cashew.

Game Setup
The game begins with the game setup. Let's take the case where we begin with 360 qubits, which we treat as (walnut) shells. A magician then waves a wand and each shell is 50% likely to have a pea inside, and 50% likely to have a cashew inside. The magician again waves his wand and each of the 360 shells has four numbers written inside it, one red one green one black one white, all equal to 1/2. We denote the colored numbers as {R,G,B,W}. The remaining 640 shells are occupied by cashews, and inside is written in color {R,G,B,W}={0,0,1,0}. As the game progresses we get to swap peas and cashews and mess around with the colored numbers. But we never get to look inside until game over. By the way the colored numbers give the probabilities, probability of (pea)=the sum of the squares of R and G, likewise probability of (cashew) is the sum of squares of B and W.

Game Rules
Now the game starts. At each stage in the game You, the quantum programmer, are allowed to do only three things, without ever being allowed to look into any shell. The game is over whenever you choose to open up all the shells. Programming a quantum computer is all about choosing which moves to make in what order so when you open up the shells you find the list of ones [peas] and zeros [cashews] equal the "exact" answer you seek.

Wait what? This is not at all how we program digital computers!

If you open the shells and don't get the correct answer after a few preassigned number of tries the house (quantum) wins. If you get the answer you seek within the allotted tries you win. We have proofs that we can indeed solve certain important math problems, assuring the house loses with very very high probability. This is the only game where you are (nearly) guaranteed to beat the house instead of vice versa!

The Three Permissible moves at each play

Double tap move: To begin we need to introduce the concept of a flip. In a flip move the pea becomes a cashew if we started with a pea or the cashew becomes a pea if we started with a cashew. You tap any one of the 1,000 shells with your left hand and tap another shell with your right hand. The magician assures that right hand shell is flipped if there is a pea in the left hand shell, and the right hand shell is left the way it started if the left hand shell is a cashew. Again you are not allowed to look into any shell before during or after this or any other move.
Color number swap: You pick any shell, and you pick either the pair of numbers {R,G} or {B,W}. Call the choice {a,b}.
Replace {a,b} by {(a+b)/√2,(a-b)/√2}. No further operation is required since probabilities are unaffected.
Probability fiddle: You again can point to any one shell. Then the magician waves his wand and the new colored numbers are
{(R+B)/√2,(G+W)/√2,(R-B)/√2,(G-W)/√2}. The magician waves his wand again and replaces the pea or cashew with the ensuing probability. [This move and only this move requires quantum systems to execute.]

That's all there is to it! The above rules are simple and complete. Yet, you should convince yourself that under the shell a lot of stuff is happening. For example if we execute move 3 a sum total of 1,000 times we have generated up to 10^300 different outcome lists. This is a lot! Even for 360 moves to just list, let alone optimize over, all the possible combinations of peas, and cashews, classically [i.e. using Newton's laws which digital computers do] would require every atom in the universe starting from the beginning of time, printing out one 360 bit combination one billion times a second. Thus, Quantum computers can optimize over lists that cannot even be described "Newtonially" by all the universe's atoms, printing lists at a 1GHz rate, using all the time since time began. This is causing some philosophers fits! I just think it is really really exciting! [The challenge is that the programming shell game is very hard as the odd rules below evince. Another challenge: We must assume there is a way to quickly check if your answer is correct or else everything falls apart.]

For you quantum experts out there you may recognize that I have described the universal Quantum gate set R(π/4), controlled-not, and Hadamard, and that colored markings are the real and imaginary entries of the unitary qubit operator. I obviously used an arbitrary initial state, and don't discuss post measurement iteration such as needed in Shor's algorithm, nor do I discuss convergence rate, I don't "warn people" that the Dwave is only adiabatic not general, I leave out almost surely asymptotic, reversibility, yadda yadda. These are true but irrelevant facts you don’t need to know them to play the described quantum shell game. I claim the game itself adequately describes exactly what quantum computing is.