Quantum Computer Demoed, Plays Sudoku

prostoalex writes "Canadian company D-Wave Systems is getting some technology press buzz after successfully demonstrating their quantum computer (discussed here earlier) that the company plans to rent out. Scientific American has a more technical description of how the quantum computer works, as well as possible areas of application: 'The quantum computer was given three problems to solve: searching for molecular structures that match a target molecule, creating a complicated seating plan, and filling in Sudoku puzzles.' Another attendee provides some videos from the demo." Anyone want to guess how long before "qubit" gets compressed to "quit" (as "bigit" became "bit" in the last century)?

Comments

BIGIT??

[CmputrAce]

Never heard of one (bigit). I have, however, heard of the "binary digit" that was shortened to "bit". Given that history, "qubit" is short for "quantum binary digit" - which is an oxymoron since quantum digits can be any (or all) of several states, not just on or off (binary). A more accurate acronymish shortening would be "quigit" - which sounds awkward enough to be shortened to "qit", (pronounced KIT rather than QUIT to avoid confusion).

I think "qubit" is here to stay, though.

Re:For real?

[jason8]

Apparently not a true quantum computer. From a wired news article:

D-Wave held its first public demonstration Tuesday of a machine it claims uses quantum mechanics to solve a certain type of problems, such as searching a database for matching molecular structures.

But the company did not make the machine available for inspection and instead showed video from a remote location, saying it was too sensitive to be easily transported.

And notwithstanding lofty claims in the company's press release about creating the world's first commercial quantum computer, D-Wave Chief Executive Herb Martin emphasized that the machine is not a true quantum computer and is instead a kind of special-purpose machine that uses some quantum mechanics to solve problems.

Common misconceptions

[rbarreira]

To save some work to people replying to misconceptions, here's a list of the common misconceptions about quantum computing that I've seen lately:

• Quantum computers can solve NP-complete problems quickly (in polynomial time) -> not true, the speedup given by Grover's algorithm is quadratic, not exponential. This means that an NP-complete problem which would take O(2^n) in a classical computer would take O(2^(n/2)) in a quantum computer, which is clearly not polynomial time in n
• Quantum computers with N qubits are as efficient as 2^N classical computers -> not true, not all algorithms can get an exponential speedup with quantum computing
• Quantum computers will render cryptography useless -> not true, breaking asymmetric ciphers with QCs are subject to the quadratic speedup I explained above which means it will be enough to double the size of the key in order to account for QCs. Some symmetric ciphers (i.e. public key systems) are broken by quantum computing (for example RSA and discrete logarithm), but it is thought that there are some symmetric ciphers which are not vulnerable to attacks by QCs (excluding by the grover search algorithm, which as I explained above is not very hard to account for). Quite ironically, I remember reading that the same attack which renders discrete logarithm public key cryptography useless also allows for the existence of a public key encryption which requires fast calculation of discrete logarithms.

Re:Traveling Salesman

[hotdiggitydawg]

all a Sudoku puzzle is, at it's core, is a depth first search. Which is not an algorithm that runs in polynomial time. It is a DFS of all (legal, remaining) permutations, which is an exponential number.

even on a moderately fast PC a DFS is fast enough to get a solution to a Sudoku puzzle in the blink of an eye. Regardless of how easy a 9x9 grid seems, Sudoku is still at its core an NP Complete (PDF warning) problem. Why is it therefore any less valid than any other NP complete problem? Travelling Salesman is also pretty easy with less than 10 nodes... likewise you can feasibly crack any encryption scheme by brute-force if you constrain it to have a tiny key size. It's all about scale.

The beauty is, if you solve any NPC problem you solve them all, by definition. So, Mr. Smarty Pants, if your Sudoku solver is good enough to solve any grid in polynomial time, please show the rest of us, as you've just cracked every encryption scheme invented to date.

Yeah, I didn't think so.