History of Quantum Computing
History of Quantum Computing
Models of Classical Computation
The following serve as universal models of computation:
Turing Machines
Circuits can describe computations which are beyond what a Turing machine can do.
Apparently, we can solve the halting problem under some circuit model. But, what is that supposed to mean?
Quantum Computation
The idea of a QC model is to have information in superposition. If we want Turing Machines to be part of the quantum computational model then we will somehow have to make the read/write head to be in a superposition. But that is not possible (doubt). Hence we use a circuit where we keep the bits in a superposition and operate on them with gates.
History of Quantum Mechanics and Computation
Major questions in QM started arising with the EPR paradox in 1936 when faster than light travel was questioned.
Here's the paradox: Consider 22 particles that are moving away. Their positions are xx and x-x and momenta are pp and p-p. Now we can't measure the exact position and momentum of one particle due to the uncertainty principle. But what if we measure the position of one particle and momentum of the other at the same time (Like a split second difference)? Assuming there is no interaction between the particles, we would in principle know the position and momentum of one particle at a time (cause we can know position or momentum of particle 11 if we measure that quantity on the second particle cause its just the negative of it). This would violate the uncertainty principle. Hence, there has to be some sort of interaction between the two particles that makes the wavefunction of particle 22 also collapse instantaneously when I measure position or momentum of particle 11. This mean that the particles were somehow connected. This was the paradox. But Schrodinger said this is possible by entanglement.
In 1964 Bell gave his Theorem and then it was later verified too which proved that Quantum Mechanics is cool with EPR pair. But there was another problem that how is faster than light communication possible? It was later proved that faster than light communication is not possible indeed as you cannot actually send 'information' with the entanglement coordination. Basically you cannot manipulate the particles to actually transmit any useful information.
Non-cloning theorem: In physics, the no-cloning theorem states that it is impossible to create an independent and identical copy of an arbitrary unknown quantum state, a statement which has profound implications in the field of quantum computing among others.