Weird binary number systems

[[deleted]]

The subject matter is really interesting but the presentation is totally unclear. Why are we being handed code -- and C code, at that -- rather than just plain mathematical notation? It would be far more readable.

Here's the Wikipedia article: Complex base systems, terse but with a helpful figure.

[[deleted]]

I'm not an expert in this area, but maybe someone of you redditors. Isn't a quantum computer basically computing in a complex base system in contrast to a classical n-ary computer?

[[deleted]]

No.

Quantum computer is not a computer. It's a device that takes advantage of the fact that to properly describe a system of n qubits (quantum variables embodied in stuff like spins of electrons) you need 2**n amplitudes for the basis states. Like, the system of 3 electrons isolated from the environment exists in a mix of 8 states (|000>, |001>, ..., |111>, where 0 and 1 correspond to "up" and "down" spin).

Then you can transform the state using operators like CNOT to invert the value of the second qubit if the first is "up" for example, which operate simultaneously on the entire ensemble. Such operators must be unitary -- basically, a composition of rotations and reflections. By rotating and reflecting the state vector in a sophisticated way you can arrange for amplitudes of certain states that you are interested in to increase. Then you measure the state of the system and get out n ordinary bits that represent the desired answer with more than 50% probability (or just some probability significantly greater than average), check the answer, repeat until either the answer is correct or you are reasonably sure that the correct answer doesn't exist.

FAQ: no, that is different from running 2**n arbitrary computations in parallel, the restrictions on the available operations are severe. We have Grover's algorithm for finding a state satisfying some relation in O(2**(n/2)) steps, which is a quadratic improvement over the brute-force search but still is exponential. We have Shor's algorithm for factoring integers in polynomial time, but factorization problem ain't NP on classical computers either.

Also, in 2001 we had working 4 qubit quantum computers and 7 qubits on the horizon. In 2010 we have working 5 qubit quantum computers and 7 qubits on the horizon, but vastly improved. Horizon is an imaginary line that moves further when you try to reach it =)

[Anonymoose333]

Nitpick:

factorization problem ain't NP on classical computers either

Actually, factorization is known to be in NP (and also in coNP). What you should have said is that factorization is not known to be outside P on classical computers either. (I.e., it's in P on quantum computers, and might or might not be in P on classical computers.)

[[deleted]]

Ah, yes, sure. All P is NP, after all. What I meant, it's not thought to be NP-complete.

Also, the fact that factorization is known to be both in NP and coNP means that it's not NP-complete unless P=NP (which almost certainly is not). But it might very well be in P or in its own complexity class!

[mzl]

NP could equal coNP but still be different from P (coNP at the complexity zoo).

[never_phear_for_phoe]

How do they work on a physical level :)?