Posts tagged: $$$

matthen:

When designing an art gallery, you might want to make it so that people can walk through it visiting each exhibit exactly once returning back to the front door.  In the plan on the left, this is possible.  In the other plan, it is impossible to visit every dot (exhibit) without revisiting an exhibit.  There is no quick method to check a general art gallery to see if it has this property (that it is Hamiltonian) - you just have to check all possible paths.  [more] [code]

I think its important to mention that there is no quick method known to anyone for solving this problem in general. If someone does know one, no one probably knows that this person knows it! In complexity theoretic terms, the Hamiltonian path problem is NP-complete. This basically means that a quick solution to this problem could be used to get a solution to any other problem (in NP) that usually requires you to check all the possible solutions.If a quick algorithm could be found for this problem, or if it can be shown that no such algorithm could exist, then the P=?NP problem would be solved and someone would get $1,000,000 and become famous for solving one of the biggest open problems in computer science for the past 40 years.

matthen:

When designing an art gallery, you might want to make it so that people can walk through it visiting each exhibit exactly once returning back to the front door.  In the plan on the left, this is possible.  In the other plan, it is impossible to visit every dot (exhibit) without revisiting an exhibit.  There is no quick method to check a general art gallery to see if it has this property (that it is Hamiltonian) - you just have to check all possible paths.  [more] [code]


I think its important to mention that there is no quick method known to anyone for solving this problem in general. If someone does know one, no one probably knows that this person knows it! In complexity theoretic terms, the Hamiltonian path problem is NP-complete. This basically means that a quick solution to this problem could be used to get a solution to any other problem (in NP) that usually requires you to check all the possible solutions.

If a quick algorithm could be found for this problem, or if it can be shown that no such algorithm could exist, then the P=?NP problem would be solved and someone would get $1,000,000 and become famous for solving one of the biggest open problems in computer science for the past 40 years.



A representation of the quantum Fourier transform on n qubits as the tensor product of n single qubit operations.


This decomposition allows for the quantum Fourier transform to be implemented on a quantum computer efficiently (fast enough for practical purposes). It is used in various algorithms, including Shor’s algorithm, which is an algorithm for factoring large (200+ digit) integers. The computational task of factoring large integers on a classical computer takes so long that the government, banks, and the internet rely on this difficulty to keep their information secure from the public (RSA cryptography).So if you have a large scale quantum computer, you could have the ability to render the RSA cryptographic protocol obsolete! The thing is, quantum computers are really hard to make. However, in 2001 IBM researchers in the foothills behind my house managed to use a quantum computer to factor the number 15 into 3 x 5!

A representation of the quantum Fourier transform on n qubits as the tensor product of n single qubit operations.


This decomposition allows for the quantum Fourier transform to be implemented on a quantum computer efficiently (fast enough for practical purposes). It is used in various algorithms, including Shor’s algorithm, which is an algorithm for factoring large (200+ digit) integers.

The computational task of factoring large integers on a classical computer takes so long that the government, banks, and the internet rely on this difficulty to keep their information secure from the public (RSA cryptography).

So if you have a large scale quantum computer, you could have the ability to render the RSA cryptographic protocol obsolete!

The thing is, quantum computers are really hard to make. However, in 2001 IBM researchers in the foothills behind my house managed to use a quantum computer to factor the number 15 into 3 x 5!