Posts tagged: $$$

"Whether or not God plays dice, I do"


A $100,000 offer is being made by quantum computing/complexity theory researcher Scott Aaronson to whomever can disprove the possibility of scalable quantum computation.

Although very primitive, small-scale quantum computers have been developed and realized in the field, the question of whether or not a large-scale quantum computer can exist to handle arbitrarily large computations is the focus of ongoing research and a matter of debate (at least to some researchers).

This is ultimately a matter of the possibility of quantum computers being able to exist in principle according to the laws of physics, and not one of just theoretical and technological advancement in a given period of time.

The way I see it is that any legitimate attempts to actually disprove the possibility of large scale quantum computation will only end up revealing more details and reasons to believe that large scale quantum computers can and will exist. I would even be willing to go as far as saying that the existence of large scale quantum computation ought to be demanded by the idea of computational universality.

Notes: 27 2/10/12 — 11:37am Filed under: #Science  #Quantum Computation  #Scott Aaronson  #$$$ 
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.

Notes: 101 6/6/11 — 2:46pm Filed under: #P vs NP  #animation  #complexity theory  #gif  #mathematica  #matthen  #$$$ 
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!

High-res Notes: 81 5/18/11 — 7:56pm Filed under: #$$$  #complexity theory  #cryptography  #ink  #math  #moleskine  #pen  #submission  #quantum computation