The Naked Scientists
Toggle navigation
Login
Register
Podcasts
The Naked Scientists
eLife
Naked Genetics
Naked Astronomy
In short
Naked Neuroscience
Ask! The Naked Scientists
Question of the Week
Archive
Video
SUBSCRIBE to our Podcasts
Articles
Science News
Features
Interviews
Answers to Science Questions
Get Naked
Do an Experiment
Science Forum
Ask a Question
About
Meet the team
Our Sponsors
Contact us
User menu
Login
Register
Search
Home
Help
Search
Tags
Recent Topics
Lonely Topics
Login
Register
Naked Science Forum
Non Life Sciences
Geek Speak
Quantum Computing Question
« previous
next »
Print
Pages: [
1
]
Go Down
Quantum Computing Question
6 Replies
3517 Views
0 Members and 1 Guest are viewing this topic.
AndroidNeox
Sr. Member
258
Activity:
0%
Thanked: 2 times
Quantum Computing Question
«
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.
Logged
Jarek Duda
Full Member
72
Activity:
0%
Thanked: 1 times
Re: Quantum Computing Question
«
Reply #1 on:
13/01/2013 08:23:53 »
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
[nofollow]
to find nontrivial factor of large number (N):
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).
Logged
evan_au
Naked Science Forum King!
4526
Activity:
45.5%
Thanked: 283 times
Re: Quantum Computing Question
«
Reply #2 on:
13/01/2013 08:59:51 »
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
...sorry, you cannot view external links. To see them, please
REGISTER
or
LOGIN
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.
Logged
syhprum
Naked Science Forum King!
3958
Activity:
2%
Thanked: 26 times
Re: Quantum Computing Question
«
Reply #3 on:
13/01/2013 22:21:22 »
Is it possible to emulate a quantum computer in software on a conventional computer and would there be any advantage in doing so.
Logged
syhprum
Jarek Duda
Full Member
72
Activity:
0%
Thanked: 1 times
Re: Quantum Computing Question
«
Reply #4 on:
14/01/2013 08:47:46 »
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
[nofollow]
). 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
[nofollow]
), 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
[nofollow]
...
Logged
evan_au
Naked Science Forum King!
4526
Activity:
45.5%
Thanked: 283 times
Re: Quantum Computing Question
«
Reply #5 on:
14/01/2013 10:00:03 »
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
...sorry, you cannot view external links. To see them, please
REGISTER
or
LOGIN
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).
Logged
AndroidNeox
Sr. Member
258
Activity:
0%
Thanked: 2 times
Re: Quantum Computing Question
«
Reply #6 on:
15/01/2013 01:51:00 »
Thank you all for the responses. You've given me good food for thought and good pointers for further reading.
Logged
Naked Science Forum
Re: Quantum Computing Question
«
Reply #6 on:
15/01/2013 01:51:00 »
Print
Pages: [
1
]
Go Up
« previous
next »
Tags:
There was an error while thanking
Thanking...