Solid state quantum computers
Researchers have built the first solid state quantum computer. Only two qubits, but it’s a start. If it scales, at least there is really no option of just sticking a lot of two bits together to get more with these quantum computer beasts; you need quantum states and that is where the tricky part is, and the quantum bus they use here might be a way to achieve this. I don’t know enough physics to have any opinion on this, though… if someone does, please enlighten me!
Quantum computers are really cool because they, in some applications, works like non-deterministic computers: when an algorithm like a search needs to make a choice in where to search next, it can go both ways and doesn’t have to first look one place and then the other like a deterministic computer (like all the computers we have today). So it can explore an exponential search space in polynomial time.
When people talk about NP (non-deterministic polynomial) problems that is what they usually mean. Problems where a non-deterministic algorithms can solve the problem in polynomial time, but where we do not know any polynomial time algorithms to solve it using a deterministic algorithm.
A lot of optimisation problems of practical importance falls into this category. Today we use all kinds of heuristics to solve these problems – usually sub-optimally – so even if we can only solve some of those kinds of problems with quantum computers, it is hard to overestimate how important quantum computers can become if we ever manage to build large ones.
–
181-177=+4