I had this idea yesterday. I was thinking about the future and if there might ever be a quantum equivalent to the Turing Arduino of today. I was thinking of my understanding of quantum computers. So I was thinking of something hard to do with a turing machine. At one point, browsing the linux man pages of gpasswd it said that it generated and stored a hash of the password. The user inputs the password, it hashes it again and checks it against the stored version. It also mentioned that it is extremely difficult to generate a string that matches the hash.
So I was thinking of an imaginary IC that would use quantum physics to crack a password. If the IC generates random data and checks it to see if it is the password, there is a very slim chance it will work. I was thinking of how to "collapse the wave function" or read only the correct possibility. This IC is a closed system. I can't measure it with a multimeter because it's way too small. If it generates output only when it has the (a) correct password there's only one possibility where I can measure it: the correct one.
You can program the arduino to behave like this mythical IC. Over serial, it will take in the hash. It will initialize the random number generator. It will take one random number. This is the length of the password. It then takes in that amount of random characters, and checks it against the hash. If it is correct, output the password over serial. It should only have to run once if it is behaving like a quantum computer.
Do I think this will work? I'm not sure I really believe that we as a species understand quantum physics yet. Maybe there's more to it than even our top physicists understand. That being said, I'm not even in college with a major in physics. I'm majoring in engineering. While I try to stay ahead, I'm not formally educated in quantum physics. I'm probably wrong.
Also, another problem. The arduino can't generate true random data. It's pseudorandom which is good for a great many things, but maybe not quantum physics. That said, I can't measure how random the arduino is actually generating numbers. There might be a slight possibility there is sufficiently random data to pull off this quantum computation. Thus, when and if we measure the password by reading it in our serial console, we make that possibility the reality.
What would it mean if this works? That we don't need sophisticated equipment to take advantage of a quantum world. All we need is a cheap microcontroller and some clever programming.
Anyways, just an interesting thing I thought of that I wanted to share.
You can program the arduino to behave like this mythical IC
Maybe you're right but I expect it will take an almost infinite amount of time to come to the right answer. Quantum computers just work on another level of physics than an Arduino does ..
I'm not sure I really believe that we as a species understand quantum physics yet.
I'm sure we don't understand all aspects of it yet but remember that many electronics we take for granted today could not be build with only pre-quantum physics techniques. That means there are people that have a really good understanding of at least some parts of the quantum physics to build high tech devices.
There are at least some properties of the QP that make it impossible to know the quantum state of a system completely. Search for Schrodingers cat or the Heisenberg uncertainty principle.
And even as I write this I recall an article of today about the Large Hadron Collider that bumped into a small deviation of the current knowledge of decay of D-mesons.
http://io9.com/D_meson/ - First cracks in the current theories are emerging and that reminds of the year 1900, when people also thought physics was almost 100% explainable, only a few small effects did not fit in. These small effects brought us understanding of radioactivity, quantum physics, relativity and even Arduino
I'm aware of shroedingers cat and and heisenburg uncertainty.
Also, saying arduino and quantum computers work on different levels of physics is... ionno. Our familiar macro physics is built from the workings of quantum physics. The "holy grail" of physics is to integrate everything into one theory. Saying they're "just different" is kind of giving up, I guess. Not that I understand how it works together either.
I am, however, glad that we have all these new branches of physics to explore. That makes now and the future an exciting time.
Be aware that some things/experiences are emerging "out of the nothing". One molecule doesn't have a temperature. It is the (intensity of their) interaction when you put enough of them together that physicists call temperature. (imho physics is a lot about statistics
Gravity1 is on atomic scale hardly existing compared to the electrical force. Do some math to compare the gravitational force between an electron and a proton (in Hydrogen) and the electrical force. Orders of magniture difference. You can check your math at - Fundamental interaction - Wikipedia -
Quantum effects and electronics are on different levels. Electronics in an Arduino works because there are many many electrons involved in one HIGH signal. In a quantum computer one single electron would/could have a superposition of many states/values. Again orders of magnitude difference.
1: maybe gravity is even not defined on atomic level as the positions of the proton and elektron are not defined precise due to Heisenberg, so their distance is uncertain too...
I get some of my info from a couple documentaries I've seen. Also wikipedia and surfing the net.
The impression I got is that there are infinite universes overlaid atop each other. Each containing a different possibilities. So if something is even remotely possible, it will happen in that universe. There might be a universe where I've already written the code to test this on the arduino.
Anyways, this wasn't really a serious thing. Just some random thought I had.
Also, it's cool that I get to talk to other people like you guys that know of quantum physics. I love the internet!
It's been a few years since I took any QM classes, but my understanding is this of quantum computing:
A quantum bit (qubit) can exist in both a state of 1 and 0 or any quantum superposition of these at the same time.
This allows all possible permutations of a problem to be calculated simulataneously.
When a measurement is made of the system it collapses down onto a one of these solutions.
If you repeat the quantum computing experiment enough times then you arrive on the correct answer with enough certainty.
If you read the wikipedia page on quantum computing it says this close to the top:
Given unlimited resources, a classical computer can simulate an arbitrary quantum algorithm so quantum computation does not violate the Church–Turing thesis.[5] However, in practice infinite resources are never available and the computational basis of 500 qubits, for example, would already be too large to be represented on a classical computer because it would require 2500 complex values to be stored.[6] Nielsen and Chuang point out that "Trying to store all these complex numbers would not be possible on any conceivable classical computer." [7]
So, while it does appear to be possible to simulate a quantum computer without actually possessing physical qubits, the resources required are would soon surpass what is available. If it were easily possible the computer scientists and physicists would simply simulate a quantum computer system rather than trying to trap atoms or manipulate photons!
With regards to your arduino idea, perhaps it can simulate very simple quantum environments, but I think that cracking cryptographic hashes might be a bit beyond its capabilities!
A quantum computer does not work by trying every solution in superposition and then magically picking out the right one (like a non-deterministic Turing machine would do). This is why quantum computers are not thought to be able to solve NP-complete problems in polynomial time (though, since the P vs NP question is still open, nobody can even prove that a classical computer can't solve NP-complete problems in polynomial time, it's just strongly suspected that neither computer can.)
The problem of inverting a cryptographically-secure hash function, which is what you're trying to do, can be reduced (converted) to the problem of searching an unordered database. Grover's quantum algorithm (Grover's algorithm - Wikipedia) can do this in O(?N) time, while a classical computer would take O(N) time (if this doesn't make sense, see Big O notation - Wikipedia). As you can see by looking at the Wikipedia page for Grover's algorithm, though, it is far from trivial to implement and is based around much more subtle effects than picking out the right answer from a multiverse of possibilities. Also, because the improvement is only quadratic rather than exponential, the problem of inverting a hash function with a sufficiently large range remains intractable even on a quantum computer.
Quantum computers can give an exponential speedup for a limited, known set of problems. The best example of this is Shor's algorithm (Shor's algorithm - Wikipedia) for factoring numbers into primes (per the fundamental theorem of arithmetic). This algorithm is what made everyone want a quantum computer, since it could be used to break RSA. Again, though, the application here is limited: it can only be used to break public key cyrptosystems based on the difficulty of factoring into primes (and related problems like discrete logarithms). It can't be used to make an otherwise intractable inversion of a hash function suddenly tractable.
The biggest elephant in the room, of course, is that no one has successfully built a quantum computer (the dubious claims of a company called D-Wave notwithstanding), and when a quantum computer is created, it won't resemble an Arduino in any way, at least not at first. For one thing, all the current quantum computing models are circuit models, not quantum Turing machines, and certainly not random access machines. This is all my speculation, but quantum computers will probably follow the evolution of classical computers. The first will be hard-wired to solve particular problems, and only later will we get programmable, general purpose versions. Maybe in time we'll have personal quantum computers, but we're very far from that right now.
I should also add that a computer with the addition of a perfect source of randomness is still not a quantum computer. The theoretical model to describe such a computer is a probabilistic Turing machine (Probabilistic Turing machine - Wikipedia). The class of problems efficiently solvable (aka in polynomial time) by such a machine is known as BPP (BPP (complexity) - Wikipedia), while the class of problems efficiently solvable by a quantum computer is called BQP (BQP - Wikipedia).
It is believed (though not proven) that BPP is the same complexity class as P (the class of problems efficiently solvable by a classical computer without a source of randomness). In other words, adding a source of randomness is not believed to fundamentally improve the efficiency of a computer (at least not to the extent of making otherwise intractable problems tractable; there may be smaller improvements to already-tractable problems). In addition to randomness, a quantum computer likely needs to take advantage of entanglement and "negative probabilities" (actually, complex numbers in QM), so that "wrong answers" can help cancel each other out. These are not features found in a classical computer, even one with a real random number generator.
Last addition: anyone interested in learning about quantum computation (just for fun, not because you'll be able to implement it with microcontrollers) should check out the excellent online lessons by Scott Aaronson (an MIT professor specializing in quantum computational complexity theory, and with a gift for explaining difficult concepts to laymen) found here: PHYS771 Quantum Computing Since Democritus
