Naked Science Forum
Non Life Sciences => Geek Speak => Topic started by: AndroidNeox on 13/01/2013 01:24:43
-
Is it possible to design a quantum computer that can perform computational loops?
I cannot see how that could work. I can see how one could get quantum computation by setting up a system that will remain unstable until some specific result is expressed, then putting it into an indeterminate state for a little while and then looking to see what value settled out, but that's not at all the same as a "universal computer".
I'd be grateful if someone could explain in general terms how quantum computing is supposed to work.
-
Quantum computer is basically: prepare initial state, perform some specific unitary evolution and finally extract some information by performing measurements.
We can imagine the first step as preparing all states to be zero: |0>.
The unitary evolution is usually constructed (in physical approaches it is a bit more complicated...) by "quantum gates": which in opposite to classical ones, have to be reversible.
For example (f is any classical gate): (x,y,z)->(x,y,z XOR f(x,y) )
These gates/unitarity require large number of auxiliary variables - set initially to 0 and ignored after all.
The unitary evolution should be made of a fixed net of such quantum gates - calculation goes exactly once through each of them. I haven't met with loops there as you would like - they seem impossible in this approach and doesn't seem required.
Here is schematic picture of probably the only really practical (known?) quantum algorithm: Shor algorithm (http://en.wikipedia.org/wiki/Shor%27s_algorithm) to find nontrivial factor of large number (N):
(https://www.thenakedscientists.com/forum/proxy.php?request=http%3A%2F%2Fdl.dropbox.com%2Fu%2F12405967%2Ffqcomp.jpg&hash=666701825bac414278d49213ff106ed1)
So after state preparation, in QC there are usually used Hadamar gates to make superposition of all possible inputs. Then you make some classical calculation on these all possible inputs (not using loops).
Then there is the step containing real superiority of quantum calculations: selection of only those possibilities having the same value of the classical calculations. In Shor case: of all 'a' such that 'y^a mod N' is the same (y is freely chosen). These 'a's fulfilling the condition form a periodic set and its period allows to find a nontrivial factor of N - the QuantumFourierTransform is to extract the period.
Observe that these gates are also reversible classically - so shouldn't we be able to reverse the calculations classically?
For example find 'a' giving chosen value of 'y^a mod N', what would also allow to easily find nontrivial factors? ... or solve 3SAT: fix 'true' on the end of verifier and propagate back to finally get some variables leading to this 'true' (much stronger use, unavailable for standard quantum computers).
Unfortunately there is essential problem with that: the large number of auxiliary variables for classical calculations - we don't know values they should have.
The superiority of quantum computers is that they can simultaneously initialize variables in the past and enforce the same value in the future by measurements while selection (unknown/random value - if we could control it, we would get muuuch stronger computers).
-
In principle, classical computers and quantum computers can emulate each other, and so they can each solve any problem that the other can solve. But in practice, quantum computers will initially be used for specific applications for which they have a clear advantage over a classical computer.
Loops are used for several different purposes in sequential programming languages, including:
- Repeat the same computation for "N" independent inputs and outputs. Assuming that the computation can be done by a quantum computer, this can be configured as a "parallel" computation, where "N" independent quantum computers calculate "N" independent results in parallel.
- Apply the same computation to "N" inputs producing a single output. This could be configured as a quantum computer with "N" inputs.
- Iterate the same computation, taking the result of the previous loop as input to the next loop. This could be implemented by running the quantum computer repeatedly, storing the result, and feeding this in as input; but the "ideal" quantum algorithm would produce the answer without such loops.
- In theory, existing quantum algorithms offer the possibility of performing looped calculations or database lookup with fewer passes through the loop - see http://en.wikipedia.org/wiki/Quantum_computer#Potential
However, it seems that conventional computers cannot do computations on entangled qubits (with or without loops).
In practice, decoherence is a major problem, and today's published quantum computers have trouble doing computations on more than a handful of qubits, so for now they will not be very good emulating a loop which executes thousands or millions of times, or taking thousands or millions of inputs.
-
Is it possible to emulate a quantum computer in software on a conventional computer and would there be any advantage in doing so.
-
Yes we can emulate (simple) quantum computers on classical ones, for example by representing the whole superposition of all possible inputs above ... but it doesn't lead to a better way of solving such problems.
The real question is if we can do it essentially smarter - e.g. by some hidden variables approaches. I was trying to fight with that some time ago, but there was always something missing. My final conclusion was the picture above - that the superiority of quantum computers is mounting possibilities in both past (preparation) and future (measurement) - selection of similar solutions. Like qbits were 4D rubber bands, mounted in the past and measurement is making them 'click' in one of two positions: up or down. As we don't have 'quantum gates' for rubber bands, I don't see how to make it classically ...
But there might be a better way - the coherence/unitarity/reversibility so difficult to maintain in quantum computers is guarding that there remains two-directional causality (past<->future): that the measurement may affect previous situation (like Wheeler's experiment (http://en.wikipedia.org/wiki/Wheeler%27s_delayed_choice_experiment)). In standard computers, thermodynamics makes that we have practically only the standard causality: past->future ... but maybe we could enclose a causality loop to make physics find its fixed point, e.g. to instantly solve NP-hard problems ...
We can do it on classical computers (continuous-time loop comuter (http://www.electro-tech-online.com/electronic-projects-design-ideas-reviews/86973-continious-time-loop-computer.html)), but it is difficult to say if it can be faster (?)
But maybe we could enclose the loop in time ... instead of maintaining coherence in standard QC, use quantum unitarity/reversibility only once, like using controlled delayed quantum erasure (http://www.thescienceforum.com/physics/27354-controlled-delayed-quantum-erasure-where-causality.html) ...
-
We can emulate a quantum computer on a classical computer by storing the qubits as vectors of imaginary numbers.
A 3-qubit memory can be represented by a vector of 8 imaginary numbers. This sounds easy, but if we could make a 256-qubit memory, all the electrons in the observable universe, each storing 1 imaginary number would not be enough to represent this value in a classical computer architecture. (See http://en.wikipedia.org/wiki/Quantum_computer#Bits_vs._qubits)
Classical computers have been honed by 70 years of engineering effort, while many of today's potential quantum computer technologies have trouble matching the information storage time of 200 microseconds achieved by some of the earliest classical computers, eg http://en.wikipedia.org/wiki/Delay_line_memory#Mercury_delay_lines
There will be an ongoing need to interface classical silicon computers with quantum computers, so each can do the parts of a problem for which it is most efficient. However, silicon chips often run at temperatures approaching boiling water, while many candidate quantum technologies require temperatures near boiling helium. Interfacing these extremes will have many thermal and electrical challenges.
While quantum computer technology "catches up" with its promise, classical computers could emulate and test quantum algorithms - perhaps on a platform of highly parallel GPUs (Graphical Processing Units used for high-end computer games).
-
Thank you all for the responses. You've given me good food for thought and good pointers for further reading.